Relations

Based on 21-127 Concepts of Mathematics

A relation applies to a set and talks about how elements in that set are related.

Formally, let there be set $X$ and a relation $R$ on the set $X$. Then $R$ is a declaration for each pair $(a, b) \in X^2$ as to whether they are related or not. If $a$ is related to $b$, we write $a \mathrel{R} b$, otherwise we write $a \\ \mathrel{\not R} \\ b$.

This is similar to the Pure Math - Functions. Basically, we consider relations to be equal iff they relate the same pairs of elements (duh). Symbolically, $R$ and $S$ on $X$ are equal iff $\forall a, b \in X, (a \mathrel{R} b \Leftrightarrow a \mathrel{S} b)$.

Let there be set $X$ and a relation $R$ on the set $X$. The graph of $R$ is the set of pairs $(a, b) \in X^2$ such that $a \mathrel{R} b$. That is, $$\mathrm{Gr}(R) = { (a,b) \in X^2 \mid a \mathrel{R} b } \subseteq X^2$$
Relations are always well defined :)

Another way to define relation equality, therefore, is to say that they have the same graph:
$$R = S \Leftrightarrow \mathrm{Gr}(R) = \mathrm{Gr}(S)$$
where $R$ and $S$ are relations on $X$.

We can have relation $E$ with $\mathrm{Gr}(E) = \varnothing$. This is the same thing as saying nothing is related.

Let $R$ be a relation on $X$. $R$ can have these properties

Reflexivity: $R$ is reflexive if $\forall x \in X, x \mathrel{R} x$. That is, every element is related to itself

Symmetry: $R$ is symmetric if $\forall a, b \in X, (a \mathrel{R} b) \Leftrightarrow (b \mathrel{R} a)$. That is, relation always go in two directions.

Antisymmetry: $R$ is antisymmetric if $\forall a, b \in X, (a \mathrel{R} b \wedge b \mathrel{R} a) \Rightarrow (a = b)$. That is, things related in both direction are equal.

Transitivity: $R$ is transitive if $\forall a,b,c \in X, (a \mathrel{R} b \wedge b \mathrel{R} c) \Rightarrow (a \mathrel{R} c)$. Think of it as we can somehow chain relations.

The usual strategy is just to show the relation satisfy a property.

An equivalence relation is a relation that is reflexive, symmetric, and transitive. (Note it could be antisymmetry too)

Given equivalence relation $\sim$ on $X$ and element $x \in X$, we can create a set of all elements that $x$ is related to by $\sim$. We call this a equivalence class. This set $[a]_{\sim}$ is defined by ${ a \in X \mid a \sim x }$.

Notice that this means the same equivalence class could be represented using different element of $X$, which we call representatives. Take the set ${ 0, 1, 2, 3 }$ and the relation $\equiv_{2}$, then $[0]{\equiv{2}} = [2]{\equiv{2}} = { 0,2 }$ and $[1]{\equiv{2}} = [3]{\equiv{2}} = { 1,3 }$.

The quotient is defined as $X/{\sim} = { U \subseteq X \mid \exists a \in X, U = [a]_{\sim} }$ viz. the set of all equivalence classes.

Lemma: equivalence in the set $X$ $\Leftrightarrow$ equality of equivalence class in $X/{\sim}$. Symbolically, $\forall a, b \in X, (a \sim b)\Leftrightarrow([a]{\sim} = [b]{\sim})$. (The proof should be straightforward)

Theorem: each equivalence relation $\sim$ on $X$ corresponds with a unique partition of $X$, namely $\mathscr{S} = X/{\sim}$. Proof omitted.

An partial order relation is a relation that is reflexive, not symmetric, antisymmetric, and transitive. (They behave like $\leq$ or $\subseteq$, and their symbol often look like $\leq$ or $\subseteq$).

Let $\preceq$ be a partial order relation on $X$ and $A \subseteq X$.

An upper bound for $A$ under $\preceq$ is an element in $X$ that is “greater” than all elements in $A$. That is, $u \in X$ s.t. $\forall a \in A, a \preceq u$.

An lower bound for $A$ under $\preceq$ is an element in $X$ that is “lower” than all elements in $A$. That is, $l \in X$ s.t. $\forall a \in A, l \preceq a$.

The supremum for $A$ under $\preceq$ is the “least” upper bound. That is, $\mathrm{sup}_{\preceq}(A) = s \in X$ such that $(\forall a \in A, a \preceq s) \wedge (\forall u \in X, (\forall a \in A, a \preceq u) \Rightarrow (s \preceq u))$ viz. it’s an upper bound and it’s “less” than all other possible upper bounds.

The infimum for $A$ under $\preceq$ is the “greatest” lower bound. That is, $\mathrm{inf}_{\preceq}(A) = i \in X$ such that $(\forall a \in A, i \preceq a) \wedge (\forall l \in X, (\forall a \in A, l \preceq a) \Rightarrow (l \preceq i))$ viz. it’s a lower bound and it’s “greater” than all other possible lower bounds.

Useful: The supremum of ${ X, Y }$ under $\subseteq$ where $X, Y$ are sets is equal to $X \cup Y$. The infimum is $X \cap Y$.

Completeness axiom: for all subset $X$ of $\mathbb{R}$, $X$ has an upper bound implies it has a supremum. Simile for infimum. Think about why.

Uniqueness theorem: if a infimum exists, it’s unique; if a supremum exists it’s unique. This comes straight out of definition of the mums and antisymmetry of the partial order relation.