# A tricky logic word problem? Any help?

#### bootleg

##### New member
Preparing for an upcoming midterm and this is one of the practice questions from an old test.

The Question:
Let X be a set with n elements, say S = {s1, s2,..., sn}
Let B be the set of binary numbers with n digits. That is, sequences of n terms, each
of which is 0 or 1.

Define f : P(S) --> B (power set of S) as follows: the image of X ∈ P(S) is the
binary sequence b1b2....bn where bi is the truth value of the statement bi ∈ X, for
i = 1, 2, ..., n.

Prove that f is a 1-1 correspondence.

My Work so far:

If A1 = A2 = An, there are n-try relation and A is a subset of An = A x A x ... x A = {(a1,, a2, ..., an) iai + A for each i = 1, ...,n}

Prove: that there are n-tuples.

I am not sure where to go from here, or if my work is heading in the right direction Any help would be much appreciated!

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Preparing for an upcoming midterm and this is one of the practice questions from an old test.

The Question:
Let X be a set with n elements, say S = {s1, s2,..., sn}
Let B be the set of binary numbers with n digits. That is, sequences of n terms, each
of which is 0 or 1.

Define f : P(S) --> B (power set of S) as follows: the image of X ∈ P(S) is the
binary sequence b1b2....bn where bi is the truth value of the statement bi ∈ X, for
i = 1, 2, ..., n.

Prove that f is a 1-1 correspondence.

My Work so far:

If A1 = A2 = An, there are n-try relation and A is a subset of An = A x A x ... x A = {(a1,, a2, ..., an) iai + A for each i = 1, ...,n}

Prove: that there are n-tuples.

I am not sure where to go from here, or if my work is heading in the right direction
Any help would be much appreciated!
Welcome to MHB, bootleg! To prove a 1-1 relation, you need to prove that for every element in P(S) there is a unique associated element in B, and also that for every element in B there is a unique associated element in P(S).

If you take any subset of S, it determines a number in B uniquely, as per the definition of your f.
Each number in B consists of n values of either 0 or 1. If we construct a set with exactly those $s_i$ that have a corresponding 1 in the number from B, we get a unique set that is an element of P(S).
Therefore the relation is 1-1.