Can You Solve This Set Theory and Binary Number Problem?

  • Context:
  • Thread starter Thread starter bootleg1
  • Start date Start date
  • Tags Tags
    Logic Word problem
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
1 reply · 2K views
bootleg1
Messages
1
Reaction score
0
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!
 
Physics news on Phys.org
bootleg said:
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.