# Power Set and String Bijection (Proof Verification)

I'm practicing my proof-writing and was hoping you could let me know if this proof looks good. I would like to know if the proof is incorrect, if there are parts that are overly wordy/complicated, or if I'm missing some element of a proof that is helpful to see, if not strictly necessary.

The Prompt (from here):

Let A be a set with n elements. Let T be the set of all ordered pairs (X, Y ) where X and Y are subsets of A. Let S be the set of 0/1/2/3 strings of length n. That is, elements of S are strings of length n where each character is 0, 1, 2, or 3. Give (and prove) a bijection between T and S. Conclude that T and S must be the same size.

My Proof:

Let a1,...,an be the n elements of A, and let skn be the n'th character of string sk ∈ S. Now define a mapping f from T to S where, for a given tk ∈ T equal to (xk, yk):

skj = 0 if aj !∈ xk ∧ aj !∈ yk

skj = 1 if aj ∈ xk ∧ aj !∈ yk

skj = 2 if aj !∈ xk ∧ aj ∈ yk

skj = 3 if aj ∈ xk ∧ aj ∈ yk

Let f(t1) = f(t2) for t1,t2∈T. Then s1 = s2 so for each m'th character s1m = s2m and so am ∈ x1 iff am ∈ x2 and am ∈ y1 iff am ∈ y2. Thus, x1=x2 and y1=y2, so t1 = t2 and f is one-to-one.

Let s be an arbitrary element of S. Then for each sk character of s, ak is either an element of just xk or yk, an element of neither, or an element of both. We can use this string to create the sets x and y such that there is a t = (x, y) such that f(t) = s. Thus f is onto.

Since we have an bijection from T to S, S must be the same size as T.

The argument is fine; the write-up has a few fairly small problems. First, $$n$$ has a fixed, defined value, so when you define $$s_k^n$$, youe actually defining only the last term of $$s_k$$. You should use an index variable that hasn’t already been given a fixed meaning; for instance, you could define $$s_k^j$$ to be the $$j$$-th character of the string $$s_k$$ for $$j=1,\ldots,n$$.

After the definition of $$f$$ you say:

• Let $$f(t_1)=f(t_2)$$ for $$t_1,t_2\in T$$. Then $$s_1 = s_2$$ . . .

You’re not actually letting $$f(t_1)$$ and $$f(t_2)$$ be equal: you’re supposing that they actually are equal, with the intention of deriving a contradiction. More important, you then make an assertion about entities $$s_1$$ and $$s_2$$ that have not yet been defined. Don’t make your reader work out from context what you intended them to be. A better way:

• Let $$s_1=f(t_1)$$ and $$s_2=f(t_2)$$, and suppose that $$s_1=s_2$$.

Then you can finish the proof that $$f$$ is injective pretty much as you did.

Your proof that $$f$$ is surjective is okay, though it could be made more explicit: you could actually construct $$x$$ and $$y$$ from $$s$$.

Here is how I might have written up essentially the same proof:

Define $$f:T\to S$$ as follows. For each $$\langle x,y\rangle\in T$$ let $$f(\langle x,y\rangle)=\langle u_1,u_2,\ldots,u_n\rangle$$, where

$$u_k=\begin{cases} 0,&\text{if }a_k\notin x\text{ and }a_k\notin y\\ 1,&\text{if }a_k\in x\text{ and }a_k\notin y\\ 2,&\text{if }a_k\notin x\text{ and }a_k\in y\\ 3,&\text{if }a_k\in x\text{ and }a_k\in y \end{cases}$$

for $$k=1,\ldots,n$$; clearly $$f(\langle x,y\rangle)\in S$$.

Let $$\langle u_1,\ldots,u_n\rangle\in S$$, and define $$x=\big\{a_k:u_k\in\{1,3\}\big\}$$ and $$y=\big\{a_k:u_k\in\{2,3\}\big\}$$; then $$\langle x,y\rangle\in T$$, and $$f(\langle x,y\rangle)=\langle u_1,\ldots,u_n\rangle\in S$$, so $$f$$ is surjective.

Finally, if $$f(\langle x,y\rangle)=\langle u_1,\ldots,u_n\rangle\in S$$ for some $$\langle x,y\rangle\in T$$, then necessarily $$x=\big\{a_k:u_k\in\{1,3\}\big\}$$ and $$y=\big\{a_k:u_k\in\{2,3\}\big\}$$, so $$f$$ is injective and therefore a bijection from $$T$$ to $$S$$.

I confess I didn't read your solution, but I would do it like this:

\begin{align} 0&= 00_2 \\ 1&=01_2\\ 2&=10_2\\ 3&=11_2\end{align}

Now, say $$n=3$$:

Say a pair of sets $$(X,Y)$$ where $$X= \{1,3\}$$ and $$Y= \{2,3\}$$ maps to $$(2,1,3)$$: $$(\{1,3\},\{2,3\})\mapsto (\color{red}{1},\color{blue}{0},\color{gold}{1};\color{red}{0},\color{blue}{1},\color{gold}{1}) \mapsto (\color{red}{10_2}, \color{blue}{01_2},\color{gold}{11_2}) = (2,1,3)$$

And vice versa, triple $$(0,2,1)$$ goes to $$(\{2\},\{3\})$$ $$(0,2,1) = (\color{red}{00_2}, \color{blue}{10_2},\color{gold}{01_2})\mapsto (\color{red}{0},\color{blue}{1},\color{gold}{0};\color{red}{0},\color{blue}{0},\color{gold}{1})\mapsto (\{2\},\{3\})$$