# Models of the reals which have no unmeasurable sets

I recall being told -- at tea, once upon a time -- that there exist models of the real numbers which have no unmeasurable sets. This seems a bit bizarre; since any two models of the reals are isomorphic, you'd expect any two models to have the same collection of subsets. Can anyone tell me exactly what the story here is? Have I misremembered something? Is this some subtlety involving how strong a choice axiom you use to define your set theory?

-
Please clarify -- what is a "model of the reals"? Do you mean the fact that any two complete real-closed fields are isomorphic? – John Goodrick Oct 20 '09 at 20:46
oh, and you should tag your question set-theory as well. there's also results like Solovay's that use versions of the Axiom of Determinacy, which is inconsistent with full choice. – Kenny Easwaran Oct 21 '09 at 5:16

As John Goodrick is asking in a few places, you have to be careful in stating what you mean by "a model of the reals". If you're going to talk about sets of reals, then you need to have variables ranging over reals, and also variables ranging over sets of reals. You also of course want symbols in your language for the field operations and ordering, and possibly more.

Three Options

One way to do this is to use the language of second-order analysis, which is bi-interpretable with the language of third-order number theory. (It's straightforward to translate between real numbers and sets of natural numbers, and then between sets of real numbers and sets of sets of naturals.)

Another way to do this is to use ZF, which talks about the reals and sets of reals, but also many many other things. (Far more than any mathematician who's not a logician (or perhaps category theorist?) ever uses.)

There's also an intermediate strategy, which is basically what Russell and Whitehead did in Principia Mathematica, where you have some variables ranging over objects at the bottom (which might be real numbers, or anything else), and then variables ranging over sets of objects, and then variables ranging over sets of sets of objects, and so on to arbitrarily high levels. This is still far weaker than ZF, because you don't get sets that mix levels, and you also can't make sense of infinitely high levels.

First-order and Higher-order logic

If you take the first or third option, then you have two more choices, which correspond to what David Speyer was saying. You can require that variables that range over sets of things range over "honest subsets" of the collection of things they're supposed to be sets of.

Or you can interpret the set variables in a "whacked model". (The technical term is a "Henkin model".) On this interpretation, the "sets" are just further objects in your domain, and "membership" is just interpreted as some arbitrary relation between the objects of one type and the objects of the "set" type, and you interpret all your axioms in first-order logic.

The difference is that the honest interpretation uses second-order logic, while the Henkin interpretation just uses first-order logic. Second-order logic (and higher-order logic) is nice in that it lets you prove all sorts of uniqueness results - there is a unique model of honest second order Peano arithmetic, and if you require honest set-hood then this means there will be unique models at the third order level and higher, giving you one result that you remember. But first-order logic is nice because there's actually a proof system - that is, there is a set of rules for manipulating sentences such that any sentence true in every first-order model can actually be reached by doing these manipulations. That is, Gödel's Completeness Theorem applies. However, his Incompleteness Theorems also apply - thus, there are lots of models of first-order Peano arithmetic, and then there are even more Henkin models of "second-order" Peano arithmetic, and far far more Henkin models of "third-order" Peano arithmetic, which is the theory you're interested in.

Unfortunately, I don't know what these Henkin models look like. It all depends on what set existence axioms you use. There's a lot of discussion of this stuff for "second-order" Peano arithmetic in Steven Simpson's book Subsystems of Second-Order Arithmetic, which is the canonical text of the field known as reverse mathematics. However, none of that talks about arbitrary sets of reals, which is what you're interested in.

Solovay's results

The other result you mention, which is cited in one of the other answers here, takes the other option from above. That is, we do everything in ZF and see what different models of ZF are like. (Note that I don't say ZFC - of course if you have choice, then you have non-measurable sets of reals.)

Every model of ZF has a set it calls ω, which is the set it thinks of as "the natural numbers". Set theorists then talk about the powerset of this set as "the real numbers" - you might prefer to think of this set as "the Cantor set", and some other object in the model of ZF as its "real numbers", but there will be some nice translation between the Cantor set and your set, that gives the relevant topological and measure-theoretic properties.

Of course, since we're just talking about models of ZF, none of this is going to be the real real numbers. After all, since ZF is a first-order theory, the Löwenheim-Skolem theorem guarantees that it has a countable model. This model thinks that its "real numbers" are uncountable, but that's just because the model doesn't know what uncountable really means. (This is called Skolem's Paradox - http://en.wikipedia.org/wiki/Skolem%27s_paradox>wikipedia, http://plato.stanford.edu/entries/paradox-skolem/>Stanford Encyclopedia of Philosophy.)

What Solovay showed is that if you start with a countable model of ZFC that has an inaccessible cardinal (assuming that inaccessibles are consistent, then there is such a model, and we have almost as much reason to believe that inaccessibles are consistent as we do to believe that ZFC is consistent) then you can use Cohen's method of forcing to construct a different (countable) model of ZF where there are no unmeasurable sets of "reals".

Of course, the first result you stated (that any two models of the reals are isomorphic) holds within any model of set theory, assuming you're talking about "honest" second-order models (that is, models of reals that are "honest" with respect to the notion of "subset" that you get from the ambient model of ZF). But the notion of "honest" second-order model doesn't even translate when you move from one model of set theory to another. So Solovay's model of ZF has the property that every "honest" model of second-order analysis (or third-order number theory) has no non-measurable sets, while any model of ZFC has the property that every "honest" model of second-order analysis (or third-order number theory) does have non-measurable sets.

That's how your two results are consistent.

-
Thanks Kenny! I wish I had more than one vote to give you. – David Speyer Oct 21 '09 at 13:04
Thanks for spelling this all out! I was thinking of writing up an answer along these lines, but got lazy, and your explanation is clear and to the point. – John Goodrick Oct 21 '09 at 14:26
Yes, seriously, thanks very much! – userN Oct 22 '09 at 1:22

Be warned: this is pretty far from my expertise; I may be making stupid errors.

There is a subtlety which shows up in theorems like "All the models of the reals are isomorphic." In any axiomatization of the reals, you will have some sort of completeness axiom. For example:

Dedekind's axiom: If L and R are subsets of the reals, such that l <= r for any l in L and r in R, then there is some x such that l <= x <= r for any l in L and any r in R.

This axiom will always make reference to set theory; in more technical terms, it is not a first order axiom.

Now, there are two things that are both true.

(1) Define a "straight-forward model of the reals" to be a set R, with relations +, *, 0, 1, =, < obeying the axioms of the reals. Here the word "subset" in Dedekind's axiom is to be interpreted as an honest subset of R.

Any two straight-forward models of R are isomorphic. Whether or not they have non-measurable sets depends on which set theory you use in the preceding definition; if you use ZFC, then they have non-measurable sets.

(2) Define a "whacked model of the reals" to be a set R, with relations +, *, 0, 1, =, <, and a set S, with relations \subset and \in. These obey the axioms of "reals and sets of reals". So R is an honest ordered field with respect to (+, *, 0, 1, =, <); the Dedekind axiom holds if we interpret "set" as "element of S"; and (S, \subset, \in) has all the properties that the subsets of R should have according to ZF (no C). However, the elements of S do not have to be all the subsets of R; they just have to be all the subsets whose existence can be proven from ZF and the axioms of the reals.

Not all whacked models are isomorphic; and some of them don't have nonmeasurable sets.

-
I guess by "model of R" you must mean, "another model satisfying all the same second-order formulas as R"? – John Goodrick Oct 21 '09 at 0:00
I'm afraid I really don't understand what a "whack model of the reals" is supposed to be. You're saying that it satisfies all the second-order axioms of the genuine real-number field, and also has a bunch of things in S which behave like subsets of S, but S may not include all subsets of S? There is a sentence phi in the second-order language with S which is true in a model M if and only if M has a subset which is not encoded by any element of S. So this formula phi could be true in a "whack model"? I.e. not all "whack models" satsify all the same second-order sentences? – John Goodrick Oct 21 '09 at 0:36
^^ "... things in S which behave like subsets of M", sorry (wish I could edit my comment). – John Goodrick Oct 21 '09 at 0:38
The answer, in both cases, is that the axiom system in question is not first order. The completeness and well ordering axioms are about subsets of R and Z. If you interpret "subset" as meaning "subset", and hence make the axiom system second order, than there really is only one model of these theories up to isomorphism. – David Speyer Oct 21 '09 at 3:47
To clarify the distinction, go through the axioms that you want R to satisfying, and replace "is a subset of" with the phrase "est un sous-ensemble de". Now the point is that you can make the notions of "ensembles" and the relation of being a "sous-ensemble" part of your model, and it doesn't have to be related to actual sets and subsets. In particular, there are models satisfying these axioms where R has only countably many "sous-ensembles". I think the presentation on Wikipedia is nice: en.wikipedia.org/wiki/Second-order_logic#Why_second-order_logic_is_not_reducible‌​_to_first-order_logic – Tom Church Oct 21 '09 at 4:23
-
Thanks for the link to the paper I was thinking of; even better would be to (shortly) describe it. It is the proof by Solovay of the (relative) consistency of ZF + Dependent Choice + "every subset of the reals is Lebesgue measurable": Solovay, Robert M. (1970). "A model of set-theory in which every set of reals is Lebesgue measurable". Annals of Mathematics. Second Series 92: 1–56. – Benoit Jubin Oct 20 '09 at 21:58

It could certainly be true if you take your set theoretic axioms to be something other than ZFC. For instance I'm pretty sure that in ZF + AD (Axiom of Determinacy), every set of the real line is measurable.

EDIT: In fact, whether or not you like AD, it is the case that "every set is measurable" is consistent with ZF. Thus ZF (without Choice) certainly supports two models of R, one in which every set is measurable and another in which there exist non-measurable sets. I'm not actually sure how to interpret your comment "any two models of the reals are isomorphic".

-

I think if you assume the Axiom of Choice, then unmeasurable sets are inevitable. Was your tea-time companion perhaps entertaining you with glimpses of the worlds that are possible without AC?

-