Chapter_1_Set_Preorder

--- title: Chapter_1_Set_Preorder tags: Category, Preorder description: Preorder type: pdf slideOptions: theme: white --- ###### tags: `Category` `Preorder` # **<div align="center">Chapter One: Sets and Preorders</div>** <div class="alert alert-info">Example text highlighted in blue background.</div> ### **1.1 Sets,Subset, and Power set** *Set, which is collection of objects*, is most common idea for us to observe, analyse, and discover the Mathematics and the real world, especially when we focus on only generalised structure rather than details of objects. Here are some examples from both real worlds and Mathematics. > **Example 1.1.1** >- set of fruits: FRUIT $:= \{apple, banana, watermelon, \dots \}$ >- set of pets: PET $:= \{cat, dog, turtle, \dots \}$ >- set of all boys in room 54: $R54_B: = \{x\ |\ x \in Room_{54}\ and\ x\ is\ male \}$ >- set of Natural Numbers: $\Bbb{N} := \{0,1,2,3,4,\dots \}$ >- set of Integers: $\Bbb{Z} : = \{\dots, -3,-2,-1,0,1,2,3,\dots\}$ >- set of Even Numbers: $Even := \{x\ |\ x = 2n, n\in\Bbb{N}\}$ >- set of nothing, i.e. empty set: $\phi := \{\}$ >- Boolean Set, which is fundation of Logic and Computer Science, $Bool := \{True,\ False\}$ From the examples above, you might also figured out how we express Sets in Mathematics. ":=" means as defined as; $\in$ means belongs to; and "|" in a set bracket means the condition an elemement has to satisfy to be in the set, whence "x" are placeholder for all elements. We can describe the relationship between an element and an underlying set, for example: > **Example 1.1.2** >- if Adam is in Room54, then Adam $\in$ $R54_B$; >- Chloe is in Room54 but she is a girl, so Chloe $\notin$ $R54_B$, "$\notin$" means "Not in"; >- also $8 \in Even$, and $\frac{1}{3} \notin \Bbb{Z}$ We can also describe relationship between sets, to see whether a set A is contained in another set B, using symbol "$⊆$". > **Example 1.1.3** >- Let three boys Adam, Bob, and Charlie from Room 54 form a set called "F3", then $F3 \subseteq R54_B$; >- Trivially, $\Bbb{N} ⊆ \Bbb{Z}$; >- $\{3,5,7\} \nsubseteq\ Even$; >- $\phi ⊆ $ all the sets in **Example 1.1.1**; Informally, we can define a concept under the set constuction, **subset**. > **Definiton (Subset)** >> For two sets A and B, if $∀ a \in A$, we have $a \in B$, then we say A is a subset of B, denote $A ⊆ B$. In the definition above, $∀$ means "for all", or "any". Following the idea of subset, if we shift our abstruction level up a bit, we can have a definition of **power set**. > **Definiton (Power Set)** >> For a set A, all subsets of A, including the empty set and A itself, form a set named Power set of A, denote $\wp(A)$ > **Example 1.1.4** >- For F3 in **Example 1.1.3**, $\wp(F3) = \{\{Adam\}, \{Bob\}, \{Charlie\},\{Adam,Bob\}, \{Adam,Charlie\}, \{Bob, Charlie\}, \phi, \{Adam, Bob, Charlie\} \}$ >- For Boolean set $Bool$, $\wp(Bool) = \{\phi, \{False\}, \{True\}, \{True, False\}\}$ It is easy to see from the example above that the element of a power set is a set. We have described two ralationship so far, 1. We use "belongs to" to express an element to a set; 2. We use "contained by" to express containness between sets; A curious reader might come across following questions: 1. How to express relationship between elements in one set? 2. How to express relationship of two sets that are not contained by one or another, but share some common elements? Also, what is the relationship between two sets have nothing in common? We will answer above 2 questions in the next two sub-chapters. > **Exercises 1.1** >1. Is it true that $\Bbb{N} = \{n \in \Bbb{Z}\ |\ n \ge 0\}$? >2. Is it true that $\phi = \{n \in \Bbb{Z}\ |\ 1< n < 2\}$? >3. Is it true that $\phi ⊆ \Bbb{Z}$? >4. With $B := \{1,2,3,4\}$, What is the Power set of B, i.e. $\wp(B)$? >5. We use "**Cardinality**" to discribe the number of elements in a set, denote $|\dot|$, for example $|B| = 4$ from above. What is $|\wp(B)|$? Can you generalise $|\wp(X)|$, given $|X| = n, n\in \Bbb{N}$? ---- ### **1.2 Cartesian Product, Relations, and functions** We firstly define an important structure of Sets, **Cartesian Product** > **Definiton (Cartesian Product)(2-sets)** >> If A and B are sets, the *Cartesian product* of A and B is the set of tuples $$A \times B := \{(a, b)\ |\ a\in A\ and\ b\in B \}$$. where the form $(a,b)$ are ordered pair. > **Example 1.2.1** >- if $A = \{1,2\}$ and $B = \{a, b\}$, then $A \times B = \{(1,a), (1,b), (2, a), (2,b)\}$; >- if $A = \{1,2\}$ and $B = \{a, b, c\}$, then $A \times B = \{(1,a), (1,b), (1,c), (2, a), (2,b), (2,c)\}$; Now before we answer questions from the previous seciton, we need to define what is a "**Ralation**". > **Definiton (Relation)** >> A relation from a set A to a set B is a **subset** of $A \times B$, denote $R ⊆ A \times B$. A (*homogeneous*) relation on A, i.e. relation between elements, is a subset of $A\times A$, denote $R ⊆ A \times A$. For the case of homogeneous ralation, we often denote $xRy$ if two elements x and y form a relation. The Definition above might be very general and abstract, which is not easy to have an intuitive example from our real life or even from basic Mathematical Objects. In fact, there is a "**pool of properties**" that belongs to the general conception of **Relation**, Some specific relations that we will come across later are just satisfaction of some of the properties in the pool. > **Common Properties of Relation (homogeneous, i.e. $R⊆A\times A$)** >> - **Reflexive**: for all x ∈ X, xRx. For example, ≥ is a reflexive relation but > is not. >>- **Symmetric**: for all x, y ∈ X, if xRy then yRx. For example, equality, "=", is symmetric; but "love" is not necessarily symmetric, e.g. Alice loves Bob, not necessarily that Bob also loves Alice. >>- **Antisymmetric**: for all x, y ∈ X, if xRy and yRx then x = y. For example, ≥ is an antisymmetric relation >>- **Asymmetric**: for all x, y ∈ X, if xRy then not yRx. For example, "is father of" is an asymmetric relation, but ≥ is not. >>- **Transitive**: for all x, y, z ∈ X, if xRy and yRz then xRz. For example, "=", ">", and "$\ge$" is a transitive relation, while "is parent of" is not, sometimes, "friendship" might be not transitive as well. >>- **Connected**: for all x, y ∈ X, if x ≠ y then xRy or yRx. This property is often used to describe an underlying Ralation inside a set as whole. When a set have a Ralation amoung its element with connected property, we say any two arbitrary element $x,y$ is comparible. otherwise, it is not comparible. With Ralations and some Propertitis above, we can discribe/summarise a set's statement under certain ralations. > **Example 1.2.2** >- Set $\Bbb{N}$ is **total ordered** under relation $\le$ the relation $\le$ in $\Bbb{N}$ is **reflexive, antisymmetric, transitive and connected**; >- Let $B = \{1,2,3\}$, then $\wp(B)$ under relation $⊆$ is **partial ordered**, i.e. Ralationship $⊆$ in $\wp(B)$ is **reflexive, antisymmetric and transitive**; $(\wp(B), ⊆)$ does not satisfy connective, e.g. $\{1\}$ and $\{2\}$ is not comparible under relation $⊆$. We can also list some common properties for heterogeneous relations. > **Common Properties of Relation (heterogeneous, i.e. $R⊆A\times B$)** >> - **Injective**: For all x, z ∈ X and all y ∈ Y, if xRy and zRy then x = z. >>- **Functional**: For all x ∈ X and all y, z ∈ Y, if xRy and xRz then y = z. Such a binary relation is called a partial function. >>- **One-to-one**: Injective and functional. >>- **One-to-many** >>- **Many-to-one**: Functional and not injective. >>- **Many-to-many** >>- **Total (also called left-total)**: For all x $\in$ X there exists a y $\in$ Y such that xRy. >>- **Surjective (also called onto)**: For all y $\in$ Y, there exists an x $\in$ X such that xRy. With the properties above, we can define the most frequently used sort of relation between sets in Mathematics, **Function** > **Definiton (Function)** >> Let S and T be sets. A function from S to T is a subset F ⊆ S × T such that for all s ∈ S there exists a unique t ∈ T with (s, t) ∈ F. So, Function is a heterogeneous relation with properties **functional and total**. >>Functions that have **injective** property is called injection; Functions that have **surjective** property is called surjection; Functions with both injective and surjective is called **bijection**. > **Example 1.2.3** >- Function $f: \Bbb{Z} \mapsto \Bbb{Z}$ with $f(x):= 2x$ is a bijection. $\{\dots, (-1,-2),(0,0),(1,2),\dots\} ⊆ \Bbb{Z}\times \Bbb{Z}$ >- Function $f: \Bbb{Z} \mapsto \Bbb{Z}$ with $f(x):= x^2$ is a function non injective and non surjective. $\{\dots,(-2,4) ,(-1,1),(0,0),(1,1), (2, 4),\dots\} ⊆ \Bbb{Z}\times \Bbb{Z}$. > **Definiton (Function Composition)** >> If F : X → Y is a function and G : Y → Z is a function, their composite is the function X → Z defined to be G(F(x)) for any x ∈ X. It is often denoted G ◦ F. It takes any element x ∈ X, evaluates F to get an element F(x) ∈ Y and then evaluates G to get an element G(F(x)). Composition of functions plays vital rules in many area of Mathematics, we will see more of its use in the coming content. > **Exercises 1.2** >1. If $|A| = m$ and $|B| = n$, $|A \times B| = ?$ >2. Check that $\Bbb{N}$ is totol ordered by providing examples for each property >3. Check that $\wp(B)$ in **Example 1.2.2** is partial ordered by providing examples for each property >4. Check that $f(x) = 2x$ in **Example 1.2.3** is bijection by giving examples, also check that $f(x) = x^2$ in **Example 1.2.3** is non-injective and non-surjective. >5. Suppose that A is a set and f : A → $\phi$ is a function to the empty set. Show that A is empty. ---- ### **1.3 Partition and Equevalence** We have learn Power set and Cartesian Product of sets. Now let's look at another important idea we can induce on a Set, **partition**. > **Definiton (Partition)** >> If A is a set, a partition of A consists of a set P and, for each p ∈ P, a nonempty subset $A_p ⊆ A$, such that $$A = \cup_{p\in P} A_p\ and\ \ if\ \ p\ne q\ then\ A_p \cap A_q = \phi$$ We may denote the partition by $\{A_p\}_{p\in P}$ . We refer to P as the set of part labels and if $p\in P$ is a part label, we refer to $A_p$ as the p th part. Let's look at some examples: > **Example 1.3.1** >- for set $B = \{1,2,3\}$, let's define $P=\{odd, even\}$, then $B_{odd} = \{1,3\}$ and $B_{even} = \{2\}$. We have $B_{odd} \cup B_{even} = B$ and $B_{odd} \cap B_{even} = \phi$ >- for the set $R54$ which denote all students in Room 54, we can define $P = \{B, G\}$ for boys and girls respectively. Then $R54_B \cup R54_G = R54$ form a partition. The powerful thing about partition is that it can natually induce an **equivalence relation** onto a set. > **Definiton (Equivalence relation)** >> Let A be a set. An equivalence relation on A is a homogeneous binary relation satisfying **reflexive**, **symmetric**, and **transitive**. Let's look at some examples: > **Example 1.3.2** >- for set $C = \{1,2,3,4,5,6\}$ with partition $C_{even}$ and $C_{odd}$. We define equivalence relation $\equiv$ as "**with the same parity**". So >>- a). $1 \equiv 1$ as 1 is with the same parity of 1, reflexive follows; >>- b) $1 \equiv 3 \iff\ 3\equiv 1$, which is 1 is with same parity of 3 iff 3 is with same parity of 1, symmetic follows; >>- c). $1 \equiv 3\ and\ 3\equiv 5\implies 1\equiv 5$, which is 1 is with same parity of 3, 3 is with same parity of 5, implies 1 is with same parity of 5, transitive follows. >- for the set $R54$ with $R54_B \cup R54_G = R54$ form a partition, the equivalence ralation for each part $\equiv$ means "is with same gender". It is easy to check that **reflexive**, **symmetric**, and **transitive** follows in each part. Thus we can define partition with equivalence relation, as well as define equivalence relation with partition. > **Definiton (Equivalence relation and Partition)** >> - Given a set A and an equivalence relation ∼ on A, we say that the quotient A/∼ of A under ∼ is the set of parts of the corresponding partition. >> - A partition on a set A can also be understood in terms of surjective functions out of A. Given a surjective function $f: A \mapsto P$, where P is any other set of part labels, the preimages $f^{-1}(p)⊆ A$, one for each element p ∈ P, form a partition of A. As we can abstruct $\wp(A)$ as power set of A, i.e. all subsets of A, we can also generalise a concept $Prt(A)$ as all partitions of A, which also form a set. > **Example 1.3.3** >- for set $B = \{1,2,3\}$, $Prt(B) = \{ \{\{1\},\{2\},\{3\}\}, \{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\}, \{\{1\},\{2,3\}\}, \{\{1,2,3\}\} \}$ Just like we can introduce $⊆$ to $\wp(A)$ as relation, we can also introduce "fineness" to $Prt(A)$ as relation. > **Definiton (finer and coarser Partition)** >> a partition P is **finer** than a partition Q if, for every part p ∈ P there is a part q ∈ Q such that $A_p \subseteq A_q$. We could also say that Q is **coarser** than P, with same condition. We will use $P \ge Q$ in this note for P is finer than Q, for $\forall P, Q \in Prt(A)$. > **Example 1.3.4** >- for set $B = \{1,2,3\}$, $Prt(B) = \{ \{\{1\},\{2\},\{3\}\}, \{\{1,2\},\{3\}\}, \{\{1,3\},\{2\}\}, \{\{1\},\{2,3\}\}, \{\{1,2,3\}\} \}$, we have $\{\{1\},\{2\},\{3\}\} \ge \{\{1,2\},\{3\}\} \ge \{\{1,2,3\}\}$ As we can define partition from surjection, we can also generalise the following proposition: > **Proposition 1.1** > Let A be a non-empty set and $P, Q \in Prt(A)$ with finite cardinality, given two surjection $\ f: A ↦ P$ and $\ g: A ↦ Q$. Then $P \ge Q$ if exist a non-injective $h: P ↦ Q$ such that $h \circ f = g$ >> **Proof:** By contrapositive, suppose $P \ngeq Q$, then we have $|P| \le |Q|$. For the case $|P| < |Q|$, it is imposible to have a $h: P ↦ Q$ such that $h \circ f = g$, as h has to be funcitional; in the case of $|P| = |Q|$, h has to be injective. So there do not exist a non-injective h. This finish the prove. $\blacksquare$ > **Exercises 1.3** >1. Let $A = \{1,2,3,4\}$, what is $|Prt(A)|$? >2. Let us assume that F is a relation on the set R real numbers defined by xFy if and only if x-y is an integer. Prove that F is an equivalence relation on R. >3. Check that R54 case defined "is same gender as" in **Example 1.3.2** is an equivalence relation; >4. Following **Example 1.3.4** provide the other two chains of fineness. >5. From the **Proposition 1.1**, give a counterexample if we allow the function h to be injective, hint, using example 1.3.4. ---- ### **1.4 Preorder, Graph and monotone function** We will start to define a general relation of a set, namely, preorder. > **Definiton (Preorder)** >> A preorder relation on a set X is a binary relation on X, here denoted with infix notation ≤, such that. >> (a). x $\le$ x; and >> (b). if x$\le$y and y$\le$z, then x$\le$z >> The first condition is called reflexivity and the second is called transitivity. >> Given a preorder (P, ≤), we may define the opposite preorder (P, $\le_{op}$ ) to have the same set of elements, but with $p ≤_{op} q$ if and only if q ≤ p. > **Example 1.4.1** >- **Discrete Preorders**: Every set X can be considered as a discrete preorder (X, =). This means that the only order relations on X are of the form x ≤ x; if x $\ne$ y then neither x ≤ y or y ≤ x hold. >- **Boolean**: The booleans B = {false, true} form a preorder with false ≤ true. The $\le$ here is simply "implies" in logic, thus we have False $\implies$ False, False $\implies$ True, and True $\implies$ True >- **$\wp(A)$** for set A, with preorder $\le$ as $\subseteq$ >- **Prt(A)** for set A, with preorder $\le$ as "finer". In category theory, we use Directed graph to represent a set embeded with preorder. So we will give definition of a Directed Graph as below, > **Definiton (Directed Graph)** >> A Directed graph G = (V, A, s, t) consists of a set V whose elements are called vertices, a set A whose elements are called arrows, and two functions s, t : A → V known as the source and target functions respectively. Given a ∈ A with s(a) = v and t(a) = w, we say that a is an arrow from v to w. >> By a path in G we mean any sequence of arrows such that the target of one arrow is the source of the next. This includes sequences of length 1, which are just arrows a ∈ A in G, and sequences of length 0, which just start and end at the same vertex v, without traversing any arrows. **Example 1.4.2** >- let Bool = \{False, True\}, then with $\implies$ form a preorder set. We can express this preorder in terms of directed graph ```mermaid flowchart LR False -->|a| True False -->|i_f| False True --> |i_t|True ``` >> In terms of Directed Graph, We have V={False, True}, A = {a, i_f, i_t}, s(a) = False, t(a) = True >- For a set A = {a,b,c}, its discrete preorder are simply ```mermaid flowchart TD a -->|i_a| a b -->|i_b| b c --> |i_c|c ``` >> In terms of Directed Graph, We have V={a, b, c}, A = {i_a, i_b, i_c}, s(i_a) = a, t(i_a) = a >- The Natural Number with $\le$ forms a preorder which is also total. ```mermaid flowchart LR 0-->1-->2-->3-->... ``` We have learnt $\wp(A)$, Prt(A), now with preorder, we can define Upper set of A > **Definiton (Upper Sets)** >> Given a preorder (P, ≤), an upper set in P is a subset U of P satisfying the condition that if p ∈ U and p ≤ q, then q ∈ U.“If p is an element then so is anything bigger.” Write U(P) for the set of upper sets in P. We can give the set U an preorder by $\subseteq$. Clearly, $U(A) \subseteq \wp(A)$ **Example 1.4.3:** - For ($\Bbb{B},\le$), the $U(\Bbb{B})$ is $\phi \rightarrow \{True\} \rightarrow \{True, False\}$, which is a subset of $\wp(\Bbb{B})$. Note that $\{False\} \notin U(\Bbb{B})$ as $False \le True$ but $True \notin \{False\}$ - Let A = {1,2,3} with preorder $\le$, then $U(A) = \{\phi,\{3\}, \{2,3\}, \{1,2,3\}\}$ <div class="alert alert-info">The most important sort of relationship between preorders is called a monotone map. These are functions that preserve preorder relations—in some sense mappings that respect ≤—and are hence considered the right notion of structure-preserving map for preorders.</div> > **Definiton (Monotone maps)** >> A monotone map between preorders (A, $\le_A$) and (B, $\le_B$ ) is a function f : A → B such that, for all elements x, y ∈ A, if $x \le_A y$ then $f (x)\le_B f (y)$. **Example 1.4.4:** - Let $f: \Bbb{R}\mapsto \Bbb{R}$ and $f(x) = 3x$, then f is monotone, however, $f(x) = sin(x)$ is not monotone. - Given a finite set X, recall the power set $\wp(X)$ and its natural order relation $\subseteq$. The map $|·| : \wp(X) → \Bbb{N}$ sending each subset S to its number of elements |S|, also called its cardinality, is a monotone map. > **Proposition 1.2** > Define a monotone map $\uparrow: P^{op} \mapsto U(P)$ by $\uparrow p := \{p^{,} \in P\ |\ p \le p^{,}\}$. Then $p \le p^{,}\ iff\ \uparrow(p^{,}) \subseteq \uparrow(p)$ We will only give an directed graph as an illustration of **Propostion 1.2**, for set $A = \{1,2,3\}$ we have: ```mermaid flowchart TD subgraph A-op 1 --> |<=|2 2 --> |<=|3 end subgraph Upper Set of A 1,2,3 --> 2,3 2,3 --> ,3 end 1 --> |up| 1,2,3 2 --> |up| 2,3 3 --> |up| ,3 ``` Finally we will define an importand concept, Isomorphism, which will come across frequently in next chapters. > **Definiton (Isomorphism)** >> Let (P, $≤_P$ ) and (Q, $≤_Q$ ) be preorders. A monotone function f : P → Q is called an isomorphism if there exists a monotone function g : Q → P such that $g \circ f = id_P$ and $f \circ g = id_Q$ . This means that for any p ∈ P and q ∈ Q, we have >> $$p = g(f(p))\ and\ q=f(g(q))$$ >> We refer to g as the inverse of f , and vice versa: f is the inverse of g. If there is an isomorphism P → Q, we say that P and Q are isomorphic. > **Exercises 1.4** >1. Let $A = \{1,2,3\}$, draw the graph of $\wp(A)$ and Prt(A) with respect to preorders $\subseteq$ and "finer". >2. Prove that the preorder of upper sets on a discrete preorder on a set X is simply the power set $\wp(X)$. >3. Show that $f: \Bbb{R}\mapsto \Bbb{R}$ and $f(x) = 3x$ is monotone, whereas $f(x) = sin(x)$ is not monotone. >4. from **Example 1.4.4:**, let $X = \{0,1,2\}$, show that the map $|·| : \wp(X) → \Bbb{N}$ sending each subset S to its number of elements |S| is monotone >5. Prove that composition of two monotone function, $f\circ g$,is also monotone. ---- ### **1.5 Join, Meet, and Generative Effect** Consider the preorder (R, ≤) of real numbers ordered in the usual way. The subset N ⊆ R has many lower bounds, namely −1.5 is a lower bound: every element of N is bigger than −1.5. But within all lower bounds for N ⊆ R, one is distinctive: a greatest lower bound—also called a meet—namely 0. It is a lower bound, and there is no lower bound for N that is above it. However, the set N ⊆ R has no upper bound, and certainly no least upper bound—which would be called a join. This motivate the definition below: > **Definiton (Meet and Join)** >> Let (P, ≤) be a preorder, and let A ⊆ P be a subset. We say that an element p ∈ P is a meet of A if >> (a). for all $a\in A$, we have $p\le a$, and >> (b). for all q such that $q\le a$ for all $a\in A$, we have $q\le p$ >> if meet of A exist, we denote it $p = \land A$; >> Similarly, we say that p is a join of A if >> (a). for all $a\in A$, we have $a\le p$, and >> (b). for all q such that $a\le q$ for all $a\in A$, we have $p\le q$ >> f join of A exist, we denote it $p = \lor A$; **Example 1.5.1:** - (Meets or joins may not exist). Note that, in an arbitrary preorder (P, ≤), a subset A need not have a meet or a join. Consider the three element set P = {p, q, r} with the discrete ordering. The set A = {p, q} does not have a join in P because if x was a join, we would need p ≤ x and q ≤ x, and there is no such element x. - In a power set $\wp(X)$, the meet of a collection of subsets, say A, B ⊆ X is their intersection A ∧ B = A ∩ B, while the join is their union, A ∨ B = A ∪ B. - In the booleans B = {false, true}, the meet of any two elements is given by AND and the join of any two elements is given by OR. And we have from Boolean logic that | Bool | Bool | AND(*) | Or(+) | | ----- | ----- | ------ | ----- | | False | False | False | False | | False | True | False | True | | True | False | False | True | | True | True | True | True | > **Proposition 1.3** > Suppose (P, ≤) is a preorder and A ⊆ B ⊆ P are subsets that have meets. Then $\land B \le \land A$. Similarly, if A and B have joins, Then $\lor A \le \lor B$. >> **Proof**: >> Let $m=\land A$ and $n=\land B$. Then for any a ∈ A we also have a ∈ B, so n ≤ a because n is a lower bound for B. Thus n is also a lower bound for A and hence n ≤ m, because m is A’s greatest lower bound. >> let $x=\lor A$ and $y=\lor B$. Then for any $a \in A$ we have $a \in B$, we have $a \le y$, so y is an upper bound for A, Since x is the smallest upper bound, we have $x \le y$. $\blacksquare$ > **Definiton (Meet and Join preserve)** >> We say that a monotone map f : P → Q preserves meets if f (a ∧ b) $\equiv$ f (a) ∧ f (b) for all a, b ∈ P. We similarly say f preserves joins if f (a ∨ b) $\equiv$ f (a) ∨ f (b) for all a, b ∈ P. > **Definiton (Generative effect)** >> We say that a monotone map f : P → Q has a generative effect if there exist elements a, b ∈ P such that $$f(a) \lor f(b) \ncong f(a\lor b)$$ **Example 1.5.2:** - Consider a sentence made with three words $\{Adam, like,apple\}$ and a function $f : Words\mapsto \Bbb{B}$ by f(x) = (if it is an explicit express). So we might see that f(Adam) = False, f(like) = False, f(apple) = False, but f(Adam likes apple) = True. So we have $f(a) \lor f(b) \ncong f(a\lor b)$, which indicate a generative effect. <div class="alert alert-info">Can we find any map that preserve join or meet? This is an important research in Mathematics, which will lead to our final section in Chapter one, Galois connections</div> > **Exercises 1.5** >1. For the set $\{\frac{1}{n+1}|n\in\Bbb{N}\}$,what is the meet if it exist, what is the join if it exist? >2. Let $P =\{p\}$ be a set with single element, what is its join and meat respectively if they exist? >3. we write n|m if n divides perfectly into m. What is the name of meet of any two numbers in this preorder, also What is the name of Join of any two numbers under this preorder? >4. Think about anogher exmaple from real life that have generative effect. >5. Prove that for any monotone map f : P → Q, if a, b ∈ P have a join and f (a), f (b) ∈ Q have a join, then indeed f (a) ∨ f (b) ≤ f (a ∨ b). ---- ### **1.6 Galois Connections** <div class="alert alert-info">The preservation of meets and joins, and in particular issues concerning generative effects, is tightly related to the theory of Galois connections, which is a special case of a more general theory we will discuss later, namely that of adjunctions.Galois connections between preorders were first considered by Évariste Galois—who didn’t call them by that name—in the context of a connection he found between “field extensions” and “automorphism groups.” Preorder isomorphisms are examples of Galois connections, but Galois connections need not be preorder isomor- phisms, it has weaker conditions.</div> > **Definiton (Galois connection)** >> A Galois connection between preorders P and Q is a pair of monotone maps f : P → Q and g : Q → P such that $$f(p) \le q\ \ if\ and\ only\ if\ p \le g(q)$$ >> We say that f is the left adjoint and g is the right adjoint of the Galois connection **Example 1.6.1** Given any funciton $g: S \mapsto T$, we will show that function g induces a Galois connection $g_!: Prt(S)\leftrightarrow Prt(T): g^*$ The left adjoint is simply $g_!(\sim_S):= \sim_T$, which maps equivalence part under partion of S to equivalence part of T. The right adjoint is simply $g^*(\sim_T):= \sim_S$ For example Let $S = \{1,2,3,4\}$, $T=\{12,3,4\}$, and $g: S\mapsto T$ by $g(1):=g(2):=12$, $g(3):=3$, $g(4):=4$ Now let's assume $c = \{\{1,3\},\{2,4\}\} \in Prt(S)$, so we have $g_!(c) = \{\{12,3,4\}\} \in Prt(T)$, now as $g_!(c)$ already the coaserest partition of Prt(T), we only need to show that $g^*(g_!(c))$ is coaserist partition Prt(S), which is trivially $\{\{1,2,3,4\}\}$ Now let's try another partition $d = \{\{1,2\},\{3\},\{4\}\}\in Prt(S)$. $g_!(d) = \{\{12\},\{3\},\{4\}\} \in Prt(T)$ is the finest one, now take any coaser partition of T, say, $d_T = \{\{12,3\},\{4\}\}$, we have $g^*(d_T) = \{\{1,2,3\},\{4\}\}$ which is coaser than d. With example above, it is not difficult to come across the following Proposition of Galois connection > **Proposition 1.4** > Suppose that f : P → Q and g : Q → P are monotone maps. The following are equivalent > (a). f and g form a Galois connection where f is left adjoint to g, > (b). for every $p\in P$ and $q\in Q$ we have > $$p\le g(f(p))\ and\ f(g(q))\le q$$ >> **Proof:** >> Suppose f is left adjoint to g. Take any p ∈ P, and let $q := f(p)$. By reflexivity, we have $f(p) ≤ q$, so by the Definition 1.95 of Galois connection we have p ≤ g(q), but this means $p ≤ g(f(p))$. The proof that $f(g(q)) ≤ q$ is similar. >> Now suppose that condition in (b) holds for all p ∈ P and q ∈ Q. We want show that $f(p) ≤ q \iff p ≤ g(q)$. Suppose $f(p) ≤ q$; then since g is monotonic, $g(f(p)) ≤ g(q)$, but $p ≤ g(f(p))$ so $p ≤ g(q)$. The proof that $p ≤ g(q) \implies f(p) ≤ q$ is similar.$\blacksquare$ Now we are going to introduce an important Proposition > **Proposition 1.5** > (Right adjoints preserve meets). Let f : P → Q be left adjoint to g : Q → P. Suppose A ⊆ Q any subset, and let $g(A) := \{g(a)\ |\ a ∈ A\}$ be its image. Then if A has a meet$\land A ∈ Q$ then g(A) has a meet $\land g(A) \in P$, and we have > $$g(\land A) \cong \land g(A)$$ > That is, right adjoints preserve meets. Similarly, left adjoints preserve joins: if A ⊆ P is any subset that has a join $\lor A ∈ P$, then f (A) has a join $\lor f(A) \in Q$, and we have > $$f(\lor A) \cong \lor f(A)$$ >> **Proof:** >> We will prove the part left adjoint preserve join, the part of right adjoint will apply similar approach that will leave as exercise. >> let $m:=\lor A \in A \subseteq P$, so we have $f(a) \le f(m), \forall a\in A$ as f is monotonic. So $f(m)$ is a upper bound of $f(A)$, we need to show that it is the smallest one. Indeed, for any $b\in Q$ with $f(a) \le b$, by right adjoint, we have $a \le g(b)$, this says that $g(b)$ is an upper bound in P for A, we have $m \le g(b)$ from definition of m, thus by left adjoint, $f(m)\le b$, as required. $\blacksquare$ Now we introduce the core output of this chapter > **Theorem 1.1 (Adjoint functor theorem for preorders)** > Suppose Q is a preorder that has all meets and let P be any preorder. A monotone map g : Q → P preserves meets if and only if it is a right adjoint. Similarly, if P has all joins and Q is any preorder, a monotone map f : P → Q preserves joins if and only if it is a left adjoint. >>**Proof:** >> We will only prove join preserving part, the meet preserving follow similar approach will leave as exercise. >> we already proved one direction in Proposition 1.5, so we will only prove that if f is a monotone map preserve join, then it is a left adjoint. We need to construct a right adjoint g, with $g(q):=\lor \{p\in P\ |\ f(p)\le q\}$. This is well defined as P has all joins. we need to show that g is monotone. let $q \le q^1$, then $\{p\in P\ |\ f(p)\le q\} \subseteq \{p^1 \in P\ |\ f(p^1)\le q^1\}$, this implies $g(q) \le g(q^1)$ from Proposition 1.3. So g is monotone. Now we need to show that for any $p_0 \in P$ and $q_0 \in Q$, we have $p_0 \le g(f(p_0))$ and $f(g(q_0))\le q_0$ >> for second one: >> $\lor \{f(p) \in Q\ |\ f(p)\le q_0 \} \le q_0 \iff f(\lor \{p \in P\ |\ f(p)\le q_0\})\le q_0 \iff f(g(q_0))\le q_0$ >> for the first one: >> $g(f(p_0)) = \lor \{p\in P\ |\ f(p)\le f(p_0)\} \ge \lor \{p_0\}=p_0$. This finish the proof. $\blacksquare$ **Application:** Given a Galois connection with f : P → Q left adjoint to g : Q → P, then the composition $g\circ f: P \mapsto P$ is a Closure operator satisfying: - $p \le g\circ f (p)$ - $g\circ f\circ g\circ f(p)\cong g\circ f(p)$ > **Exercises 1.6** >1. Show that if f : P → Q has a right adjoint g, then it is unique up to isomorphism. That means, for any other right adjoint $g^1$, we have $g(q) \cong g^1(q)$ for all q ∈ Q. >2. Finish the proof of Proposition 1.4 for the omitted part >3. For excecise 1.6.1, try another partition of S and check the Galois Connection. >4. Prove the Proposition 1.5 with the meet preserving part >5. Prove the Theorem 1.1 with the meet preserving part. ----