Vtyjkyuk

Below is my restatement of the theorem 2.15 given in the book by K.D.Joshi, titled 'Foundations of Discrete Math.', on page#80; followed by issues in it.

Let $X$ be a finite set, & $P(X)$ is power set. Then $|P(X)| = 2^X$.

Let $mathbbZ_2$ be the set $0,1$.

Let $mathbbF$ be the set of all functions from $mathbbX$ to $mathbbZ_2$, so $|mathbbF| = 2^X$.

The co-domain of function $mathbbtheta$ is $mathbbF$, which itself consists of $2^X$ functions from $mathbbX$ to $mathbbZ_2$; while the domain of $mathbbtheta$ is $P(X)$.

The proof would be completed if could establish a bijection betn. $P(X)$ & $mathbbF$.

For this, define $mathbbtheta: P(X) rightarrow mathbbF$ as below.

If $A$ is a subset of $X$, we let $f_A: Xrightarrow mathbbZ_2$ be the characteristic function of $A$, defined by $f_A=1$ if $x in A$ & $f_A=0$ if $x notin A$.
We define $mathbbtheta(A)=f_A$.

Below would take an example to elaborate the above:
Let, $X=0,1,2,3$, with $P(X) = emptyset, 0, 1, 2, 3, 0,1, 0,2,0,3, 1,2, 1,3, 2,3, 0,1,2, 0,1,3, 0,2,3,
1,2,3, 0,1,2,3 .$
So, $, |P(X)| = 2^4=16.$

The set $mathbbZ_2$ is fixed, & the set $F$ is the set of all functions from $X to mathbbZ_2$ given by $16$ combinations listed below, as ordered pairs:

$1. (0, 0), (1, 0), (2, 0), (3, 0) $,

$2. (0, 0), (1, 0), (2, 0), (3, 1) $,

$3. (0, 0), (1, 0), (2, 1), (3, 0) $,

$4. (0, 0), (1, 0), (2, 1), (3, 1) $,

$,,,,vdots$

$15. (0, 1), (1, 1), (2, 1), (3, 0) $,

$16. (0, 1), (1, 1), (2, 1), (3, 1) $,


Each of the $16$ subsets, has $4$ ordered pairs, that forms the set $F$.

The characteristic function $f_A: Xrightarrow mathbbZ_2$ is used to identify if a subset $x$ of the domain is further a subset of $A$.

Explaining the above equivalence between $mathbbtheta(A)=f_A$:

Taking a typical element of the domain of $theta$, let the subset $A$, of the domain, then $theta(A): X to mathbbZ_2$. Let it be defined as the char. fn. of $A$. Thus $[theta(A)](x) = 1$ or $0$, according as $x in A$, or $x notin A$.

To show that $theta$ is a bijection, need show two parts :-

(i) $theta$ is a one-to-one function,

(ii) $theta$ is an onto function,

(i) Need show that if $theta(A) = theta(B)$, then $A =B$.

Let $x in A$, then $theta(A)(x)=1$. This implies $theta(B)(x)=1$, which further implies that $x in B$. So, $Asubset B$. Similarly, $Bsubset A$, & so $A=B$.

(ii) Let $f$ be a function from $Xto mathbbZ_2$, i.e. $f in mathbbZ_2^X$. So, need find some point in domain (let, $A in P(X))$ that maps to $f$ in co-domain, i.e. $theta(A)(x)=f$; i.e. $f$ equals the char. fn. of $A$. So, the only choice is $A = f^-1(1)$, with $Ain P(X)$ & so $f(x) = 1$

Q.1. How can the co-domain be a set of functions, rather than a set of values?
My understanding is that co-domain is a set of values mapped from domain.

Q.2. It is known to me that for a function, multiple values cannot be mapped from domain to co-domain; but it is unclear if same element of co-domain is only mappable by a single element in a function.

So, am not clear why such combinations as $0, 0, 1, 0 $ are not allowed in the above specification of members of $F$?

Q.3. What is the logic for (the proof being based on) finding equivalence(bijection) between the domain($P(X)$) & the co-domain ($F$)?
I mean that can I be given any simpler example to understand the equivalence(bijection) between domain & co-domain, in any other proof.

Q.4. In (i) above how it is concluded by : $(x in A)implies (x in B)$, that $Asubset B$?

Q.5. In (ii) above, how is it made sure that there would a point with value $1$ available after mapping from domain to co-domain . Is it made possible by numbering the set of all functions in the co-domain (i.e., $F$)?

*Update : - * On page #89 there is given exercise #2.14, that states an alternate way to prove theorem. It states :

Let the $n$ distinct elements of finite set $X$ be $x_1, x_2,cdots, x_n$. For each subset $A$ of $X$, we define a binary sequence $a_1, a_2,cdots, a_n$ in which $a_i =1$ or $0$ according as $x_iin A$ or $x_inotin A$. This gives a bijection between $P(X)$ & the set of all binary sequences of length $n$. Since there are $2^n$ such sequences, $|P(X)| =2^n$.

Is this proof significantly different from the proof given the text?

For each element $x_i$ of finite set $X$, there is assigned a value $a_i$ & for each subset $A$ of $X$, define a binary sequence that lists which element is present in the given subset.

So, now there are $2^n$ subsets of $X$ listed as before. That makes the proof same as before.

1. No. See the "definition" part of this. $f colon X to Y$ only requires $X,Y$ to be sets, regardless the kind of sets [number sets, function sets, etc.].


2. $f colon Bbb R to 0 $ maps all real numbers to $0$. This is a function of course. I do not see the meaning of groups $alpha, beta$, so maybe I need more information to explain.


3. If you are asking about constructing bijections, then no general rules for this. If you are asking why (i)(ii) gives the verification of bijective, then I could say that this is the definition of bijections. See the 1st paragraph of bijection.


4. One thing is that $A subset B$ is defined as "for all $x in A, x in B$".


5. The $f^-1$ in $f^-1(1)$ does not mean the inverse function of $f$. This is called the "pre-image" or "inverse image" [see the inverse image part]. We do not need to require there is a $x in A$ such that $f(x)=1$, if does not exist, then $f^-1(1) = varnothing in mathcal P(X)$. After the construction of this bijection, $F$ could be numbered.

UPDATE FOR Q2.

If those are the meanings of $alpha, beta$, then $F$ is not the list. Try do the same thing for $X = 0,1,2$ or $X= 0,1,2,3,4$, and I do not think you would get the right result.

In my opinion, the element of $F$ should look like
$$
(0,1), (1,1), (2,0), (3,0).
$$
I am using parentheses to indicate these are ordered pairs.

1. The domain and codomain has to be set but they are not restricted to set of integer. real/ complex values. For example $$f: textsun, moon, earth to textluffy, sanji$$

$$f(textearth) = textluffy ,f(textmoon) = textsanji, f(textearth)=textsanji$$

is a function.

2. Be careful when you use set notation, $0,0= 0$. I believe from your updates, this is resolved.




3. This is how typically cardinality is defined. We say two sets, $A$ and $B$ share the same cardinality if we can find a bijection from $A$ to $B$. Hence, if you have proven that $|B|$ is equal to a quantity and you want to show that $|A|$ share the same cardinality, we construct a bijection from $A$ to $B$ and we write that $|A|=|B|$. We use Theorem $2.14$ to conclude that $|F|=2^X$. Hence, we just need to construct a bijection from $P(X)$ to $F$.

Q $4$ and Q $5$, refer to the other solution.

Now that rather than a set of function, we have a set of finite binary sequence of length $n$. We denote the set of binary sequence as $G$. Let the way the mapping from a subset of $X$ to $G$ be $phi$.

(i) Need show that if $phi(A) = phi(B)$, then $A =B$.

Let $phi(A)= a_1, ldots, a_n$ and $phi(B)= b_1, ldots, b_n$.
Let $x_i in A$, then $a_i=1$. This implies $b_i=1$, which further implies that $x_i in B$. So, $Asubset B$. Similarly, $Bsubset A$, & so $A=B$

(ii) Let $a_1, ldots, a_n in G$. So, need find some point in domain (let, $A in P(X))$ that maps to $a_1, ldots, a_n$ in co-domain, i.e. $phi(A)=a_1, ldots, a_n$; So, the only choice is $A = bigcup_i=1, ldots n, a_i = 1 x_i $