Kenneth Rosen Edition 6th Exercise 7.1 Question 41 (Page No. 473)

Question

How many of the 16 different relations on {0,1} contain the pair (0,1)?

Answer 1

$Let \ $ $A=\left \{ 0,1 \right \}\\ A \times A=\left \{ (0,0),(0,1),(1,0),(1,1) \right \}$

$A \ relation \ on \ a \ set \ A \ is \ the \ subset \ of \ A\times A.$

$Number \ of \ relation=2 \times 2 \times 2 \times 2=16$

$R_{1}=\left \{ \right \}\\ R_{2}=\left \{ (0,0) \right \}\\ R_{3}=\left \{ (0,1) \right \}\\ R_{4}=\left \{ (1,0) \right \}\\ R_{5}=\left \{ (1,1) \right \}\\ R_{6}=\left \{ (0,0),(0,1) \right \}\\ R_{7}=\left \{ (0,0) ,(1,0)\right \}\\ R_{8}=\left \{ (0,0),(1,1) \right \}\\$

$R_{9}=\left \{ (0,1),(1,0) \right \}\\ R_{10}=\left \{ (0,1),(1,1) \right \}\\ R_{11}=\left \{ (1,0),(1,1)\right \}\\ R_{12}=\left \{ (0,0),(0,1),(1,0)\right \}\\ R_{13}=\left \{ (0,0),(0,1),(1,1)\right \}\\ R_{14}=\left \{ (0,0),(1,0),(1,1)\right \}\\ R_{15}=\left \{ (0,1),(1,0),(1,1)\right \}\\ R_{16}=\left \{ (0,0),(0,1),(1,0),(1,1)\right \}\\$

$Number \ of \ relation \ contains \ the \ pair \ (0,1)=8$

$Alternate \ method :- $

$Let \ $ $A=\left \{ 0,1 \right \}\\ A \times A=\left \{ (0,0),(0,1),(1,0),(0,0) \right \}$

$A \ relation \ on \ a \ set \ A \ is \ the \ subset \ of \ A\times A.\\$

$Total \ number \ of \ relation=2 \times 2 \times 2 \times 2=16 \\$

$Relation \ which \ does \ not \ include \ pair \ (0,1)=2 \times 2 \times 2=8$

$Number \ of \ relation \ contains \ the \ pair \ (0,1) = \ Total \ relation \ - \ Relation \ which \ does \ not \ contains \ pair \ (0,1)$

                                                                $ = 16-8$

                                                                 $=8$

Comments

@ LeenSharma Small typo (0,0) two times in A X  A. Great answer btw.

Answer 2

First, let's consider how we get $16$ relations on $\{0, 1\}$.

A relation is just a set of ordered pairs $(a, b)$. For a set with $n$ elements, the total number of ordered pairs is $n^2$. And for each of those $n^2$ pairs, either it can be in the relation or not. Therefore, the total number of different relations possible on a set with $n$ elements is $2^{number\_of\_ordered\_pairs}$, i.e $2^{n^2}$.

Therefore, for a set with $2$ elements $\{0, 1\}$, total number of relations = $2^{2^2}$ = $16$.

Now it is given that out of those $2^2$ ordered pairs of {0, 1}, the pair $(0, 1)$ should be present in the relation. Hence it had no choice of not being in the relation.

Therefore we are now left with $2^2 - 1 = 3$ ordered pairs which can either be in the relation or not, i.e. each of these $3$ pairs have 2 choices. This gives us the answer $2^3$ = 8.