François G. Dorais

Research in Logic and Foundations of Mathematics

Some Cardinal Arithmetic

Some time ago, Asaf Karagila wrote wonderful post wherein he shows that, even without assuming the axiom of choice one can always find four cardinals and such that In the comments, Harvey Friedman asks:

Your theorem is an example of an existential sentence about cardinals in the language with only and exponentiation. Can you determine which sentences in that language are provable in ZF? More generally, expand the set of sentences about cardinals considered, obviously to include addition and multiplication, and perhaps alternating quantifiers.

After Peter Krautzberger’s tiny blogging challenge, I decided to spend 30 minutes thinking and writing about this…

I will allow myself some liberties in interpreting Friedman’s open ended question. The celebrated solution of Hilbert’s Tenth Problem by Davis, Matiyasevich, Putnam and Robinson shows that the existential theory of the finite cardinal numbers (even without exponentiation) is as complex as it could be: it is -complete. I’ll interpret Friedman’s question as asking whether the existential theory of all cardinal numbers could be simpler than that of finite cardinals.

My gut instinct is: of course not! But this is not a trivial question. For example asking whether has a solution where and has proven extremely challenging for finite cardinals but there are plenty of solutions with infinite cardinals!

One plan of attack is to try to define the finite cardinals among all cardinalsusing an existential formula. To get started, I’ll start with a rich language including constants , , relations , as well as addition, multiplication and exponentiation. Assuming the Axiom of Choice, finite cardinals are defined by the simple quantifier-free formula

Without assuming choice, this only defines the Dedekind finite sets. Fortunately, if is infinite then is never Dedekind finite. So the finite sets are always described by the quantifier-free formula

This shows that the existential theory of all cardinals in this rich language is as complex as that of finite cardinals.

Do things change if we restrict the language? Indeed, the first part of Friedman’s question only mentions exponentiation. For finite cardinals, we can recover addition and multiplication using familiar rules of exponents:

We can even eliminate and since any finite base other than and will do instead of . So, for example,

Therefore, the existential theory of finite cardinals with just exponentiation is just as complex as that with addition and multiplication.

Of course, we can’t use this to recover addition and multiplication of infinite cardinals using the methods we used above, but if we can define the class of finite cardinals then we can use the above to recover addition and multiplication for these cardinals. Can we define finite cardinals using only , and exponentiation? Well, the finite cardinals are the only ones that satisfy the monstrous inequality

We can then eliminate using the same trick as above to get an existential definition:

So my gut instinct was right: the existential theory of all cardinals using only , and exponentiation is at least as complex as that of finite cardinals!

This took more than 30 minutes but it didn’t take much more and it was a lot of fun! Hopefully, the time constraint didn’t impact the content quality too much…

CC0 Originally posted on by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.