Zermelo–Fraenkel set theory

Natural numbers

Axiom of infinity

The axiom of infinity states that:

\(\exists I (\varnothing \in I \land \forall x \in I((x\lor \{x\})\in I))\)

There exists a set, called the infinite set. This contains the empty set, and for all elements in \(I\) the set also contains the successor to it.

Sequential function

Let’s define the sequential function:

\(s(n):=\{n\lor \{n\}\}\)

We can now rewrite the axiom of infinity as:

\(\exists \mathbb{N} (\varnothing \in \mathbb{N} \land \forall x \in \mathbb{N}(s(x)\in \mathbb{N}))\)

Zero

This set contains the null set: \(\varnothing \in \mathbb{N} \).

Zero is defined as the empty set.

\(0:=\{\}\)

Natural numbers

For all elements in the infinite set, there also exists another element in the infinite set: \(\forall x \in \mathbb{N}((x\lor \{x\})\in \mathbb{N}) \).

We then define all sequential numbers as the set of all preceding numbers. So:

\(1:=\{0\}=\{\{\}\}\)

\(2:=\{0,1\}=\{\{\},\{\{\}\}\}\)

\(3:=\{0,1,2\}=\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\)

Existence of natural numbers

Does each natural number exist? We know the infinite set exists, and we also know the axiom schema of specification:

Point is: For each set, all finite subsets exist. PROVE ELSEWHERE

From infinite set to natural set

We don’t know I is limited to natural numbers. Could contain urelements etc.

More

Infinite set axiom written using N. should be I

I could be superset of N, for example set of all natural numbers, and also the set containing the set containing 2.

Can extract N using axiom of specification

We need a way to define the set of natural numbers:

\(\forall n (n\in \mathbb{N}\leftrightarrow ([n=\emptyset \lor \exists k (n=k\lor \{k\})]\land ))\)

If we can can define N, we can show it exists from specicication

\(\forall x \exists s [P(x)\leftrightarrow (x\in s)]\)

\(\forall n \exists s [n\in N \leftrightarrow (n\in s)]\)

Cardinality of the natural numbers

Consider the infinite set, that is the set of all natural numbers which is defined in ZFC. Clearly there isn’t a natural number cardinality of this – we instead write \(\aleph_0\).

We call sets with this cardinality, countably infinite.

So:

\(|\mathbb{N} |=\aleph_0\)

Cardinality of natural numbers

We define:

\(|\emptyset |=0\)

That, the empty set has a cardinality of \(0\).

As we define \(0\) as the empty set, \(|0|=0\).

What is \(1\)? using the definition above we know \(|1|>|0|\), so let’s say \(|1|=1\), and more generally:

\(\forall n \in \mathbb{N} |n|=n\)

Ordering

Ordering of the natural numbers

For natural numbers we can say that number \(n\) preceeds number \(s(n)\). That is:

\(n\le s(n)\)

Similarly:

\(s(n)\le s(s(n))\)

From the transitive property we know that:

\(n\le s(s(n))\)

We can continue this to get:

\(n\le s(s(...s(n)..))\)

What can we say about an arbitary comparison?

\(a\le b\)

We know that either:

  • \(a=b\)

  • \(b=s(s(...s(a)...))\)

  • \(a=s(s(...s(b)...))\)

In the first case the relation holds.

In the second case the relation holds.

In the third case the relation does not hold, but antisymmetry holds.

As this is is then defined on any pair, the order on natural numbers is total.

As there is a minimum, \(0\), the relation is also well-ordered.

However if this does not hold then the following instead holds:

Subsets and powersets

Subset relation

Subset

If all terms which are members of term \(x\) are also members of term \(y\), then \(x\) is a subset of \(y\).

\(\forall x\forall y[(\forall z(z\in x\rightarrow z\in y))\leftrightarrow (x\subseteq y)]\)

Proper subset

If two sets are equal, then each is a subset of the other. A proper subset is one which is a subset, and not equal to the other set.

\(\forall x\forall y[((\forall z(z\in x\rightarrow z\in y)))\land(x\ne y)\leftrightarrow (x\subset y)]\)

Powerset function

The power set of \(s\), \(P(s)\), contains all subsets of \(s\).

\(\forall x x\subseteq s \leftrightarrow x\in P(x)\)

Do all subsets exist?? show elsewhere.

Cantors theorem

The cardinality of the powerset is strictly greater than the cardinality of the underlying set.

That is, \(|P(s)|<|s|\).

This applies to finite sets and infinite sets. In particular, this means that the powerset of the natural numbers is bigger than the natural numbers.

Proof

If one set is at least as big as another, then then is a surjection from that set to the other.

That is, if we can prove that there is no surjection from a set to its powerset, then we have proved the theorem.

We consider \(f(s)\). If there is a surjection, then for every subset of \(s\) there should be a mapping from \(s\) to that subset.

We take set \(s\) and have the powerset of this, \(P(s)\).

Consider the set:

\(A=\{x\in s|x\not\in f(x)\}\)

That is, the set of all elements of \(s\) which do not map to the surjection.

Tuples

Tuples

We can get a list of sets in an order. A 2-tuple is an ordered pair:

\((a, b)\)

We can write an ordered pair of \(a\) and \(b\) as:

\(\{\{a\},\{a,b\}\}\)

Ordred pair definition, and tuple

\((a,b)=(c,d) \leftrightarrow (a=c\land b=d)\)

This is the characteristic property.

Axiom of pairing

For any pair of sets, \(x\) and \(y\) there is another set \(z\) which containing only \(x\) and \(y\).

\(\forall x \forall y \exists z \forall a[a\in z \leftrightarrow a=x \lor a=y]\)

For each set, there exists a set containing only that set

Take the axiom, but replace all instance of \(y\) with \(x\).

\(\forall x \exists z \forall a[a\in z \leftrightarrow a=x \lor a=x]\)

\(\forall x \exists z \forall a[a\in z \leftrightarrow a=x]\)

For any finite number of sets, there is a set containing only those sets

For any finite number of sets, there is a set containing the intersection of those sets

Cartesian product

The cartesian product takes two sets, and creates a set containing all ordered pairs of \(a\) and \(b\).

\(a\times b\)

Direct sums

Functions

Constructing functions

Use of ordered pairs

We can define this as a set of ordered pairs.

\(\{\{a\},\{a,b\}\}\)

Domains and ranges

Domain

All values on which the function can be called

\(\forall x(f(x)=y)\rightarrow P(y))\)

Image

\(\forall x((\exists y f(x)=y)\rightarrow P(y))\)

Outputs of a function.

AKA: Range

The image of \(x\) is \(f(x)\).

Preimage

The preimage of \(y\) is all \(x\) where \(f(x)=y\).

Codomain

Sometimes the image is a subset of another set. For example a function may map onto natural numbers above \(0\). Natural numbers above \(0\) would be the image, and the natural numbers would be the codomain.

Example

\(f(n)=s(n)\)

Domain is: \(\mathbb{N}\)

Codomain is also: \(\mathbb{N}\)

Image is \(\mathbb{N}\land n\ne 0\)

Describing functions

If function \(f\) maps from set \(X\) to set \(Y\) we can write this as:

\(f:X\rightarrow Y\)

Axiom of regularity

The axiom of regularity states that:

\(\forall x[x\ne \varnothing \rightarrow \exists y \in x (y\land x )=\varnothing]\)

That is, for all non-empty sets, there is an element of the set which is disjoint from the set itself.

This means that no set can be a member of itself.