While I'm solving exercises in the book Discrete Mathematics and Its Applications | 8th Edition (Kenneth H. Rosen), I found a wrong answer.
The last question (51) in Section 2.1 Exercise is:
Q: Describe a procedure for listing all the subsets of a finite set.
A: Let S = {a1, a2, ..., an}. Represent each subset of S with a bit string of length n, where the ith bit is 1 if and only if ai ∈ S. To generate all subsets of S, list all $2^n$ bit strings of length n (for instance, in increasing order), and write down the corresponding subsets.
In the explanation, the part "where the ith bit is 1 if and only if ai ∈ S" is wrong because ai is always an element of S since we defined S as S = {a1, a2, ..., an}.
Therefore, if we actually try to solve the question using the answer,
The bit strings that are supposed to represent each subset of S become 1111 1111 .... 1111 no matter what elements a subset has.
For example, let's say there is a set S = {1, 2, 3}
Now, according to the question, I have to represent each subset of S with a bit string of length 3.
There are 8 subsets in total,
{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}
Now, the ith bit is 1 if and only if ai ∈ S. a1 = 1, a2 = 2, a3 = 3. Let's start with an empty set.
the 1st bit string of the set {} is 1 if and only if a1 ∈ S. Since a1 = 1 and S = {1, 2, 3}, it equally means that 1 ∈ {1, 2, 3}. Therefore, the 1st bit string of an empty set is 1 which is not true. In the end, regardless of the elements in each subset, the bit strings are all going to be 111 since 1 ∈ {1, 2, 3}, 2 ∈ {1, 2, 3} and 3 ∈ {1, 2, 3}.
Let's call the subset of S as s. Then, the answer should be "the ith bit string of the subset is 1 if and only if ai ∈ s"instead of ai ∈ S.
Is my interpretation correct?
