44,029 views
Number of relations $S$ over set $\{0,1,2,3 \}$ such that $(x,y) \in S \Rightarrow x = y$

if we take subset  then it contains {  } too  and your  relation should contain only elements of form x=y  thats why i removed 1 from 16
Need to find total number of reflexive relations
Empty relation is also valid here because if (x,y) belongs to S become false so the implication become true ie (x,y) belongs to S => x = y become true.

So, this is an example of vacuous proof.

Only four pairs that satisfy the condition are: (0,0), (1,1), (2,2), (3,3).

Now the relation can include or leave each of these 4 pairs. Hence 2^4 ways.

For all other 12 possible pairs, the relation must leave them. Hence 1 way.

So no of relations = 2^4 × 1 = 16.

Note that the empty relation is also valid. In that case the condition is vacuously valid.

### 1 comment

The condition (x,y)∈S⇒x=y implies that every ordered pair in S must be equal. So how come (1,2) (2,3),(3,4) and other such pairs of different numbers can be taken in S? acc to me answer should be 4 only (0,0), (1,1), (2,2), (3,3).

where am i going wrong?

Answer is 2^4=16. The main confusion here is whether to include phi in the relation or not. well, we will count phi.

(x,y)∈S⇒x=y

clearly by law of implication, for some pair say (1,2) , if we try (1,2) ∈S but 1!=2. so this is T->F resulting in F. so (1,2) can not belong to S. now phi is an empty relation it has no element so for phi , (x,y)∈S fails and we know F->anything is True so Phi will be in the relation.

only four pairs namely (0,0),(1,1),(2,2),(3,3),and (4,4) are taken as these apir satisfy the condition x=y.

hence the nos relations which is the cartesian product are as follows like (x,y)

1                                                                     2                                    3                                 4    (y coordinate )

 (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,3) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4)

these are 16 relations which is equal to 2^4 .

1
749 views
1 vote