Home > Mathematical Logic, Model Theory, Set Theory > What the axioms do for us

What the axioms do for us

The purpose of this post is to give a brief account of the axioms of ZFC in the light of the cumulative hierarchy of sets and present what I think are two different, although both of them legitimate, senses in which they can be understood. I will follow mostly Frank R. Drake, Set Theory: an introduction to large cardinals, for the rather sketchy account of the first one of these views. Other similar presentations can be found, for example, in Shoenfield, Mathematical Logic or in Barwise (ed.) Handbook of Mathematical Logic.

The philosophical viewpoint taken here is, as Drake himself expresses in his preface, an uncompromising realism or platonism, under which in some sense sets do exist as objects to be studied and set theory is then just as much about fixed objects as is number theory. We will see, however, that there is more to be said about this point later. Let us first take a look at the axioms and how they are motivated by the cumulative hierarchy picture. I have freely used standard abbreviations in stating the axioms. Other versions and combinations of axioms, equivalent to these, are available in the literature. The following comments apply or can easily be adapted to any of them. Although some objections have been raised to this particular way of justifying the axioms, I will not address them here. A lot more on theses issues can be found elsewhere, for a start, in P. Maddy, Believing the Axioms, in C. Parsons, What is the iterative conception of set?, or in G. Boolos, Logic, logic, logic.

The Orthodox View

There are two axioms that demand that sets have certain properties: Extensionality and Foundation.

Extensionality
\forall z(z \in x \leftrightarrow z \in y) \to x=y.
Extensionality asserts that two different sets cannot have the same members in our universe. It entails that the cumulated sets obtained by succesive use of the powerset operation, although generated again and again, are always the same for us. It also entails that there is only one set without members, so that urelements are also excluded from our theory.

Foundation
\exists y (y \in x) \to \exists y (y \in x \land \forall z \lnot(z \in x \land z \in y)).
Foundation asserts that every non-empty set x has a member y with no members in common with x in our universe. It entails that no infinite descending chains, x \ni y \ni ..., or cycles, x \in ... \in x, are allowed.
To see why it is true in the cumulative hierarchy picture note that since sets are generated for the very first time at some level (for some ordinal) by collecting only other sets (if any) generated at previous levels, those members of x generated for the first time at the lowest level among those levels at which the members of x are generated for the first time cannot have any member in common with x. It is also seen that if there is any set with a given property, there is a first (lowest) level at which that property comes first.

The rest of the axioms can be read as saying that enough sets exist in some direction.

Existence
\exists x (x=x).
This axiom asserts the existence of some set in our universe.
It is usually regarded as a logical axiom, since normally only non-empty domains of discourse are cosidered worth studying.

Subsets
For every formula \phi with free variable x for which the variable y does not ocurr, the following is an axiom:
\exists y \forall x (x \in y \leftrightarrow x\in a \land \phi(x)).
Also called (Restricted) Comprehension, Separation and Specification, Subsets is an axiom schema that asserts that, in our universe, for every set a there is a (sub)set y whose members are the members of a satisfying the property \phi. The existence of subsets proved by this schema is hence limited to the expressiveness of the language.
To see it is true for the cumulative hierarchy, note that at any level where a is formed, so are any of its subsets.

Pair
\exists y \forall x (x \in y \leftrightarrow x = a \lor x = b).
Pair asserts the existence in our universe for any two sets a and b of a set y whose only members are a and b.
This is true in the cumulative hierarchy because at any level after both a and b have been formed, their unordered pair can be formed. It also entails that there is no highest level.

Power set
\exists y \forall x (x \in y \leftrightarrow \forall z (z \in x \to z \in a)).
Power set asserts the existence in our universe for any set a, of another set whose members are all of the subsets of a.
We earlier said that the subsets of a set are formed by the same level as it is formed, so at the immediately following level we can form its power set. We only need there is no last level.

Union
\exists y \forall x (x \in y \leftrightarrow \exists z (x \in z \land z \in a)).
Union asserts that in our universe for any given set a there is a set whose members are all the members of the members of a.
Since members of members of a must ocurr at levels before a their union will ocurr at the same level as a, and possibly at the level before.

Infinity
\exists w (\emptyset \in w \land \forall x (x \in w \to \exists z (z \in w \to \forall u (u \in z \leftrightarrow u \in x \lor u = x)))).
Infinity asserts the existence in our universe of a set whose members are \emptyset and its successors.
It can be seen as saying that we can imagine a simple infinite sequence of levels having been completed.

Replacement
For every formula \psi (x,y) with x and y free, without any occurrence of b, the following is an axiom:
\forall x,y,z (\psi (x,y) \land \psi (x,z) \to y = z) \to \exists b \forall y (y \in b \leftrightarrow \exists x (x \in a \land \psi (x,y))).
Replacement says that if a formula \psi defines a class function, then the image of its restriction to any set is also a set.
This is, in terms of the cumulative hierarchy, a statement about the levels having no end (as far as the expressiveness of our language allows us to go).

Choice
\forall x (x \in z \to x \neq \emptyset \land \forall y (y \in z \to x \cap y = \emptyset \lor x = y)) \to \exists u \forall x \exists v (x \in z \to u \cap x = \{v\}).
Choice says that if the members of a set z are all non-empty and pairwise disjoint, then there is a choice set that has exactly one member in common with each member of z.
This is a further attempt to say that all subsets are to be added at each level, a try to somehow overcome the limitations of Subsets.

A feature implicit all across this view is that quantifiers range over the whole universe of sets. Thus, what the axioms assert is true about the universe of the so called real sets. This universe contains every ordinal and in it we can find uncountable sets that are really uncountable, and power sets that really contain every subset of a given set. This situation has always made me feel uncomfortable for several reasons. One of them is that the notion of truth for first order languages is that of truth on a model, where a model is a given set. We expect our quantifiers to run over a fixed collection of sets, one that we can look at as a completed totality, and not an ever increasing one like the real V. So let me now examine an alternative viewpoint.

An Alternative View

Instead of thinking of our quantifiers as ranging all over the real sets, let us suppose that they range only over a part of them (the members of a given set) satisfying certain closure conditions: certain axioms must be verified on it (this is to ensure that this piece of universe we are analyzing is broad enough to satisfy our mathematical needs for the purpose at hand). This standpoint’s sensibility is guaranteed by first-order logic completeness and the assumption that the theory is consistent.

By adding new axioms to our theory of sets we may either wish to make the theory about that part of reality we want to study more accurate (projective determinacy), or we may wish to extend the range of quantification to be able to explore a broader part of that reality by significantly changing the closure conditions (large cardinals).

Looking at things this way, however, has an unpleasant drawback. By examining things a bit more closely one can see that the axioms and theorems of our theory just say nothing about the real thing.

For a trivial example, we suppose that the piece of universe our quantification ranges over is a set, so our proof of the non-existence of a universal set actually does not tell that such a set does not exist in reality, it is only telling that we have not included it under the range of our quantifiers. There’s nothing wrong in our model of set theory being a set, we simply cannot include this set under the range of quantification of our theory on pain of inconsistency (Russell’s paradox).

But this story can easily be generalized. The proof that |a| < |\mathcal{P}(a)| is based on the existence of a subset we can easily obtain for each function f from a into \mathcal{P}(a), namely \{x \in a | x \notin f(x) \}. This subset, a member of \mathcal{P}(a), cannot be the image by f of any x \in a. Hence, no function from |a| into \mathcal{P}(a) can be onto on pain of inconsistency. It turns out that if the theory is consistent it has a countable model. So, we cannot tell if really |a| < |\mathcal{P}(a)| or instead we simply have left all functions from |a| onto |\mathcal{P}(a)| out of the range of our quantifiers so that it cannot be seen that actually |a| = |\mathcal{P}(a)| (Skolem’s paradox).

Something similar happens with non-well-founded models (non-standard models): we cannot tell if sets really are well founded or if the choice we have made of the sets for the model hides the fact that the membership relation is not really well-founded.

Reality could then be as the axioms say it is, or entirely different! So we face the chance that nothing can be known about the real sets, after all; or we can accept as real all possibilities. The real sets would then look more like an inexhaustible bag of dots we can pick and organize at will.

The cumulative hierarchy, however, is still very appealing, so one would like to reconcile both views by expecting every such possibility to be realizable in V when it really is what we say it is. This hope is expressed by Dana Scott in his preface to Bell’s Boolean-valued Models and Independece Proofs.

A point of view that this is too much to expect is the Multiverse View. See, for example, Hamkins’ slides or his answer to my question in MO. From this point of view, different realities correspond to different concepts of set, and this may likely include concepts of set we have not yet imagined (maybe ‘conceived’ would be more in place here), so there would seem to be little reason that any two concepts of set can be compared together in a unique set theoretic context.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: