Example 1: Empty and universal relations in a boys' school

Basics you need

Solution

1. Picture the set of all pairs

   Every relation in A lives inside $A\times A$⁠. Imagine a table with one row and one column for each student; the cell in row $a$⁠, column $b$ stands for the ordered pair $(a,b)$⁠. A relation is a choice of which cells to fill in.

   $$\varnothing \;\subseteq\; R \;\subseteq\; A\times A \qquad\text{for every relation } R \text{ in } A.$$

   So the empty relation (no cells filled) is the smallest possible relation and the universal relation (all cells filled) is the largest. For a school of 500 boys, $A\times A$ has $500^2 = 250000$ pairs.

   Saying "$R$ is the empty relation" is a claim about which pairs belong to $R$⁠. Thinking of $R$ as a set of cells makes the two goals concrete: for $R$ we must show every cell stays blank; for $R'$ we must show every cell is filled, including the diagonal cells $(a,a)$⁠.
   A relation in A is, by definition, a subset of $A\times A$ (Section 1.2, first paragraph). The empty set is a subset of every set, and every set is a subset of itself, which is why $\varnothing$ and $A\times A$ are the two "extreme" relations.

2. $R$ is empty: no pair can satisfy "$a$ is sister of $b$"

   Take any pair $(a,b)\in A\times A$⁠. Then $a$ is a student of the school, and the school is a boys' school, so $a$ is a boy. A sister is, by the meaning of the word, female. So $a$ is not a sister of anybody, and in particular not of $b$⁠. Hence $(a,b)\notin R$⁠.

   Since the pair $(a,b)$ was arbitrary, no pair of A × A belongs to $R$⁠:

   $$R = \{(a,b)\in A\times A : a \text{ is sister of } b\} = \varnothing.$$

   So $R$ is the empty relation.

   To show a set is empty, we show that its membership condition is impossible to meet. The argument uses only one fact about $a$⁠, namely that $a$ is a student of a boys' school, and that fact is true of every element of A. That is what makes the argument cover all pairs at once. Note that we only needed to look at $a$⁠, the first entry: the rule fails because of who $a$ is, whoever $b$ may be.
   Definition 1: a relation is empty when no element of A is related to any element of A, that is $R = \varnothing$⁠. An argument about an arbitrary element proves a statement about all elements. Basics: how to prove and disprove

3. $R'$ is universal: every pair satisfies "heights differ by less than 3 m"

   Take any pair $(a,b)\in A\times A$⁠, and let their heights be $h_a$ and $h_b$ metres. Every human height is a positive number below 3 m (the tallest person ever reliably measured was about 2.72 m tall), so

   $$0 < h_a < 3 \qquad\text{and}\qquad 0 < h_b < 3.$$

   Subtracting, the difference lies strictly between $0 - 3$ and $3 - 0$⁠:

   $$-3 < h_a - h_b < 3, \qquad\text{that is}\qquad |h_a - h_b| < 3.$$

   So $(a,b)\in R'$⁠. Since the pair was arbitrary, every pair of A × A belongs to $R'$⁠:

   $$R' = A\times A.$$

   So $R'$ is the universal relation.

   The textbook calls this "obvious", and the reason is the bound above. Both heights sit inside the interval from 0 to 3 m, and two points inside an interval cannot be further apart than the interval is long. Precisely: from $h_a > 0$ and $-h_b > -3$⁠, adding gives $h_a - h_b > -3$⁠; from $h_a < 3$ and $-h_b < 0$⁠, adding gives $h_a - h_b < 3$⁠. Because this works for any two students, no cell of the table is left blank.
   Definition 2: a relation is universal when each element of A is related to every element of A, that is $R' = A\times A$⁠. Bounding a difference (Basic 5): if $0 < h_1, h_2 < M$ then $|h_1 - h_2| < M$⁠.

4. Do not forget the pairs $(a,a)$

   $A\times A$ also contains the pairs $(a,a)$ in which a student is paired with himself. Both relations behave correctly on these too:

   • $(a,a)\notin R$⁠: a boy is not his own sister (he is not anyone's sister).
   • $(a,a)\in R'$⁠: the difference between $a$'s height and itself is $0$⁠, and $0 < 3$⁠.
   Steps 2 and 3 already covered these pairs, because an arbitrary pair $(a,b)$ is allowed to have $b = a$⁠. Checking them explicitly is still worthwhile: a relation can only be universal if it contains every diagonal pair, so a rule such as "$a$ is taller than $b$" could never be universal (no one is taller than himself).
   An ordered pair $(a,b)$ in $A\times A$ may have equal entries. "Each element related to every element" (Definition 2) includes each element being related to itself.

5. Conclude

   $R = \varnothing$⁠, so $R$ is the empty relation (Definition 1). $R' = A\times A$⁠, so $R'$ is the universal relation (Definition 2). Both are trivial relations.

   These two relations are the boundary cases that motivate Definitions 1 and 2. Every other relation in A sits somewhere in between, with some cells filled and some blank.

Every fact used, and where it comes from