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₁ = f x₁hy₂:y₂ = f x₂hα:α 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₂hα:α 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₂hα:α 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₂hα:α 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₂hα:α 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₂hα:α 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₂hα:α 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₂hα:α 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₂) (hα : α 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₂hα:α 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₂hα:α 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₂hα:α 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₂hα:α 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₂hα:α x₁ = α x₂⊢ f (α x₁) = f (α 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₁ := 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))))
rfl⊢ f ((α ^ 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))))
rfl⊢ 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
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 5⊢ 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 5⊢ f ((α ^ 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! 🐙
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 = x⊢ f (α 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 = x⊢ f x = y 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
| 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! 🐙
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 4⊢ f ((α ^ 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 = x⊢ False
x:Xy:Yhy:y = f xh:(α ⊚ α) x = x⊢ False
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 = y⊢ False
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! 🐙