Wednesday, September 14, 2011 CC-BY-NC
Relations continued

Maintainer: admin

1Properties of relations

A relation $R$ on $A$ is $R \subseteq A \times A$. Such a relation can be:

(r) - reflexive
on $A$ if $aRa$ for all $a \in A$. Not intrinsic to the relation - depends on the choice of $A$.
(ir) - irreflexive
on $A$ if $aRa$ for no $a \in A$. Note that it's not a negation of the above - to say that a relation is not reflexive means that no $a \in A$ is related to itself, while a relation that is not reflexive just has to have one $a \in A$ that is not related to itself1. Irreflexivity is an intrinsic property, meaning that no $a \in A$ is related to itself for any $A$confirm?.
(s) - symmetric
if whenever $aRb$, then $bRa$.
(as) - antisymmetric
if whenever $aRb$ and $bRa$, then $a = b$. Not the negation of the above - a relation can be both symmetric and antisymmetric (or neither?). So basically $aRb$ and $bRa$ never happens when $b \neq a$. That's it.
(t) - transitive
if whenever $aRb$ and $bRc$, then $aRc$.
For any $a, b \in A$, $aRb$ or $bRa$ (or both) or $a = b$.

1.1Some example relations

On $\mathbb{R}$, the $\leq$ relation is (r), not (ir), not (s), (as), (t), and total.

The $<$ relation is not (r), (ir), not (s), (as)3, (t), and total.

The "divides" relation on $\mathbb{N} \backslash \{0\}$4: $m \mid n$ (where $m$ is typically the smaller one, the one "doing the dividing") if $n$ is divisible by $m$ (so if $m$ is a factor of $n$, or if there is a $k \in \mathbb{N}$ such that $m \cdot k = n$). This relation is (r), not (ir), not (s), (as), (t), not total.

On any set $A$, let $R = A \times A$ (so everything is related to itself). This set is (r), not (ir) unless $A = \varnothing$, (s), not (as) unless A has zero or one elements, (t), and total.

On $A \neq \varnothing$, $R = \varnothing$: not (r), (ir), (s) due to material implication, (as) also due to material implication, (t) again, and not total unless $A$ is a singleton or the empty set.

$\iota_A = \Delta_A = \{(a, a): a \in A\}$ (the diagonal, or identity relation basically): (r), not (ir) unless $A = \varnothing$, (s), (as), (t), not total unless $A$ is the empty set or a singletonwhy?. Note that a relation on $A$ is only going to be both (s) and (as) if it is a subset of $\iota_A$.

1.2Equivalence relations

A relation $R$ is called an equivalence relation on $A$ if it is (r), (s), and (t).

The largest equivalence relation on $A$ is $A \times A$, while the smallest is $\iota_A$.Add something about birthdays?

An example: let $R = \{(a, b): 3 \mid | a- b|,\, a, b \in \mathbb{N} \}$. So $aRa$ since $3 \mid 0$ (alternatively, since $a - a = 0 = 3k$ for $k=0$), meaning the relation is reflexive. It's also transitive: $aRb$ and $bRc$, then $a - b = 3k$ and $b -c = 3l$ ($k, l \in \mathbb{Z}$), and so $a - c = 3 (k + l)$ and so $aRc$ where the integer is $k + l$. And it's also symmetric as well, due to the symmetry of the absolute value function. So this is an equivalence relation. We could have used any $n \in \mathbb{N}$ except 0, actually, instead of 3. 1 would have worked too, although that's a special case that has some additional properties.

A real-world example: Loveys takes the 80 bus every day. He doesn't care which bus he takes, as long as it's going along the correct route. So there is an equivalence relation on routes, based on the numbers. So an equivalence relation really just means that things have something in common.

1.2.1Equivalence classes

Notation: $a / E$ or $[a]_E$ is the set $\{x \in A: aEx \}$ (so a subset of $A$).

In the total $(A \times A)$ relation, there is only one equivalence class. In the $\iota_A$ relation, each equivalence class is $\{x\}$, the singleton. So the number of equivalence classes is equal to the size of the set.

For the $3 \mid |a - b|$ relation, there are three different equivalence classes. Each class would contain numbers that differ by a multiple of 3. For example, one class would contain $0, 3, 6, 9 ...$, another would contain $1, 4, 7, 10 ...$ and the last would contain $2, 5, 8, 11 ...$.

Proposition: $[a]_E = [b]_E \iff aEb$.
Proof: Suppose $[a]_E = [b]_E$. Then $b \in [b]_E$ (by (r)). So $b \in [a]_E$. Hence $a Eb$.
Conversely, suppose $aEb$ and $c \in [a]_E$. So $aEc$. By (s), $bEa$, so $bEc$ by (t), so $c \in[b]_E$. Suppose $d \in [b]_E$. So $b E d$; $aEb$, so $aEd$ by (t), so $d \in [a]_E$. So $[a]_E = [b]_E$. Lol no idea

Another way to say it: if $[a]_E \cap [b]_E \neq \varnothing$, then they're equal. Why? Say $c \in [a]_E \cap [b]_E$. So $aEc$ and $bEc$. So $cEb$ by (s). So $a E b$ by (t). So every element is in exactly one equivalence class? What?


A partition $\Pi$ of $A$ is a collection of nonempty subsets of $A$, such that every element of $A$ is in just one of the sets in $\Pi$.

The sets in a partition $\Pi$ are called the parts. Given that $\Pi$ is a collection of subsets of $A$, $\Pi$ is a partition if and only if:

  1. for $P_1, P_2 \in \Pi, P_1 \neq P_2 \to (P_1 \cap P_2 \neq \varnothing)$
  2. $\bigcup$5$\{ P_1, P_2 ... \in \Pi \} = A$

An equivalence relation gives rise to a partition, and vice versa.

Suppose $\Pi$ is a partition of $A$. Define $E_{\Pi}$ on $A$ by $aE_{\Pi}b $ if and only if they're in the same part.

For example: an equivalence relation on gender, in this classroom. Two students are in the same class if and only if they have the same gender. So there are two parts - $\{M\}$, and $\{F\}$.

N.B.: $aE_{\Pi_E}b$ are in the same part if they're related by $E$ (i.e. $a Eb$. So $E_{\Pi_E} = E$. And, $\Pi_{E_{\Pi}} = \Pi$. Lol.

  1. Note: only the empty set is both (r) and (ir). 

  2. No cute little shortcut, like the others. 

  3. Because the premise is never true - we never have $aRb$ and $bRa$. So by material implication, the relation is antisymmetric. 

  4. Incidentally, 0 is divisible by everything, and divides nothing, while 1 is divisible by nothing, and divides everything. 

  5. Join all the things in the set with $\cup$