Large cardinals

How big is the universe? Ultrafinitists such as Doron Zeilberger reject the Axiom of Infinity, and only allow finite sets. The universe of all finite sets, Vω, is a perfectly consistent set theory, which obeys all of the other axioms of ZFC. It’s not a particularly powerful set theory, though, as we can’t encapsulate the notion of the set of natural numbers.

So, Vω is too small to be consistent with ZFC. It turns out that the smallest universe consistent with ZFC is L, Gödel’s constructible universe, where at each successor stage we take only the sets expressible by first-order formulae ranging over sets in the previous stage. In L, the generalised continuum hypothesis is true, so every cardinality can be obtained by taking unions and powersets. There are other nice corollaries of V = L (the axiom that the entire von Neumann universe is the same as Gödel’s constructible universe) such as the existence of a Suslin tree.

Large cardinals are those with special properties, typically whose existence is not implied by ZFC. Many of these have very complicated set-theoretic definitions, but there are some easier notions related to Ramsey theory. For example, for your favourite ordinal α, the Erdős cardinal κ(α) is the smallest cardinal such that for all n, every 2-colouring of the n-subsets of κ(α) contains a monochromatic set of order type α. If α = ω, for example, then the infinite Ramsey theorem asserts that κ(ω) = .

0# and beyond

Note that if β < α, then the existence of κ(α) implies the existence of κ(β). There’s a property of intermediate strength between the existence of κ(ω1) and the existence of κ(β) for all countable β, namely the rather interesting axiom 0#. 0# is defined as a set of true statements (in L augmented with the symbols {, , …} (one for each natural number) interpreted as cardinalities in V), but it can also be encoded as a set of naturals (by Gödel numbering) or indeed as a real number.

The only problem is that sometimes statements do not necessarily have a prescribed truth value, so 0# is not necessarily well-defined. If 0# exists, then V is much larger than L; otherwise, V can only be very slightly larger than L. So, 0# is really the first large cardinal property that goes beyond V = L.

Beyond 0#, there is a hierarchy of increasingly strong large cardinal properties. At the end of this list are Reinhardt cardinals and strong partition cardinals, which are so strong that they break ZFC (although strong partition cardinals, at least, are consistent with ZF). The strongest large cardinal that is not known to be inconsistent with ZFC is a rank-into-rank cardinal, which is marginally weaker than a Reinhardt cardinal.

Specifically, it asserts the existence of an ordinal γ such that the γth iteration of the von Neumann universe, Vγ, can be non-trivially mapped into itself such that the truth of all first-order statements are preserved. (Such a map must obviously be an injection, as the statement ‘a is not equal to b’ must be preserved for all distinct elements a and b.)

Laver tables

The existence of a rank-into-rank was used by Richard Laver to prove a certain very combinatorial statement. A Laver table of order n is the table of a binary operation $\star : \mathbb{Z}_{2^n} \times \mathbb{Z}_{2^n} \rightarrow \mathbb{Z}_{2^n}$ satisfying the properties $p \star 1 = p + 1$ and $p \star (q \star r) = (p \star q) \star (p \star r)$.

The periodicity of the first row of the Laver table, i.e. the period of $1 \star i$ as a function of i, must necessarily be a power of 2. In the example above (n = 2), the first row is (2, 4, 2, 4), which has a period of 2. The period is also an increasing function of n, but it increases extremely slowly. It (sequence A098820) begins as follows:

1, 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, ...

where the number of sixteens is more than A(9), where A(n) is the fast-growing Ackermann function. In general, the point at which the sequence first exceeds 2^m, if it exists, is not a primitive-recursive function of m (eventually dominating the Ackermann function).

The proof that the sequence increases without bound actually relies on the existence of a rank-into-rank cardinal. So, if these things don’t actually exist (which is entirely plausible), then it may be that the sequence is eventually constant. It seems extremely unusual (impossible, surely?) that such a basic combinatorial statement would be independent of ZFC, so it is generally believed that A098820 does indeed grow without bound. But then again, it has not been proved that the existence of a rank-into-rank is consistent with ZFC, and people initially believed otherwise — that the inconsistency proof of Rienhardt cardinals could be adapted to disprove the existence of a rank-into-rank — but all attempts failed miserably so the general concensus is that they are consistent with ZFC.

This entry was posted in Uncategorized. Bookmark the permalink.

16 Responses to Large cardinals

1. Johnicholas says:

If you Godel-encode a set theory with large cardinals, don’t you get something that ultrafinitists would be comfortable working with?

Unless I am mistaken, the question of whether large cardinals “exist” depends on what you mean by “exist”. The ultrafinitists would prefer to say that a mathematician manipulating large cardinals is manipulating symbols (which exist and are finite), and the set-theory realist would prefer to say that the ultrafinitist who claims to be manipulating symbols is actually manipulating some (perhaps inaccessible, situated on some dualistic plane of platonic forms) mathematical objects, and the symbols the ultrafinitist uses refer to those objects.

Is this merely an argument about terms?

• apgoucher says:

Suppose you Gödel-encode a set theory such as ZFC, and the positive integers correspond to statements. Some of these will be provably true, others will be provably false, and there are lots of statements which can neither be proved nor disproved. It is meaningless to attribute a value of true’ or false’ to those integers.

Whereas in actual set theory before you subjected it to the mincer of Gödel-encoding, it feels as though a statement such as the continuum hypothesis should be either true or false, even though we can’t prove or disprove it with the ZFC axioms.

So, that’s where the philosophies of mathematics is a formal game’ and mathematics actually exists in some reality’ differ: whether they believe that unprovable statements should have assigned truth values.

2. Thomas says:

Is there a name for binary operations * satisfying a * (b * c) = (a * b) * (a * c)?

• wojowu says:

A cool name for it would be “self-distributive” binary operation. But I think proper name would be “distributive over itself”

• Thomas says:

Well, self-left-distributive (or would that be right distributive). Also, what is known about such binary operations?

3. wojowu says:

One of the formulas does not parse for me. I also think next one should say p*1=p+1 mod 2^n.

• apgoucher says:

The formula that doesn’t parse (basically, WordPress is shockingly terrible at compiling LaTeX code) gives $\mathbb{Z}_{2^n}$ as the domain and codomain, so the `mod 2^n’ is implicit.

4. Kibo says:

Ikea used to sell Laver Tables. They stopped selling them after people realized that to seat 32 people at one, you had to buy at least A(9,A(8,A(8,255))) chairs.

http://img.docstoccdn.com/thumb/orig/151075420.png

• apgoucher says:

Haha, yes, Ikea have made it very difficult to search for Laver tables on Google images…

5. Nathan Ho says:

Let q(n) be minimal so that p(q(n)) = 2^n. I conjecture that q(6) is far larger than BH(3), SCG(13), or TREE(3).

• apgoucher says:

We know that the function (if it even is a function — I’m not convinced that ZFC + rank-into-rank is arithmetically sound, or even consistent) outgrows the Ackermann function, but there’s no reasonable upper bound.

I don’t have any reason to see why it should outgrow BH, SSCG or TREE. It’s certainly a computable function (systematically test each Laver table and check for periodicity), so it’s definitely dominated by the Busy Beaver function.

The big question is: which ordinal corresponds to this function in the Grzegorzyck hierarchy? We have omega as a lower bound, and the Church-Kleene ordinal as an upper bound. If q(n) outgrows BH, then it would establish a huge recursive ordinal (the Buchholz ordinal) as a lower bound.

• Nathan Ho says:

I’m mostly relying on intuition with fast-growing functions here. The Goodstein function can’t be proven total in PA (but it can in stronger systems), and its growth rate is measured by the proof-theoretic ordinal of that system, or epsilon_0. The BH function can’t be proven total in Pi11-CA0+BI (but it can in stronger systems), and its growth rate is also the proof-theoretic ordinal of that system, or psi(epsilon_(Omega_omega + 1)). q(n) can’t be proven total in ZFC + rank-into-rank (assuming that that actually works), and even if its growth rate doesn’t match up with the proof-theoretic ordinal of that system, I hope there’s some way we can extract a seriously powerful function out of this.

• apgoucher says:

q(n) can be proved total in ZFC + rank-into-rank (and it has). I agree that if it can’t be proved total in ZFC, then it’s most probably much faster-growing than BH et cetera, but there isn’t any evidence that this is the case (I don’t even think that it has been proved independent of PA).

Of course, ZFC is much stronger than Pi11-CA0+BI, so a ZFC-independent combinatorial theorem would lead to an extremely fast-growing function.

• Nathan Ho says:

Right, right. Thanks for clearing that up.

• wojowu says:

If you are interested in functions so extreme ZFC can’t prove them total, I recommend you this paper by Harvey Friedman: http://arxiv.org/abs/math/9811187 (I haven’t read it yet, but friend of mine has recommended it). In fact, propositions appearent in that paper are not only unprovable in ZFC, but, quoting the paper, they “imply the
consistency of ZFC+{there exists a k-subtle cardinal}_k”.