Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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}$?

share|cite|improve this answer
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 9 '13 at 20:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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