Relations Reference
Relations
A relation records which pairs of elements are connected; its properties reveal structure such as equivalence classes or an ordering.
Solved Examples
Jump directly to a worked example by type.
Fact Table
| Idea | Meaning | Use or Check |
|---|---|---|
| Relation | A relation on $A$ is a subset of $A\times A$. | A pair $(a,b)$ in the relation can be written $aRb$. |
| Reflexive | Every element is related to itself. | For each $a$, require $aRa$. |
| Symmetric | Related pairs work in both directions. | If $aRb$, then $bRa$. |
| Antisymmetric | Two-way related elements must be equal. | If $aRb$ and $bRa$, then $a=b$. |
| Transitive | A relation chains through an intermediate element. | If $aRb$ and $bRc$, then $aRc$. |
| Equivalence relation | Reflexive, symmetric, and transitive. | Its equivalence classes partition the set. |
| Partial order | Reflexive, antisymmetric, and transitive. | Some pairs may be incomparable. |
Content Formulas
Equivalence Modulo $m$
$$a\equiv b\pmod m\quad\Longleftrightarrow\quad m\mid(a-b)$$
Equivalence Class
$$[a]=\{x\in A:x\sim a\}$$
Partial Order
$$\text{reflexive}\land\text{antisymmetric}\land\text{transitive}$$
Symmetric and antisymmetric are different properties: symmetry allows a two-way link between distinct elements, while antisymmetry does not.
Classic Examples
Classify the Usual Order
On the integers, define $aRb$ when $a\le b$. Which relation properties does it have?
Solution Steps
- Check whether every integer is related to itself.
- Check reversing a pair, chaining two pairs, and the two-way condition.
It is reflexive because $a\le a$.
It is transitive because $a\le b$ and $b\le c$ imply $a\le c$.
It is antisymmetric because $a\le b$ and $b\le a$ imply $a=b$.
It is not symmetric; for example, $2\le3$ but $3\not\le2$. It is a partial order.
Find an Equivalence Class
On the integers, define $a\sim b$ when $a\equiv b\pmod 3$. Identify the class of 1.
Solution Steps
- Congruence modulo 3 is reflexive, symmetric, and transitive.
- List integers with remainder 1 when divided by 3.
$$[1]=\{\ldots,-5,-2,1,4,7,\ldots\}$$
The three equivalence classes are grouped by remainders 0, 1, and 2.
Use Divisibility as an Order
On the positive integers, define $aRb$ when $a\mid b$. Is this a partial order?
Solution Steps
- Check reflexivity, antisymmetry, and transitivity.
- Use positive integers for the antisymmetry step.
Reflexive: $a\mid a$ because $a=a\cdot1$.
Transitive: if $b=ak$ and $c=bj$, then $c=a(kj)$.
Antisymmetric: if positive $a\mid b$ and $b\mid a$, then $a=b$.
Therefore divisibility is a partial order on the positive integers.