Relations

n

-ary relation

n

-ary relation on the sets

X_{1}, X_{2}, \dots, X_{n}

is a subset

R

of their cartesian product, where we say that the relation holds between

x_{1}, x_{2}, \dots, x_{n}

when

(x_{1}, x_{2}, \dots, x_{n}) \in R

Unary Relation

A unary relation

R

on X is a

1

-ary relation

Binary Relation

A binary relation $R$ is a $2$ -ary relation, when $(x, y) \in R$ , then we write $x R y$ to say that $x$ is related to $y$ .

Note: A binary relation on $X \times X$ is stated simply as a relation on $X$

The Reverse of a Binary Relation

Suppose that

R

is a binary relation then

rev (R) : = {(y, x) : (x, y) \in R}

set filtered by a relation

Suppose that

X

is a set, and that

R

is a unary relation on

X

, then we define

X^{R} : = {a \in X : a \in R}

reflexive relation

Given a binary relation

R

X

, we say it is reflexive when every element of

X

is related to itself. Symbolically

\forall x \in X, x R x

symmetric relation

Given a binary relation

R

X

, we say it is symmetric if the relation goes both ways, that is for any

x, y \in X

x R y

then

y R x

Anti-Symmetric Relation

Given a binary relation

R

X

, we say it is anti-symmetric when for any

x, y \in X

, if

x R y

and

y R x

we have that

x = y

Asymmetric Relation

Given a binary relation

R

X

, we say it is asymmetric when for any

x, y \in X

, if

x R y

then it's false that

y R x

Transitive Relation

Given a binary relation

R

X

, we say it is transitive if for any

x, y, z \in X

x R y

and

y R z

then

y R x

The Subset Relation Is Transitive

Suppose that

A, B, C

are sets, then if

A \subseteq B

and

B \subseteq C

then

A \subseteq C

Suppose that

a \in A

then

a \in B

and so

a \in C

as needed.

Equivalence Relation

An equivalence relation is a reflexive, symmetric and transitive relation

when $R$ is an equivalence relation, we denote it by $\sim$ instead of $R$

Connected Relation

Given a binary relation

R

X

, we say it is connected if for any

x, y \in X

x \neq y

then

x R y

y R x

Strongly Connected Relation

Given a binary relation

R

X

, we say it is strongly connected if for any

x, y \in X

x R y

y R x

Equivalence Class

Given an equivalence relation

\sim

an equivalence class is a complete set of equivalent elements, which we denote by

[x]

which is defined to be the set

{y \in X : y \sim x}

Equivalence Classes Are Either Equal or Disjoint

Suppose that

(X, \sim)

is an equivalence relation, then given

a, b \in X

then either

$[a] = [b]$
$[a] \cap [b] = \emptyset$

If it's the case that $p \in [a] \cap [b]$ then we know $a \sim p$ and $p \sim b$ therefore $a \sim b$ . Now given any $x \in [a]$ we see that $x \sim a \sim b$ so that $x \sim b$ so that $x \in [b]$ therefore $[a] \subseteq [b]$ , similarly given any $y \in [b]$ then $y \sim b \sim a$ so that $y \in [a]$ therefore $[b] \subseteq [a]$ so we have $[a] = [b]$

On the other hand if we know that $[a] \cap [b] = \emptyset$ then what we want to prove is certainly true.

A Set Is a Union of Its Equivalence Classes

Suppose that

(X, \sim)

is an equivalence relation, then

⋃_{a \in X} [a] = X

We know that the left-hand side is a subset, but then it is also a superset because given any point

p \in X

then

p \in [p]

so it must be in the union

The Set of Equivalence Classes Is a Partition of X

Suppose that

(X, \sim)

is an equivalence relation then the set

{[a] : a \in X}

is a partition of

X

We already know that they cover the set, so now suppose that

[a] \neq [b] \in X

then since they are not equal they are disjoint, as needed.

A Set Modulo an Equivalence Relation

Suppose that

(X, \sim)

is an equivalence relation and

P = {[p_{α}], α \in I}

a partition of

X

X ∖ \sim : = P

Sometimes people call this dividing, roughly speaking when you divide 20 objects into groups of 4, it's as if each collection of 5 elements became one, which is roughly what happens when you mod out by an equivalence relation.

Unpacking an Equivalence Class

Suppose that

(X, \sim)

is an equivalence relation then for any

p \in X

we define the almost trivial function

unpack ([p]) = p

The reason why we have the above definition is so that we can mod out by an equivalence relation, and then peel of the equivalence classes to end back up with elements of $X$ , in other words $unpack (X ∖ \sim) \subseteq X$ , is a collection of "representatives" in $X$ .

Congruences induce a Equivalence Relation

Fix

n \in ℕ_{1}

, then relation on

ℤ

a R b

if and only if

a % n = b % n

defines an equivalence relation

Given any $a \in G$ , then clearly $a % n = a % n$ so that $a R a$ , if $a R b$ , then $a % n = b % n$ and then $b % n = a % n$ , finally if $a % n = b % n$ and $b % n = c % n$ therefore $a % n = c % n$

Induced Equivalence Relation

Suppose that suppose that we have a relation on

X

, then we can extend it to an equivalence relation by adding the minimal number of tuples

(a, b)

to construct

R^{'}

so that

R^{'}

is an equivalence relation. We denote this by

\sim (R) = R^{'}

Partial Order

A partial order is a binary relation denoted by $\leq$ on a set $X$ such that $\leq$ is reflexive, anti-symmetric and transitive relation.

The Subset Relation Is a Partial Order

Suppose that

𝒳

is a set of sets, then

(𝒳, \subseteq)

is a partial order

It is true that for any set

X \in 𝒳

we have

X \subseteq X

, thus it is reflexive, also we know that if

A, B \in 𝒳

then if

A \subseteq B

and

B \subseteq A

we have

A = B

so it is anti symmetric, finally we already know it is transitive.

Strict Partial Order

A strict partial order is a binary relation denoted by

<

on a set

X

such that

<

is transitive and asymmetric.

Every Partial Order Admits a Strict Partial Order

Suppose that

(X, \leq)

is a partial order, then there exists a relation

<

such that

(X, <)

is a partial order such that

a < b ⟺ (a \leq b \land a \neq b)

Consider the partial order

(X, \leq)

, since

\leq

is a collection of tuples we just need to consider

< = \leq ∖ {(x, x) : x \in X}

Comparable

Suppose

R

is a partial order, then elements

a, b \in R

are said to be comparable if

a R b

b R a

, otherwise they are said to be incomparable

With the strict partial order $\subset$ we can see that ${1}$ and ${2}$ are incomparable.

Total Order

A total order is a partial order which is strongly connected.

Note that a total order is sometimes known as a simple order.

well order

A well order on a set

S

is a total order on

S

along with the property that every non-empty subset of

S

has a least element under this ordering

well ordering

Every set

X

can be well ordered

TODO

The Smallest Element of a Set is Unique

Supose that

(S, \leq)

is a partial order, then the smallest element is unique

Suppose that there are two smallest elements

a, b \in S

since

a

is the smallest then

a \leq b

and since

b

is the smallest then

b \leq a

by transitivity

a = b

and so the smallest element is unique.

Interval

Suppose that

(S, \leq)

is a partial order, then a subset

A \subseteq S

is defined to be an interval if:

\forall x, y \in A, \forall t \in S : x \leq t \leq y ⟹ t \in A .

and we denote

A = (x, y)

Intersection of Intervals

The intersection of any collection of intervals in a general ordered set is also an interval.

Let $ℐ$ be a collection of intervals in $S$ , let's prove $A : = ⋂ 𝒜$ is also an interval.

Suppose $x, y \in A$ and $x \leq t \leq y$ for some $t \in S$ . We must show that $t \in A$ . Since $x$ and $y$ are in $A$ , and $A$ is the intersection of all $A_{i}$ , it follows that: $x \in A_{i} and y \in A_{i} for all i \in I .$

Since each $A_{i}$ is an interval, for every $i \in I$ we have $x \leq t \leq y ⟹ t \in A_{i} .$ so that $t \in A_{i} for all i \in I$ consequently, $t \in ⋂_{i \in I} A_{i} = A$ .