# Set Theory

## 1 Sets and Functions

Definitions of $\{\}\in\notin\subset\subseteq=\emptyset$ .

Further definitions on $\cup\cap$ , arbitrary, disjoint, pairwise disjoint. Shows how union and intersection are associative, commutative, and distributive. Defines difference, symmetric difference, complement. Shows the duality principle, leading to dual theorems.

Definitions of (real) function $f$ on $X$ , domain, range, mapping of $M$ into $N$ , image, preimage, image of $A$ , preimage of $B$ , map into, map onto, one-to-one, one-to-one correspondence, inverse of $f$ .

Theorem 1

$f^{-1}(A\cup B)=f^{-1}(A)\cup f^{-1}(B)$

Theorem 2

$f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$

Theorem 3

$f(A\cup B)=f(A)\cup f(B)$

Note $f(A\cap B)\neq f(A)\cap f(B)$ . Also note that Theorems 1-3 hold for an arbitrary number of sets.

Definitions of decomposition or partition into classes, a is related to b by the (binary) relation R, equivalence relation, reflexitivity, symmetry, transitivity.

Theorem 4

$M$ can be partitioned into classes by a relation $R$ $\Leftrightarrow$ $R$ is an equivalence relation on $M$ .

### Problems

1. Show $A\cup B=A$ and $A\cap B=A$ $\Rightarrow$ $A=B$

$B\subseteq A$ since $A\cup B=A$ and $A\subseteq B$ since $A\cap B=A$ . Hence, $A=B$

2. Show $(A-B)\cup B\neq A$

Take $A$ to be the empty set and $B$ to be any non-empty set.

3. Let $A=\{2,4,...,2n,...\}$ and $B=\{3,6,...,3n,...\}$ . Find $A\cap B$ and $A-B$

$A\cap B=\{6,12,...,6n,...\}$ . $A-B=\{2,4,8,10,14,16,...\}$

4. Prove that $(A-B)\cap C=(A\cap C)-(B\cap C)$ and $A\Delta B=(A\cup B)-(A\cap B)$

Step through using definitions, complements, idempotence, duality principle, distributivity, associativity, commutativity.

5. Prove $\cup_{\alpha}A_{\alpha}-\cup_{\alpha}B_{\alpha}\subseteq\cup_{\alpha}(A_{% \alpha}-B_{\alpha})$

Evident once some thought has been applied.

6. Let $A_{n}$ be the set of all positive integers divisible by $n$ . What are $\cup_{n=2}^{\infty}A_{n}$ and $\cap_{n=2}^{\infty}A_{n}$ ?

$\cup_{n=2}^{\infty}A_{n}=\{2,3,4,...,n,...\}$
$\cap_{n=2}^{\infty}A_{n}=\emptyset$

7. What are $\cup_{n=1}^{\infty}[a+\dfrac{1}{n},b-\dfrac{1}{n}]$ and $\cap_{n=1}^{\infty}(a-\dfrac{1}{n},b+\dfrac{1}{n})$ ?

If $b-a>1$ $\cup_{n=1}^{\infty}[a+\dfrac{1}{n},b-\dfrac{1}{n}]=(a,b)$
If $b-a\leq 1$ $\cup_{n=1}^{\infty}[a+\dfrac{1}{n},b-\dfrac{1}{n}]=[b-1,a+1]$
$\cap_{n=1}^{\infty}(a-\dfrac{1}{n},b+\dfrac{1}{n})=[a,b]$

8. Let $A_{\alpha}$ be the set of points lying on the curve $y=\dfrac{1}{x^{\alpha}}$ with $0 . What is $\cap_{\alpha\geq 1}A_{\alpha}$ ?

$(1,1)$

9. $y=f(x)=\{x\}$ (fractional part of $x$ ). Prove every closed interval of length one has the same image under $f$ . What is this image? Is $f$ one-to-one? What is the preimage of the interval $\dfrac{1}{4}\leq y\leq\dfrac{3}{4}$ ? Partition the real line into classes of points with the same image.

Simple enough.

10. Given set $M$ , let $\mathcal{R}$ be the set of all ordered pairs $(a,a)$ with $a\in M$ . Let $aRb\Leftrightarrow(a,b)\in\mathcal{R}$ . Interpret $R$ .

Equality.

11. Find a binary relation which is:

1. Reflexive and symmetric, but not transitive.

2. Reflexive, but neither symmetric nor transitive.

3. Symmetric, but neither reflexive nor transitive.

4. Transitive, but neither reflexive nor symmetric.

Blood relative. Remembers name of (provided everybody knows their own name). Not equal to. Strictly greater than. (Credit to CoveredInChocolate for the first two answers.)

## 2 Equivalence of Sets. The Power of a Set

Definitions of finite, infinite, countable, uncountable. Demonstration of how the rationals are countable.

Theorem 1

Every subset of a countable subset is countable.

Theorem 2

The union of a finite or countable number of countable sets is itself countable.

Proof

Line the elements of the sets parallel to each other, and count all of the elements ‘diagonally’.

Theorem 3

Every infinite set has a countable subset.

Definition of equivalence.

Demonstration of how the points on a sphere can be mapped one-to-one with the points in the complex plane with stereographic projection.

Theorem 4

Every infinite set $M$ is equivalent to one of its proper subsets.

Proof

By Theorem 3, every infinite set contains a countable subset $A$ . Partition this subset into two countable subsets $A_{1}$ and $A_{2}$ . A one-to-one correspondence can be set between $A$ and $A_{1}$ . Hence $M=A\cup(M-A)\sim A_{1}\cup(M-A)=M-A_{2}$ and $M-A_{2}$ is a proper subset of $M$ .

Theorem 5

The set of real numbers in the closed unit interval $[0,1]$ is uncountable.

Proof

Cantor’s diagonal. Make sure to disallow setting a digit as $0$ or $9$ .

Definition of power, aleph null, continuum.

Theorem 6

Given any set $M$ , let $\mathcal{M}$ be the set whose elements are all possible subsets of $M$ . Then the power of $\mathcal{M}$ is greater than the power of the original set $M$ .

Proof

Attempt to setup $X$ to be the set of elements of $M$ which do not belong to their ‘associated subsets’. Then we reach an argument similar to Russel’s paradox.

Theorem 7 (Cantor-Bernstein)

Given any two sets $A$ and $B$ , suppose $A$ contains a subset $A_{1}$ equivalent to $B$ , while $B$ contains a subset $B_{1}$ equivalent to $A$ . Then $A$ and $B$ are equivalent.

Proof

The proof is beautifully shown in the book. A sketch would be a disservice.

### Problems

1. Prove that a set with an uncountable subset is itself uncountable.

Suppose the set is countable, and very quickly reach a contradiction.

2. Let $M$ be any infinite set and $A$ any countable set. Prove that $M\sim M\cup A$ .

Use Theorem 3.

3. Prove that the following sets are countable:

1. The set of all numbers with two distinct decimal expansions.

Since all of the numbers can either be shown as $n.x00000$ or $n.y99999$ , only consider the $n.x00000$ representation. Evident that this is a subset of the rationals, hence countable.

2. The set of all rational points in the plane.

Simply extend the technique used for demonstrating that the rationals are countable.

3. The set of all rational intervals.

This can be transposed to be a subset of the the set of all rational points in the plane, i.e. the previous question.

4. The set of all polynomials with rational coefficients.

This can be transposed to a subset of the set of all rational points in $n$ dimensions. Extend the argument for problem 3.2. from 2 dimensions to $n$ dimensions.

4. A number $\alpha$ is called algebraic if it is a root of a polynomial equation with rational coefficients. Prove that the set of all algebraic numbers is countable.

The set of all polynomials with rational coefficients is countable, and each polynomial has a maximum of $n$ solutions. Hence countable by Theorem 2.

5. Prove that the existence of uncountably many transcendental numbers, i.e., numbers which are not algebraic.

From Theorem 5, we know that there are uncountably many numbers between $[0,1]$ . And from Theorem 2, we know that no union of countable sets will ever become uncountable. Hence there must exist numbers within $[0,1]$ which are not algebraic. We call these transcendental.

6. Prove that the set of all real functions (more generally, functions taking values in a set containing at least two elements) defined on a set $M$ is of power greater than the power of $M$ . In particular, prove that the power of the set of all real functions (continuous and discontinuous) defined in the interval $[0,1]$ is greater than $c$ .

Just look at the identity functions. The set of all identities has a one-to-one correspondence with the power set.

7. Give an indirect proof of the equivalence of the closed interval $[a,b]$ , the open interval $(a,b)$ and the half-open interval $[a,b)$ or $(a,b]$ .

Need to find suitable functions to use with Theorem 7.

8. Prove that the union of a finite or countable number of sets each of power $c$ is itself of power $c$ .

Since $[0,1]$ is uncountable, and by problem 7, so is $[0,1)$ , map each set to $[0,1)$ , $[1,2)$ , … respectively. Evidently the union is a subset within the real line, and is itself of power $c$ .

9. Prove that each of the following sets has the power of the continuum:

1. The set of all infinite sequences of positive integers.

Place $0.$ in front of the integers to get the set $(0,1)$ .

2. The set of all ordered $n$ ​-tuples of real numbers.

Use a similar argument to problem 8.

3. The set of all infinite sequences of real numbers.

Need to check how to deal with the uncountable sequences of real numbers.

10. Develop a contradiction inherent in the notion of the “set of all sets which are not members of themselves”.

## 3 Ordered Sets and Ordinal Numbers

Definitions of partial ordering, partially ordered (reflexive, transitive, antisymmetric), maximal, minimal.

A bijective function $f$ is order-preserving if $a\leq b\Rightarrow f(a)\leq f(b)$ . An order-preserving function $f$ is an isomorphism if $f(a)\leq f(b)\Leftrightarrow a\leq b$ . Two partially ordered sets are isomorphic if there exists an isomorphism between them.

Noncomparable if neither $a\leq b$ nor $b\leq a$ . A set is ordered if it contains no noncomparable elements. Two isomorphic sets have the same (order) type. Order of $\mathbb{N}$ (in the normal manner) is $\omega$ . The power $\aleph_{0}$ corresponds to the order type $\omega$ .

Definition 1 An ordered set $M$ is well-ordered if every nonempty subset $A$ of $M$ has a smallest (or “​first​”) element, i.e., an element $\mu$ such that $\mu\leq a$ for every $a\in A$ .

Definition 2 The order type of a well-ordered set is an ordinal number or simply an ordinal. If the set is infinite, the ordinal is transfinite.

Theorem 1

The ordered sum of a finite number of well-ordered sets $M_{1},M_{2},\ldots,M_{n}$ is itself a well-ordered set.

Proof

Let $M$ be an arbitrary subset of the ordered sum $M_{1}+M_{2}+\ldots+M_{n}$ , and let $M_{k}$ be the first set containing elements of $M$ . Then $M\cap M_{k}$ is a subset of the well-ordered set $M_{k}$ , and therefore has a smallest element $\mu$ . Clearly $\mu$ is also the smallest element of $M$ .

Need to check whether this holds for the sum of countably many well-ordered sets, and why?

Corollary

The ordered sum of a finite number of ordinal numbers is itself an ordinal number.

Theorem 2

The ordered product of two well-ordered sets $M_{1}$ and $M_{2}$ is well-ordered.

Proof

Let $M$ be an arbitrary subset of $M_{1}\cdot M_{2}$ , with $(a,b)$ such that $a\in M_{1}$ , $b\in M_{2}$ . The set of all second elements $b$ in $M$ is a subset of $M_{2}$ , and therefore has a least element $b_{1}$ since $M_{2}$ is well-ordered. Then look at all $(a,b_{1})$ . Again, the set of all first elements $a$ is a subset of $M_{1}$ , hence has a smallest element $a_{1}$ since $M_{1}$ is well-ordered. $(a_{1},b_{1})$ is clearly the smallest element of $M$ .

Corollary 1

The ordered product of a finite number of well-ordered sets is itself a well-ordered set.

Corollary 2

The ordered product of a finite number of ordinal numbers is itself an ordinal number.

Every element of a well-ordered set $M$ determines an (initial) section $P$ , the set of all $x\in M$ such that $x , and a remainder $Q$ , the set of all $x\in M$ such that $x\geq a$ . Given two well-ordered sets $M$ and $N$ of order type $\alpha$ and $\beta$ respectively, then:

1. $\alpha=\beta$ if $M$ and $N$ are isomorphic.

2. $\alpha<\beta$ if $M$ is isomorphic to some section of $N$ .

3. $\alpha>\beta$ if $N$ is isomorphic to some section of $M$ .

Lemma

Let $f$ be an isomorphism of a well-ordered set $A$ onto some subset $B\subseteq A$ . Then $f(a)\geq a$ for all $a\in A$ .

Proof

If there exists $a\in A$ such that $f(a) , then there is a least such element $a_{0}$ since $A$ is well-ordered. Let $b_{0}=f(a_{0})$ , then $b_{0} , and $f(b_{0}) since $f$ is an isomorphism. But then $a_{0}$ is not the smallest element such that $f(a) . Contradiction.

Theorem 3

Two given ordinal numbers $\alpha$ and $\beta$ satisfy one and only one of the relations $\alpha<\beta$ , $\alpha=\beta$ , $\alpha>\beta$ .

Proof

Let $W(\alpha)$ be the set of all ordinals $<\alpha$ . Any two numbers $\gamma$ and $\gamma^{\prime}$ in $W(\alpha)$ are comparable and the corresponding ordering of $W(\alpha)$ makes it a well-ordered set of type $\alpha$ . If a set $A$ is of type $\alpha$ , then by definition, the ordinals less than $\alpha$ are the types of well-ordered sets isomorphic to sections of $A$ . Hence, the ordinals are in one-to-one correspondence with the elements of $A$ .

Let $\alpha$ , $\beta$ be two ordinals, then $W(\alpha)$ , $W(\beta)$ are well-ordered sets of type $\alpha$ , $\beta$ respectively. Let $C=A\cap B$ . Then $C$ is well-ordered, of type $\gamma$ , say. We now show $\gamma\leq\alpha$ . If $C=A$ , then obviously $\gamma=\alpha$ . Otherwise, if $C\neq A$ , then $C$ is a section of $A$ and hence $\gamma<\alpha$ .

[Let $\xi\in C$ , $\eta\in A-C$ . Then $\xi$ , $\eta$ are comparable, i.e., either $\xi<\eta$ or $\xi>\eta$ . But $\eta<\xi<\alpha$ is impossible, since then $\eta\in C$ . Therefore $\xi<\eta$ and hence $C$ is a section of $A$ , which implies $\gamma<\alpha$ . Moreover, $\gamma$ is the first element of $A-C$ .]

Thus $\gamma\leq\alpha$ . Similarly $\gamma\leq\beta$ . The case $\gamma<\alpha$ , $\gamma<\beta$ is impossible, since then $\gamma\in A-C$ , $\gamma\in B-C$ . But then $\gamma\notin C$ on the one hand and $\gamma\in A\cap B=C$ on the other hand.

It follows that there are only three possibilities:

$\gamma=\alpha,\gamma=\beta,\alpha=\beta$ $\gamma=\alpha,\gamma<\beta,\alpha<\beta$ $\gamma<\alpha,\gamma=\beta,\alpha>\beta$

i.e., $\alpha$ and $\beta$ are comparable.

Theorem 4

Let $A$ and $B$ be well-ordered sets. Then either $A$ is equivalent to $B$ or one of the sets is of greater power than the other, i.e., the powers of $A$ and $B$ are comparable.

Proof

A definite power corresponds to each ordinal. As ordinals are comparable, so are the corresponding powers.

Well-ordering theorem

Every set can be well-ordered.

Axiom of choice

Given any set $M$ , there is a “choice function” $f$ such that $f(A)$ is an element of $A$ for every nonempty subset $A\subseteq M$ .

Definition 3 Let $M$ be a partially ordered set, and let $A$ be any subset of $M$ such that $a$ and $b$ are comparable for every $a$ , $b\in A$ . Then $A$ is a chain (in $M$ ). A chain $C$ is maximal if there is no other chain $C^{\prime}$ in $M$ containing $C$ as a proper subset.

Definiton 4 An element $a$ of a partially ordered set $M$ is an upper bound of a subset $M^{\prime}\subseteq M$ if $a^{\prime}\leq a$ for every $a^{\prime}\in M^{\prime}$ .

The below two assertions are equivalent to the axiom of choice.

Hausdorff’s maximal principle

Every chain in a partially ordered set $M$ is contained in a maximal chain in $M$ .

Zorn’s Lemma

If every chain in a partially ordered set $M$ has an upper bound, then $M$ contains a maximal element.

Theorem 5 (Mathematical induction)

Given a proposition $P(n)$ formulated fo every positive integer $n$ , suppose that

1. $P(1)$ is true.

2. The validity of $P(k)$ for all $k\leq n$ implies the validity of $P(n+1)$ .

Then $P(n)$ is true for all $n=1,2,\ldots$

Proof

Suppose $P(n)$ fails to be true for all $n=1,2,\ldots$ Let $n_{1}$ be the smallest integer for which $P(n)$ is false ($n_{1}$ exists due to the well-ordering of the positive integers). Clearly $n_{1}>1$ , so $n_{1}-1$ is a positive integer. Therefore $P(n)$ is valid for all $k\leq n_{1}-1$ , but not for $n_{1}$ . Contradiction.

Theorem 5’ (Transfinite induction)

Given a well-ordered set $A$ , let $P(a)$ be a proposition formulated for every element $a\in A$ . Suppose that

1. $P(a)$ is true for the smallest element of $A$ .

2. The validity of $P(a)$ for all $a implies the validity of $P(a^{*})$ .

Then $P(a)$ is true for all $a\in A$ .

Proof

Suppose $P(a)$ fails to be true for all $a\in A$ . Then $P(a)$ is false for all $a$ in some nonempty subset $A^{*}\subseteq A$ . By well-ordering, $A^{*}$ has a smallest element $a^{*}$ . Therefore $P(a)$ is valid for all $a but not for $a^{*}$ . Contradiction.

### 3.1 Problems

1. Exhibit both a partial ordering and a simple ordering of the set of all complex numbers.

Partial ordering: only order reals. Simple: order reals, then complex.

2. What is the minimal element of the set of all subsets of a given set $X$ , partially ordered by set inclusion? What is the maximal element?

$\emptyset$ and $X$ .

3. A partially ordered set $M$ is a directed set if, given any two element $a$ , $b\in M$ , there is an element $c\in M$ such that $a\leq c$ , $b\leq c$ . Are the partially ordered sets in Examples 1-4, Section 3.1 all directed sets?

No, yes, yes, yes.

4. The greatest lower bound of two elements $a$ and $b$ of a partially ordered set $M$ is $c\in M$ such that $c\leq a$ , $c\leq b$ and there is no element $d\in M$ such that $c , $d\leq b$ . Define least upper bound similarly. A lattice is a partially ordered set with both a greatest lower bound and a least upper bound. Prove that the set of all subsets of a given set $X$ , partially ordered by set inclusion, is a lattice. What is the set-theoretic meaning of the greatest lower bound and least upper bound of two elements of this set?

Same as 2.

5. Prove that an order-preserving mapping of one ordered set onto another is automatically an isomorphism.

All order-mapping preserving mappings are bijective. Hence an inverse exists. Need to show how the inverse also preserves order. Hence isomorphism.

6. Prove that ordered sums and products of ordered sets are associative.

Just step through to show that they are the same.

7. Construct well-ordered sets with ordinals $\omega+n$ , … Show that the sets are all countable.

$\mathbb{N}+\{a_{1},\ldots,a_{n}\}$ , … Line each one up on a row, and zigzag up and down.

8. Construct well-ordered sets with ordinals $\omega\cdot n$ , … Show that the sets are all countable.

$\mathbb{N}\cdot\{a_{1},\ldots,a_{n}\}$ , … Similar proof to countability of the rationals.

9. Show that $\omega+\omega=\omega\cdot 2$ .

Let $f$ send $a\in\mathbb{N}_{1}+\mathbb{N}_{2}$ to $(a,1)$ if $a\in\mathbb{N}_{1}$ and to $(a,2)$ if $a\in\mathbb{N}_{2}$ . Evidently bijective, and order-preserving, hence isomorphic, and hence they have equivalent ordinals too.

10. Prove that the set $W(\alpha)$ of all ordinals less than a given ordinal $\alpha$ is well-ordered.

Each ordinal less than $\alpha$ corresponds to a section of $A$ . There is a least section of $A$ , the empty set, as all other sections of $A$ are greater than or equal to it. Hence the corresponding ordinal to the empty set is the least element of $W(\alpha)$ and we also know that ordinals are comparable. Therefore $W(\alpha)$ is well-ordered.

11. Prove that any nonempty set of ordinals is well-ordered.

$A$ subset. Nonempty and ordinals are comparable so exists $\mu\in A$ such that $\mu\leq a$ for all $a\in A$ . Therefore well-ordered.

12. Prove that the set $M$ of all ordinals corresponding to a countable set is itself countable.

Line them up. Then use Cantor diagonal argument.

13. Let $\aleph_{1}$ be the power of the set $M$ in the preceding problem. Prove that there is no power $m$ such that $\aleph_{0} .

Impossible as there is no set which is strictly bigger than countable and yet strictly smaller than uncountable.

### 3.2 Open ends

1. Why do Theorems 1 and 2 hold for just finitely many? Do they also hold for countably many? If not, why not?

2. What well-ordered set has ordinal $\omega^{\omega}$ ?

I found this link https://en.wikipedia.org/wiki/Ordinal_analysis#Theories_with_proof-theoretic_ordinal_%CF%89%CF%89 but it still leaves me none the wiser. This link https://math.stackexchange.com/questions/1412153/let-omega-be-the-ordinal-of-the-well-ordered-set-mathbbn-what-does-mean is a tiny bit clearer.

3. For Problem 5, how is it shown that the inverse preserves order?

4. Is the proof for Problem 13 correct?

I would greatly appreciate any help.