7S Chapter 1 Exercises

exercise

Exercises from 7 Sketches, Chapter 1. Solutions: 7S Chapter 1 Solutions. Index: Map of Content.

Exercise 1.1

A function $f:\mathbb{R}\to \mathbb{R}$ is called (a) order-preserving if $x\le y$ implies $f(x)\le f(y)$; (b) metric-preserving if $|x-y|=|f(x)-f(y)|$; (c) addition-preserving if $f(x+y)=f(x)+f(y)$. For each property foo, find an $f$ that is foo-preserving and one that is not.

7 Sketches §1.1; context: Generative Effect, Monotone Map.

Sources: 7 Sketches, Exercise 1.1 and Solution A.1.

Solution: Solution 1.1

Exercise 1.4

What is the result of joining the two systems (partitions of $\{11,12,13,21,22,23\}$): $\{11,12\},\{13\},\{21,22,23\}$ and $\{11\},\{12,13\},\{21\},\{22\},\{23\}$?

7 Sketches §1.1.1; see Join, Preorder of Partitions.

Sources: 7 Sketches, Exercise 1.4 and Solution A.1.

Solution: Solution 1.4

Exercise 1.6

1. Write down all partitions of $\{\bullet ,\ast \}$, order them, and draw the Hasse Diagram. 2. Do the same for $\{1,2,3,4\}$ (15 partitions). Choose two systems $A$, $B$. 3. What is $A\vee B$? 4. Is $A\le A\vee B$ and $B\le A\vee B$? 5. Which $C$ satisfy $A\le C$ and $B\le C$? 6. Is $(A\vee B)\le C$ in each case?

7 Sketches §1.1.2; see Preorder of Partitions, Join.

Sources: 7 Sketches, Exercise 1.6 and Solution A.1.

Solution: Solution 1.6

Exercise 1.7

Using $\mathsf{false}\le \mathsf{true}$ on $\mathbb{B}$, compute $\mathsf{true}\vee \mathsf{false}$, $\mathsf{false}\vee \mathsf{true}$, $\mathsf{true}\vee \mathsf{true}$, $\mathsf{false}\vee \mathsf{false}$.

7 Sketches §1.1.2; see Booleans, Join.

Sources: 7 Sketches, Exercise 1.7 and Solution A.1.

Solution: Solution 1.7

Exercise 1.10

Is it true that 1. $\mathbb{N}=\{n\in \mathbb{Z}\mid n\ge 0\}$? 2. $\mathbb{N}=\{n\in \mathbb{Z}\mid n\ge 1\}$? 3. $\varnothing =\{n\in \mathbb{Z}\mid 1<n<2\}$?

7 Sketches §1.2.1; see Set.

Sources: 7 Sketches, Exercise 1.10 and Solution A.1.

Solution: Solution 1.10

Exercise 1.11

Let $A:=\{h,1\}$, $B:=\{1,2,3\}$. 1. Write the eight subsets of $B$. 2. Union of two nonempty subsets. 3. The six elements of $A\times B$. 4. The five elements of $A\bigsqcup B$. 5. Viewing $A,B\subseteq \{h,1,2,3\}$, the four elements of $A\cup B$.

7 Sketches §1.2.1; see Set, Power Set.

Sources: 7 Sketches, Exercise 1.11 and Solution A.1.

Solution: Solution 1.11

Exercise 1.16

Suppose $\{A_p{\}}_{p\in P}$ and $\{A_{p^{\prime }}^{\prime }{\}}_{p^{\prime }\in P^{\prime }}$ are partitions of $A$ such that for each $p$ there is $p^{\prime }$ with $A_p=A_{p^{\prime }}^{\prime }$. 1. Show there is at most one such $p^{\prime }$. 2. Show that for each $p^{\prime }$ there is a $p$ with $A_p=A_{p^{\prime }}^{\prime }$.

7 Sketches §1.2.1.

Sources: 7 Sketches, Exercise 1.16 and Solution A.1.

Solution: Solution 1.16

Exercise 1.17

For the partition $\{11,12\},\{13\},\{21\},\{22,23\}$ of $\{11,12,13,21,22,23\}$, write down every pair $(a,b)$ in the same part (there should be 10).

7 Sketches §1.2.1; see Partition, Equivalence Relation. Hint: “two elements $a,b$” may be the same element.

Sources: 7 Sketches, Exercise 1.17 and Solution A.1.

Solution: Solution 1.17

Exercise 1.20

Let $\sim$ be an Equivalence Relation on $A$ and $P$ the set of $(\sim )$-closed, $(\sim )$-connected subsets $\{A_p\}$. Show 1. each $A_p$ is nonempty; 2. if $p\ne q$ then $A_p\cap A_q=\varnothing$; 3. $A={\bigcup }_p{A}_p$.

7 Sketches Proposition 1.19 (Partitions Correspond to Equivalence Relations).

Sources: 7 Sketches, Exercise 1.20 and Solution A.1.

Solution: Solution 1.20

Exercise 1.24

1. Find $f:A\to B$ injective but not surjective. 2. Surjective but not injective. For the four relations drawn (between three-element sets): 3. Is it a function? 4. If so, is it injective, surjective, both, or neither?

7 Sketches §1.2.1; see Function, Injection, Surjection.

Sources: 7 Sketches, Exercise 1.24 and Solution A.1.

Solution: Solution 1.24

Exercise 1.25

Suppose $f:A\to \varnothing$ is a function to the empty set. Show that $A$ is empty.

7 Sketches §1.2.1; see Function, Initial Object.

Sources: 7 Sketches, Exercise 1.25 and Solution A.1.

Solution: Solution 1.25

Exercise 1.27

Write down a Surjection corresponding to each of the five partitions of $\{\bullet ,\ast ,\circ \}$.

7 Sketches Example 1.26.

Sources: 7 Sketches, Exercise 1.27 and Solution A.1.

Solution: Solution 1.27

Exercise 1.38

Fill in the source/target table for the Graph of Example 1.37.

Sources: 7 Sketches, Exercise 1.38 and Solution A.1.

Solution: Solution 1.38

Exercise 1.40

What Preorder $(P,\le )$ is depicted by the graph $G$ of Example 1.37 read as a Hasse Diagram?

Sources: 7 Sketches, Exercise 1.40 and Solution A.1.

Solution: Solution 1.40

Exercise 1.41

Does a collection of points, like the Discrete Preorder of Example 1.32, count as a Hasse Diagram?

Sources: 7 Sketches, Exercise 1.41 and Solution A.1.

Solution: Solution 1.41

Exercise 1.42

Let $X$ be the five partitions of $\{\bullet ,\circ ,\ast \}$ ordered by coarseness. Write every pair $x\le y$ (12 pairs).

Sources: 7 Sketches, Exercise 1.42 and Solution A.1.

Solution: Solution 1.42

Exercise 1.44

Is it correct to say that a Discrete Preorder is one where no two elements are comparable?

Sources: 7 Sketches, Exercise 1.44 and Solution A.1.

Solution: Solution 1.44

Exercise 1.46

Write down $1,\dots ,10$ and draw $a\to b$ if $a$ divides $b$. Is it a Total Order?

See Divisibility Order (Hasse diagram drawn there).

Sources: 7 Sketches, Exercise 1.46 and Solution A.1.

Solution: Solution 1.46

Exercise 1.48

Is the usual $\le$ on $\mathbb{R}$ a Total Order?

Sources: 7 Sketches, Exercise 1.48 and Solution A.1.

Solution: Solution 1.48

Exercise 1.51

Draw the Hasse diagrams for $\mathcal{P}(\varnothing )$, $\mathcal{P}\{1\}$, $\mathcal{P}\{1,2\}$.

See Power Set.

Sources: 7 Sketches, Exercise 1.51 and Solution A.1.

Solution: Solution 1.51

Exercise 1.53

For any set $S$, which Surjection corresponds to the coarsest Partition (one part)? To the finest (singletons)?

Sources: 7 Sketches, Exercise 1.53 and Solution A.1.

Solution: Solution 1.53

Exercise 1.55

Prove that the preorder of upper sets on a Discrete Preorder $X$ is the Power Set $\mathcal{P}(X)$.

Sources: 7 Sketches, Exercise 1.55 and Solution A.1.

Solution: Solution 1.55

Exercise 1.57

Draw the Hasse diagram of the Product Preorder of $(b\ge a\le c)$ and $(1\le 2)$; for bonus points compute its upper-set preorder.

Sources: 7 Sketches, Exercise 1.57 and Solution A.1.

Solution: Solution 1.57

Exercise 1.63

Let $X=\{0,1,2\}$. 1. Draw the Hasse diagram of $\mathcal{P}(X)$. 2. Draw $0\le 1\le 2\le 3$. 3. Draw the Cardinality map $|\cdot |$ as dashed lines.

Sources: 7 Sketches, Exercise 1.63 and Solution A.1.

Solution: Solution 1.63

Exercise 1.65

Draw the monotone map $\mathcal{U}(\mathbb{B})\to \mathcal{P}(\mathbb{B})$ of Example 1.64.

Sources: 7 Sketches, Exercise 1.65 and Solution A.1.

Solution: Solution 1.65

Exercise 1.66

For a preorder $P$ and $p\in P$: 1. show $\uparrow p:=\{p^{\prime }\mid p\le p^{\prime }\}$ is an upper set; 2. show $\uparrow :P^{\mathrm{op}}\to \mathcal{U}(P)$ is monotone; 3. show $p\le p^{\prime }$ iff $\uparrow p^{\prime }\subseteq \uparrow p$; 4. draw $\uparrow$ for $P=(b\ge a\le c)$.

Sources: 7 Sketches, Exercise 1.66 and Solution A.1.

Solution: Solution 1.66

Exercise 1.67

Show that if $(P,{\le }_P)$ is a Discrete Preorder, then every function $P\to Q$ is monotone, whatever the order on $Q$.

Sources: 7 Sketches, Exercise 1.67 and Solution A.1.

Solution: Solution 1.67

Exercise 1.69

Choose sets $X,Y$ with at least three elements, a surjective non-identity $f:X\twoheadrightarrow Y$, two partitions $P,Q$ of $Y$, and compute $f^{\ast }(P),f^{\ast }(Q)$.

See Pushforward and Pullback of Partitions, Example 1.68.

Sources: 7 Sketches, Exercise 1.69 and Solution A.1.

Solution: Solution 1.69

Exercise 1.71

Check Proposition 1.70: the identity is monotone, and composites of monotone maps are monotone.

Sources: 7 Sketches, Exercise 1.71 and Solution A.1.

Solution: Solution 1.71

Exercise 1.73

Show that a skeletal Dagger Preorder is a Discrete Preorder.

Sources: 7 Sketches, Exercise 1.73 and Solution A.1.

Solution: Solution 1.73

Exercise 1.77

Show that $\Phi$ (“is $\bullet$ connected to $\ast$?”) is a Monotone Map $\mathrm{Prt}(\{\ast ,\bullet ,\circ \})\to \mathbb{B}$.

Sources: 7 Sketches, Exercise 1.77 and Solution A.1.

Solution: Solution 1.77

Exercise 1.79

Exercise 1.79 (Pullback map). For monotone $f:P\to Q$, the map $f^{\ast }:\mathcal{U}(Q)\to \mathcal{U}(P)$, $U\mapsto f^{-1}(U)$, is monotone. Viewing upper sets as monotone maps to $\mathbb{B}$ (Upper Sets Classified by Maps to Bool), show $f^{\ast }$ is $u\mapsto f;u$.

Sources: 7 Sketches, Exercise 1.79 and Solution A.1.

Solution: Solution 1.79

Exercise 1.80

1. Why is $0$ a lower bound for $S=\{\frac{1}{n+1}\mid n\in \mathbb{N}\}\subseteq \mathbb{R}$? 2. Why is it the greatest lower bound (Meet)?

Sources: 7 Sketches, Exercise 1.80 and Solution A.1.

Solution: Solution 1.80

Exercise 1.85

Let $A=\{p\}$ in a preorder $P$. 1. Show $\bigwedge A\cong p$. 2. Show that if $P$ is a Partial Order then $\bigwedge A=p$. 3. Do the analogous facts hold for $\bigvee$?

Sources: 7 Sketches, Exercise 1.85 and Solution A.1.

Solution: Solution 1.85

Exercise 1.90

In the Divisibility Order on $\mathbb{N}$, what are the common names of the Meet and Join of two numbers?

Sources: 7 Sketches, Exercise 1.90 and Solution A.1.

Solution: Solution 1.90

Exercise 1.94

Prove that for any Monotone Map $f:P\to Q$, if $a\vee b$ and $f(a)\vee f(b)$ exist then $f(a)\vee f(b)\le f(a\vee b)$.

Context: Generative Effect — the effect always produces more, never merely different.

Sources: 7 Sketches, Exercise 1.94 and Solution A.1.

Solution: Solution 1.94

Exercise 1.98

Find a right adjoint for $(3\times -):\mathbb{Z}\to \mathbb{R}$ and show it is correct.

See Galois Connection, Example 1.97.

Sources: 7 Sketches, Exercise 1.98 and Solution A.1.

Solution: Solution 1.98

Exercise 1.99

For $P=Q=\underline{3}$ and the two pictured pairs of monotone maps $f:P\to Q$, $g:Q\to P$, decide whether $f⊣g$.

Sources: 7 Sketches, Exercise 1.99 and Solution A.1.

Solution: Solution 1.99

Exercise 1.101

1. Does $\lceil -/3\rceil :\mathbb{R}\to \mathbb{Z}$ have a left adjoint $L:\mathbb{Z}\to \mathbb{R}$? 2. If not, why?

Sources: 7 Sketches, Exercise 1.101 and Solution A.1.

Solution: Solution 1.101

Exercise 1.103

With $S=\{1,2,3,4\}$, $T=\{12,3,4\}$ and $g$ as in Example 1.102, choose six partitions $c$ of $S$ and compute the pushforward $g_{!}(c)$.

See Pushforward and Pullback of Partitions.

Sources: 7 Sketches, Exercise 1.103 and Solution A.1.

Solution: Solution 1.103

Exercise 1.105

For each of the five partitions $c$ of $T=\{12,3,4\}$, determine the pullback $g^{\ast }(c)$ on $S=\{1,2,3,4\}$.

Sources: 7 Sketches, Exercise 1.105 and Solution A.1.

Solution: Solution 1.105

Exercise 1.106

With $g:S\to T$ as in Example 1.102: choose a nontrivial $c$ on $S$, compute $g_{!}(c)$; choose $d$ coarser than $g_{!}(c)$ and $e$ not coarser; compute $g^{\ast }(d),g^{\ast }(e)$; check $c\le g^{\ast }(d)$ and $c\nleqq g^{\ast }(e)$.

Sources: 7 Sketches, Exercise 1.106 and Solution A.1.

Solution: Solution 1.106

Exercise 1.109

Complete the proof of Proposition 1.107: 1. if $f⊣g$ then $f(g(q))\le q$; 2. if $p\le g(f(p))$ and $f(g(q))\le q$ for all $p,q$, then $p\le g(q)$ iff $f(p)\le q$.

See Galois Connection.

Sources: 7 Sketches, Exercise 1.109 and Solution A.1.

Solution: Solution 1.109

Exercise 1.110

1. Show that if $f:P\to Q$ has a right adjoint $g$, it is unique up to isomorphism: any other right adjoint $g^{\prime }$ has $g(q)\cong g^{\prime }(q)$. 2. Same for left adjoints?

Sources: 7 Sketches, Exercise 1.110 and Solution A.1.

Solution: Solution 1.110

Exercise 1.112

Complete the proof of Proposition 1.111 by showing that left adjoints preserve joins.

See Right Adjoints Preserve Meets.

Sources: 7 Sketches, Exercise 1.112 and Solution A.1.

Solution: Solution 1.112

Exercise 1.114

In Example 1.113 ($P=\{1,2\le 3.9\le 4\}$ with $1,2\le 3.9$; $Q=\{1,2\le 4\}$; $g$ the inclusion, $f$ rounding $3.9$ to $4$), check the twelve conditions $f(p)\le q$ iff $p\le g(q)$.

Sources: 7 Sketches, Exercise 1.114 and Solution A.1.

Solution: Solution 1.114

Exercise 1.118

Choose small sets $X,Y$, a function $f:X\to Y$, subsets $B_1,B_2\subseteq Y$ and $A_1,A_2\subseteq X$; compute $f^{\ast }(B_i)$, $f_{!}(A_i)$, $f_{\ast }(A_i)$.

See Direct Image, Preimage, and Dual Image.

Sources: 7 Sketches, Exercise 1.118 and Solution A.1.

Solution: Solution 1.118

Exercise 1.119

Suppose $f⊣g$. Show 1. $p\le (f;g)(p)$; 2. $(f;g;f;g)(p)\cong (f;g)(p)$.

Hence $f;g$ is a Closure Operator.

Sources: 7 Sketches, Exercise 1.119 and Solution A.1.

Solution: Solution 1.119

Exercise 1.124

Draw the Hasse diagram of $\mathrm{Rel}(\{1,2\})$, all binary relations on $\{1,2\}$.

See Reflexive Transitive Closure.

Sources: 7 Sketches, Exercise 1.124 and Solution A.1.

Solution: Solution 1.124

Exercise 1.125

Let $S=\{1,2,3\}$. 1. Pick a preorder $\le$ on $S$ and write $U(\le )\subseteq S\times S$. 2. Pick relations $Q\subseteq U(\le )$ and $Q^{\prime }⊈U(\le )$. 3. Show concretely $\mathrm{Cl}(Q)⊑\le$. 4. Show $\mathrm{Cl}(Q^{\prime })/⊑\le$.

Sources: 7 Sketches, Exercise 1.125 and Solution A.1.

Solution: Solution 1.125