9. Relations

9.1 Relations and Their Properties

A **binary relation**（二元关系） from a set to a set is a subset of .
Let be sets. An **n-ary Relation** on these sets is a subset of . are called the **domains** of relation, and is called the **degree** of the relation.
A **relation on the set** is a relation form to .
There are binary relations on a set with elements

9.2 Representing Relations

📋The Methods of Representing Relations

• List its all ordered pairs
• Using a set build notation / specification by predicates
• 2D table
• Connection matrix / zero-one matrix
• Directed graph / Digraph

📋2D table
🌰e.g.
, , . Represent the relation using a **2D table**.
Solution:

📋Connection Matrices
Let be a relation from to . An **connection matrix** for is defined by .
🌰e.g.
The connection matrix for the 2D table above is
📋Directed graph / Digraph
A **directed graph**（有向图） or a **digraph**, consists of a set of **vertices**（结点） together with a set of ordered pairs of elements of called **edges**(or arcs). The vertices is called the **initial vertices** and **terminal vertices** of the edge .
🌰e.g.
, . Show the relation with a directed graph.

9.3 n-ary Relations and Their Applications

📋 Properties of Binary Relations

• Reflexive
• Irreflexive
• Symmetric
• Antisymmetric
• Transitive

A relation on a set is **reflexive**（自反） if . In matrices representing reflexive relations, all the elements on the main diagonal of must be 1. In digraphs representing reflexive relations, there is a loop at every vertex.
A relation on a set is **irreflexive**（反自反） if . In matrices representing irreflexive relations, all the elements on the main diagonal of must be 0. In digraphs representing irreflexive relations, there is no loop at any vertex.
⚠️ A relation on a set can be neither reflexive nor irreflexive, for example, .
A relation on a set is **symmetric**（对称） if . Matrices representing symmetric relations must be symmetric. In digraphs representing symmetric relations, if there is an arc there must be an arc .
A relation on a set is **antisymmetric**（反对称） if , or equivalently . In digraphs representing symmetric relations, if there is an arc connecting two different vertices, there can not be an arc .
⚠️ A relation on a set can be both symmetric and antisymmetric, for example, again.
A relation on a set is **transitive**（传递） if . In matrices representing transitive relations, . In digraphs representing transitive relations, if there is an arc from to and one from to then there must be one from to .
🌰 e.g.
Symmetric, Transitive ⇒ Reflexive?
Solution:
Since and is symmetric, . Since , and is transitive, . But this is valid only for satisfying . It is still possible that when .
Since relations from to is a subset of , two relations from to can be combined in any way two sets can be combined.
📋 Set Operations on Relations and Logical Operations of Matrices
We can solve the set operations on relations using exhaustive method, or logical operations of the matrices of the relations.
The Boolean Sum（布尔和） ∨:
The Boolean Product（布尔积） ∧:
The complement −:
Let , , , , the set operations of two relations are defined by

📋 Composition of Relations
, , then the **composite**（复合） of and , denoted as , is .
To compute , we can either use the definition directly or use the connection matrix.
🌰 e.g.

Solution:
(1) Using the definition directly

(2) Using the connection matrix

Let be a relation on the set . The **powers** are defined inductively by are defined inductively by .
📋 The relation on the set is transive if and only if , for

For a relation , the **inverse relation** from to is .
📋 Methods to Get

1. Using the definition directly.
2. Reverse all the arcs in the digraph representation of .
3. Take the transpose of the connection matrix of .

📋 The Rroperties of Relation Operations
Suppose that , are the relations from to , is the relation from to , is the relation from to , then

• 
• 
• 
• 
• 
• 
• 
• 

• 

  9.4 Closures of Relations

  The **closure** of a relation with respect to property is the relation with property containing such that is a subset of every relation with property containing . Which means, is the smallest relation with property containing .
  📋Let be a relation on . The **reflexive closure** of , denoted by , is , where is called the **diagnal relation** on .
  Corollary: is a reflexive relation.
  Given , to obtain its reflexive closure, we can:

• Add to all ordered pairs of the form with , not already in .

• Add loops to all vertices on the digraph representation of .
• Put 1’s on the diagonal of the connection matrix of .

📋Let be a relation on . The **symmetric closure** of , denoted by , is .
Proof:
Obviously contains and is symmetric. Then we need to show it is the smallest symmetric relation which contains .
Suppose that is a symmetric relation containing , then

Corollary: is a symmetric relation.
Given , to obtain its symmetric closure, we can:

• Add all ordered pairs of the form where is in the relation, that are not already in .
• Add an edge from to whenever this edge is not already in directed graph but the edge from to is.
• 

Then we go on to the **transive closure**（传递闭包）, denoted by . It can not be computed so simply as the two kinds of closures above. Firstly we need to introduce some terminologies.
A **path** of **length** in a digraph means a sequence of edges , denoted as . It is called a **cycle** or **circuit** if .
The term “path” also applies to relations. We say there is a path of length from to in if such that .
📋Let be a relation on . There is a path of length from to if and only if .
Proof: Using MI.
The **connectivity relation** denoted by , is the set of ordered pairs such that there is a path (in ) from to : .
📋.
Proof:
Obviously contains and is a transitive relation by its definition. Then we need to show that is the smallest transitive relation which contains .
Now suppose that is any transitive relation which contains . We need to show contains .
Since is transitive, is also transitive and . It follows that . If , then , because any path in is also a path in . So .
Corollary: is transitive.
💡 In fact, we need only consider paths of length or less, where is the cardinality of .
📋If , then any path of length must contain a cycle.
Proof: Using the Pigeon Hole Principle.
📋If , is a relation on , then .
Corollary: If then .
Corollary: .
📋A Basic Procedure for Computing t(R)

📋 Warshall’s Algorithm for Computing t(R)

别以为这个不会考！

If is a path, its **interior vertices** are , that is, all the vertices of the path that occur somewhere other than as the first and last vertices in the path. Warshall’s algorithm is based on the efficient construction of a sequence of zero–one matrices. These matrices are , where is the zero–one matrix of relation , and , where if there is a path from to such that all the interior vertices of this path are in the set (the first vertices in the list) and is 0 otherwise. Note that , because the (i, j)th entry of is 1 if and only if there is a path from to , with all interior vertices in the set .
We can compute directly from : There is a path from vi to vj with no vertices other than v1, v2, … , vk as interior vertices if and only if either there is a path from to with its interior vertices among the first vertices in the list, or there are paths from to and from to that have interior vertices only among the first vertices in the list. That is, either a path from to already existed before was permitted as an interior vertex, or allowing as an interior vertex produces a path that goes from to and then from to .

The first type of path exists if and only if , and the second type of path exists if
and only if both and are 1. Hence, whenever i, j and k are positive integers not exceeding n.

The complexity of Warshall’s algorithm is .

9.5 Equivalence Relation

A relation on a set is an **equivalence relation**（等价关系） if is reflexive, symmetric and transitive. If elements and are related by an equivalence relation , then we say and are equivalent, denoted by . In an equivalence relation , the set of all elements that are related to an element of is called the **equivalence class**（等价类） of , denoted by or .
Let be a collection of subsets of . Then the collection forms a **partition**（分割） of if and only if

denoted by . 就是说这一系列 Ai 的无交并为 A。
📋 Let be an equivalence relation on a set . The following statements are equivalent

📋 Let be an equivalence relation on a set . Then the equivalence classes of form a partition of . Conversely, given a partition of the set , there is an equivalence relation that has the sets , as its equivalence classes.
In short, an equivalence relation on a set ↔ a partition of .
📋 Congruence modulo forms a partition of all integers.


🌰e.g.
. Show that is an equivalence relation, and find its equivalence class.
Proof:
if and only if .
is reflexive because . We can also show it is symmetric and transitive using the qualities of division.
The equivalence classes are , and .
🌰e.g.
Find the partition of the set from .



📋 If are equivalence relations on , then is also an equivalence relation on .
Proof:

1. It is reflexive. , so .
2. It is symmetric. If , then and , then and , so .
3. It is transitive.

📋 If are equivalence relations on , then is reflexive and symmetric relation on . Not necessarily transitive.
📋 If are equivalence relations on , then is also an equivalence relation on .

9.6 Partial Orderings

Let be a relation on . Then is a **partial ordering**（偏序关系） or partial order if is reflexive, antisymmetric and transitive, denoted by . is called a partially ordered set or a **poset**（偏序集）.
🌰e.g.



We use the notation to represent the partial orderings including , and . is read as “ is less than or equal to “. means and , read as “ is less than “.
The elements and of a poset are called **comparable** if either or . When and are elements of such that neither nor , and are called **incomparable**.
If is a poset and every two elements of are comparable, is called a **totally ordered set**（全序集） or a **linearly ordered set**, is called a **total order** or **linear order**. In this case is called a **chain**（链）. 想象一下，全序集中的所有元素都可比较大小，因此它们可以按照大小顺序排成一条链，像数轴那样。
🌰e.g.
is a poset and is a chain. and are posets but not totally ordered sets.
is a **well-ordered** set if it is a poset such that is a total order and every nonempty subset of has a least element.
📋 The Principle of Well-Ordered Induction
Suppose that is a well-ordered set. Then , if:
Inductive Step: for every , if is true for all with , then .
Proof:
Suppose it is not the case that is true for all . Then there is an element
such that is false. Consequently, the set is nonempty. Because is well-ordered, A has a least element . By the choice of as a least element of , we know that is true for all with . This implies by the inductive step is true. This contradiction shows that must be true for all .
The **lexicographic order** on is defined as following: given two posets and , we construct an induced partial order on : if or . The definition of lexicographic order extends naturally to multiple Cartesian products of partially ordered sets.
🌰e.g. Lexicographic Order of String
The string is less than if and only if .
discredit ≺ discreet ≺ discrete ≺ discreteness ≺ discretion
**Hasse diagram**（哈塞图） is a method used to represent a partial ordering clearly.
📋 To construct a Hasse diagram:

1. Construct a digraph representation of the poset (A, R) so that all arcs point up (except the loops).
2. Eliminate all loops.
3. Eliminate all arcs that are redundant because of transitivity.
4. Eliminate the arrows at the ends of arcs since everything points up.

🌰e.g.
, and represent it using a Hasse diagram.

Let be a poset. , if is a totally ordered set, then is called a **chain** of . is called the **length** of chain. Otherwise, if , then is called an **antichain** of .
Let be a poset, then is a **maximal element**（极大元） if there does not exist an element in such that . Similarly for a **minimal element**（极小元）. Maximal and minimal elements are the “top” and “bottom” elements in the Hasse diagram.
⚠️ There can be more than one minimal and maximal element in a poset.
Let be a poset. Then an element in is a **greatest element**（最大元） of if for every in , and is a **least element**（最小元） of if for every in .
📋 The greatest and least element are unique when they exist.
Proof:
就是假设有两个最大元 / 最小元，然后证明它们必须是相等的，相当于只有一个。Suppose that is a greatest element in . It follows that for every element in . Suppose that is also a greatest element in . It follows that for every element in . It implies that and . That is .
Let be a subset of in the poset . If there exists an element in such that for all in , then is called an **upper bound**（上界） of . Similarly for **lower bounds**（下界）.
⚠️ Mind the differences of “maximal element”, “greatest element” and “upper bound”. “极大元”只要能比较大小的都小于等于它就行，“最大元”要所有元素都能和它比大小且都小于等于它，“上界”甚至可以不在子集里面但子集里所有元素必须小于等于它。
If is an upper bound for which is less than every other upper bounds, then it is the **least upper bound**（上确界）, denoted by . Similarly for the **greatest lower bound**（下确界）, .
A poset is called a **lattice** （格） if every pair of elements has a lub and a glb.

🌰e.g.
is not a lattice because there is no multiple of both 6 and 9 in these numbers. If we add 36 into these numbers then it will form a lattice.
📋 Every totally ordered set is a lattice.
⚙️ The Lattices Model of Information Flow
The Lattices Model can be used to represent different information flow policies. For example, the multilevel security policy:
Each pieces of information is assigned to a security class. Each security class is represented by a pair , where is an authority level and is a category. Order security classes by specifying that iff . For example, the typical authority levels used in the U.S. government is A={ unclassified(0), confidential(1), secret(2), top secret(3) }. If C={ spies, moles, double agents }, then their are 2|C| = 8 different categories.
Information is permitted to flow from security classes into iff . Then the set of all security classes forms a lattice.
A total ordering is said to be **compatible**（共生） with the partial ordering if whenever . Constructing a compatible total ordering from a partial ordering is called **topological sorting**（拓扑排序）.
📋 Every finite nonempty poset has at least one minimal element.
Proof:
Choose an element of . If is not minimal, then there is an element with . If is not minimal, there is an element with . Continue this process, so that if is not minimal, there is an element with .
Since there are only finite number of elements in the poset, this process must end with a minimal element.
📋 According to this lemma, to sort a poset :
Basic Step: Select a (any) minimal element and put it in the list. Delete it from .
Inducive Step: Continue until all elements appear in the list and is void.
🌰e.g.
Find a compatible total ordering for the poset .
Solution:

Delete one minimal element in each step. If there are more than one minimal element in one step, just choose a random one. This produces the total ordering 1 ≺ 5 ≺ 2 ≺ 4 ≺ 20 ≺ 12.
⚙️ Topological sorting has an application to the scheduling of projects. The Hasse diagram means the order of completing a series of projects, where the less project need to be finished before the greater project is finished. By producing a total ordering, we can find a feasible order to finish all the projects.