# Thread: 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 $\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

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 $\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

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 $\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

,
,
,

,

,

,

# charteristic fuction for set

Click on a term to search for related topics.