Looking an abstract proof to an elementary set theory property

Question

I've been scratching and pulling my hair for an hour and a half trying to come up with an abstract solution to a simple property.

For finite sets $A_1, A_2$, show that $$|A_1 \cup A_2| \leq |A_1| + |A_2|.$$

Then use (possibly induction) to show $|\cup_{i}A_i| \leq \sum_i |A_i|$

So the first thing I did was play with inequalities like $|A_1| \leq |A_1 \cup A_2|$. I got nowhere.

Then I tried doing this with cases, but I resorted to using the Venn diagram and using an example to convince myself this property got to be true and I couldn't pick out the right words to write down the formal proof. So I am convinced that cases is no good either and I was thinking my original method with inequalities is the way to go.

Answer 1

Well. Recall the definitions.

1. What does it mean when we write $|A|\leq|B|$? It means that there is an injection from $A$ into $B$.

2. What does it mean when we say $|A|+|B|$? It means that we consider the disjoint union of $A$ and $B$. Similarly for infinite sums. So we can think about $\sum_i |A_i|$ as the cardinality of $\bigcup_i(\{i\}\times A_i)$, and if you don't see it right away then you should convince yourself this is a disjoint union.

Now all that is left is finding an injection from $\bigcup A_i$ into $\bigcup(\{i\}\times A_i)$. If we assume that $I$ is well-ordered (e.g. if it's finite, or if we assume the axiom of choice¹), then you can map $a\in\bigcup A_i$ to $\langle j,a\rangle$ where $j=\min\{i\in I\mid a\in A_i\}$.

I will leave you to think why this is an injection.

---

1. Without the axiom of choice it is consistent that this inequality is ill-defined. For example we can have $|A_i|=2$ for $i\in\Bbb N$, but $\bigcup A_i$ is not equivalent to $\Bbb N$, rendering the notion of an infinite sum of cardinals meaningless.

Answer 2

Note $\sum_i |A_i|= | \sqcup_i A_i|$, where $\sqcup_i A_i$ is the disjoint union of the $A_i$'s.

Then consider the surjection $f: \sqcup_i A_i \rightarrow \cup_iA_i$ where $f(a_i)=a_i$ for $a_i\in A_i$.