Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.