Wednesday, September 14, 2011

Relations continued

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 itself¹. 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$.

total²

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)³, (t), and total.

The "divides" relation on $\mathbb{N} \backslash \{0\}$⁴: $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 singleton^why?. 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?

1.2.2Partitions¶

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$⁵$\{ 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.