Here is my question:

Let $S$ be the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ and let $R$ be a relation on $S$ such that

for any $X, Y$ belonging to the power set of $S$, (I.E the set of all subsets of $S$),

$X R Y \iff X \cap Y \neq \emptyset$

My question is how many subsets $X$ are there in $S$ such that $X R A$, where $A = \{1,2\}$?

My first attempt was to think okay, Well lets just subtract the total amount of subsets there are in $S$, and subtract the total amount of $S$ that don't include $1$ or $2$. So I did:

$2^9 - 2^7$ $=$ $384$ subsets.

However, I'm worried about where my $2^7$ came from, I'm not sure if I can just delete $1$ and $2$ from $S$, and then count the total number of subsets without them in it. Could somebody verify or correct my method? Thank you.

  • 2
    $\begingroup$ You did rightt. $\endgroup$ – Hagen von Eitzen Apr 25 '18 at 1:17
  • $\begingroup$ $R$ is not a relation on $S$, it's a relation on the set of subsets of $S$. $\endgroup$ – Gerry Myerson Apr 25 '18 at 2:14

You are correct. One way to think about it is to build a subset, you can break it down into steps, going through each member of the original set and deciding whether it belongs to the subset. This means to count the number of subsets one can apply the product rule to find without restrictions there are $2^n$ subsets for a set with cardinality $n$. Using the same process, to find the number of subsets of S that do not contain a 1 or 2, using the product rule these have 1 choice, not in the subset. All of the other elements might or might not be in there so the number of subsets is $2^7$ as you determined.

  • $\begingroup$ Thank you for confirming, and thanks for the in depth answer. $\endgroup$ – MDS18 Apr 25 '18 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.