Results 1 to 4 of 4

Math Help - characteristic functions and sets

  1. #1
    Junior Member
    Joined
    Jul 2007
    Posts
    27

    Question characteristic functions and sets

    Let X be a set and let A be one of its subsets. The characteristic function of A is the function Q_A: X--> {0,1} defined by

    Q_A (x)= {1 if x is in A,
    {0 if x is not in A.

    a) show that if A and B are subsets of X then they have the same characteristic function iff they are equal.
    b) Show that every function from X to {0,1} is the characteristic function of some subset of X.

    Actually, I dont know understand what is the relationship between sets and characteristic functions...

    Please help me or give me some hints.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by r7iris View Post
    Let X be a set and let A be one of its subsets. The characteristic function of A is the function Q_A: X--> {0,1} defined by

    Q_A (x)= {1 if x is in A,
    {0 if x is not in A.

    a) show that if A and B are subsets of X then they have the same characteristic function iff they are equal.
    b) Show that every function from X to {0,1} is the characteristic function of some subset of X.

    Actually, I dont know understand what is the relationship between sets and characteristic functions...

    Please help me or give me some hints.
    Informally:

    The charateristic function of a sub-set S of a set X is a function defined on X which takes the value 1 for any element s \in S and 0 otherwise.

    This means that any sub-set S of X is determined by its charateristic function, and any 0-1 function on X determines a sub-set of X.

    For example, let X=\{a, b, c, d\} and S=\{b, d\}, then:

    \chi_S(a)=0,\ \chi_S(b)=1,\ \chi_S(c)=0,\ \chi_S(d)=1 ,

    where \chi_D is the charateristic function of S.

    RonL

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by r7iris View Post
    Let X be a set and let A be one of its subsets. The characteristic function of A is the function Q_A: X--> {0,1} defined by

    Q_A (x)= {1 if x is in A,
    {0 if x is not in A.

    a) show that if A and B are subsets of X then they have the same characteristic function iff they are equal.
    let me take a stab at this one. tell me if i'm right guys...i'm not trying to be formal, so don't get on my case about that

    Theorem (or whatever): if A and B are subsets of X then they have the same characteristic function iff they are equal.

    Proof: Let A and B be subsets of a set X.

    For the forward implication, we use the contrapositive. Assume A \neq B, and assume, without loss of generality, that |A|>|B|. Then there is some x \in A such that x \notin B. Thus, for such an x, Q_A(x) = 1 while Q_B(x) = 0. Thus their do not have the same characteristic function.

    For the reverse implication, we use a direct proof. Assume A = B. If A = B = \emptyset then the result is immediate, since for any element x \in X we have Q_A = Q_B = 0. Assume A = B \neq \emptyset. Let x \in X be an element that is in A. Then Q_A(x) = 1. But since A = B, we have x \in B, so Q_B(x) = 1 as well. Let y \in X be an element such that it is not in A, then Q_A(x) = 0. But since A = B, we have that y \notin B, so Q_B(y) = 0 as well. Thus, the characteristic functions of A and B are always equal.

    QED
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by r7iris View Post
    b) Show that every function from X to {0,1} is the characteristic function of some subset of X.
    I'll take a stab at this one as well. i'm even less comfortable with my answer than the last one

    Result: every function from X to {0,1} is the characteristic function of some subset of X

    Proof: Let X be a set. Let Y be the set {0,1}. Let A be any arbitrary subset of X.

    Then for each x \in X, we have Q_A(x) = 0 or Q_A(x) = 1, but whatever the value of Q_A(x) we will have one such value for each subset A of X.
    Now, the number of functions from X to Y is given by |Y|^{|X|}. Let n be the number of elements in X. Since |Y| = 2, we have the number of possible functions from X to Y being 2^{n}. But that is exactly how many subsets we have in X. Thus we have one function for each subset of X.

    QED


    I think i am missing a crucial link in this proof, or maybe I messed it up altogether. You guys be the judge
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Characteristic functions
    Posted in the Advanced Statistics Forum
    Replies: 5
    Last Post: December 30th 2010, 01:54 AM
  2. Characteristic functions
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: May 16th 2010, 07:04 AM
  3. Characteristic functions
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: May 2nd 2010, 05:13 PM
  4. Characteristic functions
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: April 8th 2010, 10:55 AM
  5. questions on Characteristic functions
    Posted in the Calculus Forum
    Replies: 2
    Last Post: June 26th 2009, 09:21 PM

Search Tags


/mathhelpforum @mathhelpforum