Here we assign an ordinal to each set as its cardinality. We assign a natural number (finite ordinal) to each finite set designating the number of elements of the set, and an infinite ordinal to each infinite set designating the level of infinity of that set.

So |S| = w+1 means S has the power of the continuum (its cardinality is one level above W). This definition of cardinality appears to be what you get when you what combine GCH and Scott’s trick. Has anybody ever mentioned this trivial observation or am I the only one who likes it?

]]>Remember, a model of a first order theory *provides a set* for the quantifiers, \(\forall\) and \(\exists\), to quantify over*. So a model of ZFC means providing a universe of all sets (as well as a binary relation on it to model \(\in\)), and we check to see whether the axioms hold true when they are interpreted to quantify over that universe. (Note the potentially confusing terminology: a “group” is to “group theory” what a “ring” is to “ring theory” what a *“set-theoretical universe”* is to *“set theory”*.)

We’re gonna look at what happens if look at a really crappy attempt at a model for ZFC, namely the set of Von Neumann naturals \(\mathbb{N}\) with the usual elementhood relation \(\in\). (By “Von Neumann naturals” I mean that each natural number is coded as the set of smaller natural numbers: \(0=\{\}, \quad 1 = \{0\},\quad 2 = \{0,1\},\quad 3 = \{0,1,2\}, \quad\cdots\).) Clearly, this isn’t a model of ZFC; most obviously, it fails to satisfy the Axiom of Infinity and the Axiom of Pairing. But it *does* satisfy some of the axioms (like the Axiom of Extensionality, which just states that two sets are equal iff they have the same elements).

**In particular, surprisingly, \(\mathbb{N}\) does satisfy the Power Set Axiom.** This should sound weird: after all, don’t we have e.g. \(\mathcal{P}(2) = \{\{\},\{0\},\{1\},\{0,1\}\} \notin \mathbb{N}\)? To see why we have to break down what the Power Set Axiom actually says. The language of ZFC only has \(\in\) as a primitive symbol and we need to define what “subset” and “powerset” means from that. So the way we have to phrase “For every set X, the power set of X exists” is as “for every set X, there exists a set Y such that the elements of Y are the subsets of X”:

\[\forall X [\exists Y [ \forall y[y \in Y \longleftrightarrow y \subseteq X]]] \]

Except of course this doesn’t cut it either; we have to compile away the \(\subseteq\) too. \(A \subseteq B\) means that every element of \(A\) is an element of \(B\), so the actual power set axiom is:

\[\forall X [\exists Y [ \forall y[y \in Y \longleftrightarrow \forall a[a \in y \rightarrow a \in X]]]] \]

Now I claim that, when we take \(\in\) to be the usual but take the universe to be \(\mathbb{N}\) â€” i.e., we’re pronouncing \(\forall x\) as “for every Von Neumann natural \(x\)” â€” the sentence above is true. In particular, when \(X = 2 = \{0,1\}\), we can just set \(Y = 3 = \{\{\},\{0\},\{0,1\}\}\). You should ask: Aren’t we missing a subset, namely \(\{1\} \subseteq \{0,1\}\)? To which I answer: what’s “\(\{1\}\)”? That’s nowhere in the universe \(\mathbb{N}\); it isn’t a valid value for \(y\). Plug in our example values of \(X\) and \(Y\) we get:

\[\forall y \in \mathbb{N}[y \in \{0,1,2\} \longleftrightarrow y \subseteq \{0,1\}] \]

(Again, \(\subseteq\) is hiding another quantifier, but that doesn’t change anything so I’m abbreviating.) That’s a true statement; the only Von Neumann naturals \(y\) that satisfy \(y \subseteq \{0,1\}\) are \(0 = \{\}\), \(1 = \{0\}\), and \(2 = \{0,1\}\). We can’t even *say* \(\{1\} \subseteq \{0,1\}\) because \(\{1\}\) is nowhere in our model! In general, inside the attempted set-theoretic universe \(\mathbb{N}\), we have \(\mathcal{P}(\mathbb{n}) = n + 1\). For all \(n\) in the model, \(n+1\) contains every set *in the model* that is a subset of \(n\). Hence, the Power Set Axiom is satisfied.

___

Of course, again, \(\mathbb{N}\) isn’t a model of ZFC. E.g., the very fact that there is no set consisting solely of \(1\) violates the axiom of pairing. But for other beginners hopefully it can shed some light on what it means to talk about the view from “inside a universe”; it means that the quantifiers *only* scope over that universe, and *that’s* the standard against which we judge whether an axiom is satisfied.

A more relevant example of this idea was discussed by some commenters above: the statement “X and Y have the same cardinality” means that there exists (\(\exists\)) a bijection between X and Y. A “bijection”, like everything else, being a particular type of set. You can have a scenario where in one model, you have an \(X\), a \(Y\), and some bijection \(f : X \leftrightarrow Y\) between them â€” yet in a submodel, you have just \(X\) and \(Y\) but *not* \(f\). So: from the perspective of the supermodel, X and Y have the same cardinality, but from the perspective of the submodel, they don’t. Things that are countable in one model might be uncountable in a submodel of it! (Terminological note for fellow beginners: a submodel is not to be confused with a totally different thing called an “inner model”.) Here’s a picture of the situation from the article that I first read these examples in.

___

** Some words on the apparent circularity of saying that a model of ZFC means providing a “set” of all sets: You can’t, of course, construct a model of ZFC within ZFC; Godel’s completeness theorem, Godel’s incompleteness theorem, and the fact that ZFC is consistent conspire together to prevent that from happening. But there’s no problem if you jump up to stronger theories like ZFC+Inaccessible. In there, you can construct a “set” (in the sense of that stronger theory) that satisfies all the axioms of ZFC â€” just not one that satisfies ZFC+Inaccessible! Etc. So yeah: ZFC can’t prove or disprove the existence of models of ZFC, so whenever you hear people say they have such a model, they’re talking from the perspective of some stronger theory.*

I know a bit about topos theory, although not very much. These are categories that behave like the category of sets, so we should be able to use them to talk about models of, say, ZFC.

There is, for example, the effective topos by Martin Hyland, which basically captures computable sets:

https://en.wikipedia.org/wiki/Effective_topos

This lead me to guess that that might limit the cardinality of its reals to something something omega_CK. Well, of course, that’s just an ordinal, so maybe the corresponding cardinal should be aleph_omega_CK??

However, it seems that that’s not compatible with KÃ¶nig’s theorem. Or is it? However, aleph_omega_1 seems to be an interesting stop, too.

You see, I’m wildly confused about these things ðŸ˜€

Initially, I speculated about my guess here:

https://twitter.com/RAnachro/status/1335587810280136704

And later I carried my confusion over to Zulip. I’m sorry that there is no public web view, but you can get a login here:

https://johncarlosbaez.wordpress.com/2020/03/25/category-theory-community-server/

The thread I started can be found under #general-mathematics/forcing:cardinals-below-c

There, Matteo Capucci said that forcing can be made constructive, and suggested to read:

MacLane and Moerdijk’s book “Sheaves in Geometry and Logic”, and to look for an article by Dana Scott on boolean valued models for forcing.

This discussion is still on-going, and I might transport some more of it here later, if people show interest.

For the sake of completeness, here’s a discussion about KÃ¶nig’s theorem where some nice folks helped me to a better understanding of that bit:

https://twitter.com/RAnachro/status/1342950207315734535

P.S.: Nice post, Scott! Thanks!

]]>Now for a take that will be much more shocking: After much reflection, I now believe that CH and AC are Platonically true facts about (ZF-like) set theory despite being independent of ZF, in the same way that Con(PA) is a Platonically true fact about (PA-like) arithmetic despite being independent of PA.

To understand how I reached my opinion it is necessary to distinguish two different metamathematical philosophies, both of which I view as equally coherent but which are extremely different character.

In the first, which is modernism, one thinks of mathematical statements in some theory as being true or false according to whether they are true or false of some specific model of this theory. This seems odd and even vacuous due to the theorems of GÃ¶del and LÃ¶wenheim-Skolem (first-order theories can exert very little control over their models!). Fortunately, it is a property of first-order logic (or, at least, the first-order theories we care about most) that, assuming that a theory is consistent, not only does it have a model, it has a *smallest* model (which will necessarily be finite or countable). So we can use that property to select our distinguished model. Thusly all statements are true or false according to whether they describe the smallest model.

In the second, which is postmodernism, one never describes a statement as being Platonically true or false, but only being true *in some theory and some model* if there exists (an object in the model which the model accepts as) a proof of the statement in that theory.

Scott is an arithmetical Platonist, but a set-theoretical postmodernist. I like to keep my philosophy simple, so Iâ€™m an everything Platonist.

(The actual matter of showing that CH and AC hold in the standard model is relatively easy. For the standard model must satisfy \(V=L\); otherwise we could make a smaller model by passing to the inner model of constructible sets. Then we know, by the work of GÃ¶del, that \(V=L\) implies CH and AC, and weâ€™re done.)

And to counter the inevitable criticism that this has no consequences at all for computation: Follow the iterative procedure of GÃ¶delâ€™s Completeness Theorem to obtain the standard model of ZF, where each element is encoded (not necessarily uniquely) by a string (which in turn is secretly encoded by an integer), and where the primitive relationships of ZF are implemented as limit-computable functions (which are secretly formulas in PA). Then, to check CH, you can iterate over every possible (encoded) set, and check that it does not have intermediate cardinality between \(\Aleph_0\) and \(2^{\Aleph_0}\) (which itself is done by iterating over every possible function, and checking that it is or is not an injection or surjection with a certain domain and range); similar considerations apply for AC or any other axiom of interest. This is exactly like the process of checking the truth of an arithmetical statement with several quantifiers, and intentionally so.

]]>The short PRL paper (outline, technical proofs omitted) is here:

https://journals.aps.org/prl/issues/48/19

That page includes links to the errata (necessary)

and the Mermin/Macdonald/Pitowsky exchange.

The no-go theorems prove hidden variables do not exist are making elementary arithmetical calculations and drawing conclusions regarding *set-ups relying on standard Kolmogorov probability*. While it has been wonderful for people over the years to reduce the proofs to almost trivial arithmetic, you’ve let that fool you. In order to draw a conclusion about QM, the proofs are only relevant when talking about QM. Pitowsky sneaks past them by working with nonmeasurable sets, and inventing (using CH) a probability theory that does screwy things with them.

Also check out the recent Kellner paper https://link.springer.com/article/10.1007/s10701-016-0049-0

Kellner claims Pitowsky’s model is so deep doodoo hidden variable that it is actually a form of super-determinism.

Can you provide links to any of this Pitowsky / Mermin discussion? If I looked it up, would it directly address the fundamental confusion above?

]]>It’s been 25 years since I looked at Boos, and I forgot how incomprehensible it was. At the time of my posting, it was the only example I could remember off-hand. Had I checked first I wouldn’t have mentioned it.

But Pitowsky and Gudder are very readable, and have inspired responses both supportive and negative. In particular, Pitowsky’s original PRL short form version (look also for the errata) received a comment from Mermin, to which Pitowsky replied.

There’s also a mathoverflow discussion https://mathoverflow.net/questions/279786/on-independence-and-large-cardinal-strength-of-physical-statements/280005#280005 on his work and related proposed set theory/physics connections.

]]>