Cardinality of sets: $|A|\le|B|\Rightarrow(|A\cup B|=|B|\land|A\times B|=|B|)$

89 Views Asked by At

My book of mathematical logic states the facts that, if we call $|X|$ the cardinality of set $X$, then, for any two sets $A,B$ such that $|A|\le|B|$, $$|A\cup B|=|B|\quad\text{ and }\quad|A\times B|=|B|$$

I know that it holds for countable sets, but I would like to understand why it holds in general. The book says that it is provable by using the fact that any set can be well-ordered, but, although I know this fact, I cannot see how $|A\cup B|=|B|$ and $|A\times B|=|B|$ can derive from it. I thank you very much for any answer!

EDIT: although my text says nothing about it, $B$ must be an infinite set, as pointed out by Henrik, Ben and Asaf, and $A$ whom I thank for noticing that. Moreover, as Andrés points out, $A$ must be non-empty.

1

There are 1 best solutions below

2
On BEST ANSWER

(I'm assuming that you are talking about infinite sets, since finite sets can easily produce many counterexamples.)

Both these statements require the axiom of choice to be proved. The one about products even implies the axiom of choice itself (the one about unions is weaker than choice).

If you already know that the axiom of choice implies that every set can be well-ordered, then you can mimic the proof from the countable case to arbitrary ordinals. It's slightly harder, but you can define a bijection between $X\times X$ and $X$, when $X$ is an infinite set that can be well-ordered (equivalently, when $X$ is an infinite ordinal), and from this all the results follow:

$$|B|\leq|A|+|B|\leq|B|+|B|\leq|B\times A|\leq|B\times B|=|B|.$$

Then the axiom of choice is needed to ensure that every infinite set is equipotent with an ordinal, and the result now follow.

See Godel's pairing function and proving c = c*c for aleph cardinals and the links mentioned there for details about proving $|X|=|X\times X|$ for well-ordered sets.

If you do not yet know about the axiom of choice, or ordinals, and so on, then the result is much harder to explain intuitively. Infinite sets are "weird".