Power Set and String Bijection (Proof Verification)

Question

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 a₁,...,a_n be the n elements of A, and let s_kⁿ be the n'th character of string s_k ∈ S. Now define a mapping f from T to S where, for a given t_k ∈ T equal to (x_k, y_k):

s_k^j = 0 if a_j !∈ x_k ∧ a_j !∈ y_k

s_k^j = 1 if a_j ∈ x_k ∧ a_j !∈ y_k

s_k^j = 2 if a_j !∈ x_k ∧ a_j ∈ y_k

s_k^j = 3 if a_j ∈ x_k ∧ a_j ∈ y_k

Let f(t₁) = f(t₂) for t₁,t₂∈T. Then s₁ = s₂ so for each m'th character s₁^m = s₂^m and so a_m ∈ x₁ iff a_m ∈ x₂ and a_m ∈ y₁ iff a_m ∈ y₂. Thus, x₁=x₂ and y₁=y₂, so t₁ = t₂ and f is one-to-one.

Let s be an arbitrary element of S. Then for each s^k character of s, a_k is either an element of just x_k or y_k, 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.

Answer 1

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

Answer 2

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