Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Theorem: If $\mathfrak a$ and $\mathfrak p$ are cardinals satisfying $2\mathfrak p = \mathfrak p$ and $\mathfrak a + \mathfrak p=2^\mathfrak p$, then $\mathfrak a \ge 2^\mathfrak p$.

Here's a proof:

Proof: Let $P$ and $P'$ be disjoint sets of cardinality $\mathfrak p$, and let $A$ be a set with cardinality $\mathfrak a$ disjoint from $P$. Then $|A\cup P|=\mathfrak a + \mathfrak p = 2^\mathfrak p=2^{\mathfrak p + \mathfrak p}=|2^{P \cup P'}| $. ($2^{P \cup P'}$ stands for/denotes the power set of the set $P \cup P'.$ )

Let $f$ be a one-to-one mapping of $A \cup P$ onto $2^{P \cup P'}.$ For any subset $E$ of $P',$ let $E'$ denote the set containing $E$ and all the elements $x$ of $P$ that don't belong to the set $f(x)$. Then $E'\subset P\cup P'$, and for all $x$ in $P$, $x \in E'$ iff $x \notin f(x)$ - in short, for all $x$ in $P$, $E'\not= f(x). $ It follows that $E'=f(y)$ for some $y$ in $A$. Now $E$ is any one of the $2^\mathfrak p$ subsets of $P'$ and the correspondence between $E$ and $E'$ is one-to-one therefore there are $2^\mathfrak p$ sets of the form $E'$, hence $2^\mathfrak p$ corresponding elements $y$ in $A$. Consequently, $A$ has at least $2^\mathfrak p$ elements and so $\mathfrak a \ge 2^\mathfrak p$.

My problems start in the second paragraph.

How can $E' \subset P\cup P'$ be true? $E'$ contains $E$ which isn't an element of $P\cup P'$, right? $E',$ therefore, can't be the image of any $y$ in $A$ because the images of all the elements of $A$ have to be subsets of $P\cup P'.$ Everything else later in the proof seems fine because for each set $E$, one can construct an $E'$ matching it and so if there are $2^\mathfrak p$ subsets $E$ of $P'$, there are the same number of sets $E'$ and the result would follow but all of this depends on the two ideas I pointed out that to me seem false. The proof isn't correct, yes? Can you help make it right?

share|cite|improve this question
This is a theorem of Specker, I believe. For a wonderful proof see Andres Caicedo answer here. – Asaf Karagila Aug 18 '12 at 20:36
Also, can you try and give better linebreaks? I find it very hard to follow what is written in this post. Both your given proof as well the problem you are having with it. – Asaf Karagila Aug 18 '12 at 21:33
Is this supposed to be in ZF, without choice? If so, you should say so. If not, this is much easier than that proof suggests. – Chris Eagle Aug 18 '12 at 22:12
@Chris: Indeed. – Asaf Karagila Aug 18 '12 at 22:15
@Chris Eagle: Yes, not assuming the AC. This was in fact a lemma which was needed in the proof that the GCH implies the AC. – Mark Aug 19 '12 at 13:21
up vote 2 down vote accepted

Let $F=\{x\in P:x\not\in f(x)\}$. Then $E'=E\cup F$. $E$ is assumed to be a subset of $P'$. The set $F$ of all $x\in P$ such that $x\not\in f(x)$ is a subset of $P$. Hence $E'\subseteq P\cup P'$.

The rest of the proof seems clear to you, so I won't elaborate on that.
I believe you only misunderstood the definition of $E'$: "Let $E'$ be the set containing $E$ and ..." is supposed to mean that $E'$ is the union of $E$ and the set $F$ that I defined above. Funnily enough, this kind of ambiguity was just discussed here: How do you pronounce the inverse of the $\in$ relation? How do you say $G\ni x$?

share|cite|improve this answer
I don't know why I didn't think of it that way. Thanks. – Mark Aug 19 '12 at 13:29

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.