Practical Foundations of Mathematics

Paul Taylor

3.10  Exercises III

  1. Give an example of a strictly monotone function which is not injective.

  2. Let (X,\preccurlyeq ) be a preorder. Show that the quotient poset X/ ~ constructed in Proposition 3.1.10 is isomorphic to the image of X in its regular representation.

  3. A binary relation < is irreflexive if "x.x\not < x. Show that

    (a)
    any irreflexive relation can be recovered from its reflexive closure, characterising (in terms of decidability of equality) those reflexive binary relations that arise in this way from irreflexive ones;

    (b)
    Proposition 2.5.6 and Definition  3.2.1(c) agree on minimality;

    (c)
    the interleaved product agrees with the componentwise order, as defined in Propositions 2.6.9 and 3.5.1;

    (d)
    any function which is injective and monotone ( ie it preserves the reflexive relation) is strictly monotone (it preserves the irreflexive one), but not conversely.

    Reformulate the induction scheme (Definition  2.5.3) with respect to the reflexive relation.

  4. Show that (X, £ ) satisfies "x,y.x £ yÚy £ x iff it has binary joins and every monotone function f:X® Y preserves them. [Hint: use the representation by lower subsets.]

  5. Show that an element of a poset is locally least iff it is least in its connected component (Lemma  1.2.4), and that if the poset has pullbacks (meets of pairs which are bounded above) then it suffices that the element be minimal.

  6. For Á Ì W, show that ÚÁ Û ({T} Ì Á) and Ù IÛ (Á Ì {T} ).

  7. Describe the greatest common divisor and least common multiple of a pair of ideals in a commutative ring.

  8. Show that the various forms of the absorptive law mentioned before Proposition 3.2.13 agree.

  9. Show that any lattice homomorphism between Boolean algebras also preserves \lnot and Þ . Find a sublattice of a Boolean algebra which is a Heyting lattice but for which the implication operations are different.

  10. Let R be a ring such that "x:R.x2 = x. Show that "x.x+x = 0 and "x,y.x*y = y*x, and that xÚy º x+y-x*y, xÙy = x*y make R a Boolean algebra. Conversely, define the ring operations on any Boolean algebra, and show that a function between such structures is a ring homomorphism iff it is a homomorphism for the logical operations.

  11. Let X be a distributive lattice, but write 0, + and x instead of ^, Ú and Ù. Show that any subset Á Ì X is an ideal in the sense of ring theory (Example 2.1.3(b)) via this notation iff it is a directed lower set.

  12. Write \YYX:[X ® X]® X for the operation which yields the least fixed point of a continuous function on an ipo X. Express \YYX as \YYY(F) for some F:Y® Y and hence deduce (without any further order-theoretic calculation) that \YYX is itself continuous.

  13. (Hans Bekivc) Let h:DxE® DxE in IPO. For any e Î E devise some \funfe:D® D and hence define p(e) Î D as its fixed point. Similarly q:D® E. Using \YYD again, obtain a fixed point of h.

  14. Show that if a poset X has, or a function X ® Y preserves, both finite (^, Ú) and directed (Ú­ ) joins, then it has or preserves all joins.

  15. Let U:J® Á be a cofinal function between posets. Show that if J is directed then so is Á, and conversely if U is also full. Show that any countable directed poset has a cofinal sequence, and hence that the corresponding notions of countable Scott continuity coincide.

  16. Suppose that every ipo has a maximal element (this assertion is known as Zorn's Lemma), and assume excluded middle. Deduce the axiom of choice (Definition  1.8.8). [Hint: consider the ipo of partial functions contained in the given entire relation.]

  17. Let X be a meet-semilattice. Show that IdlX is a preframe, ie it has meets and they distribute over directed join in each argument. Also show that X® IdlX preserves T and meets.

  18. Let Y be a preframe and X a dcpo. Show that [X® Y], the dcpo of Scott-continuous functions, is also a preframe, binary meets being computed pointwise.

  19. Let X and Y be posets or domains. Show that their disjoint union X+Y (with no instances of the order relation linking the two summands) obeys the rules for sums (Remark 2.3.10).

  20. Let X, Y and Z be meet- semilattices and f:Xx Y® Z a monotone function such that f(x,-) and f(-,y) preserve binary meets, for each x Î X or y Î Y. Find a necessary and sufficient condition (in terms of the order relations but not the meets) which makes f a semilattice homomorphism ( cf Corollary  3.5.13).

  21. A poset X is boundedly complete if any subset Á Ì X which has some upper bound Á £ q actually has a join. Show that the product and function-space of two such posets are boundedly complete. Do the same for boundedly complete domains (in which directed subsets also have joins), with the Scott-continuous function-space.

  22. Construct the meet and join of a bounded inhabited set of real numbers, considered as Dedekind cuts. Assume excluded middle. Under what (simple) condition does a monotone function R® R have adjoints? Express limsup and liminf as extrema.

  23. Show that FV\dashv Cn (Notation  2.3.6).

  24. Show that for any lattice X there is an adjunction omitted diagram environment If this is an isomorphism then X is called a modular lattice.

  25. Suppose F\dashv U and U\dashv F between posets. Show that they are mutually inverse, or form a strong equivalence in the case of preorders.

  26. Let U:A\twoheadrightarrow X be a surjective function between sets. Define a preorder £ A such that U is an equivalence function (Remark 3.6.7), where £ X is discrete. Show that U is part of a strong equivalence iff it is split epi. In other words, every weak equivalence is strong iff the axiom of choice holds.

  27. Let \leftadj1:S® \A1 and \leftadj2: S® \A2 be equivalence functions between preorders. Find equivalence functions \funcGi:\Ai® \bal B with \funcG1o \leftadj1 = \funcG2o\leftadj2. [Hint: let the underlying set of \bal B be the union of those of \A1 and \A2.]

  28. Show that a semilattice equipped with an additional binary operation Þ is a Heyting semilattice (Definition  3.6.15) iff it satisfies omitted eqnarray* environment

  29. Describe implication and infinitary meet in the frame of open sets of any topological space. [Hint: do negation first.] Let f:X® Y be a continuous function. Describe the adjunctions f*\dashv \funf* between the frames of open subsets of X and Y.

  30. For any poset X, show that shv (X) is a complete Heyting lattice with [AÞ B] = { x|"y.x ³ y Î AÞ y Î B}. [Hint: use Proposition 3.1.8(b) and (-)ÇA\dashv (AÞ ( = )).] Show that x® X¯ x preserves Þ . This interpretation of intuitionistic implication is due to Saul Kripke and was inspired by Definition  3.8.2 for modal logic.

  31. Show that a poset is boundedly complete (Exercise  3.21) iff it has meets of all inhabited subsets.

  32. Let X be a poset with T and U:X® Y a monotone function to any poset. Show that it is cofinal iff U(T) is the top element of Y.

  33. Let F\dashv U with F injective. Show that F preserves minimal upper bounds, but U need not preserve maximal elements. Conversely, find a criterion involving minimal upper bounds for F:X Ì A to have a right adjoint.

  34. Show that the following are equivalent for a poset X:

    (a)
    X¯ q is a complete lattice for each q Î X;

    (b)
    X has meets of all subsets which are bounded above ( wide pullbacks, Example  7.3.2(h)), but not necessarily T;

    (c)
    for each diagram Á Ì X with an upper bound Á £ q there is a unique minimal upper bound for Á in X below q.

    X is then called an L-poset, and an L-domain if it also has all directed joins. Formulate and prove an adjoint function theorem for L-posets. Show that if U:X® Y preserves wide pullbacks and is cofinal then it has a left adjoint. (Notice how introducing a degree of uniqueness improves the result by allowing us to drop the injectivity assumption.)

  35. Describe the closure and coclosure operations arising from the examples of adjunctions in Section 3.6, and characterise the (co)closed subsets or elements.

  36. Let M:P(S)® P(S) be any closure operation. Show that it arises from the system of closure conditions
    K\triangleright t     if    t Î M(K),
    and that this is a saturated system of closure conditions, ie

    {t}\triangleright t        and       omitted prooftree environment
    but induction for \triangleright is essentially trivial. Show that the saturation of a unary closure condition < is its reflexive- transitive closure £ .

  37. Show that if M is Scott-continuous in the previous exercise then it suffices to use finite K.

  38. Let M be a closure operation on a poset or preorder (S, £ ). Let A be the set S equipped with the relation that A\preceq B if M(A) £ B. Show that (A, \preceq ) is a preorder which is equivalent to the set of fixed points of M on S. Exercise 3.56 is an example of this construction.

  39. (Tarski) Let S be a complete ( meet-semi) lattice and T:S® S a monotone function. Put A = Ù{X:S|T X £ X} and show that TA £ A. Using T(TA) £ TA, deduce that A is the least fixed point.

  40. With the same data, call an element X Î S well founded if X £ T X and "U.TUÙX £ U £ X Þ U = X. Show that if X is well founded then so is T X, and that any join of well founded elements is again well founded, so there is a greatest well founded element, and it is fixed by T. Show that if X is well founded and Tq £ q then X £ q. Compare this with the proof of Proposition  3.7.11. Show that the simpler condition that X £ T X and "U.TUÙX £ UÞ U = X is equivalent to well-foundedness.

  41. Let T:S® S be a Ù-preserving endofunction of a frame, X Î S a well founded element and Y £ X. Show that if also Y £ T Y then Y is well founded. [Hint: given TVÙY £ V £ Y consider U = (YÞ V)Ù X.] Show that the property Y £ T Y is not automatic. [Hint: S = P(2).]

  42. Let T:P(S)® P(S) be defined as in Lemma 3.7.10 from a closure condition \triangleright . Show that X is a well founded element of P(S) in the sense of Exercise  3.40 iff X has no non-trivial relatively \triangleright -closed subset ( cf Definition  3.7.8). Show also that, when \triangleright is itself defined from a binary relation \prec by Example  3.7.9(e), this is equivalent to well-foundedness of \prec on X (Definition 2.5.3).

  43. Proposition 2.5.6ff described classical approaches to induction. Discuss induction on closure conditions (Definition 3.7.8) in this fashion, giving a condition for an element not to be in the smallest closed subset.

  44. Use Proposition 3.7.11 to show that the set of closure operations on a complete lattice S is itself the image of a closure operation on [S® S]. Now let S be a dcpo. Show that the set of Scott-continuous closure operations on S is the image of a closure operation defined on id¯ [S® S] º {T :S® S|\idS £ T}.

  45. (Dmitri Pataraia) By Lemma  3.5.7, the set of inflationary monotone functions id £ f:A® A on any dcpo A forms an ipo. Show that there is a greatest such function, g. [Hint: use composition to show that the set is directed.] If A has bottom, show that g(^) is a fixed point for any inflationary function f.

  46. Let s:X® X be a monotone endofunction of an ipo. Consider the smallest subset A Ì X with ^ Î A which is closed under s and Ú­ ( cf Exercise 6.53). Using Definition  3.7.8, show that the restriction of s is inflationary on A, and so has a least fixed point. Show that this is in fact the only fixed point in A, and is its greatest element, and also that it is the least fixed point in X. Applying this to X = {X Ì S|q[X]}, prove Theorem 3.7.13. If X has binary meets, show that its subset of well founded elements (Exercise  3.40) has similar properties to A.

  47. Use infinitary conjunction to interpret "q. (TqÞ q)Þ q in a complete Heyting lattice and verify Proposition 2.8.6.

  48. For any monotone function T:W® W, show that
    m = ma.T(a) = "a.(T(a)Þ a)Þ a