Set theory

My log for studying set theory

This pages contains log for my self-study on set theory.

Chapter 1: Sets

3. The axioms

3.1

Let \(P(x, A, B)\) be the property: \(x \in A, \, x \notin B\). Then this property implies that \(x \in A\). Therefore, \(\{ x \mid x \in A, x \in B \} = \{ x \in A \mid x \in A, x \in B \} = \{ x \in A \mid x \in B \}\). This set exists by the Axiom schema of comprehension.

3.2

Let \(A\) be a set known to exist. Then using property \(P(x) = x \neq x\), we can use Axiom schema of comprehension to say that there exists set \(B = \{ x \in A \mid x \neq x \}\). Then we can easily see that such set is empty.

3.3 (a)

Suppose that there is a set of all sets \(V\). Then using Axiom schema of comprehension, there exists a set \(T = \{ x \in V \mid x \notin x \}\). Now we will show contradiction by saying \(T \notin V\) since this would mean \(T\) is not a set. Suppose \(T \in V\). Suppose \(T \notin T\). Then \(T \in T\), contradiction. Suppose \(T \in T\). Then \(T \notin T\) must hold, again contradiction. Thus \(T \notin V\).

3.3 (b)

This is easily proven because if there is some set \(A\) where \(x \in A\) for all \(x\), this would mean \(A\) is set of all sets.

3.4

This can be proven by doing axiom of schema comprehension and then doing axiom of union.

3.5

This can be proven by doing Axiom of pair and union.

3.6

We will use the hint. we can clearly see that \(Y \in p(x)\) since \(Y\) by definition is a subset of \(X\). Then we can derive contradiction by checking if \(Y \in Y\). This logic is similar to the previous proofs that showed that “set of all sets” does not exist.

3.7

Consult link.

4. Elementary operations on sets

4.4

Suppose that \(A^c\) exists. Then by axiom of union, the union of \(A\) and \(A^c\) exists. But this is set of all sets. Contradiction.

4.6

Consult link.

Chapter 2

1. Ordered pairs

1.1

We will just prove the general one. Let \(a \in A\) and \(b \in A\) (Note that in set theory, everything is a set). Then by axiom of pair, \(\{ a\}\) and \(\{a,b\}\) exists and they are elements of \(p(A)\). We can again do axiom of pair to finish the proof.

1.2

This is just proven by multiple application of axiom of pairing.

1.3

Suppose \(a \neq b\). Then as \(\{a \} = \{b\}\), this implies that \(a=b\), contradiction.

1.4, 1.5, 1.6

Consult link.

2. Relations

2.1

\((x,y) \in R\) implies that \(\{x \}, \{ x,y\} \in \cup R\). Thus we have \(x,y \in A\). Then we can use axiom schema comprehension to show that \(\text{dom} R\) exists. Same logic goes for \(\text{ran} R\).

2.2 (a)

Just use the hint and use axiom of schema comprehension.

2.2 (b)

Note that \(A \times B\) exists. thus \(A \times B \times C = (A \times B) \times C\) will also exist. We can explicitly define it as

\[ A \times B \times C = \left\{ (a,b,c) \in p \left[ p \left[ (p(p(A \cup B))) \cup C \right] \right]: a \in A, b \in B, c \in C \right\}. \]

2.3 (a)

\(y \in R [A \cup B]\) iff there is \(x \in A \cup B\) s.t. \((x,y) \in R\). This holds if and only if \(x \in A\) or \(x \in B\) s.t. \((x,y) \in R\). Then this shows that \(x \in R[A] \cup R[B]\).

2.3 (b)

Again suppose \(y \in R[A \cap B]\). Then there is \(x \in A \cap B\) s.t. \((x,y) \in R\). This means there is \(x\in A\) and \(x \in B\) such that \((x,y) \in R\).

2.3 (c)

Let \(y \in R[A] - R[B]\). Then there is \(x \in A, x \notin B\) s.t. \((x,y) \in R\). This is literally \(R[A-B]\).

2.3 (d)

For (b), think of a case where there is a point \((x1,y)\) and \((x2,y)\) where \(x1 \in A - B\) and \(x2 \in B-A\). Then this would be in \(R[A] \cap R[B]\) but \(R[A \cap B]\).

For (c), think of a case where there is some point \(x \in A-B\) and \(y \in A \cap B\) where it corresponds to same value. Then for \(R[A] - R[B]\) will not have this value although it will be in \(R[A-B]\).

2.3 (f)

Let \(x \in A \cap \text{dom} R\). Then \(x \in A\) and there is \(y\) s.t. \(xRy\). This implies that \(y \in R[A]\) by definition. Then as we know there is \(x\) s.t. \(yR^{1}x\), we get \(x \in R^{-1} \left[ R[A] \right]\). Similar logic holds for range. We can easily see that equality will not hold for cases such as \(x\) where \(x \notin A\) but there is \(y\) s.t. \(xRy\). That is, the range value is inside \(R[A]\).

2.4 (a)

Let \(y \in R[X]\). Then \((x,y) \in R\). Thus \(y \in \text{ran} R\). Note that this if iff relation to results go through. Similar to domain case.

2.4 (b)

Suppose \(R^{-1}[\{ b \}]\) is nonempty. Then there is \(a\) s.t. \(\{b, a \} \in R\). Then \(a \in \text{ran } R\). Contradiction.

2.4 (c)

\(x \in \text{dom } R\). This means \((x,y) \in R\). This implies \((y,x) \in R^{-1}\). So \(x\) is also element of \(\text{ran } R^{-1}\).

2.4 (d)

We can easily prove it by noting that \((x,y) \in R \iff (y,x) \in R^{-1}\).

3. Functions

3.1

Let \(x \in \text{dom } g \circ f\). Then there exists \(z\) s.t. \(x(g \circ f)z\). Then there exists \(y\) s.t. \(xfy, ygz\). So this implies that \(x \in \text{dom } f\).

Now suppose \(x \in \text{dom } f\). Then there is \(y\) s.t. \(xfy\). As \(ran f \subset dom g\), there is \(z\) s.t. \(ygz\). So \(x(g \circ f)z\).

3.4 (a)

Let \((x,y) \in f^{-1} \circ f\). Then there is \(z\) s.t. \(xfz\), \(zf^{-1}y\) which means \(yfz\). This means \(x=x\). So \(x \in Id\).

OTH, if \((x,x) \in Id\), there is \(y\) s.t. \(xfy\) and \(yf^{-1}x\). So \(x \in f^{-1} \circ f\).

I also proved 3.4 (b), 3.10 but lost the paper that I wrote it down and am too lazy to do it again. Contact me if you need them.

4. Equivalence relations

4.1 (c)

Reflexive: It does not hold. Since \(x=x\), \(xRx\) cannot hold.

Symmetric: It holds since \(x \neq y\) and \(y \neq x\).

Transitive: Does not hold. Think of \(x=3=z\) and \(y=4\).

4.1 (e,f)

These are equivalence relations because the conditions of the empty sets make the claims vacuously true.

4.2 (a)

Reflexive: We can easily see that \(f(x)=f(x)\).

Symmetry: Let \(xEy\). Then as \(f(x)=f(y)\), this implies \(f(y)=f(x)\). Thus \(yEx\).

Transitive: Let \(xEy\) and \(yEz\). Then we have \(f(x)=f(y)=f(z)\). Thus \(xEz\).

Hence \(E\) is equivalence relation on \(A\).

4.2 (b)

Let \([a]_E = [a']_E\). Then \(\phi([a]_E) = f(a)\) and \(\phi([a']_E) = f(a')\). Then \(f(a) = f(a')\) has to hold by definition of the equivalence.

4.2 (c)

Let \((x,y) \in f\). Since \(j\) is a function on \(A\), there will be some \(z \in A/E\) s.t. \(xjz\). In fact, \(z = [x]_E\) by definition. Then as \(f(x) = \phi([x]_E)\), it is done.

If \((x,z) \in \phi \circ j\), there is some \(y\) s.t. \(j(x) = [x]_E = y\). Also, \(\phi([x]_E) = f(x) = z\). Thus done.