SECTION 4.1 Basics of Set Theory 201
1 0 1 0 1 0
0 1 0 1 0 0
1 0 1 0 1 0
0 1 0 1 0 0
1 0 1 0 1 0
0 0 0 0 0 1
.
In this example we see thatsRsfor alls∈S. You should have no
trouble in writing down all the correct relational expressionsxRy.(iv) Here’s one of my favorite examples. Let T 5 be the set of all 2-
element subsets of{ 1 , 2 , 3 , 4 , 5 }and define the relation RonT 5
by stipulating thatA 1 RA 2 ⇔A 1 ∩A 2 =∅. Can you compute|R|
in this example (see Exercise 3, below)? Can you reformulate this
in terms of an appropriate graph, havingT 5 as its set of vertices?(v) Define the relationRon the real lineRby stipulating thatxRy⇔
x−y∈Z. What are the elements related toπ?Let Rbe a relation on a setS. We say thatRis anequivalence
relationif the following three properties hold:
Risreflexive: sRsfor anys∈S;
Rissymmetric: s 1 Rs 2 ⇔s 2 Rs 1 , s 1 , s 2 ∈S;Ristransitive: s 1 Rs 2 ands 2 Rs 3 ⇒s 1 Rs 3 ,s 1 , s 2 , s 3 ∈S.Of the five examples given above, the relations (ii), (iii), and (v)
are equivalence relations. The relation given in (i) is neither reflexive
(sincex < x isfalse for all real numbers) nor is it symmetric (1< 2
but 2 6 <1). This relation is, however transitive (easy to check!). The
analysis of the remaining cases are left to the exercises.
Example (iii) is a bit different from the others, which warrant a few
extra words. Two (almost) obvious facts are the following: Since the
matrix has all 1s down the diagonal, this already proves the reflexivity
of the relation. Next, the matrix is symmetric which proves that the