Chapter 2

2.1 - Set Theory

Definition (Primitive term)

Primitive term is a term without a formal def

Definition (Axiom)

Result or idea we accept without formal proof

axiom (1)

There is a set

axiom (2)

For every object $x$ and set $S$, we can determine if $x$ is an element of $S$ or not.

Definition (Containment)

Let $A$ and $B$ be sets. Then, $A$ is contained in $B$, written $A \subseteq B$ iff $\forall x \in A, x \in B$. Otherwise, we write $A \not\subseteq B$.

Example

Consider the following model:

1. The objects under consideration are the first five lowercase letters of the alphabet.
2. There is a set $S = \{ a, b, c, d, e \}$.

This model satisfies Axioms 1 & 2

(Figure 2.2 in the book)

Example

Consider the following model:

1. The objects under consideration are the first six lowercase letters of the alphabet.
2. There is a set $S = \{ a, b, c, d, e \}$.

This model satisfies Axioms 1 & 2

(Figure 2.2 in the book)

2.2 - Axiom of Specification

axiom (Axiom of Specification)

If $S$ is a set and $p(\bullet)$ is an open sentence for the elements of $S$, then the collection of all elements $x \in S$ that satisfy $p(x)$ is a set, too.

Proposition (Empty Set)

There is a set that contains no elements.

Proof (by construction)

By A1, we know a set $S$ exists. We also know that the open sentence $p(x) = [x \in S \land x \not\in S]$ is false for all objects.

By A3, the collection $B = \{ x : p(x) \}$ of all elements $x$ that satisfy $p(x)$ is a set also. Since $p(x)$ is false $\forall x \in S$, $B$ has no elements.

$\square$

Definition (Empty Set)

We call the set having no elements the empty set. Denoted as $\emptyset$.

Definition ()

A set $\mathcal{S}$ whose elements are sets too is called a family of sets.

Proposition (Intersection)

Let $\mathcal{C}$ be a non-empty family of sets. Then there is a set $\mathcal{I}$ so that an object $x \in \mathcal{I}$ iff $\forall c \in \mathcal{C}$ we have that $x \in \mathcal{C}$.

Proof (by construction)

Let $\mathcal{C}$ be a family of sets. $\forall C \in \mathcal{C}$, $x \in C$ is an open sentence for the elements of $\mathcal{C}$. Let $C_0$ be an arbitrary set in $\mathcal{C}$. By the axiom of specification, $\mathcal{I} = \{ x \in C_0 : \forall C \in \mathcal{C}, x \in C \}$ is a set and it contains the elements that are in every set $C \in \mathcal{C}$.

$\square$

Definition (Intersection)

Let $\mathcal{C}$ be a family of sets. The set of elements $x$ so that $x \in C \forall C \in \mathcal{C}$ is called the intersection of $\mathcal{C}$ and is denoted $\bigcap \mathcal{C}$.

If $A$ and $B$ are sets, their intersection is written $A \cap B$.

Proposition

Let $\mathcal{C}$ be a family of sets and $C \in \mathcal{C}$. Then $\bigcap \mathcal{C} \subseteq C$.

Definition (disjoint)

Let $\mathcal{C}$ be a family of sets. If $\bigcap \mathcal{C} = \emptyset$, then the family of sets is called disjoint.

Example

Let $\mathcal{C} = \{A, B, C\}$ where $A = \{1, 2\}$, $B = \{2, 3, 4\}$, $C = \{3, 4, 5\}$

1. $A \cap B = \{ 2 \}$
2. $B \cap C = \{ 3, 4 \}$
3. $\bigcap \mathcal{C} = \emptyset$

Proposition

Let $A$ and $B$ be sets. Then there is a set that contains all elements of $A$ that are not in $B$.

Proof (by construction)

Let $A$ and $B$ be sets. Let $p(x) = \{ x \in A \land x \not\in B \}$ be an open sentence for the elements of $A$. Then the set of elements of $A$ that are not in $B$ exists and is $\{ x \in A : x \not\in B\}$.

$\square$

Definition (Relative Compliment)

Let $A$ and $B$ be sets. Then we call the relative compliment, or compliment of $B$ in $A$, the set $A \setminus B = \{x \in A : x \not\in B\}$.

2.3 -- Axiom of Extension

axiom (Axiom of Extension)

Two sets are equal iff they have the same elements. That is if $A$, $B$ are sets, $A = B \iff \forall x, x \in A \iff x \in B$

sidenote (def of containment)

$A \subseteq B$ iff $x \in A \implies x \in B$

Theorem

$A = B \iff A \subseteq B \land B \subseteq A$

Proof

($\implies$) Suppose $A = B$. Then, by definition, $x \in A \implies x \in B$ and $x \in B \implies x \in A$.

Then by definition of subsets, $A \subseteq B$ and $B \subseteq A$.

($\impliedby$) Suppose $A \subseteq B \land B \subseteq A$. Let $x \in A$ be an arbitrary but fixed. Since $A \subseteq B$, we have $x \in B$, thus $x \in A \implies x \in B$. Now, let $x \in B$ be arbitrary but fixed. Since $B \subseteq A$, $x \in A$, thus $x \in B \implies x \in A$. Therefore, $x \in A \iff x \in B$ and by definition, $A = B$.
$\square$

This tells us that we can use mutual containment, $A \in B \land B \in A \implies A = B$, to prove equality.

Theorem

$A \cap B = B \cap A$

Proof (by mutual containment)

1. Prove $A \cap B \subseteq B \cap A$

Let $x \in A \cap B$ be arbitrary but fixed.
Then $x \in A \land x \in B$.
Thus, $x \in B \land x \in A$.
Therefore, $x \in B \cap A$ and $A \cap B \subseteq B \cap A$.

2. Prove $B \cap A \subseteq A \cap B$

Let $x \in B \cap A$ be arbitrary but fixed.
$\implies x \in B \land x \in A$.
$\implies x \in A \land x \in B$.
$\implies x \in A \cap B$
$\implies B \cap A \subseteq A \cap B$.

Thus, by M.C., $A \cap B = B \cap A$.
$\square$

Theorem

Let $A, B, C$ be sets, then $A \cap (B \cap C) = (A \cap B) \cap C$.

Prove as exercise.

Theorem

Let $A, B$ be sets. Then $A \subseteq B \iff A \cap B = A$.

($\implies$) Let $A \subseteq B$. To show $A \cap B = A$, we will use mutual containment.

Let $x \in A \cap B$ be ABF. By def, $x \in A$, thus $A \cap B \subseteq A$.

Let $x \in A$ be ABF. Since $A \subseteq B$, $x \in B$. As $x \in A \land x \in B$, $x \in A \cap B$ and $A \subseteq A \cap B$. Thus, $A \cap B = A$.

($\impliedby$) Let $A \cap B = A$. Let $x \in A$ be ABF. Since $A = A \cap B$, $x \in A \cap B$. Then, $x \in A \land x \in B$. Thus, $x \in B$ and $A \subseteq B$. Therefore, $A \subseteq B \iff A \cap B = A$
$\square$

Theorem

$A \setminus (A \setminus B) = A \cap B$

Proof

Let $x \in A \setminus (A \setminus B)$ be ABF.
$\implies x \in A \land x \not\in A \setminus B$
$\implies x \in A \land \neg [x \in A \land x \not\in B]$ $\implies x \in A \land [\underbrace{x \not\in A}_\text{false} \land x \in B]$
$\implies x \in A \land x \in B$
$\implies x \in A \cap B$
Thus, $A \setminus (A \setminus B) \subseteq A \cap B$.

Let $x \in A \cap B$ be ABF.
$\implies x \in A \land x \in B$
$\implies x \in A \land [\underbrace{x \not\in A}_\text{false} \land x \in B]$
$\implies x \in A \land \neg [x \in A \land x \not\in B]$ $\implies x \in A \land x \not\in A \setminus B$
Thus, $x \in A \setminus (A \setminus B)$.
$\square$

2.4 -- Axiom of Unions

For every family $\mathcal{C}$ of sets, there exists a set whose elements are all elements that belong to at least one element of the family denoted $\bigcup \mathcal{C}$ or $A \cup B$

Proposition

let $\mathcal{C}$ be a family of sets and $C \in \mathcal{C}$. Then C is a subset of $\bigcup \mathcal{C}$.

Proof

Let $x \in C$ be ABF. By the axiom of unions, $x \in \bigcup \mathcal{C}$. Thus, $C \subseteq \bigcup \mathcal{C}$.
$\square$

Theorem

$A \cup B = B \cup A$

% TODO: FINISH NOTES FROM NOTEPAD

Theorem (DeMorgan's Laws)

1. $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$

Proof (algebraic)

$$\begin{align} A \setminus (B \cup C) &= \{ x : x \in A \setminus (B \cup C) \} \\ &= \{ x : x \in A \land x \not\in (B \cup C) \} \\ &= \{ x : x \in A \land x \not\in B \land x \not\in C \} \\ &= \{ x : (x \in A \land x \in A) \land x \not\in B \land x \not\in C \} \\ &= \{ x : (x \in A \land x \not\in B) \land (x \in A \land x \not\in C) \} \\ &= \{ x : x \in (A \setminus B) \land x \in (A \setminus C) \} \\ &= \{ x : x \in ((A \setminus B) \cap (A \setminus C)) \} \end{align}$$ $\square$

2. $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$

Definition (Symmetric Difference)

The symmetric difference $A \triangle B = (A \setminus B) \cup (B \setminus A)$

ex: Prove $A \triangle B = (A \cup B) \setminus (A \cap B)$

2.5 -- Axiom of Powers; Relations and Functions

axiom (Axiom of powers)

For every set $S$, there exists a set $\mathcal{P}(S)$ called the "power set" of $S$ whose elements are all subsets of $S$.

Example

Let $S = \{a, b\}$

$\mathcal{P}(S) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$

Let $S = \emptyset$

$\mathcal{P}(S) = \{\emptyset\}$

If $|S| = n$, then $|\mathcal{P}(S)| = 2^n$

Theorem

Let $\{a, b\}$ and $\{c, d\}$ be sets with one or two elements ($a$ can be equal to $b$). Then $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$ holds iff $a = c$ and $b = d$.

Proof

($\impliedby$) Suppose $a = c$ and $b = d$. Then $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$.

($\implies$) Suppose $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$. By the axiom of extension, they have exactly the same elements. Then we have two disjoint cases.

1. $\{ a \} = \{ c, d \}$. By the axiom of extension, $a = c = d$. This implies $\{ \{ c \} \} = \{ \{ c \}, \{ c, d \} \} = \{ \{ a \}, \{ a, b \} \} \implies c = a = b$ Thus, $a = b = c = d$, i.e. $a = c \land b = d$.

2. $\{a\} \neq \{c,d\}$. Then, $\{ a \} = \{ c \}$. Then, $a = c$. Since $\{ \{ a \}, \{a,b\}\} = \{ \{ c \}, \{ c, d \} \}$ and $\{a\} \neq \{c,d\}$, we have $\{a,b\} = \{c,d\}$. $c \neq d$, therefore $b = d$. Thus, $a = c \land b = d$.

$\square$

Definition (Ordered Pair)

Let $A$ and $B$ be sets with $a \in A \land b \in B$. Then the ordered pair $(a, b) = \{ \{a\}, \{a, b\} \}$

• $(a, b) = (c, d) \iff a = c \land b = d$

Definition (Cartesian Product)

Let $A$, $B$ be sets. The Cartesian product is defined as $A \times B = \{ (a, b) : a \in A \land b \in B \}$

Definition

A subset $\char`~ \subseteq A \times B$ is also called a relation from $A$ to $B$.

Example

$$\begin{align} A &= \{a, b, c\} \\ B &= \{1, 2, 3\} \\ A \times B &= \{(a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3)\} \\ \end{align}$$

notation

If an element, say $(a, 1) \in \sim$, we write $a \sim 1$. If an element, say $(b, 1) \not\in \sim$, we write $b \not\sim 1$. We also write the relation as $\sim: A \to B$.

Definition (Domain, Range)

Let $\sim: A \to B$ be a relation.

Domain: $dom(\sim) = \{ a \in A: \exists b \in B : a \sim b \}$
Range: $rng(\sim) = \{ b \in B: \exists a \in A : a \sim b \}$

Example

$A = \{ 1, 2, 3, 4 \}$
$B = \{ 2, 5, 6, 7 \}$
let $\sim: \{(1, 2), (2, 2), (3, 5)\}$
$dom(\sim) = \{ 1, 2, 3 \}$
$rng(\sim) = \{ 2, 5 \}$

Example

Let $\sim$ be $<$. This is a relation.

If $a < b$, then $a \sim b$, i.e. $(a, b) \in \sim$

$A = \{ 1, 2, 8, 9 \}$
$B = \{ 2, 5, 1, 10 \}$
$\sim: \{ (1, 2), (1, 5), (1, 10), (2, 5), (2, 10), (8, 10), (9, 10) \}$

Definition

Let $A$ and $B$ be sets and $f : A \to B$ be a relation from $A$ to $B$. Then $f$ is a function iff the following hold:

• $f$ is well defined. $\forall a \in A \land b_1, b_2 \in B$ we have that if $(a, b_1) \in f \land (a, b_2) \in f$, then $b_1 = b_2$.
• $f$ is totally defined. $\forall a \in A \exists b \in B : (a, b) \in f$

Functions are also called mappings.

We also write $f(a) = b$ if $(a, b) \in f$.

Definition

Let $A$, $B$ be sets and $f: A \to B$ be a function.

1. $f$ is injective iff $\forall x, y \in A: x \neq y \implies f(x) \neq f(y)$
2. $f$ is surjective iff $\forall y \in B \exists x \in A : f(x) = y$

If a function is both injective AND surjective, then it is called bijective.

Proposition

Let $A$, $B$ be sets. Let $f: A \to B$ be a function. Then $f$ is injective iff $\forall x, y \in A$ we have that $f(x) = f(y) \implies x = y$.

Example

Let $f: \R \setminus \{ 2 \} \to \R : f(x) = \frac{4x + 3}{x-2}$ (we'll pretend $\R$ exists)

Prove it is injective:

Let $f(x) = f(y)$ : $\frac{4x+3}{x-2} = \frac{4y+3}{y-2}$ $$\begin{align} (4x+3)(y-2) &= (4y+3)(x-2) \\ 4xy - 8x + 3y - 6 &= 4xy - 8y + 3x - 6 \\ 8x + 3y &= 8y + 3x \\ 11y &= 11x \\ y &= x \\ \end{align}$$

Definition

Let $A$, $B$, $C$ be sets and $g : A \to B \land f: B \to C$ be functions. The composition is defined:
$$f \circ g = \{ (a, c) \in A \times C : [ \exists b \in B : g(a) = b \land f(b) = c ] \}$$

$$f \circ g = f(g(a)) = f(b) = c$$

Example

$$\begin{align} A &= \{ a, b, c, d \} \\ B &= \{ \alpha, \beta, \gamma, \omega \} \\ C &= \{ 1, 2, 3 \} \\ g &= \{(a, \beta), (b, \omega), (c, \gamma), (d, \alpha)\}: A \to B \\ f &= \{ (\alpha, 3), (\beta, 1), (\gamma, 3), (\omega, 2) \}: B \to C \\ f \circ g &= \{ (a, 1), (b, 2), (c, 3), (d, 3) \} \end{align}$$

Definition (Identity Function)

Let $A$ be a set $id_A = \{ (a, a) \in A \times A : a \in A \}$ is called the identity function on $A$.

Example

Let $f: A \to B$ and $g: C \to A$ be functions. Find $f \circ id_A$ and $id_A \circ g$.

1. $f: A \to B : f(a) = b$
   $id_A : A \to A : id_A(a) = a$
   $f \circ id_A = f(id_A(a)) = f(a) = b$
   $f \circ id_A = f$

2. Exercise

Definition (inverse)

let $A$, $B$ be sets and let $f: A \to B$ be a function. The function $g: B \to A$ is called the inverse of $f$ iff $f \circ g = id_B$ and $g \circ f = id_A$.

Example

$$\begin{align} A &= \{ \alpha, \beta, \gamma\} \\ B &= \{ a, b, c \} \\ id_A &= \{ (\alpha, \alpha), (\beta, \beta), (\gamma, \gamma)\} \\ id_B &= \{ (a, a), (b, b), (c, c) \} \\ \end{align}$$

let $f = \{(\alpha, b), (\beta, a), (\gamma, c) \}$
let $g = \{(a, \beta), (b, \gamma), (c, \alpha) \}$

$$\begin{align} f \circ g &= f(g) \\ f(g(a)) &= f(\beta) = a \\ f(g(b)) &= f(\gamma) = c &&& \text{Not inverses} \\ f \circ g &= f(g) = \{ (a, a), (b, c) \end{align}$$

Example

$$\begin{align} A &= \{ \alpha, \beta, \gamma\} \\ B &= \{ a, b, c \} \\ id_A &= \{ (\alpha, \alpha), (\beta, \beta), (\gamma, \gamma)\} \\ id_B &= \{ (a, a), (b, b), (c, c) \} \\ \end{align}$$

let $f = \{(\alpha, b), (\beta, a), (\gamma, c) \}$
let $g = \{(a, \beta), (b, \alpha), (c, \gamma) \}$

$$\begin{align} f(g(a)) &= f(\beta) = a \\ f(g(b)) &= f(\alpha) = b \\ f(g(c)) &= f(\gamma) = c \\ f \circ g &= f(g) = \{ (a, a), (b, b), (c, c) \} = id_B \\ g \circ f &= g(f) = \{ (\alpha, \alpha), (\beta, \beta), (\gamma, \gamma) \} = id_A \\ \end{align}$$

Definition

Two sets $A$, $B$ are equivalent iff $\exists$ a bijective function $f: A \to B$.

Theorem

If $X$ is a set, then $X$ is not equivalent to $P(X)$

Proof

SFAC, $\exists$ a bijective function $f: X \to P(X)$.

$B = \{ x \in X : x \not\in f(x) \}$ -- This is the set of elements $x$ that are mapped to a subset of $X$ for which $x$ is not a member.

By the axiom of specification, $B$ is a set and $B \subseteq X$. Then, $B \in P(X)$. Since $f$ is surjective, $\exists b \in X : f(b) = B$. If $b \in B$, then $b \not\in f(b) = B$, thus $b \not\in B$, but then $b \in B$. Contradiction.

Thus, no bijection exists and the sets are not equivalent.
$\square$

Definition (Indexed Family of Subsets)

let $X$ be a set. An indexed family of subsets $S_i$ of $X$ is denoted $\{ S_i \}_{i \in I}$ where it is understood that there is a function from $I$ to $P(X)$ that maps each $i \in I$ to $S_i$. If $\{S_i\}_{i \in I}$ is an indexed family of sets, the union is $\bigcup_{i \in I}S_i = \{x \in X : [\exists i \in I : x \in S_i ]\}$ and the intersection $\bigcap_{i \in I}S_i = \{x \in X : [\forall i \in I : x \in S_i ]\}$

Definition

Let $X$ be a set. Define $V_0(X) = X$ and for each $n \in \N$, define $V_n(X) = V_{n-1} \cup P(V_{n-1}(X))$

Example

$$\begin{align} X &= \{ a, b, c \} \\ V_0(X) &= \{ a, b, c \} \\ V_1(X) &= V_0 \cup P(V_0) = \{ \{ a, b, c \}, \{\emptyset, \{a\}, \{b\}, \{c\}, \mathtt{..P(X)} \} \} \\ \end{align}$$

$V(X) = \cup_{n \in N_0}V_n \in (C)$ is called the superstructure of $X$.

2.6 -- The Axiom of Infinity and the Natural Numbers

axiom

There is a set $I$ that contains $\emptyset$ and an element and for each $a \in I$ the set $a \cup \{ a \} \in I$ also.

$\emptyset \in I$
$\emptyset \cup \{ \emptyset \} \in I$ => $\{ \emptyset \} \in I$
$\{ \emptyset \} \cup \{ \{ \emptyset \} \} \in I$ => $\{ \emptyset, \{ \emptyset \}\} \in I$

$$\begin{align} I = \{ \\ & \emptyset, \\ & \big\{ \emptyset \big\} \\ & \big\{ \emptyset, \{ \emptyset \} \big\} \\ & \big\{ \emptyset, \{ \emptyset \}, \{ \emptyset, \{ \emptyset \} \} \big\} \\ & \cdots \} \end{align}$$

let $1 = \{ \emptyset \}$
and $\forall n \in I$, let $n' = n \cup \{n\}$

Definition (successor set)

We call $S \subseteq I$ a successor set iff $\emptyset \not\in S$, $1 \in S$, and $\forall n \in S, n' \in S$

• $I \setminus \emptyset$ is a successor set

The Peano Axioms

There is a set, denoted $\N$ called the natural numbers, such that:

1. $\exists$ a special element, $1 \in \N$
2. $\forall n \in \N, \exists n' \in \N$, called the successor of $n$.
3. $1$ is not the successor of any element $n \in \N$.
4. Principle of Induction: If $S \subseteq N$ is such that $1 \in S$ and $\forall n \in S$, we have $n' \in S$, then $S = \N$.
5. $\forall n, m \in \N$, if $m' = n'$, then $m = n$

Notice: All successor sets are subsets of $I$
$\implies$ every successor set $\in P(I)$. By the axiom of specification, $\exists$ a subset $\mathcal{S} \subseteq P(I)$ whose elements are all the successor sets.
Let $\N = \bigcap \mathcal{S}$

Proof

1. We need to prove $1 \in \N$. Every successor set $S$ contains $1$ as an element, thus $1 \in \bigcap \mathcal{S} = \N$.
2. Now, we need to prove $\forall n \in \N$, $n' \in \N$. Let $n \in \N$ be ABF.
   Since, $n \in \N$, $n \in \bigcap \mathcal{S}$, thus $\forall S \in \mathcal{S}, n \in S$. By definition of successor sets, $n' \in S \forall S$, thus $n' \in \bigcap \mathcal{S} = \N$.
3. We need to show that $1$ is not the successor of any element of $\N$. SFAC that $1 = x'$ for some $x \in \N$. Then, $1 = x' = x \cup \{ x \}$. BUt we defined, $1 = \{ \emptyset \}$. Then $\{ \emptyset \} = x \cup \{ x \} \implies x = \emptyset$. But we defined $S$ so that the $\emptyset \not\in S$. Contradiction. Thus, $1$ is not a successor.
4. We must prove that $S \subseteq \N$ and $1 \in S$ and $\forall n \in S : n' \in S$, then $S = \N$. Let $S$ be ABF subset of $\N$ so that $1 \in S$ and $\forall n \in S : n' \in S$.
   We will prove $S = \N$ by mutual containment. Clearly, $S \subseteq N$.
   We defined $\N = \bigcap \mathcal{S}$, thus $\forall S \in \mathcal{S}, \N \subseteq S$. Therefore, $S = \N$.
5. Se must prove $\forall n, m \in \N$ with $m' = n'$, we have $m = n$. First, we prove $\forall n \in \N$, every element of $n$ is a subset of $n$. Let $S = \{ n \in \N : [ \forall m \in n : m \subseteq n ] \}$. This is equivalent to $S = \N$. Trivially, $1 \in S$. Let $n \in S$. To prove $n' \in S$, recall that $n' = n \cup \{ n \}$. Hence, if $m \in n'$, then $m \in n \cup \{ n \}$. Thus, $m = n$ or $m \in n$. If $m = n$, since $n \subseteq n'$, $m \subseteq n'$ and $n' \in S$. If $m \in n$, because $n \in S$, $m \subseteq n \subseteq n'$. Thus, $n' \in S$ and by Principle of Induction, $S = \N \implies$ if $m \in n$, $m \subseteq n$.
   Now, let $m' = n'$. Then, $m' = m \cup \{ m \} = n' = n \cup \{ n \}$. SFAC that $m \neq n$. Then $\{ m \} \neq \{ n \}$. Which implies $m \in n \land n \in m$, but then $m \subseteq n \land n \subseteq m$ and $n = m$. Contradiction. Therefore, if $m' = n'$, then $m = n$.