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₂) (hα : α x₁ = α x₂) : β y₁ = β y₂ := X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂⊢ (ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom β) y₂ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂hβy₁:(ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₁)⊢ (ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom β) y₂ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂hβy₁:(ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₁)hβy₂:(ConcreteCategory.hom β) y₂ = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₂)⊢ (ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom β) y₂ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂hβy₁:(ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₁)hβy₂:(ConcreteCategory.hom β) y₂ = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₂)hfα:(ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₁) = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₂)⊢ (ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom β) y₂ 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₂) (hα : α x₁ = α x₂) : β y₁ = β y₂ := X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂⊢ (ConcreteCategory.hom β) y₁ = (ConcreteCategory.hom β) y₂ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂⊢ (ConcreteCategory.hom β) ((ConcreteCategory.hom f) x₁) = (ConcreteCategory.hom β) ((ConcreteCategory.hom f) x₂) X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂⊢ (ConcreteCategory.hom (β ⊚ f)) x₁ = (ConcreteCategory.hom (β ⊚ f)) x₂ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂⊢ (ConcreteCategory.hom (f ⊚ α)) x₁ = (ConcreteCategory.hom (f ⊚ α)) x₂ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂hα:(ConcreteCategory.hom α) x₁ = (ConcreteCategory.hom α) x₂⊢ (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₁) = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) 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₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁⊢ y₂ = (ConcreteCategory.hom (β ^ 5)) y₁ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ y₂ = (ConcreteCategory.hom (β ^ 5)) y₁ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ (ConcreteCategory.hom (β ^ 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₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ (ConcreteCategory.hom (β ^ 5)) y₁ = (ConcreteCategory.hom (β ^ 5)) ((ConcreteCategory.hom 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₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ (ConcreteCategory.hom ((β ^ 5) ⊚ f)) x₁ = (ConcreteCategory.hom (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₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ (ConcreteCategory.hom f) ((ConcreteCategory.hom (α ^ 5)) x₁) = (ConcreteCategory.hom f) x₂ All goals completed! 🐙 _ = y₂ := X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ (ConcreteCategory.hom f) 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 open ConcreteCategory in lemma _root_.pow_comm {X Y : Type} (f : X ⟶ Y) (α : End X) (β : End Y) (hf_comm : f ⊚ α = β ⊚ f) (n : ℕ) : f ⊚ ↾(α^[n]) = ↾(β^[n]) ⊚ f := X:TypeY:Typef:X ⟶ Yα:End Xβ:End Yhf_comm:f ⊚ α = β ⊚ fn:ℕ⊢ f ⊚ ↾(⇑(hom α))^[n] = ↾(⇑(hom β))^[n] ⊚ f X:TypeY:Typef:X ⟶ Yα:End Xβ:End Yhf_comm:f ⊚ α = β ⊚ fn:ℕhf_semiconj:Semiconj ⇑(hom f) ⇑(hom α) ⇑(hom β)⊢ f ⊚ ↾(⇑(hom α))^[n] = ↾(⇑(hom β))^[n] ⊚ f X:TypeY:Typef:X ⟶ Yα:End Xβ:End Yhf_comm:f ⊚ α = β ⊚ fn:ℕhf_semiconj:Semiconj ⇑(hom f) ⇑(hom α) ⇑(hom β)hf_pow_semiconj:Semiconj (⇑(hom f)) (⇑(hom α))^[n] (⇑(hom β))^[n]⊢ f ⊚ ↾(⇑(hom α))^[n] = ↾(⇑(hom β))^[n] ⊚ f X:TypeY:Typef:X ⟶ Yα:End Xβ:End Yhf_comm:f ⊚ α = β ⊚ fn:ℕhf_semiconj:Semiconj ⇑(hom f) ⇑(hom α) ⇑(hom β)hf_pow_semiconj:Semiconj (⇑(hom f)) (⇑(hom α))^[n] (⇑(hom β))^[n]x:(fun X ↦ X) X⊢ (hom (f ⊚ ↾(⇑(hom α))^[n])).toFun x = (hom (↾(⇑(hom β))^[n] ⊚ f)).toFun x All goals completed! 🐙

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₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁⊢ y₂ = (ConcreteCategory.hom (β ^ 5)) y₁ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ y₂ = (ConcreteCategory.hom (β ^ 5)) y₁ X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ (ConcreteCategory.hom f) ((ConcreteCategory.hom (α ^ 5)) x₁) = (ConcreteCategory.hom (β ^ 5)) ((ConcreteCategory.hom f) x₁) X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx₁:Xx₂:Xy₁:Yy₂:Yhy₁:y₁ = (ConcreteCategory.hom f) x₁hy₂:y₂ = (ConcreteCategory.hom f) x₂h:x₂ = (ConcreteCategory.hom (α ^ 5)) x₁hf_pow_comm:f ⊚ α ^ 5 = (β ^ 5) ⊚ f⊢ (ConcreteCategory.hom (f ⊚ α ^ 5)) x₁ = (ConcreteCategory.hom ((β ^ 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 = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom α) x = x⊢ (ConcreteCategory.hom β) y = y calc β y _ = β (f x) := X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom α) x = x⊢ (ConcreteCategory.hom β) y = (ConcreteCategory.hom β) ((ConcreteCategory.hom 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 = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom α) x = x⊢ (ConcreteCategory.hom (β ⊚ f)) x = (ConcreteCategory.hom (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 = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom α) x = x⊢ (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x) = (ConcreteCategory.hom f) x All goals completed! 🐙 _ = y := X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom α) x = x⊢ (ConcreteCategory.hom f) 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 := ↾fun | X.x₁ => X.x₂ | X.x₂ => X.x₂ def β : Y ⟶ Y := ↾fun | 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⊢ ¬(ConcreteCategory.hom α) X.x₁ = X.x₁ ∧ (ConcreteCategory.hom β) ((ConcreteCategory.hom f) X.x₁) = (ConcreteCategory.hom f) X.x₁ f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ ¬(ConcreteCategory.hom α) X.x₁ = X.x₁f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ (ConcreteCategory.hom β) ((ConcreteCategory.hom f) X.x₁) = (ConcreteCategory.hom f) X.x₁ f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ ¬(ConcreteCategory.hom α) X.x₁ = X.x₁ All goals completed! 🐙 f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ (ConcreteCategory.hom β) ((ConcreteCategory.hom f) X.x₁) = (ConcreteCategory.hom 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 = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 4)) x = x⊢ (ConcreteCategory.hom (β ^ 4)) y = y X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 4)) x = xhf_pow_comm:f ⊚ α ^ 4 = (β ^ 4) ⊚ f⊢ (ConcreteCategory.hom (β ^ 4)) y = y X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 4)) x = xhf_pow_comm:f ⊚ α ^ 4 = (β ^ 4) ⊚ f⊢ (ConcreteCategory.hom (β ^ 4)) ((ConcreteCategory.hom f) x) = (ConcreteCategory.hom f) x nth_rw 2 [X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 4)) x = xhf_pow_comm:f ⊚ α ^ 4 = (β ^ 4) ⊚ f⊢ (ConcreteCategory.hom (β ^ 4)) ((ConcreteCategory.hom f) x) = (ConcreteCategory.hom f) ((ConcreteCategory.hom (α ^ 4)) x)X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 4)) x = xhf_pow_comm:f ⊚ α ^ 4 = (β ^ 4) ⊚ f⊢ (ConcreteCategory.hom (β ^ 4)) ((ConcreteCategory.hom f) x) = (ConcreteCategory.hom f) ((ConcreteCategory.hom (α ^ 4)) x) X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 4)) x = xhf_pow_comm:f ⊚ α ^ 4 = (β ^ 4) ⊚ f⊢ (ConcreteCategory.hom f) ((ConcreteCategory.hom (α ^ 4)) x) = (ConcreteCategory.hom (β ^ 4)) ((ConcreteCategory.hom f) x) X:TypeY:Typeα:End Xβ:End Yf:X ⟶ Yhf_comm:f ⊚ α = β ⊚ fx:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 4)) x = xhf_pow_comm:f ⊚ α ^ 4 = (β ^ 4) ⊚ f⊢ (ConcreteCategory.hom (f ⊚ α ^ 4)) x = (ConcreteCategory.hom ((β ^ 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 := ↾fun | X.x₁ => X.x₂ | X.x₂ => X.x₃ | X.x₃ => X.x₄ | X.x₄ => X.x₁ def β : End Y := ↾fun | Y.y₁ => Y.y₂ | Y.y₂ => Y.y₁ def f : X ⟶ Y := ↾fun | 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 = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (α ^ 4)) x = x ∧ ¬(ConcreteCategory.hom (α ^ 2)) x = x ∧ (ConcreteCategory.hom (β ^ 2)) y = y ∧ ¬(ConcreteCategory.hom β) y = y x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (α ^ 4)) x = xx:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom (α ^ 2)) x = xx:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) y = yx:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom β) y = y x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (α ^ 4)) x = x y:Yhy:y = (ConcreteCategory.hom f) X.x₁⊢ (ConcreteCategory.hom (α ^ 4)) X.x₁ = X.x₁y:Yhy:y = (ConcreteCategory.hom f) X.x₂⊢ (ConcreteCategory.hom (α ^ 4)) X.x₂ = X.x₂y:Yhy:y = (ConcreteCategory.hom f) X.x₃⊢ (ConcreteCategory.hom (α ^ 4)) X.x₃ = X.x₃y:Yhy:y = (ConcreteCategory.hom f) X.x₄⊢ (ConcreteCategory.hom (α ^ 4)) X.x₄ = X.x₄ y:Yhy:y = (ConcreteCategory.hom f) X.x₁⊢ (ConcreteCategory.hom (α ^ 4)) X.x₁ = X.x₁y:Yhy:y = (ConcreteCategory.hom f) X.x₂⊢ (ConcreteCategory.hom (α ^ 4)) X.x₂ = X.x₂y:Yhy:y = (ConcreteCategory.hom f) X.x₃⊢ (ConcreteCategory.hom (α ^ 4)) X.x₃ = X.x₃y:Yhy:y = (ConcreteCategory.hom f) X.x₄⊢ (ConcreteCategory.hom (α ^ 4)) X.x₄ = X.x₄ All goals completed! 🐙 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom (α ^ 2)) x = x x:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 2)) x = x⊢ False x:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ⊚ α)) x = x⊢ False y:Yhy:y = (ConcreteCategory.hom f) X.x₁h:(ConcreteCategory.hom (α ⊚ α)) X.x₁ = X.x₁⊢ Falsey:Yhy:y = (ConcreteCategory.hom f) X.x₂h:(ConcreteCategory.hom (α ⊚ α)) X.x₂ = X.x₂⊢ Falsey:Yhy:y = (ConcreteCategory.hom f) X.x₃h:(ConcreteCategory.hom (α ⊚ α)) X.x₃ = X.x₃⊢ Falsey:Yhy:y = (ConcreteCategory.hom f) X.x₄h:(ConcreteCategory.hom (α ⊚ α)) X.x₄ = X.x₄⊢ False all_goals y:Yhy:y = (ConcreteCategory.hom f) X.x₄h:X.x₂ = X.x₄⊢ False All goals completed! 🐙 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) y = y x:Xhy:Y.y₁ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₁ = Y.y₁x:Xhy:Y.y₂ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₂ = Y.y₂ x:Xhy:Y.y₁ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₁ = Y.y₁x:Xhy:Y.y₂ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₂ = Y.y₂ All goals completed! 🐙 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom β) y = y x:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom β) y = y⊢ False x:Xhy:Y.y₁ = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom β) Y.y₁ = Y.y₁⊢ Falsex:Xhy:Y.y₂ = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom β) Y.y₂ = Y.y₂⊢ False all_goals x:Xhy:Y.y₂ = (ConcreteCategory.hom f) xh:Y.y₁ = Y.y₂⊢ False All goals completed! 🐙