Additional axioms

Foundation

The following was not part of Zermelo set theory but is often taken as an axiom.

I’m not sure I’ve ever seen anyone present an argument that this statement is true, as opposed to simply convenient.

Some programming languages provide a set data type, which generally means a finite set data type, natively while there are library implementations in some others. Most of those do not appear to satisfy the Axiom of Foundation, which makes it hard to argue that this axiom reflects people’s intuitive understanding of sets, even when restricted to finite sets. Even the arguments that Foundation is convenient are somewhat suspect since it is generally assumed by mathematicians but never really used by them.

It is at least safe to assume it, in the sense that if it is possible to prove a contradiction using this axiom then it is also possible to prove one without it.

Extensionality, again

There is another, stronger, form of the Axiom of Extensionality.

Formally, \[ [ ∀ A . [ ∀ B . [ [ ∀ x . [ [ [ x ∈ A ] ⊃ [ x ∈ B ] ] ∧ [ [ x ∈ B ] ⊃ [ x ∈ A ] ] ] ] ] ⊃ [ A = B ] ] ] . \]

The difference between this version and the previous version is that one began with the words “Suppose \({ A }\) and \({ B }\) are sets” and the formal version had some additional conditions expressing that assumption. So the strong version of the axiom implies that if \({ A }\) has no members then \({ A }\) is the empty set. This might seem innocuous but it means that for all \({ A }\), \({ A }\) is a set, which is an additional assumption we haven’t made previously. Assuming this axiom, whenever we see a statement of the form \({ x ∈ A }\) not only must \({ A }\) be a set but so must \({ x }\). I’ve been deliberately vague about what can be a member of a set but with this version of Extensionality the answer is that the only things which can be members of sets are sets.

Can we have a set of natural numbers? That is compatible with the strong version of Extensionality because we’ve implemented natural numbers as sets. We can also implement integers, rational numbers, real numbers and complex numbers as sets. The usual way to implement the integers, for example, is as equivalence classes of ordered pairs of natural numbers, where the equivalence relation is the set of pairs of pairs \({ ( ( v , w ) , ( x , y ) ) }\) for which \({ v + y = w + x }\).

In general this version of Extensionality is compatible with modern mathematics. Whether it’s a good idea or not is another question. It forces us to implement everything as a set. The fact that we can do this doesn’t necessarily mean we want to be forced to.

Assuming this version of Extensionality, if we start with a set then all of its members, if it has any, are sets. All of their members, if they have any, are sets. The same applies to their members. Starting from a set, choosing one of its members, then one of its members, etc. we get a sequence of sets which is either infinite or terminates with the empty set. If we assume the Axiom of Foundation and the Axiom of Replacement as well then it cannot give an infinite sequence and so must terminate with the empty set. So in some sense all sets are built from only the empty set.

Zermelo-Fraenkel

The most common choice of axioms for set theory is

The version without the Axiom of Choice is known as Zermelo-Fraenkel, or just ZF. The version with Choice is just called Zermelo-Fraenkel with the Axiom of Choice, or ZFC.

Most introductions to set theory start with examples from outside mathematics, e.g. the set of students in a particular class, the set of people in a building, etc. In view of the comments on the strong version of Extensionality none of these things are sets in Zermelo-Fraenkel, with or without the Axiom of Choice. In fact Zermelo-Fraenkel set theory has no possible application outside of mathematics.

A version of set theory sufficient for large parts of mathematics and nearly all of computer science, and less openly hostile to other applications would be

You don’t really need any form of Choice for computer science but Dependent Choice is useful. The axioms above, together with Dependent Choice, are also sufficient for nearly all of classical mathematics, i.e. calculus, number theory, etc.