# bijective proof

• Nov 12th 2009, 07:27 AM
withoutaclue
bijective proof
Hi everyone, I am stuck on the following question, can anyone help!

let A be a finite set with m elements (m is a member of N). And suppose x is an object that is not a member of A
Prove that A U {x} has m+1 elemetns.

The answer is soo obvious but just dont know how to prove! Thanks so much!
• Nov 12th 2009, 07:35 AM
aman_cc
Quote:

Originally Posted by withoutaclue
Hi everyone, I am stuck on the following question, can anyone help!

let A be a finite set with m elements (m is a member of N). And suppose x is an object that is not a member of A
Prove that A U {x} has m+1 elemetns.

The answer is soo obvious but just dont know how to prove! Thanks so much!

Hint: Define a one-one onto mapping between A U {x} and set {1,2,3,....,m,m+1}
• Nov 12th 2009, 07:43 AM
Plato
Quote:

Originally Posted by withoutaclue
let A be a finite set with m elements (m is a member of N). And suppose x is an object that is not a member of A
Prove that A U {x} has m+1 elements.

By definition there is a bijection $f:A \leftrightarrow \left\{ {1,2, \cdots ,m} \right\}$.
Define $g:A \cup \{ x\}\mapsto \{1,2,\cdots,m,m+1\} \;,\;g(y) = \left\{ {\begin{array}{rl}
{f(y),} & {y \ne x} \\ {m + 1,} & {y = x} \\ \end{array} } \right.$

Prove that $g$ is a bijection.
• Nov 12th 2009, 02:09 PM
withoutaclue
thanks very much
it gave me some clue now