1. What is a set

What is a set?

Set

A set is a collection of things, any things, called its elements.

Link to original

If $S$ is a set and $x$ is an element in $S$, then $x\in S$. If $x$ is not an element in $S$, then $x\notin S$. If both $x\in S$ and $y\in S$, then $x,y\in S$.

To describe a set:

• We can explicitly name its elements.

  We can form the set $A$ by collecting three things:

  Minecraft, League, ETS2

  Any set defined this way is denoted by listing its elements, separated by commands, surrounded by braces:

  $$A=\{\text{Minecraft, League, ETS2}\}$$

• Anything can be an element of a set.

  A set can be an element of another set.

  For example, the set $B=\{x,\{x,y\}\}$ has two elements:

  • One element is $x$.
  • The other element is the set $\{x,y\}$.

  In this case we can write $x\in B$ and $\{x,y\}\in B$.

Important Features of Sets

The only thing we consider is what is in and isn’t in the set.

• Repeated occurrences don’t matter $\{H,E,L,L,O\}$ and $\{H,E,L,O\}$ describe the same set. It is more ergonomic to only display each once.

• Order of listing doesn’t matter $\{H,E,L,O\}$ and $\{E,H,L,O\}$ describe the same set.

Special sets

Empty set

An empty set is a set with no elements, it is denoted by $\{\}$ or more commonly referred to by the symbol $\boxed \emptyset$.

The empty set has no elements so no matter what $x$ denotes, $x\notin \varnothing$.

Although, an empty set can be an element of another set, $\varnothing \in \{a,\varnothing ,Joe\}$ or $\varnothing \in \{\varnothing \}$.

Link to original

Singleton

A singleton is any set with only one element. For example, $\{a\}$ and $\{Monday\}$ are both singletons.

Link to original

Equality of sets

Two sets are equal if they contain the same elements.

We can denote this by $A=B$. If two sets are not equal, we write $A\ne B$.

Link to original

2. Describing sets by properties

Describing sets by properties

Finite set

A finite set is a set that has a finite number of elements. We can informally define it as a set which one could count and finish counting.

Link to original

Infinite set

An infinite set is a set which is not a [[Finite set|finite set]], there is no definitive end.

Examples include:

• Set of all integers

  $\mathbb{Z}=\{...,-3,-2,-1,0,1,2,3,...\}$ is the set of all integers.

  Link to original

• Set of natural numbers

  $\mathbb{N}=\{0,1,2,3,...\}$ is the set of all natural numbers.

  Link to original

• Set of positive natural numbers

  ${\mathbb{N}}^{+}=\{1,2,3,...\}$ is the set of all positive natural numbers, or otherwise all positive integers.

  Link to original

• Set of rational numbers

  $\mathbb{Q}=\{\frac{m}{n},...\}$ is the set of rational numbers, any number that can be expressed as $\frac{m}{n}$ for some integers $m$ and $n \ne 0$.

  Link to original

• Set of real numbers

  $\mathbb{R}=\{-1,0,1,\pi ,\sqrt{2}...\}$ is the set of real numbers, which includes all rational and irrational numbers.

  Link to original

• Set of positive real numbers

  ${\mathbb{R}}^{+}=\{1,2,\pi ,...\}$ is the set of positive real numbers.

  Link to original

Link to original

Set builder notation

Describing a set by listing is not ideal, we can instead describe a property that the elements of the set satisfy.

If $\mathcal{P}$ is a property, then the set $S$ whose elements hold this property is denoted by:

$$\begin{array}{rl}S& =\{x|x\text{ has property }\mathcal{P}\}\\ & =\{x|P(x)\}\end{array}$$

$S$ is the set of all $x$ such that $x$ has property $\mathcal{P}$.

If we know that all elements in $S$ come from a larger set $A$:

$$S=\{x\in A|x\text{ has property }\mathcal{P}\}$$

For example, let $\text{Odd}$ be the set of all odd integers, we can describe this in a number of different ways:

$$\begin{array}{rl}\text{Odd}& =\{...,-5,-3,-1,1,3,5,...\}\\ & =\{x|x\text{ is an odd integer}\}\\ & =\{x\in \mathbb{Z}|x\text{ is odd}\}\\ & =\{x|x=2k+1\text{ for some integer }k\}\\ & =\{x|x=2k+1\text{ for some }k\in \mathbb{Z}\}\\ & =\{2k+1|k\text{ is an integer}\}\\ & =\{2k+1|k\in \mathbb{Z}\}\end{array}$$Link to original

4. Describing sets by recursion

Describing sets by recursion

Recursive set description

A recursive description of a set $S$ consists of three steps: ?

• Basis step: Specify one or more elements of $S$.
• Recursive step: Give one or more rules to construct new elements of $S$ from existing elements of $S$.
• Exlusion rule: State that $S$ consists only of the elements that are specified by the basis step, or generated by successive applications of the recursive step. Nothing else is in the $S$. (This step is usually assumed rather than explicitly stated)

Link to original

title: Example 1
The set $\mathbb N$ of natural numbers can be defined recursively:
- **Basis step**: $0 \in \mathbb N$
- **Recursive step**: If $n \in \mathbb N$ then $n + 1 \in \mathbb N$
 
Eventually, by this rule, we will find each and every number in the set.

title: Example 2
The set $\text{Odd}$ of odd numbers can be defined recursively:
- **Basis step**: $813 \in \mathbb N$
- **Recursive step**: If $n \in \text{Odd}$ then $n + 2 \in \text{Odd}$ and $n - 2 \in \text{Odd}$

title: Example 3
The set $A = \{ 3k + 1 | k \in \mathbb N \}$ can be defined recursively:
- **Basis step**: $1 \in A$
- **Recursive step**: If $x \in A$ then $x + 3 \in A$
 
This is processed as so:
- $k = 0 \rightarrow 1 \in A$
- $k = 1 \rightarrow 4 \in A$
- $k = 2 \rightarrow 7 \in A$

title: Example 4
The set $F$ of all formulas of propositional logic can be defined recursively:
- **Basis step**: every propositional variable is in $F$
- **Recursive step**: If $p \in F$ and $q \in F$, then $(\neg p) \in F$, $(p \land q) \in F$, $(p \lor q) \in F$, $(p \rightarrow q) \in F$ and $(p \iff q) \in F$.

Link to original

5. Subsets

Subsets

Subset

A set $B$ is a subset of a set $A$ if every element of $B$ is also an element of $A$. Notation is $\boxed{B \subseteq A}$.

Venn diagram of $B\subseteq A$

Link to original

For example:

• $\{a,c\}\subseteq \{a,b,c,d\}$
• $\{0,1,5\}\subseteq \mathbb{N}$
• $\mathbb{N}\subseteq \mathbb{Z}$
• $\mathbb{N}\subseteq \mathbb{N}$

We always have, for every set $S$: $\boxed{S\subseteq S}$ and $\boxed{\varnothing \subseteq S}$

Proper subset

$B$ is a proper subset of $A$, $\boxed{B\subset A}$, if $B$ is a subset of $A$ and there is some element in $A$ that is not in $B$. Essentially, $B \subset A$ if $B \subseteq A$ but $B \neq A$.

Link to original

title: Example 1
Let $A = \{ x | x \text{ is a prime number and } 42 \leq x \leq 51 \}$.
Let $B = \{ x | x = 4k + 3 \text{ and } k \in \mathbb N \}$.
 
**Show that $A \subseteq B$.**
We need to show that every element in $A$ is also in $B$.
Prove that $\forall x(x \in A \rightarrow x \in B)$
 
Take an **arbitrary** $x \in A$, then $x$ is a prime number and $42 \leq x \leq 51$,
so we either have $x = 43$ or $x = 47$.
 
- We can have $43 = 4 \times 10 + 3$, so $k = 10$ shows that $43 \in B$.
- We can have $47 = 4 \times 11 + 3$, so $k = 11$ shows that $47 \in B$.
 
$\therefore A \subseteq B$

title: Example 2
Using $A$ and $B$ from above.
 
**Show that $A \subset B$.**
We know that $A \subseteq B$, so we just need to find an element $x \in B$ that $x \notin A$.
For example, $x = 3$:
- As $0 \in \mathbb N$ and $3 = 4 \times 0 + 3$, we have $3 \in B$.
- Although $42 \nleq 3$, so we have $3 \notin A$.
 
$\therefore A \subset B$

title: Example 3
Let $A = \{ 3k + 1 | k \in \mathbb N \}$.
Let $B = \{ 4k + 1 | k \in \mathbb N \}$.
 
**Show that $A \nsubseteq B$.** ($A$ is not a subset of $B$)
Prove that $\neg \forall x (x \in A \rightarrow x \in B)$
 
We need to find a counterxample: an element $x \in A$ such that $x \notin B$.
For example, $x = 4$:
- $4 = 3 \times 1 + 1$ so $k = 1$ shows $4 \in A$.
- We need to show that $4 \notin B$, that is, there is no $k \in \mathbb N$ such that $4 = 4k + 1$.
  If $k = 0$, then $4k + 1 = 4 \times 0 + 1 = 1 \neq 4$.
  If $k \geq 1$, then $4k + 1 \geq 4 \times 1 + 1 = 5 \ge 4$.
  So it is not possible to fina a $k \in \mathbb N$ such that $4 = 4k + 1$, and so $4 \notin B$.
 
$\therefore A \nsubseteq B$

Link to original

6. Equality of sets, powersets

Equality of sets

How to prove $A=B$ or $A\ne B$

$\boxed{A=B}$ means that the sets $A$ and $B$ have the same elements. This is the statement of the form $\forall x(x\in A⟺x\in B)$.

$$A=B⟺A\subseteq B\text{ and }B\subseteq A$$ $$A\ne B⟺A⊈B\text{ and }B⊈A$$

If we need to show that $\boxed{A=B}$ then:

• We need to show both $\boxed{A\subseteq B}$ and $\boxed{B\subseteq A}$.

If the task is to show that $\boxed{A\ne B}$ then:

• We either need to find an element in $A$ that is not in $B$ or an element in $B$ that is not in $A$.

Powersets

Power set

The power set, $\boxed{P(S)}$, is the set of all subsets of a set $S$. So $P(S) = \{ A | A \subseteq S \}$.

As every set $S$ will always have $\varnothing \subseteq S$ and $S\subseteq S$, then $\boxed{\varnothing \subseteq P(S)}$ and $\boxed{S\subseteq P(S)}$ will always be true.

Link to original

Examples:

• $P(\{u,v,w\})=\{\varnothing ,\{u\},\{v\},\{w\},\{u,v\},\{v,w\},\{w,u\},\{u,v,w\}\}$
• $P(\{\text{Among, Us}\})=\{\varnothing ,\{\text{Among}\},\{\text{Us}\},\{\text{Among, Us}\}\}$
• $P(\{s,u,s\})=\{\varnothing ,\{s\},\{u\},\{s,u,s,u,s\}\}$
• $P(\mathbb{N})=\{X|X\subseteq \mathbb{N}\}$ We can say $\{123,96,3\}\in P(\mathbb{N})$, $\{2,81\}\in P(\mathbb{N})$ or $\varnothing \in P(\mathbb{N})$. But $\{123,-300\}\notin P(\mathbb{N})$, $\{\frac{5}{3}\}\notin P(\mathbb{N})$ and $\{\varnothing \}\notin P(\mathbb{N})$.

Link to original

7. Set operations

Set operations

Union

Set operation (Union)

The union of sets $A$ and $B$, $A\cup B$, is the set $$ A \cup B = \{ x | x \in A \text{ (inclusive)} \text{ or } x \in B \} $$

$A\cup B$ consists of elements in either $A$ or $B$ or both.

Venn diagram of $A\cup B$

For example, let $A=\{4,7,8\}$ and $B=\{10,4,9\}$. Hence, $A\cup B=\{4,7,8,9,10\}$.

Properties of union

• Identity law (Sets)

  The identity law is that $A\cup \varnothing =$ $A$.

  Link to original

• $A\subseteq B⟺A\cup B=B$

Link to original

Intersection

Set operation (Intersection)

The intersection of sets $A$ and $B$, $A\cap B$, is the set $$ A \cap B = \{ x | x \in A \text{ and } x \in B \} $$

$A\cap B$ consists of elements in both $A$ and $B$.

Venn diagram of $A\cap B$

For example, let $A=\{4,7,8\}and$B = { 10, 4, 9 }. Hence $A\cap B=\{4\}$.

Disjoint

Disjoint sets are sets with no common elements, $A \cap B = \emptyset$.

Link to original

Properties of intersection

• The domination law states that $A\cap \varnothing =\varnothing$.
• $A\subseteq B⟺A\cap B=A$

Link to original

Difference / Complement

Set operation (Difference)

The difference of sets $A$ and $B$, $A-B$, is the set $$ A - B = \{ x | x \in A \text{ and } x \notin B \} $$

$A-B$ consists of those elements that are in $A$ but not in $B$. This can also be called the complement of $B$ with respect to $A$.

Venn diagram of $A-B$

For example, let $A=\{4,7,8\}$ and $B=\{10,4,9\}$. Hence $A-B=\{7,8\}$ and $B-A=\{10,9\}$.

Properties of complementation

• Complementation laws (Sets)

  There are complementation laws that say that:

  • $A\cup \bar{A}=U$
  • $A\cap \bar{A}=\varnothing$
  • $\overline{\stackrel{ˉ}{A}}=A$
  • $\bar{U}=\varnothing$
  • $\bar{\varnothing }=U$

  Link to original

• De Morgan's law (Sets)

  The De Morgan’s law can be represented in sets as so: ?

  • $\overline{A\cup B}=\bar{A}\cap \bar{B}$
  • $\overline{A\cap B}=\bar{A}\cup \bar{B}$

  Link to original

• $A-B=A\cap \bar{B}$
• $A\subseteq B⟺\bar{B}\subseteq \bar{A}$

Link to original

Absolute complement

Set operation (Absolute complement)

Sometimes we may consider all sets as being subsets of some given universal set, $U$.

Given a universal set $U$ and $A\subseteq U$, the complement of $A$, $\bar{A}$, is the set $$ \begin{aligned} \bar A &= U - A \\ &= \{ x \in U | x \notin A \} \end{aligned} $$

Venn diagram of $\bar{A}$

Link to original

Common Laws

• Commutative law (Sets)

  The commutative law says that $A\cup B=$ $B \cup A$ and $A \cap B = B \cap A$.

  Link to original

• Associative law (Sets)

  The associative law says that $(A\cup B)\cup C=A\cup (B\cup C)$ and that $(A\cap B)\cap C=A\cap (B\cap C)$.

  We can meaningfully write, $A\cup B\cup C$ or ${\bigcup }_{i=1}^n{A}_i$.

  Similarly, we can also write, $A\cap B\cap C$ or ${\bigcap }_{i=1}^n{A}_i$.

  Link to original

• Idempotent law (Sets)

  The idempotent law says that $A\cup A=$ $A$ and $A \cap A = A$.

  Link to original

• Distributive laws (Sets)

  There are two distributive laws: ?

  • $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
  • $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

  Link to original

Link to original

8. Two exercises about sets

Two exercises about sets

title: Example 1: Prove that, for any $X$, $Y$ and $Z$, we always have $X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)$.
 
We need to show both:
1. $X \cap (Y \cup Z) \subseteq (X \cap Y) \cup (X \cap Z)$
1. $(X \cap Y) \cup (X \cap Z) \subseteq X \cap (Y \cup Z)$
 
We need to show both of these using no assumptions on the sets and their elements, using only properties of set properties union and intersection.
 
Hence:
1. We need to show every element of $X \cap (Y \cup Z)$ is also an element of $(X \cap Y) \cup (X \cap Z)$.
 
   Take an arbitrary element $x \in X \cap (Y \cup Z)$.
   This element is both $x \in X$ and $x \in Y \cup Z$.
   So the element can either be $x \in X \cap Y$ or $x \in X \cup Z$.
   Hence, $x \in (X \cap Y) \cup (X \cap Z)$.
 
2. We need to show every element of $(X \cap Y) \cup (X \cap Z)$ is also an element of $X \cap (Y \cup Z)$.
 
   Take an arbitrary element $x \in (X \cap Y) \cup (X \cap Z)$.
   This element can either be $x \in X \cap Y$ or $x \in X \cap Z$.
   In both cases, $x \in X$ but it can either be $x \in Y$ or $x \in Z$.
   Hence, $x \in X \cup (Y \cap Z)$.

title: Example 2: Show that there are sets $A$ and $B$ such that $A \cup \bar B \neq \bar A \cup B$.
 
We can have an infinite amount of solutions here, we just need to pick any two partially overlapping sets of numbers.
 
Let the universal set, $U = \{ 1, 2, 3 \}$.
Let $A = \{ 1 \}$ and $B = \{ 2 \}$.
 
Hence:
- $\bar A = \{ 2, 3 \}$
- $\bar B = \{ 1, 3 \}$
- $A \cup \bar B = \{ 1, 3 \}$
- $\bar A \cup B = \{ 2, 3 \}$
 
Therefore there are sets $A$ and $B$ such that $A \cup \bar B \neq \bar A \cup B$.

Link to original

9. Sequences, Cartesian product of sets

Sequences

Sequence

A sequence is a list of things, taken in a certain order. $$ \begin{array}{c} (1, 2, 3, -3, 8) \\ (\text{Among, Us, Impostor}) \end{array} $$

Unlike sets, they are instead denoted using brackets instead of braces.

Important features of sequences: ?

• Order of list matters. $(1,2,3)$ and $(3,2,1)$ are different sequences.
• Repeated occurrences matter. $(H,E,L,O)$ and $(H,E,L,L,O)$ are different sequences.

Link to original

Tuple

A tuple is a finite [[Sequence|sequence]].

Two tuples are equal if they have the same length and their corresponding elements are the same:

$$\boxed{(x_1,x_2,...,x_k)=(y_1,y_2,...,y_n)}\text{ means that }k=n\text{ and that }{x}_1=y_1\text{ and so on...}$$Link to original

k-Tuple

A $k\text{-tuple}$ is a sequence with $k$ elements, the number $k$ is called the length of the tuple.

Ordered pair

An ordered pair is another name for a $2\text{-tuple}$, $$ \boxed{(a, b) = (c, d)} \text{ means that } a = c \text{ and } b = d $$

Link to original

Link to original

Cartesian product of sets

Cartesian product of sets

The Cartesian product of sets $A$ and $B$ is the set $$ A \times B = \{ (x, y) | x \in A \text{ and } y \in B \} $$

$A\times B$ consists of ordered pairs $(x,y)$ where $x\in A$ and $y\in B$.

For example, let $A=\{1,2\}$ and $B=\{a,b,c\}$. Hence, $A\times B=\{(1,a),(2,a),(1,b),(2,b),(1,c),(2,c)\}$.

Generic Format

The Cartesian product of sets $A_1,A_2,...,A_k$ is the set $$ A_1 \times A_2 \times ... \times A_k = \{ (x_1, x_2, ..., x_k) | x_i \in A \text{ for } i = 1, 2, ..., k \} $$

$A_1\times A_2\times ...\times A_k$ consists of those $k\text{-tuples }(x_1,x_2,...,x_k)$ where $x_1\in A_1,x_2\in A_2,..$

Link to original

Link to original

10. Relations

Relations

Binary relation

Binary relation

For sets $A$ and $B$, a (binary) relation from $A$ to $B$ is any subset $R$ of the [[Cartesian product of sets|Cartesian product]] $A \times B$ or otherwise a set consisting of some ordered pairs.

We use notation $\boxed{aRb}$ to denote that $(a,b)\in R$, and say that $a$ is $R$-related to $b$. If $(a,b)\notin R$, then we right $\boxed{a\cancel{R}b}$.

Link to original

For example, let $P$ be the set of people, and $C$ be the set of Among Us crewmates. Define a relation $\text{Suspicious\_of}$ by taking

$$\text{Suspicious\_of}=\{(x,y)\in P\times C|x\text{ is suspicious of }y\}$$

If I am suspicious of Red but think Blue is a crewmate, then

$$(\text{insert, Red})\in \text{Suspicious\_of}\text{ but }(\text{insert, Blue})\notin \text{Suspicious\_of}$$

This can also be written as

$$\text{insert Suspicious\_of Red}\text{ and }\text{insert }\cancel{\text{Suspicious\_of}}\text{ Blue}$$

Relations on a set

Relation on a set

A relation from a set $A$ to $A$ itself is called a relation on $A$.

It can also be said that:

• a relation on a set $A$ is a subset of $A\times A$
• a relation on a set $A$ is a set consisting some ordered pairs of elements from $A$

Link to original

For example, let $A$ be the set of all people in the class.

$$\begin{array}{rl}{R}_1& =\{(u,v)\in A\times A|u\text{ likes }v\}\\ R_2& =\{(u,v)\in A\times A|u\text{ is taller than }v\}\end{array}$$

Will is 180cm tall and likes Jill who is 165cm. But Jill does not like Will. Hence, $(\text{Will, Jill})\in R_1$, $(\text{Will, Jill})\in R_2$, $(\text{Jill, Will})\in R_1$ and $(\text{Jill, Will})\in R_2$.

Relations on the set $Z$ of integers

• ‘smaller than’: $<=\{(x,y)\in \mathbb{Z}\times \mathbb{Z}|x\text{ is smaller than }y\}$
  • $5$ is smaller than $25$, so $(5,25)\in <$ or more commonly $5<25$
  • $10$ is not smaller than $2$ so $(10,2)\notin <$ or more commonly $10\nless 2$
• ‘smaller than or equal to’: $\le =\{(x,y)\in \mathbb{Z}\times \mathbb{Z}|x\text{ is smaller than or equal to }y\}$
  • $-1\le -1$
  • $1\nleqq 0$
  • $<\subset \le$
• ‘divisibility’: $\text{div}=\{(x,y)\in \mathbb{Z}\times \mathbb{Z}|x\text{ divides }y\}$
  • $(1,25)\in \text{div}$
  • $(6,3)\notin \text{div}$

Link to original

11. Representing relations

Representing relations

Let $A=\{1,2,3,4\}$ and take the following relation $R$ on $A$:

$$R=\{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,4),(3,3)\}$$

$R$ can be represented by a directed graph:

digraph G {
  1->1,2,3,4
  2->1,2,4
  3->3
}

Alternatively we can use a 0-1 matrix:

$$\begin{array}{cc}& \begin{array}{cccc}1& 2& 3& 4\end{array}\\ \begin{array}{c}1\\ 2\\ 3\\ 4\end{array}& \left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 0& 1\\ 0& 0& 1& 0\\ 0& 0& 0& 0\end{array}\right]\end{array}$$Link to original

12-15,17. Properties of relations

Properties of relations

Reflexive relations

Reflexive relation

A relation $R$ on a set $A$ is called a reflexive, if $(a, a) \in R$ for every element $a \in A$, in effect everything loops.

For example:

• Reflexive: $R_1=\{(1,1),(1,2),(3,1),(2,2),(3,3)\}$ on $\{1,2,3\}$ Each element refers to itself.

  digraph G {
  	1->1
    1->2
    3->1
    2->2
    3->3
  }

• Reflexive: $\le$, $\ge$, $=$ Each and every number is lesser than or equal to, greater than or equal or equal to itself.

• Reflexive: ‘divisibility’ on ${\mathbb{N}}^{+}$ Each and every number is divisible by itself.

• Not reflexive: $R_2=\{(1,1),(1,2),(3,1)\}$ on $\{1,2,3\}$ Not every element refers to itself.

  digraph G {
  	1->1
    1->2
    3->1
  }

Link to original

Irreflexive relations

Irreflexive relation

A relation $R$ on a set $A$ is called irreflexive if $(a,a) \notin R$ for every element $a \in A$, in effect there are no loops.

For example:

• Irreflexive: $<$, $>$, $\ne$ on $\mathbb{N}$ or on $\mathbb{Z}$ Elements do not refer to themselves.

• Irreflexive: $R_3=\{(1,2),(1,3),(2,1),(3,2)\}$ on $\{1,2,3\}$

  digraph G {
  	1->2
    1->3
    2->1
    3->2
  }

title: Not all "not reflexive" relations are irreflexive!
**Not irreflexive**: $R_2 = \{ (1,1), (1,2), (3,1) \}$ on $\{ 1,2,3 \}$
Some elements refer to themselves.
 
```graphviz
digraph G {
  1->1
  1->2
  3->1
}

Link to original

Symmetric relations

Symmetric relation

A relation $R$ on a set $A$ is called symmetric, if for all elements $a, b \in A$, $(b,a) \in R$ whenever $(a, b) \in R$. In effect, all relations must be mirrored.

For example:

• Symmetric: $R_1=\{(1,1),(1,2),(2,1),(2,3),(3,2),(3,3)\}$ on $\{1,2,3\}$ All pairs of elements have the same properties in both directions.

  digraph G {
  	1->1
    1->2
    2->1
    2->3
    3->2
    3->3
  }

• Symmetric: $R_2=\{(1,1),(2,2),(3,3)\}$ on $\{1,2,3\}$ All pairs of elements have the same properties in both directions.

  digraph G {
  	1->1
    2->2
    3->3
  }

• Symmetric: $\{(x,y)\in \mathbb{N}\times \mathbb{N}|x-y\text{ is divisible by }3\}$ on $\mathbb{N}$

• Not symmetric: $R_3=\{(1,1),(1,2),(2,1),(3,1),(3,3)\}$ on $\{1,2,3\}$ Not all pairs of elements have the same properties in both directions.

  digraph G {
  	1->1
    1->2
    2->1
    3->1
    3->3
  }

Link to original

Antisymmetric relations

Antisymmetric relation

A relation $R$ on a set $A$ is called antisymmetric, if $(a, b)$ and $(b, a)$ cannot both be in $R$ unless $a = b$.

(it also does not mean $(a,a)$ should be in $R$)

This is also not opposite to symmetric, instead it means that you can go one way but you cannot come back unless if you’re going from an element to itself.

For example:

• Antisymmetric: $<$, $>$, $leq$, $geq$ on $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ or $\mathbb{R}$.

• Antisymmetric: $R_1=\{(1,1),(1,3),(2,3),(3,3)\}$ on $\{1,2,3\}$ You can go one way but not the other.

  digraph G {
  	1->1
    1->3
    2->3
    3->3
  }

• Antisymmetric (also symmetric): $R_2=\{(1,1),(2,2),(3,3)\}$ on $\{1,2,3\}$ You can go one way but not the other.

  digraph G {
  	1->1
    2->2
    3->3
  }

• Not antisymmetric: $R_3=\{(1,1),(1,2),(2,1)\}$ on $\{1,2\}$ There are bi-directional paths here.

  digraph G {
    1->1
  	1->2
    2->1
  }

Link to original

Transitive relations

Transitive relation

A relation $R$ on a set $A$ is called transitive, if the following hold, for all elements $a,b,c\in A$: $$ \text{If both } (a, b) \in R \text{ and } (b, c) \in R \text{ then } (a, c) \in R $$

In the directed graph representing $R$, $R$ is transitive, if every two-step journey along arrows can be done in one step. For example:

• The following graphs are not transitive:

  digraph A {
  	x->y
    y->z
    z->w
    x->z
  }
   
  digraph B {
  	x->y
    y->z
    z->w
    x->z
    x->w
  }

• The following graph is transitive:

  digraph B {
  	x->y
    y->z
    z->w
    x->z
    x->w
    y->w
  }

• Transitive: $<$, $>$, $\le$, $\ge$ on $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$ For example, if $a<b$ then $b<c$ and so on…

• Transitive: $R_1=\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}$ on $\{1,2,3,4\}$

  digraph B {
  	1->1
    1->2
    1->3
    2->2
    2->3
    3->3
  }

• Transitive: $R_2=\{(3,4)\}$ on $\{3,4\}$ We cannot show it’s not transitive, since we only have one one-step journey.

  digraph B {
    3->4
  }

• Not transitive: $R_3=\{(1,1),(1,2),(2,1)\}$ on $\{1,2\}$

  digraph B {
    1->1
    1->2
    2->1
  }

Link to original

Transitive closure

Transitive closure

Given that $R$ is a relation on a set $A$. The transitive closure of $R$ is the smallest transitive relation on $A$ containing $R$. We denote the transitive closure of $R$ by $\boxed {R^*}$.

If $R$ is already transitive, then $R^{\ast }=R$.

For example, given the following definition of $R$, we find $R^{\ast }$:

digraph A {
	label="R"
	x->y
	y->z
	z->w
	x->z
}
digraph B {
	label="R*"
	x->y
	y->z
	z->w
	x->z
	x->w
	y->w
}

Given $R$, we can define the transitive closure, $R^{\ast }$, recursively: ?

• Basis step: $R\subseteq R^{\ast }$ The pairs in $R$ are all in $R^{\ast }$.
• Recursive step: If $(a,b)\in R^{\ast }$ and $(b,c)\in R^{\ast }$ then $(a,c)\in R^{\ast }$. We add the missing pairs step by step.

Warshall’s algorithm

Warshall's algorithm

Algorithm

An algorithm is a finite sequence of precise step-by-step instructions.

Link to original

Warshall’s algorithm computes the matrix of the transitive closure $R^{\ast }$ of $R$. ?

• Given a relation $R$ on a set $A$ with $n$ elements, we begin with its $n\times n$ matrix. $\boxed{M_0}$
• There are $n$ rounds. For each, we mutate the matrix. $$M_0\stackrel{\text{round 1}}{⇝}{M}_1\stackrel{\text{round 2}}{⇝}{M}_2\stackrel{\text{round 3}}{⇝}...\stackrel{\text{round n}}{⇝}{M}_n$$ $\boxed{M_n}$ is the matrix of the transitive closure $R^{\ast }$ of $R$.
  • 1st rule: never change $1$ to $0$
  • 2nd rule: for the $k$ round, we select the $k$th row and the $k$th column, we look at all of the $0$ values not in this row or column. From the position of the $0$ value we are looking at, we check to see if the corresponding cells in the $k$th row and column are $1$, if they are, we change $0$ to $1$ otherwise we don’t do anything. $$\begin{array}{cc}& jk\text{th column}\\ \begin{array}{c}i\\ \\ k\text{th row}\end{array}& \left[\begin{array}{ccc}0& \to & 1\\ \downarrow & & \\ 1& & \end{array}\right]\end{array}\stackrel{\text{round }k}{⇝}\begin{array}{cc}& \begin{array}{ccc}j& & k\end{array}\\ \begin{array}{c}i\\ \\ k\end{array}& \left[\begin{array}{ccc}\text{1}& & 1\\ & & \\ 1& & \end{array}\right]\end{array}$$

Link to original

Example

Let $R$ be a relation on $\{a,b,d,d\}$. $R=\{(a,d),(b,a),(b,c),(c,a),(c,d),(d,c)\}$

We first construct our starting matrix.

$$M_0=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 1.

$$M_1=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& \boxed{1}\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 2.

$$M_2=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right]\end{array}$$

Round 3.

$$M_3=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 1\\ 1& 0& 0& 1\\ \boxed{1}& 0& 1& \boxed{1}\end{array}\right]\end{array}$$

Round 4.

$$M_4=\begin{array}{cc}& \begin{array}{cccc}a& b& c& d\end{array}\\ \begin{array}{c}a\\ b\\ c\\ d\end{array}& \left[\begin{array}{cccc}\boxed{1}& 0& \boxed{1}& 1\\ 1& 0& 1& 1\\ 1& 0& \boxed{1}& 1\\ 1& 0& 1& 1\end{array}\right]\end{array}$$

Hence this is our final relation.

$$R^{\ast }=\{(a,a),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,c),(c,d),(d,a),(d,c),(d,d)\}$$

digraph A {
	label = "R"
	a->d
	b->a
	b->c
	c->a
	c->d
	d->c
}
 
digraph B {
	label = "R*"
	a->a
	a->c
	a->d
	b->a
	b->c
	b->d
	c->a
	c->c
	c->d
	d->a
	d->c
	d->d
}

Link to original

Equivalence relation

Equivalence relation

A relation $R$ on a set $A$ is called an equivalence relation if it is: ?

• reflexive: everything loops
• symmetric: all arrows come in pairs
• transitive: every 2-step journey must be also done in 1-step

For example:

• $=$ on any set
• $\{(x,y)\in \mathbb{Z}\times \mathbb{Z}|x-y\text{ is divisble by }4\}$ on $\mathbb{Z}$

Link to original

Partial Order

Partial order

A relation $R$ on a set $A$ is called an partial order if it is: ?

• reflexive: everything loops
• antisymmetric: we can only travel one way
• transitive: every 2-step journey must be also done in 1-step

For example:

• $\le$, $\ge$, and ‘divisibility’ on ${\mathbb{N}}^{+}$
• Prove that $\subseteq$ is a partial order on the power set $P(S)$ of a set $S$.
  • $\subseteq$ is reflexive because $A\subseteq A$ for every set $A$.
  • $\subseteq$ is antisymmetric because if $A\subseteq B$ and $B\subseteq A$, then $A=B$ holds.
  • $\subseteq$ is transitive because if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$ holds.

Link to original

Linear Order

Linear order

A relation on a set $A$ is called a linear order if: ?

• It is also a partial order.
• For all $a,b\in A$, either $(a,b)\in R$ or $(b,a)\in R$.

For example:

$\le$ on $\mathbb{N}$	$\ge$ on $\mathbb{Z}$
Graph of less than or equal to on natural numbers graph G { 2--1 1--0 } Link to original	Graph of greater than or equal to on integer numbers graph G { { m [label="-1"] } m--0 0--1 } Link to original

Example

Let $S$ be a set with more than one element. Show that $\subseteq$ is not a linear order on $P(S)$.

If $S$ has more than one element, then there are at least two different elements, say $x$ and $y$:

• $x\in S$ so $\{x\}\subseteq S$ and so $\{x\}\in P(S)$
• $y\in S$ so $\{y\}\subseteq S$ and so $\{y\}\in P(S)$
• Neither $\{x\}\subseteq \{y\}$ or $\{y\}\subseteq \{x\}$ hold as $x\ne y$.

So $\{x\}$ and $\{y\}$ are two elements in $P(S)$ such that either $\{x\}\subseteq \{y\}$ or $\{y\}\subseteq \{x\}$, so so $\subseteq$ is not a linear order. (It does not form a line.)

graph G {
	{
		a [label="P(s)"]
		x [label="{x}"]
		y [label="{y}"]
	}
	
	x,y--a
}

Link to original

Link to original

16. Hasse diagrams

Hasse diagrams

If we know that a relation is a partial order, then we can use a simplified representation rather than using a directed graph.

Example Diagram

For example, take the ‘divisibility’ relation on the set $\{1,2,3,5,10,11,15,25\}$.

$$\begin{array}{r}\{(1,1),(1,2),(1,3),(1,5),(1,10),(1,11),(1,25),(2,2),(2,10),(3,3),\\ (3,15),(5,5),(5,10),(5,15),(5,25),(10,10),(11,11),(15,15),(25,25)\}\end{array}$$

digraph G {
	{
		a [label="1"]
		b [label="2"]
		c [label="3"]
		d [label="5"]
		e [label="10"]
		f [label="11"]
		g [label="15"]
		h [label="25"]
	}
 
	a->a
	a->b
	a->c
	a->d
	a->e
	a->f
	a->h
	b->b
	b->e
	c->c
	c->g
	d->d
	d->e
	d->g
	d->h
	e->e
	f->f
	g->g
	h->h
}

As partial orders are always reflexive, a loop is always present at every point, so we can remove these loops without losing information:

digraph G {
	{
		a [label="1"]
		b [label="2"]
		c [label="3"]
		d [label="5"]
		e [label="10"]
		f [label="11"]
		g [label="15"]
		h [label="25"]
	}
 
	a->b
	a->c
	a->d
	a->e
	a->f
	a->h
	b->e
	c->g
	d->e
	d->g
	d->h
}

Partial orders are always transitive, so we don’t lose any information by only indicating ‘one-step’ arrows.

digraph G {
	{
		a [label="1"]
		b [label="2"]
		c [label="3"]
		d [label="5"]
		e [label="10"]
		f [label="11"]
		g [label="15"]
		h [label="25"]
	}
 
	a->b
	a->c
	a->d
	a->f
	b->e
	c->g
	d->e
	d->g
	d->h
}

Partial orders are also antisymmetric, which means that between any two points there can only be an arrow one way, not both. We can remove the arrows and ensure everything stems from bottom to top.

graph G {
	rankdir = BT
 
	{
		a [label="1"]
		b [label="2"]
		c [label="3"]
		d [label="5"]
		e [label="10"]
		f [label="11"]
		g [label="15"]
		h [label="25"]
	}
 
	a--b
	a--c
	a--d
	a--f
	b--e
	c--g
	d--e
	d--g
	d--h
} 

Example 2

The Hasse diagram of $\subseteq$ on the power set $P(\{x,y,z\})$ of $\{x,y,z\}$:

graph G {
	{
		e [label="0"]
		x [label="{x}"]
		y [label="{y}"]
		z [label="{z}"]
		a [label="{x,y}"]
		s [label="{y,z}"]
		d [label="{x,z}"]
		f [label="{x,y,z}"]
	}
	
	x,y,z--e
	a--x,y
	s--y,z
	d--x,z
	f--a,s,d
}

Link to original