Welcome to our community

Be a part of something great, join today!

A tricky logic word problem? Any help?

bootleg

New member
Oct 23, 2013
1
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 (Speechless)
Any help would be much appreciated!
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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.