Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Do you know the definition of reflexive, symmetric, transitive? –  Pedro Tamaroff May 23 '13 at 17:21
    
Is $\{1\}\mathrel{\mathcal{R}}\{1\}$? Is $\{1\}\mathrel{\mathcal{R}}\{2,3\}$? Is $\{2,3\}\mathrel{\mathcal{R}}\{4\}$? Is $\{1\}\mathrel{\mathcal{R}}\{4\}$? –  egreg May 23 '13 at 17:30
5  
"I need help with relations" Don't we all. –  Austin Mohr May 23 '13 at 17:33
add comment

1 Answer

up vote 4 down vote accepted

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$.

share|improve this answer
    
Thank you, that really helps –  Maria May 23 '13 at 18:09
    
@Maria: You’re welcome. –  Brian M. Scott May 23 '13 at 18:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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