Sets

Fundamentals

We define first what a set is:

We start with some axioms:

1. (Sets are objects) If $A$ is a set, then $A$ is also an object. A side track about "Pure Set Theory" - This theory states that everything in the mathematical universe is a set. We can write 0 as or an empty set, 1 can be written as 0 and 2 as 0,1 and so on. Terence Tao argues that they are the 'cardinalities of the set.'

2. (Equality of sets) Two sets A and B are equal, A = B, iff every element of A is an element of B. A = B, if and only if every element of $x$ of A also belongs to B, and every element $y$ of B belongs to A.

3. (Empty set) There exists a set $\emptyset$ known as the empty set, which contains no elements. $x \notin \emptyset$

Proof. If $x \in A$, then $x \in B$, If $x \in B$, then $x \in C$, Then $x \in A$, then $x \in C$

Thus, $A \subseteq C$

Proof. Proving by contradiction, Suppose there is no object $x$ that belongs to A. For all $x$, we have $x \notin A$. We know from Axiom 3, that $x \notin \emptyset$

For the statement,

$$x \in A \Leftrightarrow x \in \emptyset$$

Is false both ways, which gives us the result true, which is a contradiction.

Thus we also prove that $\emptyset$ is unique.

4. (Singleton sets and pair sets) If $a$ is an object, then there exists a set $\{a\}$ whose only element is $a$, i.e. for every object $y$, we have $y \in \{a\}$ if and only if $y=a$; we refer to $\{a\}$ as the singleton set whose element is $a$. Furthermore if $a$ and $b$ are objects, then there exists a set $\{a,b\}$ if and only if $y=a$ or $y=b$, we refer to this set as the pair set formed by $a$ and $b$.

5. (Single choice) $a$ is an object, $\{a\}$. $y \in \{a\}$, y = a

6. (Pairwise Union) $A \cup B = \{x : x \in A \text{ or } x \in B\}$

Proof. Taking the left hand side, We have $x \in A$ or $x \in (B \cup C)$. If we look to the right hand side, we have $x \in (A \cup B)$ or $x \in C$ If we break the statement down further. We have $x \in A$ or $x \in B$ or $x \in C$, and on the right $x \in A$ or $x \in B$ or $x\in C$

The two statements are equivalent.

7. (Axiom Of Specification) A, $x \in A$, let P(x) be a property pertaining to $x$. Then there exists a set called $\{x \in A, P(x) \text{is true}\}$ whose elements are precisely the elements $x$ in A for which $P(x)$ is true.

8. (Replacement) Let A be a set, for any object $x \in A$, and any object $y$, suppose we have a statement $P(x,y)$ pertaining to $x$ and $y$, such that for each $x \in A$ there is at most one $y$ for which $P(x,y)$ is true. Then there exists a set $\{y : P(x,y)$ is true for some $x \in A\}$

9. (Infinity) There exists a set $\mathbb{N}$, whose elements are called natural numbers, as well as an object $0$ in $\mathbb{N}$, and an object $n++$ assigned to every natural number $n \in \mathbb{N}$ such that the Peano axioms hold.

10. Russel's Paradox (Axiom Of Universal Specification) Suppose for every $x$ we have a property $P(x)$ pertaining to $x$, Then there exists a set $\{x : P(x)$ is true$\}$ such that for every object $y$:

$$y \in \{ x : P(x) \text{is true} \} \Leftrightarrow P(y) \text{is true.}$$

This is quite a handy axiom, we can even find all the axioms through this axiom, but there's an issue.

Let's say we defined the property $P(x) \Leftrightarrow \text{x is a set, and } x \notin x$ And we defined a set $\Omega$ for which this property is true. A paradox is created, where we don't know whether $\Omega$ belongs in this set or not, it's simultaneously true and untrue. If $\Omega$ is not in the set, then it is a set that is not in its own set, thereby being contained in the set. If $\Omega$ is in the set, then it's a set that is in itself, therefore it cannot be in the set. To resolve this paradox we have, the next axiom.

There is a similar paradox known as the "Grellig-Nelson paradox" with the words heterological and autological, the word autological means that the word is an example of itself, for example, the word 'word' is a word or 'pronounceable' is pronounceable or a 'noun' is a noun. The word heterological means that the word is not an example of itself. The word 'triangle' is clearly not a $\triangle$ and so on. The question arises, is heterological autological or heterological?

Proof. Proving for each axiom:

1. For the axiom of null sets,

   We can construct null sets in many ways. We can define the set such that:

$$\{ x : x \ne x \}$$

A property that is not true for any given object. This allows us to then say that, for $P(y)$ is true, where $y \in \phi$ then that means $y \neq y$ which is not true. The third axiom is true.

2. For the axiom of single choice,

   We define the property $P(x)$ such that $x = a$,

   Then for $y \in \{x : P(x) \text{is true}\}$, then $y \in A$

3. For the axiom of pair sets,

   We define the property similarly $P(x)$ such that $x = a$ or $x = b$

   For the axiom of pairwise unions,

   We take $P(x)$ to be $x \in A$ or $x \in B$ For the axiom of specification,

   We define a property $Q(x) : x \in A, P(x)$ is true.

   Then we have,

$$y \in \{x : x\in A, Q(x) \text{is true}\}$$

This means that when $Q(y)$ is true, $y \in A$ $P(y)$ is true

4. For the axiom of replacement, We define $Q(y): x \in A, P(x,y) is true$

   $z \in \{y: Q(y) \text{ is true} \}\Leftrightarrow Q(z) \text{is true or } P(x,z) \text{is true}$

5. For the axiom of infinity, We take the property $P(x)$ that $x$ is a natural number.

11. (Axiom Of Regularity) If A is a non-empty set, then there is at least one element $x$ of A which is either not a set or is disjoint from A. How exactly does this mitigate the issues that come in from Russel's Paradox?

Proof. We take the set A and form a singleton set, $\{A\}$

A, if $x \in \{A\} \Rightarrow x = A$

$$A \cap \{A\} = \phi$$

$$\Rightarrow A \notin A$$

Proof. Let's say we have $A,B$ such that $x \in \{A,B\} \Rightarrow x = A$ or $x = B$

x = A,

$$A \cap \{A,B\} = \phi$$ $$B \notin A \cup \{A,B\}$$ $$B \in \{A,B\}$$

So if $A \cap \{A,B\} = \phi$ Then we know that,

$$B \notin A$$

Because if it were then we'd have$A \cap \{A,B\} = B$

Proof. We can say from the axiom of universal specification,

$$\Omega = \{ x : x \text{ is an object}\}$$

Conversely,

Assuming the universal set exists, we can write

$$\{x \in \Omega, P(x) \text{ is true }\}$$

Since every object belongs to the universal set, this gives us the axiom of universal specificiation

Proof. We define the property $P(x,y)$ to be $y=x$ Thus, we get the axiom of specification. Since $y=x$ we are saying something about $P(x)$ Proof. Proving the converse statement is relatively straightforward,

Given that, $A = \{x\}$

We must prove that there are no non-empty proper subsets of $A$.

A proper subset of $A$ is defined as $A \subseteq B, A \neq B$,

Suppose there is a non-empty proper subset $B$ of $A$

$$\begin{aligned} y \in B & \Rightarrow y \in A = \{x\} \\ & \Rightarrow y = x \end{aligned}$$

Which would mean,

$$\begin{aligned} B & = A \text{ or } \\ B & = \phi \\ \end{aligned}$$

Which is a contradiction.

For the statement, If A does not have any non-empty proper subsets, then A is of the form $A = \{x\}$,

Proving by contradiction,

Suppose that A does not have any non-empty proper subsets and A is not singleton.

This means that the only proper subset of $A$ has to be $\phi$.

But we know from Axiom 4, that all sets are built off of singleton sets, which would be a non-empty proper subset of that set $A$.

Thus the statement is true, proven by contradiction

Proof. 1. $A' \cup B \subseteq A \cup B$
This means $x \in A' or x \in B$

We already know that $A' \subseteq A$ or if $x \in A'$, then $x \in A$. This means, we can say

$$\begin{aligned} A' \cup B \subseteq A \cup B & = x \in A or x \in B \\ A' \cup B \subseteq A \cup B & = A \cup B \\ \end{aligned}$$

When we take out the Axiom Of Universal Specification, we have a set of axioms known as "Zermelo- Fraenkel Set Theory".

We will discuss another axiom, known as the "Axiom of choice" in upcoming sessions, which allows us to talk about unions and intersections of sets that aren't countable.

Functions

These functions are extremely important for modelling the real world. We represent bodies as a set of points. And the way we model the real world is by making these sets have a one-to-one mapping with the Euclidean space.

This leads to the introduction of a new Axiom.

The Power set Axiom.

There exists a set $Y^X$ such that all the functions $f$ that map from $X$ to $Y$ are contained within it.

Similarly, intersections can be described as,

Cartesian Products