# Question involving showing there's a bijection

• Nov 14th 2012, 03:29 PM
sakuraxkisu
Question involving showing there's a bijection
My question is:

Let A be a finite set with m elements, for some $\displaystyle m\in\mathbb N$. And suppose x is an object that is not a member of A.

Prove, using the definitions, that $\displaystyle A \cup \{x\}$ has m+1 elements.

(All you are told about A is that it has m elements. You need to show that there is a bijection from $\displaystyle \mathbb N_m_+_1$ to $\displaystyle A \cup \{x\}$.)

Any help would be appreciated :)
• Nov 14th 2012, 03:34 PM
Re: Question involving showing there's a bijection
Do you need to show there's a bijection?

You could use induction as well. Start with the empty set (base case m=0). empty set union with {x} is {x} by definition and has 0+1 = 1 elements. so the base case is true.
then assume P(k): "A union with {x} has m+1 elements for $\displaystyle k \leq m$"

then prove P(k+1)
• Nov 14th 2012, 03:44 PM
sakuraxkisu
Re: Question involving showing there's a bijection
Yeah, I need to show that there's a bijection rather than doing a proof by induction. Would you be able to help me? Thanks
• Nov 14th 2012, 03:53 PM
$\displaystyle A \cup \{x\}\\$ has elements a0 a1, a2 ... am, x
Let f be a bijection from $\displaystyle A \cup \{x\}\\$ to Nm+1 such that an -> n for $\displaystyle n \leq m$ and x -> m+1