Results 1 to 3 of 3

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

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    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 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.
    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: December 10th 2009, 07:35 AM

Search Tags


/mathhelpforum @mathhelpforum