# Counting Subsets of a relation $\mathcal R$

I'm studying for my discrete math final and my professor gives us practice questions but no solutions. Counting is not my forte so I was hoping you could check over my work, make sure my end result is correct and my explanation is sufficient. Any help is appreciated! Below is the question followed by my attempt.

Let $X = \{1, 2,... , 10\}$. Define the relation $\mathcal R$ on $X$ by: For all $a,b ∈ X, a\mathcal Rb$ if and only if $ab$ is even.

(a) Find and simplify the number of two-element subsets $S$ of $X$ that satisfy the following property: $∀a ∈ S, a\mathcal R1$. Explain.

First I let $T$ be the set of all $x \in X$ so that $a \mathcal R 1$. Then $T= \{2,4,6,8,10\}$ so then the question becomes, how many two element subsets of S are there, which would be ${5\choose2}=10$

(b) Find the number of subsets $S$ of $X$ (of any size) that satisfy the following property: $∀a \in S, ∃b∈S$ so that $a\mathcal Rb$. Explain.

Let $x,y \in \mathbb Z$. Then we have the following properties: If $x,y$ odd then $xy$ is odd. If $x,y$ even then $xy$ is even. If $x$ odd and $y$ even then $xy$ even. So for a set to satisfy the property above it must contain at least one even number. To get this I will calculate the total number of subsets of $X$ and subtract the number of subsets of $X$ which contain only odd numbers (that is, the number of subsets of $\{1,3,5,7,9\}$). So then the answer should be $2^{10}-2^5=992$

For part (b) I have counted the empty set in my final answer but I'm unsure if it would actually satisfy the property..

Your first answer is correct. The $S$ are precisely the sets where both elements are even. For the second part, notice that the $S$ are just the subsets of $X$ that contain an even element. The only subsets that don't contain an even element are subsets of $\{1,3,5,7,9\}$, of which there are $2^5 = 32$. Then there are $| P(X) | - 2^5 = 2^{10}-2^5$ ' sets containing an even.
EDIT: The second part of my answer is incorrect, the empty set does indeed vacuously satisfy the property. That is because its negation states there exists an $x \in S$ such that for all $y \in S$ we have $x \not R y$. Since we are dealing with the empty set, there is no such $x$. The correct number of $S$ is then $2^{10}-2^5+1$.
• +1: I'm pretty sure you don't mean "contrapositive" here. Another way you can formulate it, though, is $$(a\in S)\implies(\exists b\in S:a\:\mathcal R\:b).$$ Since the antecedent is false for $S=\emptyset,$ the implication is vacuously true. – Cameron Buie Dec 18 '15 at 4:04
• Ah! That's what you were getting at. In that case, it should say $\neg(x\:\mathcal R\: y),$ instead. – Cameron Buie Dec 18 '15 at 4:34