Charles C.Pinter - Set theory

Let $a,b,c$ be any cardinal numbers.

Give a counterexample to the rule: $$a+b = a+c \implies b=c$$

Does there exist a counterexample?


$$\begin{align}&1.\quad\aleph_0=\aleph_0+0=\aleph_0+1\\&2.\quad 0\neq 1\end{align}$$

Where $\aleph_0$ is the cardinality of countably infinite sets, e.g. the non-negative integers, $\mathbb N$.

  • $\begingroup$ This is certainly the very simplest counterexample. $\endgroup$ – Michael Hardy May 11 '12 at 23:59
  • $\begingroup$ or any infinite cardinal $\endgroup$ – Greg Martin May 12 '12 at 0:03
  • $\begingroup$ @Greg: Assuming the axiom of choice, yes. $\endgroup$ – Asaf Karagila May 12 '12 at 10:06
  • $\begingroup$ @AsafKaragila: aha, equivalently the well-ordering principle - interesting. Can one construct a counterexample if the axiom of choice isn't assumed? $\endgroup$ – Greg Martin May 12 '12 at 19:41
  • $\begingroup$ @Greg: Indeed. We say that A is a Dedekind-finite set if whenever $B\subsetneq A$, $|B|<|A|$. Equivalently this is to say that $|A|<|A|+1$. Every finite set is Dedekind-finite, and assuming the axiom of choice the opposite is also true: Dedekind-finite sets are finite sets. However it is consistent that without the axiom of choice there may be infinite Dedekind-finite sets. These sets may be used to construct such counterexamples. $\endgroup$ – Asaf Karagila May 12 '12 at 21:48

Here's one: $|\Bbb N| + |\{1\}| =|\Bbb N| + |\{2, 3\}| $, but $|\{1\}| \ne|\{2,3\}|$.


You will probably learn later that for any infinite cardinal $a$ the equality $$a+a=a\cdot a=a$$ holds. This implies that for any infinite cardinal $a$ you have a counterexample $a+a=a+0$.

More generally, if $b$, $c$ are infinite cardinals then $$b+c=b\cdot c=\max\{b,c\}.$$

The proof of these general result is not that simple, it requires axiom of choice. See e.g. the following questions: About a paper of Zermelo and How to prove that from "Every infinite cardinal satisfies $a^2=a$" we can prove that $b+c=bc$ for any two infinite cardinals $b,c$?

However, showing the above result for some special cases, like $a=\aleph_0$ or $a=2^{\aleph_0}$ is not that difficult and it might be a useful exercise for someone learning basics of set theory and cardinal arithmetic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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