Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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.) –  Andres Caicedo May 15 '13 at 22:56
1  
How do you want to prove this per induction for $m=n=3$? I think that this induction does not work. –  The User May 15 '13 at 22:58
    
I just heard this nice result from Fred Galvin a few weeks ago. My understanding is that he proved it without knowing a reference. –  Péter Komjáth May 16 '13 at 3:41
1  
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. –  Benjamin Dickman May 16 '13 at 6:25
    
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 –  Gerhard Paseman May 16 '13 at 9:44

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
2  
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. –  Joel David Hamkins May 15 '13 at 23:51
1  
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? –  Joel David Hamkins May 16 '13 at 0:31
1  
(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.) –  Andres Caicedo May 16 '13 at 23:43
1  
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. –  Asaf Karagila May 17 '13 at 0:36
2  
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. –  Asaf Karagila May 17 '13 at 0:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.