We want to formalise the relationship between the preterite and the set. An obvious way of doing this is to add an axiom for each preterite in our structure that:
\(\forall x \exists s[P(x)\leftrightarrow (x\in s)]\)
This is known as "unrestricted comprehension" and there are problems with this approach.
Consider a predicate for all terms which are not members of themselves. That is:
\(\neg (x\in x)\)
This implies the following is true:
\(\forall x\exists s[\neg (x\in x) \leftrightarrow (x\in s)]\)
As this is true for all \(x\), it is true for \(x=s\). So:
\(\exists s[\neg (s\in s) \leftrightarrow (s \in s)]\)
This statement is false. As we have inferred a false formula, the axiom of unrestricted comprehension does not work. This result is known as Russel’s Paradox.
This is an axiom schema rather than an axiom. That is, there is a new axiom for each preterite.
To resolve Russel’s paradox, we amend the axiom schema to:
\(\forall x \forall a \exists s[(P(x)\land x\in a )\leftrightarrow (x\in s)]\)
That is, for every set \(a\), we can define a subset \(s\) for each predicate.
This resolves Russel’s Paradox. Let’s take the same steps on the above formula as in unrestricted comprehension;
\(\forall x \forall a \exists s[(\neg (x\in x)\land x\in a )\leftrightarrow (x\in s)]\)
\(\exists s[(\neg (s\in s)\land s\in s )\leftrightarrow (s\in s)]\)
So long as the subsets \(s\) are not members of themselves, this holds.
Finite subsets. Don’t know about infinite subsets
If we can define a subset, by the axiom of specification it exists.
For example if set \(\{a,b,c\}\) exists, we can define a preterite to select any subset of this.
For example we can use define a \(P(x)\) as \(x=a\lor x=b\) to extract the subset \(\{a,b\}\).
If a subset is infinitely large,
Can prove exists from this axiom
\(\forall x \forall a \exists s[(P(x)\land x\in a )\leftrightarrow (x\in s)]\)
We can use short-hand to describe sets.
\(\{x\in S: P(x)\}\)
This defines a set by a restriction. For example we will later be able to define natural numbers above \(5\) as:
\(\{x\in \mathbb{N} : x>5\}\)
Emuneration can be done through set builder notation too
Can define sets formally! defintion doesn’t just affect sets
\(\forall x (x\in C \leftrightarrow P(x))\)
NB: We’re not saying C exists
Can then use examples of equiv class
\(\forall x (x\in C \leftrightarrow x=x)\)
We can use this to define the empty set - the set with no members.
\(\varnothing =\{\}\)
Using the above definition this is the same as writing:
\(\forall x \neg (x\in \varnothing )\)
We can describe a set by the elements it contains.
\(s=\{a,b,c\}\)
This is a shorthand way of writing:
\(\forall x (x\in s \leftrightarrow (x=a\lor x=b \lor x=c))\)
A set is finite is there is a proper subset without a bijection.
Proper subset: \(A\subset B\)
For example for set \(\{a,b,c\}\) There is no subset with a bijection.
For the natural numbers, all natural numbers except 0 is a proper subset, and there is a bijection.
The cardinality of a set \(s\) is shown as \(|s|\). It is the number of elements in the set. We define it formally below.
Consider \(2\) sets. If there is an injective from \(a\) to \(b\) then for every element in \(a\) there is a unique element in \(b\).
If this injective exists then we say \(|a|\le |b|\).
Similarly, if there is a surjective, that is for every element in \(b\) there is a unique element in \(a\), then \(|a|\ge |b|\).
Therefore, if there is a bijection, \(|a|=|b|\), and if there is only an injective or a surjective then \(|a|<|b|\) or \(|a|>|b|\) respectively.
Every set has a cardinality. As a result cardinality cannot be a well-defined function, for the same reason there is no set of all sets.
Cardinality functions can be defined on subsets.
Say we have a preterite \(P(x)\) which is true for some values of \(x\). Sets allow us to explore the properties of these values.
We may want to talk about a collection of terms for which \(P(x)\) is true, which we call a set.
To do this we need to introduce new axioms, however first we can add (conservative) definitions to help us do this.
We introduce a new relation: membership. If element \(x\) is in set \(s\) then the following relation is true, otherwise it is false:
\(x\in s\)
Sets are also terms. In first-order logic they will be included in quantifiers. Indeed, in set theory, we aim to treat everything as sets.
If a term is not a member of another term, we can write this using the non-member relation as follows:
\(\forall x \forall s [\neg (x\in s)\leftrightarrow x\not\in s]\)