Foundations of Set Theory

Sets

Definition

A set is a well-defined collection of distinct objects, called elements or members, considered as a single entity.

Notation

Sets are usually denoted with capital letters or are written out as their elements in curly braces.

Containment to sets

Notation

If an element $x$ is contained in a set $A$ it is denoted using the greek letter epsilon in the following way:

$$ x \in A $$

Equality of sets

Axiom of extension

Two sets are equal if and only if they have the same elements.

Notation

For two sets $A$ and $B$ if they are equal we write:

$$ A = B $$

or if they are not equal

$$ A \neq B $$

Remark

Equality of two sets is symmetric as:

$$ A = B \quad \text{is the same as} \quad B=A$$

Inclusion in sets

Definition

A set $A$ can be included in a distinct set $B$ if and only if the all the elements of the set $A$ are also included in $B$.

Notation

• We denote inclusion of $A$ in $B$ by writing:

  $$ A \subset B $$

  similarly

  $$ B \supset A $$

• Furthermore if $A$ and $B$ are subsets but may equal we can write:

  $$ A \subseteq B $$

  similarly

  $$ B \supseteq A $$

Remark

Both $A$ is included in $B$ and $A$ is a subset of $B$ are equal and mean the same thing.

Properties

• Reflexive

  A sole set $A$ by definition is reflexive, it is included in itself.

• Proper

  Both $A$ and $B$ are proper sets if and only if:

  $$ A \subset B $$

  and

  $$ A \neq B $$

• Transitive

  The sets $A$, $B$ and $C$ are transitive if and only if:

  $$ A \subset B \quad \text{and} \quad B \subset C$$ $$ \iff A \subset C $$

• Antisymmetric

  If $A$ and $B$ are sets such that:

  $$ A \subset B \quad \text{and} \quad A \supset B $$ $$ \iff A = B $$

  By extension they must also have the same elements.

Axiom of pairing

For any two sets there exists a set that they both included in.

Logical operators, Logical connectives

Some logical operators are:

Remark

The Negation or not operator can also be written as:

$$ \text{not}(S(x)) $$

Sentences

Definition

A sentence is a logical statement with no free variables, meaning its truth value can be determined as either true or false. Sentences are built from set-theoretic expressions using logical connectives and quantifiers.

Axiom of specification

To every set $A$ and to every condition $S(x)$ there corresponds a set $B$ whose elements are exactly those elements $x$ of $A$ for which $S(x)$ holds.

$$ B = \{ x \in A : S(x) \} $$

Universe

A universe is the set defined as having included within it every possible element there exists.

The empty set

Definition

The empty set is defined as the set which contains no elements of any kind.

Notation

The empty set is commonly denoted in the following ways:

$$ \emptyset \quad \text{or} \quad \varnothing \quad \text{or} \quad \left \{ \right \} $$

Property

The empty set by definition is included in every set.

Pairs, Singeltons etc.

Unions

Axiom of unions

For every collection of sets $C$ there exists a set $U$ that contains all the elements $x$ that belong to at least one set of the given collection.

$$ U = \{ x : x \in X, \, \forall X \in C \} $$

Notation

A union of two sets $A$ and $B$ can be denoted as follows:

$$ A \cup B $$

Definition

The union over a collection of sets indexed by \( n \) is the set of all elements that belong to at least one of the sets in the collection. Formally, if \( \{A_n\}_{n \in \mathbb{N}} \) is a sequence of sets, then the union over \( n \in \mathbb{N} \) is written as:

$$ \bigcup_{n \in \mathbb{N}} A_n = \{ x : \exists n \in \mathbb{N},\ x \in A_n \} $$

Unions of pairs

Properties

Unions of pairs have the following properties:

1. Identity

   $ A \cup \varnothing = A $

2. Commutativity

   $ A \cup B = B \cup A $

3. Associativity

   $A \cup \left( B \cup C \right) = \left( A \cup B \right) \cup C $

4. Idempotence

   $ A \cup A = A $

5. Subset Characterization

   $ A \subset B \iff A \cup B = B $

Proofs

1. Identity: \( A \cup \varnothing = A \)

   Let \( x \in A \cup \varnothing \). Then \( x \in A \) or \( x \in \varnothing \). But \( \varnothing \) has no elements, so \( x \in A \). Thus, \( A \cup \varnothing \subseteq A \). Conversely, any \( x \in A \) is also in \( A \cup \varnothing \). Hence:

   $$ A \cup \varnothing = A $$

2. Commutativity: \( A \cup B = B \cup A \)

   Let \( x \in A \cup B \). Then \( x \in A \) or \( x \in B \), so \( x \in B \cup A \). Similarly, any \( x \in B \cup A \) implies \( x \in A \cup B \). Therefore:

   $$ A \cup B = B \cup A $$

3. Associativity: \( A \cup (B \cup C) = (A \cup B) \cup C \)

   Let \( x \in A \cup (B \cup C) \). Then \( x \in A \), or \( x \in B \cup C \), meaning \( x \in B \) or \( x \in C \). In all cases, \( x \in (A \cup B) \cup C \). The reverse direction follows similarly.

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

4. Idemportence: \( A \cup A = A \)

   Let \( x \in A \cup A \). Then clearly \( x \in A \), so:

   $$ A \cup A = A $$

5. Subset Characterization: \( A \subseteq B \iff A \cup B = B \)

   • If \( A \subseteq B \), then every element of \( A \) is already in \( B \), so \( A \cup B = B \).

   • If \( A \cup B = B \), then any \( x \in A \) must be in \( B \), so \( A \subseteq B \).

   $$ A \subseteq B \iff A \cup B = B $$

$\square$