Set Theory

Sets

A set $S$ is an unordered collection of distinct elements (also called members).
- $x$ is an element of set $S$ is denoted as $x \in S$ .
- $x$ is not an element of set $S$ is denoted as $x \notin S$ .
Two sets are equal if they have precisely the same elements. This is also called the axiom of extensionality. It can be written as:
The universal set $U$ is the set containing all elements for a specific context. This context is called the domain of discourse.
A singleton is a set with exactly one element.

Set Notation

Roster notation is a method of defining a set by listing its elements between braces, separated by commas.
- Examples: ${2, 3, 5}$ denotes the set containing the first 3 prime numbers, ${}$ denotes the empty set, and ${42}$ denotes a singleton containing only the element $42$ .
- When specifying a set, all that matters is whether each potential element is in the set or not. Consequently, a set does not change if elements are repeated or arranged in a different order.
  - Example: ${1, 2, 3, 4} = {4, 2, 1, 3} = {4, 2, 4, 3, 1, 3}$
Set builder notation is a method to define a set by describing the properties that members must satisfy, rather than listing the elements.
- Notation: ${x ∣ P (x)}$
- The set of all elements $x$ for which the predicate $P (x)$ is true.
- Example: ${x \in N ∣ \exists k \in N (x = 2 k)}$ defines the set of even natural numbers.

Subsets and Supersets

A set $A$ is a subset of set $B$ (denoted $A \subseteq B$ ) if every element in $A$ is also an element of $B$ . The set $A$ is a proper subset of $B$ (denoted $A \subset B$ ) if $A$ is a subset of $B$ but $A \neq B$ .
A set $B$ is a superset of set $A$ (denoted $B \supseteq A$ ) if $A$ is a subset of set $B$ . The set $B$ is a proper superset of $A$ (denoted $B \supset A$ ) if $A$ is a proper subset of $B$ .
The power set of $A$ is the set of all possible subsets of $A$ :

Definition	Formula	Diagram
The union of sets $A$ and $B$ is the set of all elements that are in $A$ , in $B$ , or in both.	$A \cup B = {x ∣ x \in A or x \in B}$
The intersection of sets $A$ and $B$ is the set of all elements that are in both $A$ and $B$ .	$A \cap B = {x ∣ x \in A and x \in B}$
The difference of sets $A$ and $B$ is the set of elements that are in $A$ but not in $B$ .	$A ∖ B = {x ∣ x \in A and x \notin B}$
The symmetric difference of sets $A$ and $B$ is the set of elements in either $A$ or $B$ , but not in their intersection.	$A Δ B = (A \cup B) ∖ (A \cap B)$
The complement of set $A$ is the set of all elements in the universal set $U$ that are not in $A$ .	$A^{c} = {x ∣ x \in U and x \notin A}$

Some properties of the the basic set operations are as follows:

Commutative Laws: The order doesn't matter for union or intersection.
- $A \cup B = B \cup A$
- $A \cap B = B \cap A$
Associative Laws: The grouping doesn't matter for union or intersection.
- $(A \cup B) \cup C = A \cup (B \cup C)$
- $(A \cap B) \cap C = A \cap (B \cap C)$
Distributive Laws: Union and intersection can be "distributed" over each other.
- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
- $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
De Morgan's Laws: These describe how to find the complement of a union or intersection.
- $(A \cup B)^{c} = A^{c} \cap B^{c}$
- $(A \cap B)^{c} = A^{c} \cup B^{c}$

Ordered collections

A tuple is an ordered collection of elements.
- Unlike sets: may contain duplicates, and order matters.
- An ordered pair is a tuple of 2 elements.
- An n-tuple is a tuple of $n$ elements.
Cartesian product ( $A \times B$ ) is the set of all possible ordered pairs where the first element is from $A$ and the second is from $B$ .
A relation on sets $A$ and $B$ is a subset of the Cartesian product $A \times B$ .
A binary relation on $A$ is a subset of $A \times A$ .
- Notation: We often write $a R b$ to mean $(a, b) \in R$ (e.g., $x \leq y$ ).
Properties of binary relations:
- Reflexive: $\forall a \in A, (a, a) \in R$
- Symmetric: $\forall a, b \in A, a R b \to b R a$
- Antisymmetric: $\forall a, b \in A, (a R b \land b R a) \to a = b$
- Transitive: $\forall a, b, c \in A, (a R b \land b R c) \to a R c$
If a relation is reflexive, symmetric, and transitive, it is an equivalence relation.
If a relation is reflexive, anti-symmetric, and transitive, it is a partial order.

Functions

A function $f$ from set $A$ to set $B$ (denoted $f : A \to B$ ) is a relation where every input has exactly one output.
- Domain: The set $A$ of all possible inputs.
- Codomain: The set $B$ of all allowed outputs.
- Range (or Image): The set ${f (a) ∣ a \in A}$ of all actual possible outputs.
For a relation to be a function, it must be total and well-defined.
- Total: Every input has at least one output.
  - For every $a \in A$ , there is some $b \in B$ such that $(a, b) \in f$ .
- Well-defined: Every input has at most one output.
  - If $(a, b) \in f$ and $(a, c) \in f$ , then $b = c$ .
A function may be classified based on its outputs.
- Injective (One-to-One): Every output corresponds to at most one input.
  - $\forall x, y \in A, f (x) = f (y) ⟹ x = y$
- Surjective (Onto): Every output corresponds to at least one input.
  - $\forall b \in B, \exists a \in A such that f (a) = b$
- Bijective (One-to-One Correspondence): Both Injective and Surjective.
  - An inverse function $f^{- 1}$ exists if and only if $f$ is bijective.

Hyperoperation Sequence

The hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations in this context), where each operation at Rank $n$ is defined as the repetition of the operation at rank $n - 1$ .

Hyperoperation	Inverse
Rank 0: succession is the foundational unary operation upon which all others are built. It simply advances a value to the next. $H_{0} (a, b) = a + 1$	The inverse of succession is predecession. $a + 1 = x ⟺ x - 1 = a$
Rank 1: addition is defined as repeated succession. To add $a$ to $b$ you increment $a$ , $b$ times. $H_{1} (a, b) = a + b = a \underset{b times}{\underset{⏟}{+ 1 + \dots + 1}}$	The inverse of addition is subtraction. $a + b = x ⟺ x - a = b and x - b = a$
Rank 2: multiplication is defined as repeated addition. To multiply $a$ by $b$ you need to add $a$ to itself $b$ times. $H_{2} (a, b) = a \times b = \underset{b times}{\underset{⏟}{a + a + \dots + a}}$	The inverse of multiplication is division. $a \times b = x ⟺ \frac{x}{a} = b and \frac{x}{b} = a$
Rank 3: exponentiation is defined as repeated multiplication. To raise $a$ to the power of $b$ you need to multiply $a$ by itself $b$ times. $H_{3} (a, b) = a^{b} = \underset{b times}{\underset{⏟}{a \times a \times \dots \times a}}$	The inverses of exponentiation are roots and logarithms. Because exponentiation is non-commutative, two distinct operations are required to reverse it. $a^{b} = x ⟺ \sqrt[b]{x} = a and \log_{a} (x) = b$
Rank 4: tetration is defined as repeated exponentiation. To tetrate $a$ to the height of $b$ you need to raise $a$ to its own power $b$ times. $H_{4} (a, b) =^{b} a = \underset{b times}{\underset{⏟}{a^{a^{\cdot^{\cdot^{a}}}}}}$	The inverses of tetration are super-roots and super-logarithms. Like exponentiation, tetration is non-commutative and requires two distinct operations to reverse. $^{b} a = x ⟺ {ssrt}_{b} (x) = a and {slog}_{a} (x) = b$

This pattern may be repeated indefinitely.

Number Sets

Natural numbers ( $N$ ) is the set of counting numbers.
- $N = {0, 1, 2, 3, \dots}$
Integers ( $Z$ ) is the set of all whole numbers.
- $Z = {\dots, - 2, - 1, 0, 1, 2, \dots}$
Rational numbers ( $Q$ ) is the set of numbers that can be expressed as a fraction $\frac{p}{q}$ where $p$ and $q$ are integers, and $q \neq 0$ .
- $Q = {\frac{p}{q} ∣ p, q \in Z \land q \neq 0}$
- Includes all numbers with finite and repeating decimals (e.g., $0.5$ , $0.333 \dots$ ).
Real numbers ( $R$ ) is the set of all numbers representing points on a continuous line (informally).
Complex numbers ( $C$ ) is the set of all complex numbers that can be formed by combining a real and an imaginary part.
- $C = {a + b i ∣ a, b \in R and i = \sqrt{- 1}}$

TODO: explain the relation with closure, and the stability of the complex number set.

Cardinality

The cardinality of a set $S$ is the number of elements in the set. Denoted $| S |$ .
TODO: write about countable vs uncountable infinities.