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