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)
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₂
have hβy₂ : β y₂ = f (α x₂) := by
calc β y₂
_ = β (f x₂) := by 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 β) ((ConcreteCategory.hom f) x₂) rw [hy₂ 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 β) ((ConcreteCategory.hom f) x₂) = (ConcreteCategory.hom β) ((ConcreteCategory.hom f) x₂)] All goals completed! 🐙
_ = (β ⊚ f) x₂ := rfl
_ = (f ⊚ α) x₂:= by 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 (β ⊚ f)) x₂ = (ConcreteCategory.hom (f ⊚ α)) x₂ rw [hf_comm 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 (β ⊚ f)) x₂ = (ConcreteCategory.hom (β ⊚ f)) x₂] All goals completed! 🐙
_ = f (α x₂) := rfl 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₂
have hfα : f (α x₁) = f (α x₂) := by rw [hα 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 f) ((ConcreteCategory.hom α) x₂) = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) 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₂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₂
rw [hβ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 f) ((ConcreteCategory.hom α) x₁) = (ConcreteCategory.hom β) y₂ hβ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 f) ((ConcreteCategory.hom α) x₁) = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₂) hfα 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 f) ((ConcreteCategory.hom α) x₂) = (ConcreteCategory.hom f) ((ConcreteCategory.hom α) x₂)] 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₂ := by 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₂
rw [hy₁, 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 β) y₂ hy₂ 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 β) ((ConcreteCategory.hom f) x₁) = (ConcreteCategory.hom β) ((ConcreteCategory.hom f) x₂)
change (β ⊚ f) x₁ = (β ⊚ 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₂
rw [← hf_comm 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₂
change f (α x₁) = 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₂)
rw [hα 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! 🐙
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₁ := by 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₁
have hf_pow_comm : f ⊚ (α ^ 5) = (β ^ 5) ⊚ f := by
calc f ⊚ (α ^ 5)
_ = f ⊚ (α ⊚ α ^ 4) := rfl
_ = (f ⊚ α) ⊚ (α ^ 4) := rfl
_ = (β ⊚ f) ⊚ (α ^ 4) := by 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₁⊢ (f ⊚ α) ⊚ α ^ 4 = (β ⊚ f) ⊚ α ^ 4 rw [hf_comm 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₁⊢ (β ⊚ f) ⊚ α ^ 4 = (β ⊚ f) ⊚ α ^ 4] All goals completed! 🐙
_ = β ⊚ (f ⊚ (α ^ 4)) := rfl
_ = β ⊚ ((f ⊚ α) ⊚ (α ^ 3)) := rfl
_ = β ⊚ ((β ⊚ f) ⊚ (α ^ 3)) := by 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₁⊢ β ⊚ (f ⊚ α) ⊚ α ^ 3 = β ⊚ (β ⊚ f) ⊚ α ^ 3 rw [hf_comm 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₁⊢ β ⊚ (β ⊚ 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)) := by 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₁⊢ (β ^ 2) ⊚ (f ⊚ α) ⊚ α ^ 2 = (β ^ 2) ⊚ (β ⊚ f) ⊚ α ^ 2 rw [hf_comm 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₁⊢ (β ^ 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) ⊚ α) := by 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₁⊢ (β ^ 3) ⊚ (f ⊚ α) ⊚ α = (β ^ 3) ⊚ (β ⊚ f) ⊚ α rw [hf_comm 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₁⊢ (β ^ 3) ⊚ (β ⊚ f) ⊚ α = (β ^ 3) ⊚ (β ⊚ f) ⊚ α] All goals completed! 🐙
_ = ((β ^ 3) ⊚ (β ⊚ f)) ⊚ α := rfl
_ = ((β ^ 4) ⊚ f) ⊚ α := rfl
_ = (β ^ 4) ⊚ (f ⊚ α) := rfl
_ = (β ^ 4) ⊚ (β ⊚ f) := by 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₁⊢ (β ^ 4) ⊚ f ⊚ α = (β ^ 4) ⊚ β ⊚ f rw [hf_comm 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₁⊢ (β ^ 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₁ = (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₁
apply Eq.symm 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₁) := by 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₁) rw [hy₁ 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)) ((ConcreteCategory.hom f) x₁) =
(ConcreteCategory.hom (β ^ 5)) ((ConcreteCategory.hom f) x₁)] All goals completed! 🐙
_ = ((β ^ 5) ⊚ f) x₁ := rfl
_ = (f ⊚ (α ^ 5)) x₁ := by 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₁ rw [hf_pow_comm 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 ((β ^ 5) ⊚ f)) x₁] All goals completed! 🐙
_ = f ((α ^ 5) x₁) := rfl
_ = f x₂ := by 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₂ rw [h 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) ((ConcreteCategory.hom (α ^ 5)) x₁)] All goals completed! 🐙
_ = y₂ := by 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₂ rw [hy₂ 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₂ = (ConcreteCategory.hom f) x₂] 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 := by X:TypeY:Typef:X ⟶ Yα:End Xβ:End Yhf_comm:f ⊚ α = β ⊚ fn:ℕ⊢ f ⊚ ↾(⇑(hom α))^[n] = ↾(⇑(hom β))^[n] ⊚ f
have hf_semiconj : Semiconj f α β := fun x ↦ congr_hom hf_comm x 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
have hf_pow_semiconj : Semiconj f (α^[n]) (β^[n]) :=
Semiconj.iterate_right hf_semiconj n 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
ext x 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
exact hf_pow_semiconj 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₁ := by 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₁
have hf_pow_comm : f ⊚ (α ^ 5) = (β ^ 5) ⊚ f :=
pow_comm f α β hf_comm 5 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₁
rw [hy₁, 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)) ((ConcreteCategory.hom f) x₁) hy₂, 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₂ = (ConcreteCategory.hom (β ^ 5)) ((ConcreteCategory.hom f) x₁) h 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) ((ConcreteCategory.hom (α ^ 5)) x₁) =
(ConcreteCategory.hom (β ^ 5)) ((ConcreteCategory.hom f) x₁)
change (f ⊚ (α ^ 5)) x₁ = ((β ^ 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 (f ⊚ α ^ 5)) x₁ = (ConcreteCategory.hom ((β ^ 5) ⊚ f)) x₁
rw [hf_pow_comm 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 ((β ^ 5) ⊚ f)) x₁] All goals completed! 🐙
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 := by 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) := by 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) rw [hy 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 β) ((ConcreteCategory.hom f) x) = (ConcreteCategory.hom β) ((ConcreteCategory.hom f) x)] All goals completed! 🐙
_ = (β ⊚ f) x := rfl
_ = (f ⊚ α) x := by 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 rw [hf_comm 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 := by 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 rw [h 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! 🐙
_ = y := by 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 rw [hy 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! 🐙
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₁ := by f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ ¬(ConcreteCategory.hom α) X.x₁ = X.x₁ ∧
(ConcreteCategory.hom β) ((ConcreteCategory.hom f) X.x₁) = (ConcreteCategory.hom f) X.x₁
constructor left f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ ¬(ConcreteCategory.hom α) X.x₁ = X.x₁right f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ (ConcreteCategory.hom β) ((ConcreteCategory.hom f) X.x₁) = (ConcreteCategory.hom f) X.x₁
· left f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ ¬(ConcreteCategory.hom α) X.x₁ = X.x₁ decide All goals completed! 🐙
· right f:X ⟶ Yhf_comm:f ⊚ α = β ⊚ f⊢ (ConcreteCategory.hom β) ((ConcreteCategory.hom f) X.x₁) = (ConcreteCategory.hom f) X.x₁ dsimp [β] All goals completed! 🐙
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 := by 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
have hf_pow_comm : f ⊚ (α ^ 4) = (β ^ 4) ⊚ f :=
pow_comm f α β hf_comm 4 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
rw [hy 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] 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 [← h 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)
apply Eq.symm 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)
change (f ⊚ (α ^ 4)) x = ((β ^ 4) ⊚ 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
rw [hf_pow_comm 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) ⊚ f)) 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) := by 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
and_intros refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (α ^ 4)) x = xrefine_2.refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom (α ^ 2)) x = xrefine_2.refine_2.refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) y = yrefine_2.refine_2.refine_2 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom β) y = y
· refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (α ^ 4)) x = x cases x refine_1.x₁ y:Yhy:y = (ConcreteCategory.hom f) X.x₁⊢ (ConcreteCategory.hom (α ^ 4)) X.x₁ = X.x₁refine_1.x₂ y:Yhy:y = (ConcreteCategory.hom f) X.x₂⊢ (ConcreteCategory.hom (α ^ 4)) X.x₂ = X.x₂refine_1.x₃ y:Yhy:y = (ConcreteCategory.hom f) X.x₃⊢ (ConcreteCategory.hom (α ^ 4)) X.x₃ = X.x₃refine_1.x₄ y:Yhy:y = (ConcreteCategory.hom f) X.x₄⊢ (ConcreteCategory.hom (α ^ 4)) X.x₄ = X.x₄ <;> refine_1.x₁ y:Yhy:y = (ConcreteCategory.hom f) X.x₁⊢ (ConcreteCategory.hom (α ^ 4)) X.x₁ = X.x₁refine_1.x₂ y:Yhy:y = (ConcreteCategory.hom f) X.x₂⊢ (ConcreteCategory.hom (α ^ 4)) X.x₂ = X.x₂refine_1.x₃ y:Yhy:y = (ConcreteCategory.hom f) X.x₃⊢ (ConcreteCategory.hom (α ^ 4)) X.x₃ = X.x₃refine_1.x₄ y:Yhy:y = (ConcreteCategory.hom f) X.x₄⊢ (ConcreteCategory.hom (α ^ 4)) X.x₄ = X.x₄ rfl All goals completed! 🐙
· refine_2.refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom (α ^ 2)) x = x by_contra h refine_2.refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ^ 2)) x = x⊢ False
change (α ⊚ α) x = x at h refine_2.refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom (α ⊚ α)) x = x⊢ False
cases x refine_2.refine_1.x₁ y:Yhy:y = (ConcreteCategory.hom f) X.x₁h:(ConcreteCategory.hom (α ⊚ α)) X.x₁ = X.x₁⊢ Falserefine_2.refine_1.x₂ y:Yhy:y = (ConcreteCategory.hom f) X.x₂h:(ConcreteCategory.hom (α ⊚ α)) X.x₂ = X.x₂⊢ Falserefine_2.refine_1.x₃ y:Yhy:y = (ConcreteCategory.hom f) X.x₃h:(ConcreteCategory.hom (α ⊚ α)) X.x₃ = X.x₃⊢ Falserefine_2.refine_1.x₄ y:Yhy:y = (ConcreteCategory.hom f) X.x₄h:(ConcreteCategory.hom (α ⊚ α)) X.x₄ = X.x₄⊢ False
all_goals
dsimp [α] at h refine_2.refine_1.x₄ y:Yhy:y = (ConcreteCategory.hom f) X.x₄h:X.x₂ = X.x₄⊢ False
contradiction All goals completed! 🐙
· refine_2.refine_2.refine_1 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) y = y cases y refine_2.refine_2.refine_1.y₁ x:Xhy:Y.y₁ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₁ = Y.y₁refine_2.refine_2.refine_1.y₂ x:Xhy:Y.y₂ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₂ = Y.y₂ <;> refine_2.refine_2.refine_1.y₁ x:Xhy:Y.y₁ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₁ = Y.y₁refine_2.refine_2.refine_1.y₂ x:Xhy:Y.y₂ = (ConcreteCategory.hom f) x⊢ (ConcreteCategory.hom (β ^ 2)) Y.y₂ = Y.y₂ rfl All goals completed! 🐙
· refine_2.refine_2.refine_2 x:Xy:Yhy:y = (ConcreteCategory.hom f) x⊢ ¬(ConcreteCategory.hom β) y = y by_contra h refine_2.refine_2.refine_2 x:Xy:Yhy:y = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom β) y = y⊢ False
cases y refine_2.refine_2.refine_2.y₁ x:Xhy:Y.y₁ = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom β) Y.y₁ = Y.y₁⊢ Falserefine_2.refine_2.refine_2.y₂ x:Xhy:Y.y₂ = (ConcreteCategory.hom f) xh:(ConcreteCategory.hom β) Y.y₂ = Y.y₂⊢ False
all_goals
dsimp [β] at h refine_2.refine_2.refine_2.y₂ x:Xhy:Y.y₂ = (ConcreteCategory.hom f) xh:Y.y₁ = Y.y₂⊢ False
contradiction All goals completed! 🐙