Discarding lower cardinality subset doesn't change infinite cardinality?

Question

This is a basic question about set theory.

I am of the belief that if $A$ is a set of some infinite cardinality and $B$ is a subset with lower cardinality, $A\setminus B$ has the same cardinality as $A$.

This is true, right? How is it proven?

Thanks in advance.

(Thoughts: the statement is equivalent to saying if $A$ is infinite and $B$ is a subset that doesn't biject onto $A$, then its complement does biject, right? This is actually kind of an unbelievable statement to me! How could the failure of $B$ to biject be enough to know that its complement bijects??)

Answer 1

It’s true if you’re talking about well-ordered cardinals (assuming, of course, that $\lambda\ge\omega$). Let $\kappa$ and $\lambda$ be cardinals with $\kappa<\lambda$. Clearly $$f:\lambda\setminus\kappa\to\lambda:\xi\mapsto\xi$$ is an injection. The map

$$g:\lambda\to\lambda\setminus\kappa:\xi\mapsto\kappa+\xi\;,$$

where the addition is ordinal addition, is also an injection, so $|\lambda\setminus\kappa|=\lambda$ follows from the Schröder-Bernstein theorem.

In the absence of the axiom of choice you can have an amorphous set set $X$, an infinite set that is not the union of two disjoint infinite sets. Let $X_k=X\times\{k\}$ for $i\in\{0,1\}$, and let $Y=X_0\cup X_1$. Then $|X_0|<|Y|$, since there is no injection of $Y$ into $X$, but $$|Y\setminus X_0|=|X_1|=|X_0|\ne |Y|\;.$$

Added: In fact, as Asaf reminds me, the result is equivalent to the axiom of choice. Suppose that $X$ is a set that cannot be well-ordered, and let $\kappa$ be the Hartogs number of $X$: $\kappa$ is the smallest well-ordered cardinal that cannot be injected into $X$, and its existence is provable in $\mathsf{ZF}$. Let $Y=X\sqcup\kappa$. Then $|X|<|Y|$, but $Y\setminus X=\kappa$, and $|Y|>\kappa$, since there is no injection $Y\to\kappa$: if there were one, $X$ would be well-orderable.

Answer 2

For any cardinals $\alpha,\beta$ one has $\alpha + \beta \leq \max(\alpha,\beta,\aleph_0)$. Apply this with $\alpha = |A \setminus B|$ and $\beta = |B|$.

Answer 3

Assuming the axiom of choice we have the following law of absorption for cardinals:

Suppose that $\kappa,\lambda$ are cardinals and at least one of them is infinite, then $\kappa+\lambda=\max\{\kappa,\lambda\}$.

To see that this implies the wanted conclusion, note that $$|A|=|A\setminus B|+|B|=\max\{|A\setminus B|,|B|\}.$$ Since we assume that $|B|<|A|$, it has to be the case that $|A|=|A\setminus B|$.

---

Without the axiom of choice, let $X$ be any set which cannot be well-ordered, and let $\lambda$ an ordinal such that $\lambda\nless|X|$ (i.e. there is no injection from $\lambda$ into $X$), and we can assume $X\cap\lambda=\varnothing$.

Take $A=X\cup\lambda$, then $\lambda<|A|$ for obvious reasons (equality is ruled out because then $A$ can be well-ordered, and so could $X$), therefore $|X|<|A|$. However we have the following decomposition: $$|A|=|A\setminus X|+|X|=\lambda+|X|.$$