# Thread: 1-1 correspondance question

1. ## 1-1 correspondance question

Let X be a subset of {1,2,3,...,n} such that |X| is even. Define f(X) to
be the set obtained from X by adding the element n when n is not in set X, and deleting the element n when n is in set X. (That is, f(X) = X union {n} if n is not in X, and f(X) = X \ {n} if n is in X.) Prove that f is a 1-1 correspondence between the subsets of {1, 2,....,n} with an even number of elements and the ones with an odd number of elements.

2. Originally Posted by sbankica
Let X be a subset of {1,2,3,...,n} such that |X| is even. Define f(X) to
be the set obtained from X by adding the element n when n is not in set X, and deleting the element n when n is in set X. (That is, f(X) = X union {n} if n is not in X, and f(X) = X \ {n} if n is in X.) Prove that f is a 1-1 correspondence between the subsets of {1, 2,....,n} with an even number of elements and the ones with an odd number of elements.
Assume, by contradiction, that f is not 1-1 between subsets of $\{1,...,n\}$ with even cardinality and those of odd cardinality. Then, there exist sets $A,B \subset \{1,...,n\}$ with even cardinality, such that $A \neq B$ and $f(A) = f(B)$.

Now, separate this into three cases:

1. $n \in A, n \in B \Rightarrow f(A) = A - \{n\} = f(B) = B - \{n\} \Rightarrow A = B$, contradiction.

2. $n \in A, n \notin B$ (same when n is in B and not A).

3. $n \notin A, n \notin B$

I did the first one for you, now see if you can do the others (they are just as simple).

3. Originally Posted by sbankica
Let X be a subset of {1,2,3,...,n} such that |X| is even. Define f(X) to be the set obtained from X by adding the element n when n is not in set X, and deleting the element n when n is in set X. Prove that f is a 1-1 correspondence between the subsets of {1, 2,....,n} with an even number of elements and the ones with an odd number of elements.
Let’s setup some background. Suppose that $K \subseteq \left\{ {1,2, \cdots ,n} \right\}$.
Then we know that $n\in f(K)\text{ if and only if }n\notin K.$
If $n\in K$ then $|f(K)|=|K|-1$ and $n\notin K$ then $|f(K)|=|K|+1$.
From that we can see that $f$ will map a set with an even number of elements to a set of odd number of elements and vice versa.

Define $\mathcal{E}=\left\{ Y \subseteq \{1,2, \cdots ,n\}:\left| Y \right| \text{ is even} \right\}$
Define $\mathcal{O}=\left\{ Z \subseteq \{1,2, \cdots ,n\}:\left| Z \right| \text{ is odd} \right\}$

Now we show that $f: \mathcal{E}\mapsto \mathcal{O}$ is onto.
Suppose that $J\in \mathcal{O}$.
If $n\in J$ then $f\left(J\setminus\{n\}\right)=J$.
On the other hand, if $n\notin J$ then $f\left(J\cup\{n\}\right)=J$.
So in either case $f$ is onto.

Now you work on it being one-to-one.