8.1: Solutions for Chapter 1
- Page ID
- 54938
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)For each of the following properties, we need to find a function f : \(\mathbb{R}\) → \(\mathbb{R}\) that preserves it, and another function call it that does not.
order-preserving: Take f(x) = x + 5; if x ≤ y then x + 5 ≤ y + 5, so f is order-preserving.
Take g(x) := −x; even though 1 ≤ 2, the required inequality −1 ≤\(^{?}\) −2 does not hold, so g is not order-preserving.
metric-preserving: Take f(x) := x + 5; for any x, y we have |x − y| = |(x + 5) − (y + 5)| by the rules of arithmetic, so |x − y| = |f (x) − f (y)|, meaning f preserves metric. Take g(x) := 2 ∗ x; then with x = 1 and y = 2 we have |x − y| = 1 but |2x − 2y| = 2, so g does not preserve the metric.
addition-preserving: Take f(x) := 3 ∗ x; for any x, y we have 3 ∗ (x + y) = (3 ∗ x) + (3 ∗ y), so f preserves addition.
Take g(x) := x + 1; then with x = 0 and y = 0, we have g(x + y) = 1, but g(x) + g(y) = 2, so g does not preserve addition.
Here is the join of the two systems:
1. Here is the Hasse diagram for partitions of the two element set {•,∗}:
2. Here is a picture (using text, rather than circles) for partitions of the set 1, 2, 3, 4:
For the remaining parts, we choose A = (12)(3)(4) and B = (13)(2)(4).
3. A \(\land\) B = (123)(4).
4. Yes, it is true that A ≤ (A \(\lor\) B) and that B ≤ (A \(\lor\) B).
5. The systems C with A ≤ C and B ≤ C are: (123)(4) and (1234).
6.Yes, it is true that in each case (A \(\lor\) B) ≤ C.
1. true \(\lor\) false = true.
2. false \(\lor\) true = true.
3. true \(\lor\) true = true.
4. false \(\lor\) false = false.
1. This is true: a natural number is exactly an integer that is at least 0.
2. This is false: 0 \(\in\) \(\mathbb{N}\) but 0 \(\not \in\) {n \(\in\) \(\mathbb{Z}\) | n ≥ 1}.
3. This is true: no elements of \(\mathbb{Z}\) are strictly between 1 and 2.
1. The eight subsets of B := {1, 2, 3} are
Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.
2. The union of {1, 2, 3} and {1} is {1, 2, 3} \(\bigcup\) {1} = {1,2,3}.
3. The six elements of {h, 1} × {1, 2, 3} are
(h, 1), (h, 2), (h, 3), (1, 1), (1, 2), (1, 3).
4. The five elements of {h, 1} ⊔ {1, 2, 3} are
(h, 1), (1, 1), (1, 2), (2, 2), (3, 2).
5. The four elements of {h, 1} \(\bigcup\) {1, 2, 3} are
h, 1, 2, 3.
Suppose that A is a set and {A\(_{p}\)}\(_{p \in P}\) and {A′\(_{p'}\)}\(_{p' \in P'}\) are two partitions of A such that for each p \(\in\) P there exists a p′ \(\in\) P′ with A\(_{p}\) = A′\(_{p'}\).
1. Given p \(\in\) P, suppose we had p′\(_{1}\),p′\(_{2}\) \(\in\) P′such that A\(_{p}\) = A′\(_{p'_{1}}\) and A\(_{p}\) = A′\(_{p'_{2}}\). Well then A\(_{p'_{1}}\) = A\(_{p'_{2}}\), so in particular A\(_{p'_{1}}\) ∩ A\(_{p'_{2}}\) =A\(_{p'_{1}}\). By the definition of partition (1.14), A\(_{p'_{1}}\) \(\neq\) Ø, and yet if p\(_{1}\) \(\neq\) p\(_{2}\) then A\(_{p'_{1}}\) ∩ A\(_{p'_{2}}\) = Ø. This can’t be, so we must have p′\(_{1}\) = p′\(_{2}\), as desired.
2. Suppose given p′ \(\in\) P′; we want to show that there is a p \(\in\) P such that A\(_{p}\) = A′\(_{p'}\).
Since A′\(_{p'}\) \(\neq\) Ø is nonempty by definition, we can pick some a \(\in\) A′\(_{p'}\); since A′\(_{p'}\) \(\subseteq\) A, we have a \(\in\) A.
Finally, since A = \(\bigcup_{p \in P} A_{p}\), there is some p with a \(\in\) A\(_{p}\).
This is our candidate p; now we show that A\(_{p}\) = A′\(_{p'}\).
By assumption there is some p′′ \(\in\) P′ with A\(_{p}\) = A′\(_{p'}\), so now a \(\in\) A′\(_{p''}\) and a \(\in\) A′\(_{p' '}\), so a \(\in\) A′\(_{p'}\) ∩ A′\(_{p''}\). Again by definition, having a nonempty intersection means p′ = p′′. So we conclude that A\(_{p}\) = A′\(_{p'}\).
The pairs (a, b) such that a ∼ b are:
(11, 11) (21, 21) (12, 11) (12, 12) (13, 13)
(21, 21) (22, 22) (12, 23) (23, 22) (23, 23)
1. One aspect in the definition of the parts is that they are connected, and one aspect of that is that they are nonempty. So each part A\(_{p}\) is nonempty.
2. Suppose p \(\neq\) q, i.e. Ap and Aq are not exactly the same set. To prove A\(_{p}\) ∩ A\(_{q}\) = Ø, we suppose otherwise and derive a contradiction.
So suppose there exists a \(\in\) A\(_{p}\) ∩ A\(_{q}\); we will show that A\(_{p}\) = A\(_{q}\), which contradicts an earlier hypothesis. To show that these two subsets are equal, it suffices to show that a′ \(\in\) A\(_{p}\) iff a′ \(\in\) A\(_{q}\) for all a′ \(\in\) A.
Suppose a′ \(\in\) A\(_{p}\); then because A\(_{p}\) is connected, we have a ∼ a′. And because A\(_{q}\) is closed, a′ \(\in\) A\(_{q}\).
In just the way, if a′ \(\in\) A\(_{q}\) then because A\(_{q}\) is connected and A\(_{p}\) is closed, a′ \(\in\) A\(_{p}\), and we are done.
3. To show that A = \(\bigcup_{p \in P} A_{p}\), it suffices to show that for each a \(\in\) A, there is some p ∈ P such that a ∈ A\(_{p}\) .
We said that P was the set of closed and connected subsets of A, so it suffices to show that there is some closed and connected subset containing a.
Let X := {a′ \(\in\) A | a′ ∼ a}; we claim it is closed and connected and contains a. To see X is closed, suppose a′ \(\in\) X and b ∼ a′; then b ∼ a by transitivity and symmetry of ∼, so b \(\in\) X. To see that X is connected, suppose b, c \(\in\) X; then b ∼ a and c ∼ a so b ∼ c by the transitivity and symmetry of ∼. Finally, a \(\in\) X by the reflexivity of ∼.
1. The unique function Ø → {1} is injective but not surjective.
2. The unique function {a, b} → {1} is surjective but not injective.
3. These second and third are not functions; the first and fourth are functions.
4. Neither the second nor third is ‘total’. Moreover, the second one is not deterministic. The first one is a function which is not injective and not surjective. The fourth one is a function which is both injective and surjective.
By Definition 1.22, a function f : A → Ø is a subset F \(\subseteq\) A × Ø such that for all a \(\in\) A, there exists a unique b \(\in\) Ø with (a, b) \(\in\) F.
But there are no elements b \(\in\)\(^{?}\) Ø, so if F is to have the above property, there can be no a \(\in\) A either; i.e. A must be empty.
Below each partition, we draw a corresponding surjection out of {•, ∗, ◦}:
The graph G from Exercise 1.38 is a strange Hasse diagram because it has two arrows 1 → 3 and a loop, both of which are “useless” from a preorder point-of-view. But that does not prevent our formula from working. The preorder (P, ≤) is given by taking P := V = {1, 2, 3, 4} and writing p ≤ q whenever there exists a path from p to q. So:
1 ≤ 1, 1 ≤ 2, 1 ≤ 3, 2 ≤ 2, 2 ≤ 3, 3 ≤ 3, 4 ≤ 4
A collection of points, e.g. • • • is a Hasse diagram, namely for the discrete order, i.e. for the order where x ≤ y iff x = y.
Let’s write the five elements of X as
Our job is to write down all 12 pairs of x\(_{1}\), x\(_{2}\) \(\in\) X with x\(_{1}\) ≤ x\(_{2}\). Here they are:
The statement in the text is almost correct. It is correct to say that a discrete preorder is one where x and y are comparable if and only if x = y.
No, it is not a total order; for example 4 \(\nleq\) 6 and 6 \(\nleq\) 4.
Yes, the usual ≤ ordering is a total order on \(\mathbb{R}\): for every a, b \(\in\) \(\mathbb{R}\) either a ≤ b or b ≤ a.
The Hasse diagrams for P(Ø), P{1}, and P{1, 2} are
The coarsest partition on S corresponds to the unique function !: S → {1}. The finest partition on S corresponds to the identity function id\(_{S}\) : S → S.
If X has the discrete preorder, then every subset U of X is an upper set: indeed, if p \(\in\) U, the only q such that p ≤ q is p itself, so q is definitely in U! This means that U(X) contains all subsets of X, so it’s exactly the power set, U(X) = P(X).
The product preorder and its upper set preorder are:
With X = {0, 1, 2}, the Hasse diagram for P(X), the preorder 0 ≤ · · · ≤ 3, and the cardinality map between them are shown below:
- Let q \(\in\) ↑p, and suppose q ≤ q′. Since q \(\in\) ↑p, we have p ≤ q. Thus by transitivity p ≤ q′,so q′ \(\in\) ↑ p. Thus ↑ p is an upper set.
- Suppose p ≤ q in P; this means that q ≤\(^{op}\) p inP\(^{op}\). We must show that ↑q \(\subseteq\) ↑p. Take any q′ \(\in\) ↑ q. Then q ≤ q′, so by transitivitiy p ≤ q′, and hence q′ \(\in\) ↑ p. Thus ↑ q \(\subseteq\) ↑ p.
- Monotonicity of ↑ says that p ≤ p′ implies ↑(p′) \(\subseteq\) ↑(p). We must prove the other direction, that if p \(\nleq\) p′ then ↑(p′) \(\subseteq\) ↑(p). This is straightforward, since by reflexivity we always have p′ \(\in\) ↑(p′), but if p \(\nleq\) p′, then p′ \(\not \in\) ↑(p), so ↑(p′) \(\not \subseteq\) ↑(p).
- The map ↑: P\(^{op}\) → U(P) can be depicted:
Suppose (P, ≤\(_{P}\)) is a discrete preorder and that (Q , ≤\(_{Q}\)) is any preorder.
We want to show that every function f :P → Q is monotone, i.e. that if p\(_{1}\) ≤\(_{P}\) p\(_{2}\) then f (p\(_{1}\)) ≤Q f (p\(_{2}\)).
But in P we have p\(_{1}\) ≤\(_{P}\) p\(_{2}\) iff p\(_{1}\) = p\(_{2}\); that’s what discrete means.
If p\(_{1}\) ≤\(_{P}\) p\(_{2}\) then p\(_{1}\) = p\(_{2}\), so f (p\(_{1}\)) = f (p\(_{2}\)), so f (p\(_{1}\)) ≤ f (p\(_{2}\)).
Let X = \(\mathbb{Z}\) = {..., −2, −1, 0, 1, ...} be the set of all integers, and let Y = {n, z, p}; let f : X → Y send negative numbers to n, zero to z, and positive integers to p. This is surjective because all three elements of Y are hit.
We consider two partitions of Y, namely P := (nz)(p) and Q := (np)(z). Technically, these are notation for \(\{\{n, z\},\{p\}\}\) and \(\{\{n, p\},\{z\}\}\) as sets of disjoint subsets whose union is Y. Their pulled back partitions are \(f^{*}\) P=(..., -2, -1, 0)(1, 2, ...) and \( f^{*}Q\) = (0)(..., -2,-1,1,2,...), or technically
\(f^{*}(P)\) = \(\{\{x \in \mathbb{Z} \mid x \leq 0\}\),\(\{x \in \mathbb{Z} \mid x \geq 1\}\}\) and \(f^{*}(Q)\) = \(\{\{0\},\{x \in \mathbb{Z} \mid x \neq 0\}\}\).
We have preorders (P, ≤\(_{P}\)), (Q, ≤\(_{Q}\)), and (R, ≤\(_{R}\)), and we have monotone maps f : P → Q and g : Q → R.
1. To see that id\(_{P}\) is monotone, we need to show that if p\(_{1}\) ≤\(_{P}\) p\(_{2}\) then id\(_{P}\)(p\(_{1}\)) ≤ id\(_{P}\)(p\(_{2}\)). But id\(_{P}\)(p) = p for all p \(\in\) P, so this is clear.
2. We have that p\(_{1}\) ≤\(_{P}\) p\(_{2}\) implies f (p\(_{1}\)) ≤\(_{Q}\) f (p\(_{2}\)) and that q\(_{1}\) ≤\(_{Q}\) q\(_{2}\) implies g(q\(_{1}\)) ≤\(_{R}\) g(q\(_{2}\)).
By substitution, p\(_{1}\) ≤\(_{P}\) p\(_{2}\) implies g(f (p1)) ≤\(_{R}\) g(f (p2)) which is exactly what is required for (f ; g) to be monotone.
We need to show that if (P, ≤\(_{P}\)) is both skeletal and dagger, then it is discrete. So suppose it is skeletal, i.e. p\(_{1}\) ≤ p\(_{2}\) and p\(_{2}\) ≤ p\(_{1}\) implies p\(_{1}\) = p\(_{2}\). And suppose it is dagger, i.e. p\(_{1}\) ≤ p\(_{2}\) implies p\(_{2}\) ≤ p\(_{1}\). Well then p\(_{1}\) ≤ p\(_{2}\) implies p\(_{1}\) = p\(_{2}\), and this is exactly the definition of P being discrete.
The map Φ from Section 1.1.1 took partitions of {•, ∗, ◦} and returned true or false based on whether or not • was in the same partition as ∗. We need to see that it’s actually a monotone map Φ : Prt({•, ∗, ◦}) → \(\mathbb{B}\). So suppose P, Q are partitions with P ≤ Q; we need to show that if Φ(P) = true then Φ(Q) = true. By definition P ≤ Q means that P is finer than Q: i.e. P differentiates more stuff, and Q lumps more stuff together. Technically, x ∼P y implies x ∼Q y for all x, y \(\in\) {•, ∗, ◦}. Applying this to •, ∗ gives the result.
Given a function f : P → Q, we have f \(^{∗}\) : U(Q) → U(P) given by U \(\longmapsto\) f \(^{−1}\)(U). But upper sets in Q are classified by monotone maps u : Q → \(\mathbb{B}\), and similarly for P; our job is to show that f \(^{∗}\)(U) is given by composing the classifier u with f. Given an upper set U \(\subseteq\) Q, let u : Q → \(\mathbb{B}\) be the corresponding monotone map, which sends q \(\longmapsto\) true iff q \(\in\) U.
Then (f ; u) : P→ \(\mathbb{B}\) sends p \(\longmapsto\) true iff f(p) \(\in\) U; it corresponds to the upper set {p \(\in\) P | f (p) \(\in\) U} which is exactly f \(^{−1}\)(U).
1. 0 is a lower bound for \(S=\left\{\frac{1}{n+1} \mid n \in \mathbb{N}\right\}\) because 0 ≤ \(\frac{1}{n+1}\) for any n \(\in\) \(\mathbb{N}\).
2. Suppose that b is a lower bound for S; we want to see that b ≤ 0. If one believes to the contrary that 0 < b, then consider 1/b; it is a real number so we can find a natural number n that’s bigger 1/b < n < n + 1. This implies 1 < b(n + 1) and hence \(\frac{1}{n+1}\) < b, but that is a contradiction of b being a lower bound for S. The false believer is defeated!
We have a preorder (P, ≤), an element p \(\in\) P, and a subset A = {p} with one element.
- To see that \(\bigwedge\)A \(\cong\) p, we need to show that p ≤ a for all a \(\in\) A and that if q ≤ a for all a \(\in\) A then q ≤ p. But the only a \(\in\) A is a = p, so both are obvious.
- We know p is a meet of A, so if q is also a meet of A thenq ≤ a for all a \(\in\) A so q ≤ p; similarly p ≤ a for all a \(\in\) A, so p ≤ q. Then by definition we have p \(\cong\) q, and since (P, ≤) is a partial order, p = q.
- The analogous facts are true when \(\bigwedge\) is replaced by \(\bigvee\); the only change in the argument is to replace ≤ by ≥ and ‘meet’ by ‘join’ everywhere.
The meet of 4 and 6 is the highest number in the order that divides both of them; the numbers dividing both are 1 and 2, and 2 is higher, so 4 \(\land\) 6 = 2. Similar reasoning shows that 4 \(\lor\) 6 = 12.
The meet is the ‘greatest common divisor’ and the join is the ‘least common multiple,’ and this holds up for all pairs m, n \(\in\) \(\mathbb{N}\) not just 4, 6.
Since f is monotone, the facts that a ≤ a \(\lor\) b and b ≤ a \(\lor\) b imply that f (a) ≤ f (a \(\lor\) b) and f (b) ≤ f (a \(\lor\) b). But by definition of join, f (a) \(\lor\) f (b) is the largest element with that property, so f (a) \(\lor\) f (b) ≤ f (a \(\lor\) b), as desired.
By analogy with Example 1.97, the right adjoint for (3 × −) should be ⌊−/3⌋. But to prove this is correct, we must show that for any any r \(\in\) \(\mathbb{R}\) and z \(\in\) \(\mathbb{Z}\) we have z ≤ ⌊r/3⌋ iff 3 ∗ z ≤ r. Suppose the largest integer below r/3 is z′ := ⌊r/3⌋. Then z ≤ z′ implies 3∗z ≤ 3∗z′ ≤ 3∗r/3 = r, giving one direction. For the other, suppose 3 ∗ z ≤ r. Then dividing both sides by 3, we have z = 3 ∗ z/3 ≤ r/3. Since z is an integer below r/3 it is below ⌊r/3⌋ because ⌊r/3⌋ is the greatest integer below r/3, and we are done.
1. We need to check that for all nine pairs {(p,q) | 1 ≤ p ≤ 3 and 1 ≤ q ≤ 3} we have f (p) ≤ q iff p ≤ g(q), where f and g are the functions shown here:
When p = q = 1 we have f (p) = 1 and g(q) = 2, so both f (p) = 1 ≤ 1 = q and p = 1 ≤ g(q); it works! Same sort of story happens when (p, q) is (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), and (3, 3). A different story happens for p = 3, q = 1 and p = 3, q = 2. In those cases f (p) = 3 and g(q) = 2, and neither inequality holds: f (p) \(\nleq\) q and p \(\nleq\) g(q). But that’s fine, we still have f (p) ≤ q iff p ≤ g(q) in all nine cases, as desired.
2.
Here f is not left adjoint to g because f (2) \(\nleq\) 1 but 2 ≤ g(1).
- Let’s suppose we have a monotone map L: \(\mathbb{Z}\) → \(\mathbb{R}\) that’s left adjoint to ⌈−/3⌉ and see what happens. Writing C(r) :=⌈r/3⌉, then for all z \(\in\) \(\mathbb{Z}\) and r \(\in\) \(\mathbb{R}\) we have L(z) ≤ r iff z ≤ C(r) by definition of adjunction. So take z = 1 and r = .01; then ⌈r/3⌉ = 1 so z ≤ C(r), and hence L(z) ≤ r, i.e. L(1) ≤ 0.01. In the same way L(1) ≤ r for all r > 0, so L(1) ≤ 0. By definition of adjunction 1 ≤ C(0) = ⌈0/3⌉ = 0, a contradiction.
- There’s no left adjoint, because starting with an arbitrary one, we derived a contradiction.
We have S = {1, 2, 3, 4}, T = {12, 3, 4}, and g : S → T the “obvious” function between them; see Example 1.102. Take c\(_{1}\), c\(_{2}\), c\(_{3}\), c\(_{4}\) to be the following partitions:
Then the induced partitions g!(c\(_{1}\)), g!(c\(_{2}\)), g!(c\(_{3}\)), and g!(c\(_{4}\)) on T are:
1. We choose the following partition c on S and compute its push forward g!(c):
2. Let d be the partition as shown, which was chosen to be coarser than g!(c).
3. Let e be the partition as shown, which was chosen to not be coarser than g!(c).
4. Here are \(g^{∗}(d)\) and \(g^{∗}(e)\):
5. Comparing c, the left-hand partition in part 1., with \(g^{∗}(d)\) and \(g^{∗}(e)\), we indeed have c ≤ \(g^{∗}(d)\) but c \(\nleq\) \(g^{∗}(e)\)), as desired.
Suppose P and Q are preorders, and that \(f: P \leftrightarrows Q: g\) are monotone maps.
- Suppose f is left adjoint to g. By definition this means f(p) ≤ q iff p ≤ g(q), for all p \(\in\) P and q \(\in\) Q. Then starting with the reflexivity fact g(q) ≤ g(q), the definition with p := g(q) gives f (g(q)) ≤ q for all q.
- Suppose that p ≤ g( f (p)) and f (g(q)) ≤ q for all p \(\in\) P and q \(\in\) Q. We first want to show that p ≤ g(q) implies f (p) ≤ q, so assume p ≤ g(q). Then applying the monotone map f to both sides, we have f (p) ≤ f (g(q)), and then by transitivity f (g(q)) ≤ q implies f (p) ≤ q, as desired. The other direction is similar.
- Suppose that f :P → Q has two right adjoints, g, g′ : Q → P. We want to show that g(q) \(\cong\) g′(q) for all q \(\in\) Q. We will prove g(q) ≤ g′(q); the inequality g′(q) ≤ g(q) is similar. To do this, we use the fact that p ≤ g′( f (p)) and f (g(q)) ≤ q for all p, q by Eq. (1.108). Then the trick is to reason as follows:
g(q) ≤ g′(f (g(q))) ≤ g′(q).
- It is the same for left adjoints.
Suppose f : P → Q is left adjoint to g : Q → P. Let A \(\subseteq\) P be any subset and let j := \(\bigvee\)A be its join.
Then since f is monotone f (a) ≤ f (j) for all a \(\in\) A, so f (j) is an upper bound for the set f (A). We want to show it is the least upper bound, so take any other upper bound b for f (A), meaning we have f (a) ≤ b for all a \(\in\) A. Then by definition of adjunction, we also have a ≤ g(b) for all a \(\in\) A. By definition of join, we have j ≤ g(b). Again by definition of adjunction f (j) ≤ b, as desired.
We want to show that in the following picture, g is really right adjoint to f :
Here g preserves labels and f rounds 3.9 to 4.
There are twelve tiny things to check: for each p \(\in\) P and q \(\in\) Q, we need to see that f (p) ≤ q iff p ≤ g(q).
Consider the function shown below, which “projects straight down”:
1. Let B\(_{1}\) := {a, b} and B\(_{2}\) := {c}.Then f \(^{∗}\)(B\(_{1}\)) = {a\(_{1}\)} and f \(^{∗}\)(B\(_{2}\)) = {c\(_{1}\), c\(_{2}\)}.
2. Let A\(_{1}\) := Ø and A\(_{1}\) := {a\(_{1}\), c\(_{1}\)}. Thenf\(_{!}\)(A\(_{1}\)) := Ø and f\(_{!}\)(A\(_{2}\)) = {a,c}.
3. With the same A\(_{1}\) and A\(_{2}\), we compute f \(^{∗}\)(A\(_{1}\)) = {b} and f \(^{∗}\)(A\(_{2}\)) = {a, b}.
Assume f :P → Q is left adjoint to g :Q → P.
- It is part of the definition of adjunction (Proposition1.107) that p ≤ g(f (p)), and of course g(f (p)) and ( f ; g)(p) mean the same thing.
- We want to show that g(f (g (f (p)))) ≤ g(f (p)) and g(f (p)) ≤ g(f (g(f (p)))) for all p. The latter is just the fact that p′ ≤ g(f (p′)) for any p′, applied with g(f (p)) in place of p′. The former uses that f (g(q)) ≤ q, with f (p) substituted for q: this gives f (g( f (p))) ≤ f (p), and then we apply g to both sides.
We denote tuples (a, b) by ab for space reasons. So the relation {(1, 1), (1, 2), (2, 1)} will be denoted {11, 12, 21}.
Let S := {1, 2, 3}.
1. Let ≤ be the preorder with 1 ≤ 2, and of course 1 ≤ 1, 2 ≤ 2, and 3 ≤ 3. Then U(≤) = {(1, 1), (1, 2), (2, 2), (3, 3)}.
- Let Q := {(1,1)} and Q′ := {(2,1)}.
- The closure Cl(Q) of Q is the smallest preorder containing (1,1), which is Cl(Q) = {(1,1),(2,2),(3,3)}.
Similarly, Cl(Q′) = {(1, 1), (2, 1), (2, 2), (3, 3)}. It is easy to see that Cl(Q) \(\sqsubseteq\)\) ≤ because every ordered pair in Cl(Q) is also in ≤.
- It is easy to see that Cl(Q′) \(\not \sqsubseteq\) ≤ because the ordered pair (2,1) is in Cl(Q′) but is not in ≤.