Axiom schema of specification

Defining sets

Axiom schema of specification

The axiom schema of unrestricted comprehension

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.

Axiom schema of specification

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.

Implications of axiom schema of specification

All finite subsets exist

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,

Intersections of finite sets exist

Can prove exists from this axiom

If any set exists, the empty set exists

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

Set-builder notation

Notation

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\}\)

Class builder notation

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)\)

Empty set

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 )\)

Defining sets by enumeration

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))\)

Finite and infinite sets

Finite sets

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.

Infinite sets

For the natural numbers, all natural numbers except 0 is a proper subset, and there is a bijection.

Cardinality

Cardinality of finite sets

The cardinality of a set \(s\) is shown as \(|s|\). It is the number of elements in the set. We define it formally below.

Injectives, surjectives and bijectives

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.

Cardinality as a function

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.

Introduction to sets

Membership relation

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]\)