# Do cardinals in ZF have lattice operations?

The answer to the question in the title is probably "no", although the cardinal sum appears to have many of the properties of the lattice join. But it would be nice to have an explicit example of failure of the lattice meet and join properties.

Does $\sf ZF$ prove the existence of greatest lower bounds and/or least upper bounds for pairs of (not necessarily well-ordered) cardinals $\frak m,n$?

With $\sf AC$, the answer is clearly "yes", because then the cardinals are totally ordered so for any pair of cardinals one is the meet and the other is the join.

• No, of course not. I will post an answer later if none were given. – Asaf Karagila Dec 8 '17 at 7:19
• I think I have a proof that the meet exists iff the join exists. Do you know a simple characterization of this condition? – Mario Carneiro Dec 8 '17 at 7:22
• Not that I can recall right now. But there are papers about this topic, I will look for them once I'm up and about. – Asaf Karagila Dec 8 '17 at 7:25
• I claim the answer is no if you don't have any choice principle. Indeed, let $X$ be an infinite Dedekind finite set : there is no meet of $X$ and $\mathbb{N}$ : indeed if there were, clearly we could assume it's a subset of $\mathbb{N}$, so it's either equipotent with $\mathbb{N}$, which would contradict the Dedekind finiteness of $X$, or it's finite but then you can always add one more element since $X$ is infinite, so it would not be a meet. I don't have an answer for joins though – Max Dec 8 '17 at 7:26
• @Stefan: I'm currently digging into references and writing an answer, but sure, I definitely support other people writing answers as well. – Asaf Karagila Dec 8 '17 at 9:15

No. Of course not.

Hickman, John L., Boundedness properties of cardinals, Z. Math. Logik Grundlagen Math. 25, 485-486 (1979). ZBL0424.03025.

Hickman shows that for infinite Dedekind-finite cardinals (called "medial cardinals" in the paper) the existence of least upper bound is equivalent to the existence of greatest lower bound is equivalent to the cardinals being comparable.

It is easy to arrange a model with two incomparable infinite Dedekind-finite cardinals (in fact, it is hard to produce a nontrivial model where they are all comparable), and therefore it is easily not provable that the cardinals form a lattice.

Moreover, it is shown in the paper that if every two cardinals have a greatest lower bound, and for all $n<\omega$, $n|X|\leq|Y|$, then $\aleph_0|X|\leq|Y|$. Of course, this directly implies there are no infinite Dedekind-finite cardinals on its own.

Finally, it points to the following book with the proof that "Every pair of cardinals has a greatest lower bound implies that they have a least upper bound", as well as "Every infinite cardinal $x$ satisfies $2x=x$ implies that every pair of cardinals has a least upper bound".

Rubin, J.E., Set theory for the mathematician, San Francisco-Cambridge-London-Amsterdam: Holden-Day. XI, 387 p. (1967). ZBL0154.26101.

while the question whether or not the reverse implications holds remains open. Hickman conjectures that they are false.

### Footnotes

1. I do remember other papers about this, but I do not recall by whom or where they might be; however the following paper might be of interest to you:

Truss, John, Convex sets of cardinals, Proc. Lond. Math. Soc., III. Ser. 27, 577-599 (1973). ZBL0272.02086.

2. You might find interesting stuff in the "big choice dictionary". Specifically, you're looking for Form 3.

• I am thoroughly confused about the downvote. – Asaf Karagila Dec 8 '17 at 15:12
• Maybe the second downvoter can explain also the first downvote? – Asaf Karagila Jan 24 '18 at 11:03

I claim the answer is no if you don't have any choice principle. This is maybe more elementary than the papers Asaf has cited (although I didn't read them so I'm not sure).

Indeed, let $X$ be an infinite Dedekind finite set : there is no meet of $X$ and $\mathbb{N}$ : indeed if there were, clearly we could assume it's a subset of $\mathbb{N}$, so it would either be equipotent with $\mathbb{N}$ which would contradict the Dedekind finiteness of $X$, or it would be finite but then you can always add one more element since $X$ is infinite, so it would not be a meet. I don't have an answer for joins though, but according to Asaf's answer, it is likely that the existence of a join is equivalent to that of a meet (I say "likely" because the result he mentions is about two infinite Dedekind finite cardinals, not one such cardinal and $\mathbb{N}$)

• This can be generalized, whenever the Hartogs number of $X$ is a limit cardinal... – Asaf Karagila Dec 8 '17 at 10:17
• Indeed, so even ZF + countable choice is not enough (though it was to be expected, even without your references) – Max Dec 8 '17 at 10:21
• Indeed this is the case. – Asaf Karagila Dec 8 '17 at 10:37

A reasonable follow-up question is whether there are some natural algebraic properties that the class of cardinals satisfies (provably in $\mathsf{ZF}$ or in $\mathsf{ZF}$ together with a weak axiom of choice). This is a natural problem and was investigated by Tarski in the 1940s, see

MR0029954 (10,686f). Tarski, Alfred. Cardinal Algebras. With an Appendix: Cardinal Products of Isomorphism Types, by Bjarni Jónsson and Alfred Tarski. Oxford University Press, New York, N. Y., 1949. xii+326 pp.

Tarski isolated such a set of properties under the notion of a cardinal algebra. A cardinal algebra consists of an abelian semigroup $(A,+)$ with identity together with an infinitary addition operation $\sum\!:A^{\mathbb N}\to A$, subject to some axioms. The theory found an unexpected recent application in descriptive set theory, in the study of Borel equivalence relations and their associated Borel cardinalities, see

MR3549382. Kechris, Alexander S.; Macdonald, Henry L. Borel equivalence relations and cardinal algebras. Fund. Math. 235 (2016), no. 2, 183–198.

In the paper by Kechris and Macdonald, the axioms are described in a somewhat different (but equivalent) way than in Tarski's book, namely:

• $\sum_{n=0}^\infty \mathfrak{m}_n=\mathfrak m_0+\sum_{n=0}^\infty \mathfrak m_{n+1}$.
• $\sum_n (\mathfrak m_n+\mathfrak n_n)=\sum_n \mathfrak m_n+\sum_n\mathfrak n_n$.
• If $\mathfrak m+\mathfrak n=\sum_n\mathfrak o_n$, then there are sequences $(\mathfrak m_n)_{n=0}^\infty$ and $(\mathfrak n_n)_{n=0}^\infty$ such that $\mathfrak m=\sum_n \mathfrak m_n$, $\mathfrak n=\sum_n \mathfrak n_n$, and $\mathfrak m_n+\mathfrak n_n=\mathfrak o_n$ for all $n$.
• If two sequences $(\mathfrak m_n)$ and $(\mathfrak n_n)$ satisfy $\mathfrak m_n=\mathfrak n_n+\mathfrak m_{n+1}$ for all $n$, then there is an $\mathfrak o$ such that, for all $n$, $\mathfrak m_n=\mathfrak o+\sum_k \mathfrak n_{n+k}$.

Tarski proves in his book that many properties of cardinal numbers provable in $\mathsf{ZF}$ or even $\mathsf{ZF}+\mathsf{AC}_\omega$ follow from his postulates (and some additional properties were later verified by Truss). He also provides several examples of cardinal algebras.

What Kechris and Macdonald do is to note that there are natural operations $+$ and $\sum$ on the class of Borel equivalence relations on standard Borel spaces such that certain subclasses are cardinal algebras (for instance, the class of countable Borel equivalence relations, the class of treeable countable Borel equivalence relations, and others) . This results in proofs of new facts about Borel equivalence relations that had been open for years. For instance, if $E$ and $F$ are countable Borel equivalence relations and $nE\sim_B nF$, then $E\sim_B F$. Here, $\sim_B$ is the relation of Borel bireducibility. For another example, any sequence $F_0\le_B F_1\le_B \dots$ of countable Borel equivalence relations admits a least upper bound under Borel reducibility $\le_B$.

• I still can't believe that I own that book. – Asaf Karagila Dec 9 '17 at 6:59