Math Help - characteristic functions and sets

1. 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...

2. Originally Posted by r7iris
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...

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

3. Originally Posted by r7iris
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

4. Originally Posted by r7iris
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