Results 1 to 4 of 4

Thread: 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
    5
    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 $\displaystyle S$ of a set $\displaystyle X$ is a function defined on $\displaystyle X$ which takes the value $\displaystyle 1$ for any element $\displaystyle s \in S$ and $\displaystyle 0$ otherwise.

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

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

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

    where $\displaystyle \chi_D$ is the charateristic function of $\displaystyle 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 $\displaystyle A \neq B$, and assume, without loss of generality, that $\displaystyle |A|>|B|$. Then there is some $\displaystyle x \in A$ such that $\displaystyle x \notin B$. Thus, for such an $\displaystyle x$, $\displaystyle Q_A(x) = 1$ while $\displaystyle Q_B(x) = 0$. Thus their do not have the same characteristic function.

    For the reverse implication, we use a direct proof. Assume $\displaystyle A = B$. If $\displaystyle A = B = \emptyset$ then the result is immediate, since for any element $\displaystyle x \in X$ we have $\displaystyle Q_A = Q_B = 0$. Assume $\displaystyle A = B \neq \emptyset$. Let $\displaystyle x \in X$ be an element that is in A. Then $\displaystyle Q_A(x) = 1$. But since A = B, we have $\displaystyle x \in B$, so $\displaystyle Q_B(x) = 1$ as well. Let $\displaystyle y \in X$ be an element such that it is not in A, then $\displaystyle Q_A(x) = 0$. But since A = B, we have that $\displaystyle y \notin B$, so $\displaystyle 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 $\displaystyle x \in X$, we have $\displaystyle Q_A(x) = 0$ or $\displaystyle Q_A(x) = 1$, but whatever the value of $\displaystyle 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 $\displaystyle |Y|^{|X|}$. Let $\displaystyle n$ be the number of elements in X. Since |Y| = 2, we have the number of possible functions from X to Y being $\displaystyle 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: Dec 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: Apr 8th 2010, 10:55 AM
  5. questions on Characteristic functions
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Jun 26th 2009, 09:21 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum