# Relations

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/relations

## Binary Relations

A **binary relation** $R$ is a subset of ordered pairs from a set, written $a\,R\,b$ to show elements are "related." They underlie databases, graphs, and ordering.

Three core properties classify relations:

| Property | Definition | Example |
| --- | --- | --- |
| **Reflexive** | $a\,R\,a$ for all $a$ | "is equal to" |
| **Symmetric** | If $a\,R\,b$, then $b\,R\,a$ | "is a sibling of" |
| **Transitive** | If $a\,R\,b$ and $b\,R\,c$, then $a\,R\,c$ | "is less than" |

**Common pitfall:** Do not confuse **symmetric** with **transitive**. Symmetry reverses a single pair, while transitivity chains two pairs. "Is one mile from" is symmetric, but walking one mile twice doesn't put you two miles away from the start.

## Special Relations

Abstract properties let us reason without knowing the specific items. Two combinations matter most:

- **Equivalence relation**: Reflexive, symmetric, _and_ transitive. It behaves like "sameness" and **partitions** the set into disjoint **equivalence classes** of mutually related elements. Example: "same remainder mod 5."
- **Partial order**: Reflexive, transitive, and **antisymmetric** (if $a\,R\,b$ and $b\,R\,a$, then $a = b$). It captures "ordering" like $\le$ or subset inclusion, where some elements are incomparable.

**Pitfall:** A relation can easily possess one property without the others. Never assume a reflexive relation is also symmetric or transitive.

## Practice questions

5 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Congruence mod 5 partitions the integers into exactly five classes, while "less than or equal to" partitions nothing. Both are reflexive and transitive. What does the third property decide?

A. Transitivity, which congruence has and less-than-or-equal-to lacks.
B. Symmetry versus antisymmetry: one groups, the other arranges.
C. The size of the underlying set, since only finite sets can be partitioned.
D. Whether the relation is defined by a formula, which congruence is and ordering is not.

**Answer:** B. Symmetry versus antisymmetry: one groups, the other arranges.

**Why:** Congruence is symmetric, so relatedness is mutual and a group of mutually related elements has no internal direction, a clump. Ordering is antisymmetric, so the relation runs one way and arranges rather than groups. Reflexive+symmetric+transitive gives a partition; reflexive+antisymmetric+transitive gives a hierarchy. Which you have decides what you can do.

Page: https://tryals.app/practice/computer-science-i/relations/congruence-mod-5-partitions-the-integers-into-exactly-five-classes

### 2. Task dependencies form a partial order and topological sort produces a valid build order. Why does the algorithm need a *partial* order rather than a total one?

A. Because total orders cannot be sorted algorithmically
B. Because partial orders permit cycles, which build systems need
C. Because most tasks are genuinely incomparable
D. Because a total order would require every task to depend on every other

**Answer:** C. Because most tasks are genuinely incomparable

**Why:** Most pairs of tasks have no relationship, and a partial order says so, which is exactly the information a build system exploits to run them in parallel. A total order would invent constraints that do not exist. Option 4 has it backwards: a cycle means a circular dependency, which is the error a build tool reports.

Page: https://tryals.app/practice/computer-science-i/relations/task-dependencies-form-a-partial-order-and-topological-sort-produces

### 3. You are handed an unfamiliar relation and want to know whether it partitions its set into classes. Order the checks, from the one that rules out the most to the one that settles it.

**Answer:**

1. Does every element relate to itself? If not, some element belongs to no class.
2. Is relatedness mutual? If a relates to b but not the reverse, the grouping has a direction and is not a partition.
3. Does relatedness chain? If a to b and b to c leaves a and c unrelated, the classes would overlap without merging.
4. All three hold, so the relation is an equivalence and its classes partition the set.

**Why:** The three properties are checked in increasing order of effort, and each failure has its own consequence.

Reflexivity failing means an element belongs to no class at all, so no partition exists - and it is a single glance to check.

Symmetry failing means the relation has a direction, which produces a hierarchy rather than a grouping; that is a partial order, useful and not a partition.

Transitivity failing is the subtle one, and "is one mile from" is the standard counterexample: symmetric, reflexive if you allow zero distance, and A a mile from B and B a mile from C says nothing about A and C. The classes would have to overlap without merging, which a partition forbids.

Only when all three hold do the classes come out disjoint and exhaustive - which is exactly the argument the equivalence-relation theorem makes.

Page: https://tryals.app/practice/computer-science-i/relations/you-are-handed-an-unfamiliar-relation-and-want-to-know-whether-it

### 4. R is the relation 'has the same remainder when divided by 4' on the integers. Select every pair of numbers that R actually relates.

A. 3 and 15
B. 5 and 10
C. 12 and 20
D. 6 and 9
E. 7 and 11

**Answer:** A. 3 and 15; C. 12 and 20; E. 7 and 11

**Why:** 7 and 11 both leave 3; 12 and 20 both leave 0; 3 and 15 both leave 3. But 6 leaves 2 while 9 leaves 1, and 5 leaves 1 while 10 leaves 2, so those pairs are unrelated. Equivalently, the related pairs are exactly those whose difference is divisible by 4, which is why the relation partitions the integers into four classes.

Page: https://tryals.app/practice/computer-science-i/relations/r-is-the-relation-has-the-same-remainder-when-divided-by-4-on-the

### 5. Because 'divides' is transitive on the positive integers, knowing 3 divides 12 and 12 divides 60 is enough to conclude 3 divides 60.

**Answer:** True

**Why:** True. Transitivity is exactly the licence to chain: $a \mid b$ and $b \mid c$ give $a \mid c$, so $3 \mid 12$ and $12 \mid 60$ settle $3 \mid 60$ without dividing. Chaining like this is what lets a Hasse diagram omit every implied edge and draw only the covering relations, the transitive ones are recoverable.

Page: https://tryals.app/practice/computer-science-i/relations/because-divides-is-transitive-on-the-positive-integers-knowing-3