Chapter 2. Mathematical preliminaries

Sets, Relations, and Functions ​

Sets and Numbers ​

• Standard notation:

  • Use $\{...\}$ for explicit lists or comprehension (e.g., $\{x\in S|...\}$).

  • $\varnothing$ denotes the empty set.

  • $S\setminus T$ denotes set difference (elements in $S$ but not in $T$).

  • $|S|$ denotes the size of set $S$.

  • $𝒫(S)$ is the powerset (set of all subsets) of $S$.

• Natural numbers ($\mathbb{N}$): The set $\{0,1,2,...\}$.

• Countable: A set is countable if it has a one-to-one correspondence with $\mathbb{N}$.

Relations ​

• n-place relation: An n-ary relation.

• Predicate: A one-place (unary) relation on a set $S$.

  Written $P(s)$ or $s\in P$ regarding $P$ as a function mapping to truth values.

• Binary relation: A two-place relation on sets $S$ and $T$.

  Often written $sRt$ instead of $(s,t)\in R$.

• Mixfix syntax: For readability, relations with 3+ places often use symbols separating elements to form the name (e.g., $\mathrm{\Gamma }⊢s:T$).

• Domain & Codomain:

  • Domain ($dom(R)$): The set of elements $s\in S$ such that $(s,t)\in R$ for some $t$.

  • Codomain/Range ($range(R)$): The set of elements $t\in T$ such that $(s,t)\in R$ for some $s$.

• Preservation: A predicate $P$ is preserved by a relation $R$ if $sR{s}^{\prime }$ and $P(s)$ implies $P(s^{\prime })$.

Functions ​

• Partial function: A relation $R$ where $(s,t_1)\in R$ and $(s,t_2)\in R$ implies $t_1=t_2$.

  • Defined: Written $f(x)\downarrow$ means $x\in dom(f)$.

  • Undefined: Written $f(x)\uparrow$ or $f(x)=⟂$ means $x\notin dom(f)$.

• Total function: A partial function where $dom(R)=S$.

• Failure: Distinct from divergence.

  Formally, a function that may fail maps $S\to T\cup \{fail\}$.

Ordered sets ​

Properties of binary relations ​

Given a relation $R$ on set $S$:

• Reflexive: $sRs$ for all $s\in S$.

• Symmetric: $sRt$ implies $tRs$.

• Transitive: $sRt$ and $tRu$ implies $sRu$.

• Antisymmetric: $sRt$ and $tRs$ implies $s=t$.

Types of orders ​

• Preorder: A relation that is reflexive and transitive.

  • Notation: Often written $\le$ or $\lesssim$.

  • Strict inequality ($s<t$): Means $s\le t\wedge s\ne t$.

• Partial order: A preorder that is also antisymmetric.

• Total order: A partial order where for every $s,t$, either $s\le t$ or $t\le s$.

• Equivalence: A relation that is reflexive, transitive, and symmetric.

Bounds and Closures ​

• Join (Least upper bound $\vee$): An element $j$ is the join of $s$ and $t$ if $s\le j$, $t\le j$, and $j$ is less than or equal to any other upper bound $k$.

• Meet (Greatest lower bound $\wedge$): An element $m$ is the meet of $s$ and $t$ if $m\le s$, $m\le t$, and $m$ is greater than or equal to any other lower bound $n$.

• Closures:

  • Reflexive closure: The smallest reflexive relation containing $R$.

  • Transitive closure ($R^{+}$): The smallest transitive relation containing $R$.

  • Reflexive and transitive closure ($R^{\ast }$): The smallest relation containing $R$ that is both reflexive and transitive.

Chains and well-foundedness ​

• Decreasing chain: A sequence $s_1,s_2,...$ where $s_{i+1}<s_i$.

• Well-founded: A preorder is well-founded if it contains no infinite decreasing chains.

  • Example: Standard order on $\mathbb{N}$ is well-founded; standard order on integers is not.

Sequences ​

• Notation: Elements are separated by commas (e.g., $3,2,1$).

• Cons and Append: The comma serves as both "cons" (adding an element) and "append" (joining sequences).

  • Example: If $a=\mathrm{3,2,1}$, then $0,a$ is $\mathrm{0,3,2,1}$.

• Range: $\mathrm{1..}n$ abbreviates the sequence from $1$ to $n$.

• Length: $|a|$ denotes the length of sequence $a$.

• Empty sequence: Written as $ϵ$ or a blank.

• Permutation: A sequence containing the same elements as another, possibly in a different order.

Induction ​

Induction on natural numbers ​

• Axiom: Principle of ordinary induction

  If $P(0)$ holds, and $P(i)⟹P(i+1)$ for all $i$, then $P(n)$ holds for all $n$.

• Axiom: Principle of complete induction

  If showing $P(n)$ is possible assuming $P(i)$ for all $i<n$, then $P(n)$ holds for all $n$.

Lexicographic induction ​

• Lexicographic order: On pairs of numbers, $(m,n)\le (m^{\prime },n^{\prime })$ iff $m<m^{\prime }$ OR ($m=m^{\prime }$ and $n\le n^{\prime }$).

• Axiom: Principle of lexicographic induction

  If showing $P(m,n)$ is possible assuming $P(m^{\prime },n^{\prime })$ for all $(m^{\prime },n^{\prime })<(m,n)$, then $P(m,n)$ holds for all pairs.

• Usage: Generalized to triples, 4-tuples, etc. Useful for nested inductions.

Exercises ​

Exercise 2.2.6 ​

Problem: Suppose we are given a relation $R$ on a set $S$. Define the relation $R^{\prime }$ as follows:

$R^{\prime }=R\cup \{(s,s)|s\in S\}$

That is, $R^{\prime }$ contains all the pairs in $R$ plus all pairs of the form $(s,s)$ .

Task: Show that $R^{\prime }$ is the reflexive closure of $R$.

Take $R^{\prime \prime }$ to be the reflexive closure of $R$.

By definition:

• $R^{\prime \prime }$ is reflexive.

• $R\subseteq R^{\prime \prime }$.

• For any reflexive relation $S$ such that $R\subseteq S$, we have $R^{\prime \prime }\subseteq S$.

By the problem statement, $R^{\prime }$ is reflexive and $R\subseteq R^{\prime }$.

Therefore, $R^{\prime \prime }\subseteq R^{\prime }$.

Now, it suffices to show that $R^{\prime }\subseteq R^{\prime \prime }$.

Take an element $x\in R^{\prime }$.

• If $x\in R$, then $x\in R^{\prime \prime }$.

• If $x=(s,s)$ for some $s\in S$, then $x\in R^{\prime \prime }$ because $R^{\prime \prime }$ is reflexive.

Therefore, $R^{\prime }\subseteq R^{\prime \prime }$.

In conclusion, $R^{\prime }\equiv R^{\prime \prime }$ or $R^{\prime }$ is the reflexive closure of $R$.

Exercise 2.2.7 ​

Problem: Here is a more constructive definition of the transitive closure of a relation $R$. First, we define the following sequence of sets of pairs:

• $R_0=R$

• $R_{i+1}=R_i\cup \{(s,u)|\text{for some }t,(s,t)\in R_i\text{ and }(t,u)\in R_i\}$

That is, we construct each $R_{i+1}$ by adding to $R_i$ all the pairs that can be obtained by "one step of transitivity" from pairs already in $R_i$. Finally, define the relation $R^{+}$ as the union of all the $R_i$: $R^{+}={\bigcup }_i{R}_i$.

Task: Show that this $R^{+}$ is really the transitive closure of $R$-i.e., that it satisfies the conditions given in Definition 2.2.5.

• Problem

  Take $R^{\prime }$ to be the transitive closure of $R$.

  By definition:

  • $R^{\prime }$ is transitive.

  • $R\subseteq R^{\prime }$.

  • For any transitive relation $S$ such that $R\subseteq S$, we have $R^{\prime }\subseteq S$.

  • Prove that $R^{+}$ is transitive

    Suppose there exist $s,r,t$ such that $(s,r)\in R^{+}$ and $(r,t)\in R^{+}$ but $(s,t)\notin R^{+}$.

    Because $(s,r)\in R^{+}$, there exists $i_0$ such that $(s,r)\in R_{i_0}$.

    Similarly, there exists $i_1$ such that $(r,t)\in R_{i_1}$.

    Therefore, we have $(s,r)\in R_{\min i_0,i_1}$ and $(r,t)\in R_{\min i_0,i_1}$. Then, $(s,t)\in R_{\min i_0,i_1+1}\subseteq R^{+}$. This is a contradiction.

  • It's obvious that $R\subseteq R^{+}$.

  • Therefore, $R^{\prime }\subseteq R^{+}$.

  • Prove that $R^{+}\subseteq R^{\prime }$

    It's obvious that $R_0\equiv R\subseteq R^{\prime }$.

    Suppose for $R_i\subseteq R^{\prime }$ for some $i\ge 0$.

    We will prove that $R_{i+1}\subseteq R^{\prime }$. This is trivial.

    By induction, $R_i\subseteq R^{\prime }$ for any $i\ge 0$.

    Therefore, $R^{+}\subseteq R^{\prime }$.

  • In conclusion, $R^{+}\equiv R^{\prime }$.

Exercise 2.2.8 ​

Problem: Suppose $R$ is a binary relation on a set $S$ and $P$ is a predicate on $S$ that is preserved by $R$.

Task: Show that $P$ is also preserved by $R^{\ast }$ (the reflexive and transitive closure of $R$).

• Problem

  Because $P$ is a predicate on $S$ that is preserved by $R$: For any $r,t\in S$ such that $rRt$, we have $P(r)⟹P(t)$.

  Take $R^{ref}$ to be the reflexive closure of $R$.

  Then, $R^{\ast }$ is the transitive closure of $R^{ref}$.

  Assume $r,t\in S$ such that $r{R}^{\ast }t$.

  • If $rRt$, it's trivial that $P$ is preserved.

  • If $r\mathrm{R̸}t$ but $r{R}^{ref}t$, then $r=t$. Therefore, $P$ is also preserved.

  • If $r{\mathrm{R̸}}^{ref}t$ but $r{R}^{\ast }t$, that means $r{R}_{i}t$ for some $i\ge 0$, with $R_i$ as defined in the previous exercise.

    Assume $i$ is smallest such number.

    • $i$ must not be $0$, else we would have $r{R}^{ref}t$, a contradiction.

    • Assume that if $r_i{R}_i{t}_i$ then $P(r_i)⟹P(t_i)$.

      We will prove that if $r_{i+1}{R}_{i+1}{t}_{i+1}$ then $P(r_{i+1})⟹P(t_{i+1})$.

      By assumption, $r_{i+1}{\mathrm{R̸}}_i{t}_{i+1}$.

      Therefore, there exists $s$ such that $r_{i+1}{R}_{i}s$ and $s{R}_i{t}_{i+1}$.

      By the induction hypothesis, we have $P(r_{i+1})⟹P(s)$ and $P(s)⟹P(t_{i+1})$.

      It follows that, $P(r_{i+1})⟹P(t_{i+1})$.

      By induction, if $r{R}_{i}t$ for any $i$, we have $P(r)⟹P(t)$.

    This concludes our proof.