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.
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}))\)
This set contains the null set: \(\varnothing \in \mathbb{N}\).
Zero is defined as the empty set.
\(0:=\{\}\)
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\}=\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\)
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
We don’t know I is limited to natural numbers. Could contain urelements etc.
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)]\)
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\)
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\)
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:
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)]\)
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)]\)
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.
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.
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.
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.
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]\)
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]\)
The cartesian product takes two sets, and creates a set containing all ordered pairs of \(a\) and \(b\).
\(a\times b\)
We can define this as a set of ordered pairs.
\(\{\{a\},\{a,b\}\}\)
All values on which the function can be called
\(\forall x(f(x)=y)\rightarrow P(y))\)
\(\forall x((\exists y f(x)=y)\rightarrow P(y))\)
Outputs of a function.
AKA: Range
The image of \(x\) is \(f(x)\).
The preimage of \(y\) is all \(x\) where \(f(x)=y\).
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.
\(f(n)=s(n)\)
Domain is: \(\mathbb{N}\)
Codomain is also: \(\mathbb{N}\)
Image is \(\mathbb{N}\land n\ne 0\)
If function \(f\) maps from set \(X\) to set \(Y\) we can write this as:
\(f:X\rightarrow Y\)
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.