9
$\begingroup$

Is there a published reference for this ZF theorem?

Let $m,n\in\mathbb{N}$. If $a_1,\dots,a_m$ and $b_1,\dots,b_n$ are cardinals such that $a_i\le b_j$ for all $i$ and $j$, then there is a cardinal $x$ such that $a_i\le x\le b_j$ for all $i$ and $j$.

It's enough if the proposition is stated for the case $m = n = 2$, as the rest follows by an easy induction.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Funny, when you mentioned this in your previous question, I almost asked for a reference. I'm still in the process of trying to dig one up myself. (In other news, I believe Marion and I owe you an email.) $\endgroup$
    – Andrés E. Caicedo
    Commented May 15, 2013 at 22:56
  • 1
    $\begingroup$ How do you want to prove this per induction for $m=n=3$? I think that this induction does not work. $\endgroup$
    – The User
    Commented May 15, 2013 at 22:58
  • $\begingroup$ I just heard this nice result from Fred Galvin a few weeks ago. My understanding is that he proved it without knowing a reference. $\endgroup$
    – Péter Komjáth
    Commented May 16, 2013 at 3:41
  • 1
    $\begingroup$ Perhaps eudml.org/doc/213170 (`Axiomatic and algebraic aspects of two theorems on sums of cardinals', Tarski, 1948) is a good place to look for this theorem, a result implying it, or a separate reference. I hope someone with more patience/time than I have at the moment finds this a helpful start. $\endgroup$
    – Benjamin Dickman
    Commented May 16, 2013 at 6:25
  • $\begingroup$ Butch, you missed an answer posted by Asaf Karagila, which was later deleted because of (I suspect) a nonobvious use of choice. Somehow a set which was some form of union of (images of) the a cardinals was shown to exist inside the b cardinals and that this set exhibited the desired cardinality. While it was a nice presentation, I was unsure how the set guaranteed the desired cardinality in ZF. On the matter of personal remarks, it's best to pretend you are at a televised seminar when you are making them. Gerhard "Typing This While Mostly Naked" Paseman, 2013.05.16 $\endgroup$
    – Gerhard Paseman
    Commented May 16, 2013 at 9:44

1 Answer 1

Reset to default
4
$\begingroup$

The comments by The User and Joel David Hamkins refer to a previous version of the answer which contained a mistake. The current version is completely disjoint of the previous one, and the comments no longer apply.

This appears in Tarski's book Cardinal Algebras as Theorem 2.28, called Interpolation Theorem, and the statement of the theorem is as follows:

If $n\leqq\infty,\ p\leqq\infty$, such that $a_i\leqq b_j$ for $i< n$ and $j < p$, then there is an element $c$ such that $a_i\leqq c\leqq b_j$ for every $i < n$ and $j < p$.

The theorem appears on page 27. The full citation is given below, one can also read about it on MathSciNet.

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.

One note about the use of $\infty$ here, Tarski assumes that there is an operator of summation of a countable sequence, and therefore the theorem holds in that case as well. This may require the axiom of choice (or rather a minor fragment thereof), but if we remove that case, then the proof goes through just fine.

The proof begins with the case of $n=p=2$, in which cardinals are manipulated by hand. It then proceeds to the case where $n$ is arbitrary and $p=2$, where a sequence is defined by induction and the existence of a supremum is guaranteed by a previous theorem. Here we use choice when $n=\infty$, but if $n$ is finite then the induction halts and the upper bound of the last step is our wanted $x$.

Next he proves for $n=2$ and $p$ arbitrary. For finite $p$ the proof is purely constructive, and I suspect it holds without the axiom of choice for $p=\infty$ as well (it relies on previous theorems which I haven't read thoroughly in search of choices).

Lastly he argues that the proof of the general case follows as the proof of the second case, with using the third case to reason instead of the first case. In either case, if we assume $p,n<\infty$ then there is no invocation of the axiom of choice.

Improve this answer
$\endgroup$
11
  • 2
    $\begingroup$ To explain Asaf's without-loss-of-generality argument: first assume that all $A_i$'s and $B_j$'s are disjoint. Now, since $A_0$ injects into every $B_j$, we can replace each image with $A_0$, so that $A_0\subset B_j$ using the new versions of $B_j$. Now move on to $A_1$, and when you do the replacing, also replace the corresponding points in $A_0$. etc. After $m$ steps, you gain Asaf's assumption, which trivializes the rest of the problem. $\endgroup$
    – Joel David Hamkins
    Commented May 15, 2013 at 23:51
  • 1
    $\begingroup$ Hang on, I'm a little confused with the later stages of this replacement procedure, since things aren't disjoint any more and it seems that competing requirements arise. Asaf, could you kindly give a more straightforward account of your reduction? $\endgroup$
    – Joel David Hamkins
    Commented May 16, 2013 at 0:31
  • 1
    $\begingroup$ (Asaf: You may leave a comment at the beginning of the answer, indicating that the comments refer to a prior, completely different, version of the answer.) $\endgroup$
    – Andrés E. Caicedo
    Commented May 16, 2013 at 23:43
  • 1
    $\begingroup$ Butch, there is no footnote by that theorem, and Tarski mentions in the preface that if there is no footnote then to the best of his knowledge, that is the first publication - with the exception of the first chapter which covers elementary results. So it's probably the first publication of this theorem. $\endgroup$
    – Asaf Karagila ♦
    Commented May 17, 2013 at 0:36
  • 2
    $\begingroup$ The $\infty$ symbol was a source of discomfort for me. But I feel that Tarski is using this symbol for $\omega$. Yes, this is a stronger theorem than you have requested for. Tarski proves in four parts: $n=p=2$; $n$ arbitrary, $p=2$; $n=2$ and $p > 0$; $n$ and $p$ arbitrary. Glancing over the proof of the second case, he constructs a sequence of upper bounds and then uses the fact that an increasing sequence has an upper bound. Although the infinite case does seem to require choice for an infinite summation to work; the finite case holds just fine. $\endgroup$
    – Asaf Karagila ♦
    Commented May 17, 2013 at 0:52

You must log in to answer this question.