1

For a set $E$ and $n \in \mathbb{N}$ we say $\# (E) = n$ if there is a bijection from $I_n$ to $E$, where

$$I_n \overset{\text{def}}= \{k\in \mathbb{N}: k \leq n\}$$

Suppose that $\# (E) = n$, $\#(G) = k$ and $E \cap G = \varnothing$. Show that

$$\#(E \cup G) = \#(E) + \#(G)$$

My thoughts

It may be tempting to use $E \cup G = E + G - (E \cap G)$, set $\#$ by both sides and evaluate both sides to get the statement I want to prove, but is this right? I thought of the bijection as some sort of homomorphism. It's something like this

$$\#(E \cup G) = \#(E) + \#(G) - \#(E \cap G)$$ $$\#(E \cup G) = \#(E) + \#(G)$$

Another thing: Do I need to apply the ordering on the set to show the given equation, or is that unnecessary? I thought of this because of the given set.

I'm quite stuck on proof because I don't really know how it goes. Any advices or comments?

NasuSama
  • 3,364

1 Answers1

1

There is a bijection $f : E \to I_{\#E}$, and a bijection $g : G \to I_{\#G}$. Let us extend $f$ to $E \cup G$ by definining

$$f(x) = \left\{ \begin{array}{lr} f(x) & : x \in E \\ 0 & : x \in G\end{array}\right.$$

Since $E \cap G$ is empty, $f$ is well-defined. Do the same for $g$.

Now consider $h = f + g$ defined pointwise; can you show that $h$ is a bijection with $I_{\#E + \#G}$?

  • Since $f$ and $g$ are bijections, then by hypothesis, $h = f + g$ is also a bijection. Since we have well-defined bijections $f:E\rightarrow I_{#E}$ and $g:G\rightarrow I_{#G}$, then $(f + g):(E \cup G) \rightarrow I_{#(E \cup G)}$, which is actually $h$, the function YOU defined. Thus, since $(E \cap G)$ is empty, $h:(E \cup G) \rightarrow I_{#(E) + #(G)}$ – NasuSama Oct 09 '13 at 20:07