Results 1 to 3 of 3

Thread: 1-1 correspondance question

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by sbankica View Post
    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 $\displaystyle \{1,...,n\}$ with even cardinality and those of odd cardinality. Then, there exist sets $\displaystyle A,B \subset \{1,...,n\}$ with even cardinality, such that $\displaystyle A \neq B$ and $\displaystyle f(A) = f(B)$.

    Now, separate this into three cases:

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

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

    3. $\displaystyle 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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,744
    Thanks
    2815
    Awards
    1
    Quote Originally Posted by sbankica View Post
    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 $\displaystyle K \subseteq \left\{ {1,2, \cdots ,n} \right\}$.
    Then we know that $\displaystyle n\in f(K)\text{ if and only if }n\notin K.$
    If $\displaystyle n\in K$ then $\displaystyle |f(K)|=|K|-1$ and $\displaystyle n\notin K$ then $\displaystyle |f(K)|=|K|+1$.
    From that we can see that $\displaystyle f$ will map a set with an even number of elements to a set of odd number of elements and vice versa.

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

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

    Now you work on it being one-to-one.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subgroup of S_n, relation and 1-1 correspondance
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Dec 10th 2009, 07:35 AM

Search Tags


/mathhelpforum @mathhelpforum