A Lean Companion to Conceptual Mathematics

Session 14: Maps preserve positive properties

For the exercises in this Session, we use the category Type instead of the category 𝑺 of sets, and we are told to assume that {f \circ \alpha = \beta \circ f}. (We use End X and End Y here instead of X ⟶ X and Y ⟶ Y to facilitate the use of exponents in Exercises 2 and 5.)

variable (X Y : Type) (α : End X) (β : End Y) (f : X Y) (hf_comm : f α = β f)
Exercise 1 (p. 170)

Let x_1 and x_2 be two points of X and define {y_1 = f(x_1)} and {y_2 = f(x_2)}. If \alpha(x_1) = \alpha(x_2) \text{ in } X (i.e. pushing the button \alpha we arrive at the same state whether the initial state was x_1 or x_2) then show that \beta(y_1) = \beta(y_2) \text{ in } Y (the 'same' statement with button \beta on the machine Y^{↻\beta} with regard to its two states y_1 and y_2).

Solution: Exercise 1

The solution below faithfully follows the one provided in the book on p. 171.

example (x₁ x₂ : X) (y₁ y₂ : Y) (hy₁ : y₁ = f x₁) (hy₂ : y₂ = f x₂) ( : α x₁ = α x₂) : β y₁ = β y₂ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂β y₁ = β y₂ have hβy₁ : β y₁ = f (α x₁) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂β y₁ = β y₂ calc β y₁ _ = β (f x₁) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂β y₁ = β (f x₁) All goals completed! 🐙 _ = (β f) x₁ := rfl _ = (f α) x₁ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂(β f) x₁ = (f α) x₁ All goals completed! 🐙 _ = f (α x₁) := rfl have hβy₂ : β y₂ = f (α x₂) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂β y₁ = β y₂ calc β y₂ _ = β (f x₂) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂hβy₁:β y₁ = f (α x₁) := Trans.trans (Trans.trans (Trans.trans (Trans.trans rfl (Eq.mpr (id (congrArg (fun _a β _a = β (f x₁)) hy₁)) (Eq.refl (β (f x₁))))) rfl) (Eq.mpr (id (congrArg (fun _a (β f) x₁ = _a x₁) hf_comm)) (Eq.refl ((β f) x₁)))) rflβ y₂ = β (f x₂) All goals completed! 🐙 _ = (β f) x₂ := rfl _ = (f α) x₂:= X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂hβy₁:β y₁ = f (α x₁) := Trans.trans (Trans.trans (Trans.trans (Trans.trans rfl (Eq.mpr (id (congrArg (fun _a β _a = β (f x₁)) hy₁)) (Eq.refl (β (f x₁))))) rfl) (Eq.mpr (id (congrArg (fun _a (β f) x₁ = _a x₁) hf_comm)) (Eq.refl ((β f) x₁)))) rfl(β f) x₂ = (f α) x₂ All goals completed! 🐙 _ = f (α x₂) := rfl have hfα : f (α x₁) = f (α x₂) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂β y₁ = β y₂ All goals completed! 🐙 All goals completed! 🐙

An alternative and more efficient implementation could be as follows:

example (x₁ x₂ : X) (y₁ y₂ : Y) (hy₁ : y₁ = f x₁) (hy₂ : y₂ = f x₂) ( : α x₁ = α x₂) : β y₁ = β y₂ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂β y₁ = β y₂ X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂β (f x₁) = β (f x₂) X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂(β f) x₁ = (β f) x₂ X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂(f α) x₁ = (f α) x₂ X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂:α x₁ = α x₂f (α x₁) = f (α x₂) All goals completed! 🐙
Exercise 2 (p. 170)

If instead we know that x_2 = \alpha^5(x_1) \text{ in } X (i.e. that starting from state x_1, five pushes of the button \alpha will bring X to the state x_2), show that the 'same' statement is true of the states y_1 and y_2 in Y^{↻\beta}; i.e. y_2 = \beta^5(y_1) \text{ in } Y

Solution: Exercise 2

The solution below faithfully follows the one provided in the book on p. 172.

example (x₁ x₂ : X) (y₁ y₂ : Y) (hy₁ : y₁ = f x₁) (hy₂ : y₂ = f x₂) (h : x₂ = (α ^ 5) x₁) : y₂ = (β ^ 5) y₁ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁y₂ = (β ^ 5) y₁ have hf_pow_comm : f (α ^ 5) = (β ^ 5) f := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁y₂ = (β ^ 5) y₁ calc f (α ^ 5) _ = f (α α ^ 4) := rfl _ = (f α) (α ^ 4) := rfl _ = (β f) (α ^ 4) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁(f α) α ^ 4 = (β f) α ^ 4 All goals completed! 🐙 _ = β (f (α ^ 4)) := rfl _ = β ((f α) (α ^ 3)) := rfl _ = β ((β f) (α ^ 3)) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁β (f α) α ^ 3 = β (β f) α ^ 3 All goals completed! 🐙 _ = (β (β f)) (α ^ 3) := rfl _ = ((β ^ 2) f) (α ^ 3) := rfl _ = (β ^ 2) (f (α ^ 3)) := rfl _ = (β ^ 2) ((f α) (α ^ 2)) := rfl _ = (β ^ 2) ((β f) (α ^ 2)) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁(β ^ 2) (f α) α ^ 2 = (β ^ 2) (β f) α ^ 2 All goals completed! 🐙 _ = ((β ^ 2) (β f)) (α ^ 2) := rfl _ = ((β ^ 3) f) (α ^ 2) := rfl _ = (β ^ 3) (f (α ^ 2)) := rfl _ = (β ^ 3) ((f α) α) := rfl _ = (β ^ 3) ((β f) α) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁(β ^ 3) (f α) α = (β ^ 3) (β f) α All goals completed! 🐙 _ = ((β ^ 3) (β f)) α := rfl _ = ((β ^ 4) f) α := rfl _ = (β ^ 4) (f α) := rfl _ = (β ^ 4) (β f) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁(β ^ 4) f α = (β ^ 4) β f All goals completed! 🐙 _ = (β ^ 5) f := rfl X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans rfl rfl) rfl) (Eq.mpr (id (congrArg (fun _a _a α ^ 4 = (β f) α ^ 4) hf_comm)) (Eq.refl ((β f) α ^ 4)))) rfl) rfl) (Eq.mpr (id (congrArg (fun _a β _a α ^ 3 = β (β f) α ^ 3) hf_comm)) (Eq.refl (β (β f) α ^ 3)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 2) _a α ^ 2 = (β ^ 2) (β f) α ^ 2) hf_comm)) (Eq.refl ((β ^ 2) (β f) α ^ 2)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 3) _a α = (β ^ 3) (β f) α) hf_comm)) (Eq.refl ((β ^ 3) (β f) α)))) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 4) _a = (β ^ 4) β f) hf_comm)) (Eq.refl ((β ^ 4) β f)))) rfl(β ^ 5) y₁ = y₂ calc (β ^ 5) y₁ _ = (β ^ 5) (f x₁) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans rfl rfl) rfl) (Eq.mpr (id (congrArg (fun _a _a α ^ 4 = (β f) α ^ 4) hf_comm)) (Eq.refl ((β f) α ^ 4)))) rfl) rfl) (Eq.mpr (id (congrArg (fun _a β _a α ^ 3 = β (β f) α ^ 3) hf_comm)) (Eq.refl (β (β f) α ^ 3)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 2) _a α ^ 2 = (β ^ 2) (β f) α ^ 2) hf_comm)) (Eq.refl ((β ^ 2) (β f) α ^ 2)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 3) _a α = (β ^ 3) (β f) α) hf_comm)) (Eq.refl ((β ^ 3) (β f) α)))) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 4) _a = (β ^ 4) β f) hf_comm)) (Eq.refl ((β ^ 4) β f)))) rfl(β ^ 5) y₁ = (β ^ 5) (f x₁) All goals completed! 🐙 _ = ((β ^ 5) f) x₁ := rfl _ = (f (α ^ 5)) x₁ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans rfl rfl) rfl) (Eq.mpr (id (congrArg (fun _a _a α ^ 4 = (β f) α ^ 4) hf_comm)) (Eq.refl ((β f) α ^ 4)))) rfl) rfl) (Eq.mpr (id (congrArg (fun _a β _a α ^ 3 = β (β f) α ^ 3) hf_comm)) (Eq.refl (β (β f) α ^ 3)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 2) _a α ^ 2 = (β ^ 2) (β f) α ^ 2) hf_comm)) (Eq.refl ((β ^ 2) (β f) α ^ 2)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 3) _a α = (β ^ 3) (β f) α) hf_comm)) (Eq.refl ((β ^ 3) (β f) α)))) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 4) _a = (β ^ 4) β f) hf_comm)) (Eq.refl ((β ^ 4) β f)))) rfl((β ^ 5) f) x₁ = (f α ^ 5) x₁ All goals completed! 🐙 _ = f ((α ^ 5) x₁) := rfl _ = f x₂ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans rfl rfl) rfl) (Eq.mpr (id (congrArg (fun _a _a α ^ 4 = (β f) α ^ 4) hf_comm)) (Eq.refl ((β f) α ^ 4)))) rfl) rfl) (Eq.mpr (id (congrArg (fun _a β _a α ^ 3 = β (β f) α ^ 3) hf_comm)) (Eq.refl (β (β f) α ^ 3)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 2) _a α ^ 2 = (β ^ 2) (β f) α ^ 2) hf_comm)) (Eq.refl ((β ^ 2) (β f) α ^ 2)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 3) _a α = (β ^ 3) (β f) α) hf_comm)) (Eq.refl ((β ^ 3) (β f) α)))) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 4) _a = (β ^ 4) β f) hf_comm)) (Eq.refl ((β ^ 4) β f)))) rflf ((α ^ 5) x₁) = f x₂ All goals completed! 🐙 _ = y₂ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans (Trans.trans rfl rfl) rfl) (Eq.mpr (id (congrArg (fun _a _a α ^ 4 = (β f) α ^ 4) hf_comm)) (Eq.refl ((β f) α ^ 4)))) rfl) rfl) (Eq.mpr (id (congrArg (fun _a β _a α ^ 3 = β (β f) α ^ 3) hf_comm)) (Eq.refl (β (β f) α ^ 3)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 2) _a α ^ 2 = (β ^ 2) (β f) α ^ 2) hf_comm)) (Eq.refl ((β ^ 2) (β f) α ^ 2)))) rfl) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 3) _a α = (β ^ 3) (β f) α) hf_comm)) (Eq.refl ((β ^ 3) (β f) α)))) rfl) rfl) rfl) (Eq.mpr (id (congrArg (fun _a (β ^ 4) _a = (β ^ 4) β f) hf_comm)) (Eq.refl ((β ^ 4) β f)))) rflf x₂ = y₂ All goals completed! 🐙

We can improve upon this solution from the book by first proving a lemma pow_comm (which we'll also need later in Exercise 5).

open Function lemma _root_.pow_comm {X Y : Type} (f : X Y) (α : End X) (β : End Y) (hf_comm : f α = β f) (n : ) : f (α^[n]) = (β^[n]) f := have hf_semiconj : Semiconj f α β := semiconj_iff_comp_eq.mpr hf_comm have hf_pow_semiconj : Semiconj f (α^[n]) (β^[n]) := Semiconj.iterate_right hf_semiconj n semiconj_iff_comp_eq.mp hf_pow_semiconj

An alternative and more efficient implementation now follows:

example (x₁ x₂ : X) (y₁ y₂ : Y) (hy₁ : y₁ = f x₁) (hy₂ : y₂ = f x₂) (h : x₂ = (α ^ 5) x₁) : y₂ = (β ^ 5) y₁ := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁y₂ = (β ^ 5) y₁ X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := pow_comm f α β hf_comm 5y₂ = (β ^ 5) y₁ X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := pow_comm f α β hf_comm 5f ((α ^ 5) x₁) = (β ^ 5) (f x₁) X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = f x₁hy₂:y₂ = f x₂h:x₂ = (α ^ 5) x₁hf_pow_comm:f α ^ 5 = (β ^ 5) f := pow_comm f α β hf_comm 5(f α ^ 5) x₁ = ((β ^ 5) f) x₁ All goals completed! 🐙
Exercise 3 (p. 170)

If {\alpha(x) = x} (i.e. x is an 'equilibrium state' or 'fixed point' of \alpha), then the 'same' is true of {y = f(x)} in Y^{↻\beta}.

Solution: Exercise 3

The solution below faithfully follows the one provided in the book on pp. 172–173.

example (x : X) (y : Y) (hy : y = f x) (h : α x = x) : β y = y := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:α x = xβ y = y calc β y _ = β (f x) := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:α x = xβ y = β (f x) All goals completed! 🐙 _ = (β f) x := rfl _ = (f α) x := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:α x = x(β f) x = (f α) x All goals completed! 🐙 _ = f (α x) := rfl _ = f x := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:α x = xf (α x) = f x All goals completed! 🐙 _ = y := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:α x = xf x = y All goals completed! 🐙
Exercise 4 (p. 171)

Give an example in which x is not a fixed point of \alpha but {y = f(x)} is a fixed point of \beta. This illustrates that although certain important properties are 'preserved' by f they are not necessarily 'reflected'. Hint: The simplest conceivable example of Y^{↻\beta} will do.

Solution: Exercise 4

The solution below faithfully follows the one provided in the book on p. 174.

inductive X | x₁ | x₂ deriving DecidableEq inductive Y | y₁ def α : X X | X.x₁ => X.x₂ | X.x₂ => X.x₂ def β : Y Y | Y.y₁ => Y.y₁ variable (f : X Y) (hf_comm : f α = β f)

In our example, X.x₁ is not a fixed point of \alpha, but its image f X.x₁ is a fixed point of \beta.

example : ¬(α X.x₁ = X.x₁) β (f X.x₁) = f X.x₁ := f:X Yhf_comm:f α = β f¬α X.x₁ = X.x₁ β (f X.x₁) = f X.x₁ f:X Yhf_comm:f α = β f¬α X.x₁ = X.x₁f:X Yhf_comm:f α = β fβ (f X.x₁) = f X.x₁ f:X Yhf_comm:f α = β f¬α X.x₁ = X.x₁ All goals completed! 🐙 f:X Yhf_comm:f α = β fβ (f X.x₁) = f X.x₁ All goals completed! 🐙
Exercise 5 (p. 171)

Show that if {\alpha^4(x) = x}, then the 'same' is true of {y = f(x)}. (Same idea as Exercise 2.) But give an example where {\alpha^4(x) = x} and {\alpha^2(x) \ne x}, while {\beta^2(y) = y} and {\beta(y) \ne y}. This illustrates that while f preserves the property of being in a small cycle, the size of the cycle may decrease.

Solution: Exercise 5

For the first part of the exercise, we show that {\alpha^4(x) = x} implies {\beta^4(f(x)) = f(x)}. To do so, we make use of the lemma pow_comm that we defined earlier in Exercise 2.

example (X Y : Type) (α : End X) (β : End Y) (f : X Y) (hf_comm : f α = β f) (x : X) (y : Y) (hy : y = f x) (h : (α ^ 4) x = x) : (β ^ 4) y = y := X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:(α ^ 4) x = x(β ^ 4) y = y X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:(α ^ 4) x = xhf_pow_comm:f α ^ 4 = (β ^ 4) f := pow_comm f α β hf_comm 4(β ^ 4) y = y X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:(α ^ 4) x = xhf_pow_comm:f α ^ 4 = (β ^ 4) f := pow_comm f α β hf_comm 4(β ^ 4) (f x) = f x nth_rw 2 [ hX:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:(α ^ 4) x = xhf_pow_comm:f α ^ 4 = (β ^ 4) f := pow_comm f α β hf_comm 4(β ^ 4) (f x) = f ((α ^ 4) x) X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:(α ^ 4) x = xhf_pow_comm:f α ^ 4 = (β ^ 4) f := pow_comm f α β hf_comm 4f ((α ^ 4) x) = (β ^ 4) (f x) X:TypeY:Typeα:End Xβ:End Yf:X Yhf_comm:f α = β fx:Xy:Yhy:y = f xh:(α ^ 4) x = xhf_pow_comm:f α ^ 4 = (β ^ 4) f := pow_comm f α β hf_comm 4(f α ^ 4) x = ((β ^ 4) f) x All goals completed! 🐙

For the second part of the exercise, we give the following example that meets the required conditions:

inductive X | x₁ | x₂ | x₃ | x₄ inductive Y | y₁ | y₂ def α : End X | X.x₁ => X.x₂ | X.x₂ => X.x₃ | X.x₃ => X.x₄ | X.x₄ => X.x₁ def β : End Y | Y.y₁ => Y.y₂ | Y.y₂ => Y.y₁ def f : X Y | X.x₁ => Y.y₁ | X.x₂ => Y.y₂ | X.x₃ => Y.y₁ | X.x₄ => Y.y₂ example (x : X) (y : Y) (hy : y = f x) : (α ^ 4) x = x ¬((α ^ 2) x = x) (β ^ 2) y = y ¬(β y = y) := x:Xy:Yhy:y = f x(α ^ 4) x = x ¬(α ^ 2) x = x (β ^ 2) y = y ¬β y = y x:Xy:Yhy:y = f x(α ^ 4) x = xx:Xy:Yhy:y = f x¬(α ^ 2) x = xx:Xy:Yhy:y = f x(β ^ 2) y = yx:Xy:Yhy:y = f x¬β y = y x:Xy:Yhy:y = f x(α ^ 4) x = x y:Yhy:y = f X.x₁(α ^ 4) X.x₁ = X.x₁y:Yhy:y = f X.x₂(α ^ 4) X.x₂ = X.x₂y:Yhy:y = f X.x₃(α ^ 4) X.x₃ = X.x₃y:Yhy:y = f X.x₄(α ^ 4) X.x₄ = X.x₄ y:Yhy:y = f X.x₁(α ^ 4) X.x₁ = X.x₁y:Yhy:y = f X.x₂(α ^ 4) X.x₂ = X.x₂y:Yhy:y = f X.x₃(α ^ 4) X.x₃ = X.x₃y:Yhy:y = f X.x₄(α ^ 4) X.x₄ = X.x₄ All goals completed! 🐙 x:Xy:Yhy:y = f x¬(α ^ 2) x = x x:Xy:Yhy:y = f xh:(α ^ 2) x = xFalse x:Xy:Yhy:y = f xh:(α α) x = xFalse y:Yhy:y = f X.x₁h:(α α) X.x₁ = X.x₁Falsey:Yhy:y = f X.x₂h:(α α) X.x₂ = X.x₂Falsey:Yhy:y = f X.x₃h:(α α) X.x₃ = X.x₃Falsey:Yhy:y = f X.x₄h:(α α) X.x₄ = X.x₄False all_goals y:Yhy:y = f X.x₄h:X.x₂ = X.x₄False All goals completed! 🐙 x:Xy:Yhy:y = f x(β ^ 2) y = y x:Xhy:Y.y₁ = f x(β ^ 2) Y.y₁ = Y.y₁x:Xhy:Y.y₂ = f x(β ^ 2) Y.y₂ = Y.y₂ x:Xhy:Y.y₁ = f x(β ^ 2) Y.y₁ = Y.y₁x:Xhy:Y.y₂ = f x(β ^ 2) Y.y₂ = Y.y₂ All goals completed! 🐙 x:Xy:Yhy:y = f x¬β y = y x:Xy:Yhy:y = f xh:β y = yFalse x:Xhy:Y.y₁ = f xh:β Y.y₁ = Y.y₁Falsex:Xhy:Y.y₂ = f xh:β Y.y₂ = Y.y₂False all_goals x:Xhy:Y.y₂ = f xh:Y.y₁ = Y.y₂False All goals completed! 🐙