I need help with relations

73 Views Asked by At

Let $S$ be the power set $P({1,2,...,10})$; that is, $S$ is the set of all subsets of $\{1,2,\dots,10\}$. define the relation $\mathcal R$ on $S$ by:

For all subsets $A,B$ of $\{1,2,\dots,10\}$, $A\mathcal RB$ if and only if $A\cup B$ has exactly $3$ elements.

a) Is $\mathcal R$ reflexive? Symmetric? Transitive?
b) Find and simplify the number of subsets $A$ is contained in $\{1,2,\dots,10\}$ so that $A \mathcal R\{1,2,7\}$.
c) Find and simplify the number of subsets $A$ is contained in $\{1,2,\dots,10\}$ so that $A\mathcal R\varnothing$.

Any help would be appreciated seeing that I don't know where to start

1

There are 1 best solutions below

2
On BEST ANSWER

HINT: You can quite easily determine whether $R$ is reflexive, symmetric, or transitive directly from the definition.

  • Reflexive: If $A\subseteq\{1,\dots,10\}$, is it always true that $A\mathbin{R}A$? In other words, is it always true that $|A\cup A|=3$?

  • Symmetric: If $A,B\subseteq\{1,\dots,10\}$, and $A\mathbin{R}B$, is it always true that $B\mathbin{R}A$? In other words, if $|A\cup B|=3$, is it always true that $|B\cup A|=3$?

  • Transitive: If $A,B,C\subseteq\{1,\dots,10\}$, $A\mathbin{R}B$, and $B\mathbin{R}C$, is it always true that $A\mathbin{R}C$? In other words, if $|A\cup B|=3$, and $|B\cup C|=3$, must it be the case that $|A\cup C|=3$? What if $A=C=\varnothing$, for instance?

For the other parts of the question you should begin by trying to understand just how $R$ works. Consider the set $A=\{1,3,7,8\}$; is there any set $B\subseteq\{1,\dots,10\}$ such that $A\mathbin{R}B$? No: no matter what set you choose for $B$, $A\cup B$ is going to have at least $4$ elements, namely, the $4$ elements of $A$. Now what if $A=\{1,3,7\}$? If $B$ contains at least one element that is not already in $A$, $A\cup B$ is going to contain at least $4$ elements. Thus, the only hope of getting $A\mathbin{R}B$ is to have $B\subseteq A$, and that always works: in this case $A\mathbin{R}B$ if and only if $B\subseteq A$. Now what if $A=\{1,3\}$? In order to have $A\mathbin{B}$, $B$ must contain exactly one element that is not in $A$: $B$ must be of the form $X\cup\{b\}$, where $X\subseteq A$, and $b\in\{1,\dots,10\}\setminus A$.

It shouldn’t be too hard to extrapolate from these examples to be able to say for any $A\subseteq\{1,\dots,10\}$ exactly which $B\subseteq\{1,\dots,10\}$ satisfy $A\mathbin{R}B$, and once you’ve done that, it’s not very hard to count those sets $B$.