Session 4: Division of maps: Isomorphisms
2. Inverses versus reciprocals
If {A \xrightarrow{f} B}, an inverse for f is a map {B \xrightarrow{g} A} satisfying both
g \circ f = 1_A \quad\text{and}\quad f \circ g = 1_B.
If f has an inverse, we say that f is an isomorphism or invertible map.
See the original presentation of these definitions at the beginning of Article II.
Any map f has at most one inverse.
Say {A \xrightarrow{f} B}, and suppose that both {B \xrightarrow{g} A} and {B \xrightarrow{h} A} are inverses for f; so
g \circ f = 1_A \quad\text{and}\quad f \circ g = 1_B,\\\
h \circ f = 1_A \quad\text{and}\quad f \circ h = 1_B.
We only need two of these equations to prove that g and h are the same:
g = 1_A \circ g = (h \circ f) \circ g = h \circ (f \circ g) = h \circ 1_B = h.
See the Lean implementation uniqueness_of_inverses under the original presentation of this theorem in Article II.
4. A small zoo of isomorphisms in other categories
In some of the Exercises that follow, we start to make use of mathlib's implementation of the Category class (see the definition of category at the end of Article I) ahead of our more extensive reliance on it in later Articles and Sessions.
Finish checking that d is an isomorphism in our category by showing that {h \circ d} and {d \circ h} are indeed identity maps.
Solution: Exercise 1
To begin tackling this Exercise, we first define an abstract algebraic object as a type equipped with a carrier set and a 'combining-rule', which operates on elements of the carrier set (and which has the closure property).
structure AlgebraicObj where
t : Type
carrier : Set t
oper : t → t → t
oper_mem {a b} : a ∈ carrier → b ∈ carrier → oper a b ∈ carrier
Next we register a Category instance for our algebraic object, defining maps/morphisms between algebraic objects as morphisms between their underlying types that map elements of the domain carrier set to elements of the codomain carrier set and that respect the combining-rules.
instance : Category AlgebraicObj where
Hom X Y := {
f : X.t ⟶ Y.t //
(∀ x ∈ X.carrier, f x ∈ Y.carrier) -- maps to codomain
∧ (∀ x₁ ∈ X.carrier, -- respects combining-rules
∀ x₂ ∈ X.carrier, f (X.oper x₁ x₂) = Y.oper (f x₁) (f x₂))
}
id X := ⟨
𝟙 X.t,
X:AlgebraicObj⊢ (∀ x ∈ X.carrier, (ConcreteCategory.hom (𝟙 X.t)) x ∈ X.carrier) ∧
∀ x₁ ∈ X.carrier,
∀ x₂ ∈ X.carrier,
(ConcreteCategory.hom (𝟙 X.t)) (X.oper x₁ x₂) =
X.oper ((ConcreteCategory.hom (𝟙 X.t)) x₁) ((ConcreteCategory.hom (𝟙 X.t)) x₂)
X:AlgebraicObj⊢ ∀ x ∈ X.carrier, (ConcreteCategory.hom (𝟙 X.t)) x ∈ X.carrierX:AlgebraicObj⊢ ∀ x₁ ∈ X.carrier,
∀ x₂ ∈ X.carrier,
(ConcreteCategory.hom (𝟙 X.t)) (X.oper x₁ x₂) =
X.oper ((ConcreteCategory.hom (𝟙 X.t)) x₁) ((ConcreteCategory.hom (𝟙 X.t)) x₂)
X:AlgebraicObj⊢ ∀ x ∈ X.carrier, (ConcreteCategory.hom (𝟙 X.t)) x ∈ X.carrier X:AlgebraicObjx✝:X.thx:x✝ ∈ X.carrier⊢ (ConcreteCategory.hom (𝟙 X.t)) x✝ ∈ X.carrier
All goals completed! 🐙
X:AlgebraicObj⊢ ∀ x₁ ∈ X.carrier,
∀ x₂ ∈ X.carrier,
(ConcreteCategory.hom (𝟙 X.t)) (X.oper x₁ x₂) =
X.oper ((ConcreteCategory.hom (𝟙 X.t)) x₁) ((ConcreteCategory.hom (𝟙 X.t)) x₂) X:AlgebraicObjx₁✝:X.ta✝¹:x₁✝ ∈ X.carrierx₂✝:X.ta✝:x₂✝ ∈ X.carrier⊢ (ConcreteCategory.hom (𝟙 X.t)) (X.oper x₁✝ x₂✝) =
X.oper ((ConcreteCategory.hom (𝟙 X.t)) x₁✝) ((ConcreteCategory.hom (𝟙 X.t)) x₂✝)
All goals completed! 🐙
⟩
comp := ⊢ {X Y Z : AlgebraicObj} →
{ f //
(∀ x ∈ X.carrier, (ConcreteCategory.hom f) x ∈ Y.carrier) ∧
∀ x₁ ∈ X.carrier,
∀ x₂ ∈ X.carrier,
(ConcreteCategory.hom f) (X.oper x₁ x₂) =
Y.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂) } →
{ f //
(∀ x ∈ Y.carrier, (ConcreteCategory.hom f) x ∈ Z.carrier) ∧
∀ x₁ ∈ Y.carrier,
∀ x₂ ∈ Y.carrier,
(ConcreteCategory.hom f) (Y.oper x₁ x₂) =
Z.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂) } →
{ f //
(∀ x ∈ X.carrier, (ConcreteCategory.hom f) x ∈ Z.carrier) ∧
∀ x₁ ∈ X.carrier,
∀ x₂ ∈ X.carrier,
(ConcreteCategory.hom f) (X.oper x₁ x₂) =
Z.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂) }
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.thf:(∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrier) ∧
∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)g:Y✝.t ⟶ Z✝.thg:(∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrier) ∧
∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)⊢ { f //
(∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Z✝.carrier) ∧
∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂) }
exact ⟨
g ⊚ f,
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.thf:(∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrier) ∧
∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)g:Y✝.t ⟶ Z✝.thg:(∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrier) ∧
∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)⊢ (∀ x ∈ X✝.carrier, (ConcreteCategory.hom (g ⊚ f)) x ∈ Z✝.carrier) ∧
∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom (g ⊚ f)) (X✝.oper x₁ x₂) =
Z✝.oper ((ConcreteCategory.hom (g ⊚ f)) x₁) ((ConcreteCategory.hom (g ⊚ f)) x₂)
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thg:(∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrier) ∧
∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)hf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)⊢ (∀ x ∈ X✝.carrier, (ConcreteCategory.hom (g ⊚ f)) x ∈ Z✝.carrier) ∧
∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom (g ⊚ f)) (X✝.oper x₁ x₂) =
Z✝.oper ((ConcreteCategory.hom (g ⊚ f)) x₁) ((ConcreteCategory.hom (g ⊚ f)) x₂)
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)⊢ (∀ x ∈ X✝.carrier, (ConcreteCategory.hom (g ⊚ f)) x ∈ Z✝.carrier) ∧
∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom (g ⊚ f)) (X✝.oper x₁ x₂) =
Z✝.oper ((ConcreteCategory.hom (g ⊚ f)) x₁) ((ConcreteCategory.hom (g ⊚ f)) x₂)
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)⊢ ∀ x ∈ X✝.carrier, (ConcreteCategory.hom (g ⊚ f)) x ∈ Z✝.carrierX✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)⊢ ∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom (g ⊚ f)) (X✝.oper x₁ x₂) =
Z✝.oper ((ConcreteCategory.hom (g ⊚ f)) x₁) ((ConcreteCategory.hom (g ⊚ f)) x₂)
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)⊢ ∀ x ∈ X✝.carrier, (ConcreteCategory.hom (g ⊚ f)) x ∈ Z✝.carrier X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)x:X✝.thx:x ∈ X✝.carrier⊢ (ConcreteCategory.hom (g ⊚ f)) x ∈ Z✝.carrier
All goals completed! 🐙
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)⊢ ∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom (g ⊚ f)) (X✝.oper x₁ x₂) =
Z✝.oper ((ConcreteCategory.hom (g ⊚ f)) x₁) ((ConcreteCategory.hom (g ⊚ f)) x₂) X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)x₁:X✝.thx₁:x₁ ∈ X✝.carrierx₂:X✝.thx₂:x₂ ∈ X✝.carrier⊢ (ConcreteCategory.hom (g ⊚ f)) (X✝.oper x₁ x₂) =
Z✝.oper ((ConcreteCategory.hom (g ⊚ f)) x₁) ((ConcreteCategory.hom (g ⊚ f)) x₂)
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)x₁:X✝.thx₁:x₁ ∈ X✝.carrierx₂:X✝.thx₂:x₂ ∈ X✝.carrier⊢ (ConcreteCategory.hom g) ((ConcreteCategory.hom f) (X✝.oper x₁ x₂)) =
Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂))
X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)x₁:X✝.thx₁:x₁ ∈ X✝.carrierx₂:X✝.thx₂:x₂ ∈ X✝.carrierh₁:(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)⊢ (ConcreteCategory.hom g) ((ConcreteCategory.hom f) (X✝.oper x₁ x₂)) =
Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂))
right X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)x₁:X✝.thx₁:x₁ ∈ X✝.carrierx₂:X✝.thx₂:x₂ ∈ X✝.carrierh₁:(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)⊢ (ConcreteCategory.hom g) (Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)) =
Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂))
have h₂ :=
hg_comb (f x₁) (hf_mtc x₁ hx₁) (f x₂) (hf_mtc x₂ hx₂) right X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)x₁:X✝.thx₁:x₁ ∈ X✝.carrierx₂:X✝.thx₂:x₂ ∈ X✝.carrierh₁:(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)h₂:(ConcreteCategory.hom g) (Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)) =
Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂))⊢ (ConcreteCategory.hom g) (Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)) =
Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂))
rw [h₂ right X✝:AlgebraicObjY✝:AlgebraicObjZ✝:AlgebraicObjf:X✝.t ⟶ Y✝.tg:Y✝.t ⟶ Z✝.thf_mtc:∀ x ∈ X✝.carrier, (ConcreteCategory.hom f) x ∈ Y✝.carrierhf_comb:∀ x₁ ∈ X✝.carrier,
∀ x₂ ∈ X✝.carrier,
(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)hg_mtc:∀ x ∈ Y✝.carrier, (ConcreteCategory.hom g) x ∈ Z✝.carrierhg_comb:∀ x₁ ∈ Y✝.carrier,
∀ x₂ ∈ Y✝.carrier,
(ConcreteCategory.hom g) (Y✝.oper x₁ x₂) = Z✝.oper ((ConcreteCategory.hom g) x₁) ((ConcreteCategory.hom g) x₂)x₁:X✝.thx₁:x₁ ∈ X✝.carrierx₂:X✝.thx₂:x₂ ∈ X✝.carrierh₁:(ConcreteCategory.hom f) (X✝.oper x₁ x₂) = Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)h₂:(ConcreteCategory.hom g) (Y✝.oper ((ConcreteCategory.hom f) x₁) ((ConcreteCategory.hom f) x₂)) =
Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂))⊢ Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂)) =
Z✝.oper ((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₁))
((ConcreteCategory.hom g) ((ConcreteCategory.hom f) x₂))] All goals completed! 🐙
⟩
Lastly we define the concrete algebraic object of real numbers with addition as the combining-rule.
abbrev RealAdd : AlgebraicObj := {
t := ℝ
carrier := Set.univ
oper := (· + ·)
oper_mem := fun _ _ ↦ Set.mem_univ _
}
We are now ready to complete the Exercise by defining d and h as morphisms in our category and showing that they are inverses.
def d : RealAdd ⟶ RealAdd := ⟨
↾fun (x : ℝ) ↦ 2 * x,
by ⊢ (∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ 2 * x)) x ∈ RealAdd.carrier) ∧
∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ 2 * x)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₁) ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₂)
constructor left ⊢ ∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ 2 * x)) x ∈ RealAdd.carrierright ⊢ ∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ 2 * x)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₁) ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₂)
· left ⊢ ∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ 2 * x)) x ∈ RealAdd.carrier exact fun _ _ ↦ Set.mem_univ _ All goals completed! 🐙
· right ⊢ ∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ 2 * x)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₁) ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₂) intros right x₁✝:RealAdd.ta✝¹:x₁✝ ∈ RealAdd.carrierx₂✝:RealAdd.ta✝:x₂✝ ∈ RealAdd.carrier⊢ (ConcreteCategory.hom (↾fun x ↦ 2 * x)) (RealAdd.oper x₁✝ x₂✝) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₁✝) ((ConcreteCategory.hom (↾fun x ↦ 2 * x)) x₂✝)
dsimp [RealAdd] right x₁✝:RealAdd.ta✝¹:x₁✝ ∈ RealAdd.carrierx₂✝:RealAdd.ta✝:x₂✝ ∈ RealAdd.carrier⊢ 2 * (x₁✝ + x₂✝) = 2 * x₁✝ + 2 * x₂✝
ring All goals completed! 🐙
⟩
noncomputable def h : RealAdd ⟶ RealAdd := ⟨
↾fun (x : ℝ) ↦ x / 2,
by ⊢ (∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ x / 2)) x ∈ RealAdd.carrier) ∧
∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ x / 2)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₁) ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₂)
constructor left ⊢ ∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ x / 2)) x ∈ RealAdd.carrierright ⊢ ∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ x / 2)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₁) ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₂)
· left ⊢ ∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ x / 2)) x ∈ RealAdd.carrier exact fun _ _ ↦ Set.mem_univ _ All goals completed! 🐙
· right ⊢ ∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ x / 2)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₁) ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₂) intros right x₁✝:RealAdd.ta✝¹:x₁✝ ∈ RealAdd.carrierx₂✝:RealAdd.ta✝:x₂✝ ∈ RealAdd.carrier⊢ (ConcreteCategory.hom (↾fun x ↦ x / 2)) (RealAdd.oper x₁✝ x₂✝) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₁✝) ((ConcreteCategory.hom (↾fun x ↦ x / 2)) x₂✝)
dsimp [RealAdd] right x₁✝:RealAdd.ta✝¹:x₁✝ ∈ RealAdd.carrierx₂✝:RealAdd.ta✝:x₂✝ ∈ RealAdd.carrier⊢ (x₁✝ + x₂✝) / 2 = x₁✝ / 2 + x₂✝ / 2
ring All goals completed! 🐙
⟩
example : IsIso d := {
out := by ⊢ ∃ inv, inv ⊚ d = 𝟙 RealAdd ∧ d ⊚ inv = 𝟙 RealAdd
use h h ⊢ h ⊚ d = 𝟙 RealAdd ∧ d ⊚ h = 𝟙 RealAdd
constructor h.left ⊢ h ⊚ d = 𝟙 RealAddh.right ⊢ d ⊚ h = 𝟙 RealAdd
· h.left ⊢ h ⊚ d = 𝟙 RealAdd show h ⊚ d = 𝟙 RealAdd h.left ⊢ h ⊚ d = 𝟙 RealAdd
apply Subtype.ext h.left ⊢ ↑(h ⊚ d) = ↑(𝟙 RealAdd)
ext x h.left x:RealAdd.t⊢ (ConcreteCategory.hom ↑(h ⊚ d)).toFun x = (ConcreteCategory.hom ↑(𝟙 RealAdd)).toFun x
change (2 * x) / 2 = x h.left x:RealAdd.t⊢ 2 * x / 2 = x
ring All goals completed! 🐙
· h.right ⊢ d ⊚ h = 𝟙 RealAdd show d ⊚ h = 𝟙 RealAdd h.right ⊢ d ⊚ h = 𝟙 RealAdd
apply Subtype.ext h.right ⊢ ↑(d ⊚ h) = ↑(𝟙 RealAdd)
ext x h.right x:RealAdd.t⊢ (ConcreteCategory.hom ↑(d ⊚ h)).toFun x = (ConcreteCategory.hom ↑(𝟙 RealAdd)).toFun x
change 2 * (x / 2) = x h.right x:RealAdd.t⊢ 2 * (x / 2) = x
ring All goals completed! 🐙
}
Find an isomorphism
(\{\textit{odd}, \textit{even}\}, +) \xrightarrow{f} (\{\textit{positive}, \textit{negative}\}, \times).
Hint: There are only two invertible maps of sets from {\{\textit{odd}, \textit{even}\}} to {\{\textit{pos.}, \textit{neg.}\}}. One of them 'respects the combining rules', but the other doesn't.
Solution: Exercise 2
For this Exercise, we continue to use the category of algebraic objects we defined in Exercise 1.
Define addition for parity and multiplication for sign, and allow use of + and * notation.
inductive Parity
| odd | even
def add : Parity → Parity → Parity
| Parity.odd, Parity.odd => Parity.even
| Parity.odd, Parity.even => Parity.odd
| Parity.even, Parity.odd => Parity.odd
| Parity.even, Parity.even => Parity.even
instance : Add Parity where
add := add
inductive Sign
| pos | neg
def mul : Sign → Sign → Sign
| Sign.pos, Sign.pos => Sign.pos
| Sign.pos, Sign.neg => Sign.neg
| Sign.neg, Sign.pos => Sign.neg
| Sign.neg, Sign.neg => Sign.pos
instance : Mul Sign where
mul := mul
Create algebraic objects for parity with addition and sign with multiplication.
def parityAdd : AlgebraicObj := {
t := Parity
carrier := Set.univ
oper := (· + ·)
oper_mem := fun _ _ ↦ Set.mem_univ _
}
def signMul : AlgebraicObj := {
t := Sign
carrier := Set.univ
oper := (· * ·)
oper_mem := fun _ _ ↦ Set.mem_univ _
}
Propose a map f from parity to sign, and its inverse, and form the corresponding morphisms between algebraic objects.
def f' : Parity ⟶ Sign := ↾fun
| Parity.odd => Sign.neg
| Parity.even => Sign.pos
def finv' : Sign ⟶ Parity := ↾fun
| Sign.pos => Parity.even
| Sign.neg => Parity.odd
def f : parityAdd ⟶ signMul := ⟨
f',
by ⊢ (∀ x ∈ parityAdd.carrier, (ConcreteCategory.hom f') x ∈ signMul.carrier) ∧
∀ x₁ ∈ parityAdd.carrier,
∀ x₂ ∈ parityAdd.carrier,
(ConcreteCategory.hom f') (parityAdd.oper x₁ x₂) =
signMul.oper ((ConcreteCategory.hom f') x₁) ((ConcreteCategory.hom f') x₂)
constructor left ⊢ ∀ x ∈ parityAdd.carrier, (ConcreteCategory.hom f') x ∈ signMul.carrierright ⊢ ∀ x₁ ∈ parityAdd.carrier,
∀ x₂ ∈ parityAdd.carrier,
(ConcreteCategory.hom f') (parityAdd.oper x₁ x₂) =
signMul.oper ((ConcreteCategory.hom f') x₁) ((ConcreteCategory.hom f') x₂)
· left ⊢ ∀ x ∈ parityAdd.carrier, (ConcreteCategory.hom f') x ∈ signMul.carrier exact fun _ _ ↦ Set.mem_univ _ All goals completed! 🐙
· right ⊢ ∀ x₁ ∈ parityAdd.carrier,
∀ x₂ ∈ parityAdd.carrier,
(ConcreteCategory.hom f') (parityAdd.oper x₁ x₂) =
signMul.oper ((ConcreteCategory.hom f') x₁) ((ConcreteCategory.hom f') x₂) intro a _ b _ right a:parityAdd.ta✝¹:a ∈ parityAdd.carrierb:parityAdd.ta✝:b ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper a b) =
signMul.oper ((ConcreteCategory.hom f') a) ((ConcreteCategory.hom f') b)
cases a right.odd b:parityAdd.ta✝¹:b ∈ parityAdd.carriera✝:Parity.odd ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.odd b) =
signMul.oper ((ConcreteCategory.hom f') Parity.odd) ((ConcreteCategory.hom f') b)right.even b:parityAdd.ta✝¹:b ∈ parityAdd.carriera✝:Parity.even ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.even b) =
signMul.oper ((ConcreteCategory.hom f') Parity.even) ((ConcreteCategory.hom f') b) <;> right.odd b:parityAdd.ta✝¹:b ∈ parityAdd.carriera✝:Parity.odd ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.odd b) =
signMul.oper ((ConcreteCategory.hom f') Parity.odd) ((ConcreteCategory.hom f') b)right.even b:parityAdd.ta✝¹:b ∈ parityAdd.carriera✝:Parity.even ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.even b) =
signMul.oper ((ConcreteCategory.hom f') Parity.even) ((ConcreteCategory.hom f') b) cases b right.even.odd a✝¹:Parity.even ∈ parityAdd.carriera✝:Parity.odd ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.even Parity.odd) =
signMul.oper ((ConcreteCategory.hom f') Parity.even) ((ConcreteCategory.hom f') Parity.odd)right.even.even a✝¹:Parity.even ∈ parityAdd.carriera✝:Parity.even ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.even Parity.even) =
signMul.oper ((ConcreteCategory.hom f') Parity.even) ((ConcreteCategory.hom f') Parity.even) <;> right.odd.odd a✝¹:Parity.odd ∈ parityAdd.carriera✝:Parity.odd ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.odd Parity.odd) =
signMul.oper ((ConcreteCategory.hom f') Parity.odd) ((ConcreteCategory.hom f') Parity.odd)right.odd.even a✝¹:Parity.odd ∈ parityAdd.carriera✝:Parity.even ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.odd Parity.even) =
signMul.oper ((ConcreteCategory.hom f') Parity.odd) ((ConcreteCategory.hom f') Parity.even)right.even.odd a✝¹:Parity.even ∈ parityAdd.carriera✝:Parity.odd ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.even Parity.odd) =
signMul.oper ((ConcreteCategory.hom f') Parity.even) ((ConcreteCategory.hom f') Parity.odd)right.even.even a✝¹:Parity.even ∈ parityAdd.carriera✝:Parity.even ∈ parityAdd.carrier⊢ (ConcreteCategory.hom f') (parityAdd.oper Parity.even Parity.even) =
signMul.oper ((ConcreteCategory.hom f') Parity.even) ((ConcreteCategory.hom f') Parity.even) rfl All goals completed! 🐙
⟩
def finv : signMul ⟶ parityAdd := ⟨
finv',
by ⊢ (∀ x ∈ signMul.carrier, (ConcreteCategory.hom finv') x ∈ parityAdd.carrier) ∧
∀ x₁ ∈ signMul.carrier,
∀ x₂ ∈ signMul.carrier,
(ConcreteCategory.hom finv') (signMul.oper x₁ x₂) =
parityAdd.oper ((ConcreteCategory.hom finv') x₁) ((ConcreteCategory.hom finv') x₂)
constructor left ⊢ ∀ x ∈ signMul.carrier, (ConcreteCategory.hom finv') x ∈ parityAdd.carrierright ⊢ ∀ x₁ ∈ signMul.carrier,
∀ x₂ ∈ signMul.carrier,
(ConcreteCategory.hom finv') (signMul.oper x₁ x₂) =
parityAdd.oper ((ConcreteCategory.hom finv') x₁) ((ConcreteCategory.hom finv') x₂)
· left ⊢ ∀ x ∈ signMul.carrier, (ConcreteCategory.hom finv') x ∈ parityAdd.carrier exact fun _ _ ↦ Set.mem_univ _ All goals completed! 🐙
· right ⊢ ∀ x₁ ∈ signMul.carrier,
∀ x₂ ∈ signMul.carrier,
(ConcreteCategory.hom finv') (signMul.oper x₁ x₂) =
parityAdd.oper ((ConcreteCategory.hom finv') x₁) ((ConcreteCategory.hom finv') x₂) intro a _ b _ right a:signMul.ta✝¹:a ∈ signMul.carrierb:signMul.ta✝:b ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper a b) =
parityAdd.oper ((ConcreteCategory.hom finv') a) ((ConcreteCategory.hom finv') b)
cases a right.pos b:signMul.ta✝¹:b ∈ signMul.carriera✝:Sign.pos ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.pos b) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.pos) ((ConcreteCategory.hom finv') b)right.neg b:signMul.ta✝¹:b ∈ signMul.carriera✝:Sign.neg ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.neg b) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.neg) ((ConcreteCategory.hom finv') b) <;> right.pos b:signMul.ta✝¹:b ∈ signMul.carriera✝:Sign.pos ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.pos b) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.pos) ((ConcreteCategory.hom finv') b)right.neg b:signMul.ta✝¹:b ∈ signMul.carriera✝:Sign.neg ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.neg b) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.neg) ((ConcreteCategory.hom finv') b) cases b right.neg.pos a✝¹:Sign.neg ∈ signMul.carriera✝:Sign.pos ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.neg Sign.pos) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.neg) ((ConcreteCategory.hom finv') Sign.pos)right.neg.neg a✝¹:Sign.neg ∈ signMul.carriera✝:Sign.neg ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.neg Sign.neg) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.neg) ((ConcreteCategory.hom finv') Sign.neg) <;> right.pos.pos a✝¹:Sign.pos ∈ signMul.carriera✝:Sign.pos ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.pos Sign.pos) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.pos) ((ConcreteCategory.hom finv') Sign.pos)right.pos.neg a✝¹:Sign.pos ∈ signMul.carriera✝:Sign.neg ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.pos Sign.neg) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.pos) ((ConcreteCategory.hom finv') Sign.neg)right.neg.pos a✝¹:Sign.neg ∈ signMul.carriera✝:Sign.pos ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.neg Sign.pos) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.neg) ((ConcreteCategory.hom finv') Sign.pos)right.neg.neg a✝¹:Sign.neg ∈ signMul.carriera✝:Sign.neg ∈ signMul.carrier⊢ (ConcreteCategory.hom finv') (signMul.oper Sign.neg Sign.neg) =
parityAdd.oper ((ConcreteCategory.hom finv') Sign.neg) ((ConcreteCategory.hom finv') Sign.neg) rfl All goals completed! 🐙
⟩
Give a proof that our proposed map f is indeed an isomorphism.
example : IsIso f := {
out := by ⊢ ∃ inv, inv ⊚ f = 𝟙 parityAdd ∧ f ⊚ inv = 𝟙 signMul
use finv h ⊢ finv ⊚ f = 𝟙 parityAdd ∧ f ⊚ finv = 𝟙 signMul
constructor h.left ⊢ finv ⊚ f = 𝟙 parityAddh.right ⊢ f ⊚ finv = 𝟙 signMul
all_goals
apply Subtype.ext h.right ⊢ ↑(f ⊚ finv) = ↑(𝟙 signMul)
ext x h.right x:signMul.t⊢ (ConcreteCategory.hom ↑(f ⊚ finv)).toFun x = (ConcreteCategory.hom ↑(𝟙 signMul)).toFun x
cases x h.right.pos ⊢ (ConcreteCategory.hom ↑(f ⊚ finv)).toFun Sign.pos = (ConcreteCategory.hom ↑(𝟙 signMul)).toFun Sign.posh.right.neg ⊢ (ConcreteCategory.hom ↑(f ⊚ finv)).toFun Sign.neg = (ConcreteCategory.hom ↑(𝟙 signMul)).toFun Sign.neg <;> h.right.pos ⊢ (ConcreteCategory.hom ↑(f ⊚ finv)).toFun Sign.pos = (ConcreteCategory.hom ↑(𝟙 signMul)).toFun Sign.posh.right.neg ⊢ (ConcreteCategory.hom ↑(f ⊚ finv)).toFun Sign.neg = (ConcreteCategory.hom ↑(𝟙 signMul)).toFun Sign.neg rfl All goals completed! 🐙
}
An unscrupulous importer has sold to the algebraic category section of our zoo some creatures which are not isomorphisms. Unmask the impostors.
(a) {(\mathbb{R}, +) \xrightarrow{p} (\mathbb{R}, +)} by 'plus 1': {p\:x = x + 1}.
(b) {(\mathbb{R}, \times) \xrightarrow{\mathit{sq}} (\mathbb{R}, \times)} by 'squaring': {\mathit{sq}\:x = x^2}.
(c) {(\mathbb{R}, \times) \xrightarrow{\mathit{sq}} (\mathbb{R}_{\ge 0}, \times)} by 'squaring': {\mathit{sq}\:x = x^2}.
(d) {(\mathbb{R}, +) \xrightarrow{m} (\mathbb{R}, +)} by 'minus': {m\:x = -x}.
(e) {(\mathbb{R}, \times) \xrightarrow{m} (\mathbb{R}, \times)} by 'minus': {m\:x = -x}.
(f) {(\mathbb{R}, \times) \xrightarrow{c} (\mathbb{R}_{>0}, \times)} by 'cubing': {c\:x = x^3}.
Hints: Exactly one is genuine. Some of the cruder impostors fail to be maps in our category, i.e. don't respect the combining-rules. The crudest is not even a map of sets with the indicated domain and codomain.
Solution: Exercise 3
For clarity of presentation here, we restrict our use of the category of algebraic objects we defined in Exercise 1 to the one genuine case of (d).
(a) p fails to respect the combining-rules.
example {p : ℝ ⟶ ℝ} (hp : ∀ x : ℝ, p x = x + 1)
: ¬(∀ a b : ℝ, p (a + b) = p a + p b) := by p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ ¬∀ (a b : ℝ), (ConcreteCategory.hom p) (a + b) = (ConcreteCategory.hom p) a + (ConcreteCategory.hom p) b
push Not p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ ∃ a b, (ConcreteCategory.hom p) (a + b) ≠ (ConcreteCategory.hom p) a + (ConcreteCategory.hom p) b
use 0, 0 h p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ (ConcreteCategory.hom p) (0 + 0) ≠ (ConcreteCategory.hom p) 0 + (ConcreteCategory.hom p) 0
rw [add_zero, h p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ (ConcreteCategory.hom p) 0 ≠ (ConcreteCategory.hom p) 0 + (ConcreteCategory.hom p) 0 ne_eq, h p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ ¬(ConcreteCategory.hom p) 0 = (ConcreteCategory.hom p) 0 + (ConcreteCategory.hom p) 0 left_eq_add, h p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ ¬(ConcreteCategory.hom p) 0 = 0 hp h p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ ¬0 + 1 = 0] h p:ℝ ⟶ ℝhp:∀ (x : ℝ), (ConcreteCategory.hom p) x = x + 1⊢ ¬0 + 1 = 0
linarith All goals completed! 🐙
(b) \mathit{sq} has no retraction.
example {sq : ℝ ⟶ ℝ} (hsq : ∀ x : ℝ, sq x = x ^ 2)
: ¬(∃ r : ℝ → ℝ, (∀ x : ℝ, r (sq x) = x)) := by sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2⊢ ¬∃ r, ∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = x
by_contra h sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2h:∃ r, ∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = x⊢ False
obtain ⟨r, h⟩ := h sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = x⊢ False
have hpos : r (sq 1) = 1 := h 1 sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = xhpos:r ((ConcreteCategory.hom sq) 1) = 1⊢ False
have hneg : r (sq (-1)) = -1 := h (-1) sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = xhpos:r ((ConcreteCategory.hom sq) 1) = 1hneg:r ((ConcreteCategory.hom sq) (-1)) = -1⊢ False
rw [hsq sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:r ((-1) ^ 2) = -1⊢ False] at hpos hneg sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:r ((-1) ^ 2) = -1⊢ False
rw [neg_sq, sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:r (1 ^ 2) = -1⊢ False hpos sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:1 = -1⊢ False] at hneg sq:ℝ ⟶ ℝhsq:∀ (x : ℝ), (ConcreteCategory.hom sq) x = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:1 = -1⊢ False
linarith All goals completed! 🐙
(c) \mathit{sq} has no retraction.
open NNReal in
example {sq : ℝ ⟶ ℝ≥0} (hsq : ∀ x : ℝ, sq x = x ^ 2)
: ¬(∃ r : ℝ → ℝ, (∀ x : ℝ, r (sq x) = x)) := by sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2⊢ ¬∃ r, ∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = x
by_contra h sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2h:∃ r, ∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = x⊢ False
obtain ⟨r, h⟩ := h sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = x⊢ False
have hpos : r (sq 1) = 1 := h 1 sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = xhpos:r ↑((ConcreteCategory.hom sq) 1) = 1⊢ False
have hneg : r (sq (-1)) = -1 := h (-1) sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = xhpos:r ↑((ConcreteCategory.hom sq) 1) = 1hneg:r ↑((ConcreteCategory.hom sq) (-1)) = -1⊢ False
rw [hsq sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:r ((-1) ^ 2) = -1⊢ False] at hpos hneg sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:r ((-1) ^ 2) = -1⊢ False
rw [neg_sq, sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:r (1 ^ 2) = -1⊢ False hpos sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:1 = -1⊢ False] at hneg sq:ℝ ⟶ ℝ≥0hsq:∀ (x : ℝ), ↑((ConcreteCategory.hom sq) x) = x ^ 2r:ℝ → ℝh:∀ (x : ℝ), r ↑((ConcreteCategory.hom sq) x) = xhpos:r (1 ^ 2) = 1hneg:1 = -1⊢ False
linarith All goals completed! 🐙
(d) m is genuine.
def m : RealAdd ⟶ RealAdd := ⟨
↾fun (x : ℝ) ↦ -x,
by ⊢ (∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ -x)) x ∈ RealAdd.carrier) ∧
∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ -x)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ -x)) x₁) ((ConcreteCategory.hom (↾fun x ↦ -x)) x₂)
constructor left ⊢ ∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ -x)) x ∈ RealAdd.carrierright ⊢ ∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ -x)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ -x)) x₁) ((ConcreteCategory.hom (↾fun x ↦ -x)) x₂)
· left ⊢ ∀ x ∈ RealAdd.carrier, (ConcreteCategory.hom (↾fun x ↦ -x)) x ∈ RealAdd.carrier exact fun _ _ ↦ Set.mem_univ _ All goals completed! 🐙
· right ⊢ ∀ x₁ ∈ RealAdd.carrier,
∀ x₂ ∈ RealAdd.carrier,
(ConcreteCategory.hom (↾fun x ↦ -x)) (RealAdd.oper x₁ x₂) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ -x)) x₁) ((ConcreteCategory.hom (↾fun x ↦ -x)) x₂) intros right x₁✝:RealAdd.ta✝¹:x₁✝ ∈ RealAdd.carrierx₂✝:RealAdd.ta✝:x₂✝ ∈ RealAdd.carrier⊢ (ConcreteCategory.hom (↾fun x ↦ -x)) (RealAdd.oper x₁✝ x₂✝) =
RealAdd.oper ((ConcreteCategory.hom (↾fun x ↦ -x)) x₁✝) ((ConcreteCategory.hom (↾fun x ↦ -x)) x₂✝)
dsimp [RealAdd] right x₁✝:RealAdd.ta✝¹:x₁✝ ∈ RealAdd.carrierx₂✝:RealAdd.ta✝:x₂✝ ∈ RealAdd.carrier⊢ -(x₁✝ + x₂✝) = -x₁✝ + -x₂✝
ring All goals completed! 🐙
⟩
def minv := m
example : IsIso m := {
out := by ⊢ ∃ inv, inv ⊚ m = 𝟙 RealAdd ∧ m ⊚ inv = 𝟙 RealAdd
use minv h ⊢ minv ⊚ m = 𝟙 RealAdd ∧ m ⊚ minv = 𝟙 RealAdd
constructor h.left ⊢ minv ⊚ m = 𝟙 RealAddh.right ⊢ m ⊚ minv = 𝟙 RealAdd
all_goals
apply Subtype.ext h.right ⊢ ↑(m ⊚ minv) = ↑(𝟙 RealAdd)
ext x h.right x:RealAdd.t⊢ (ConcreteCategory.hom ↑(m ⊚ minv)).toFun x = (ConcreteCategory.hom ↑(𝟙 RealAdd)).toFun x
change -(-x) = x h.right x:RealAdd.t⊢ - -x = x
ring All goals completed! 🐙
}
(e) m fails to respect the combining-rules.
example {m : ℝ ⟶ ℝ} (hm : ∀ x : ℝ, m x = -x)
: ¬(∀ a b : ℝ, m (a * b) = m a * m b) := by m:ℝ ⟶ ℝhm:∀ (x : ℝ), (ConcreteCategory.hom m) x = -x⊢ ¬∀ (a b : ℝ), (ConcreteCategory.hom m) (a * b) = (ConcreteCategory.hom m) a * (ConcreteCategory.hom m) b
push Not m:ℝ ⟶ ℝhm:∀ (x : ℝ), (ConcreteCategory.hom m) x = -x⊢ ∃ a b, (ConcreteCategory.hom m) (a * b) ≠ (ConcreteCategory.hom m) a * (ConcreteCategory.hom m) b
use 1, 1 h m:ℝ ⟶ ℝhm:∀ (x : ℝ), (ConcreteCategory.hom m) x = -x⊢ (ConcreteCategory.hom m) (1 * 1) ≠ (ConcreteCategory.hom m) 1 * (ConcreteCategory.hom m) 1
rw [mul_one, h m:ℝ ⟶ ℝhm:∀ (x : ℝ), (ConcreteCategory.hom m) x = -x⊢ (ConcreteCategory.hom m) 1 ≠ (ConcreteCategory.hom m) 1 * (ConcreteCategory.hom m) 1 ne_eq, h m:ℝ ⟶ ℝhm:∀ (x : ℝ), (ConcreteCategory.hom m) x = -x⊢ ¬(ConcreteCategory.hom m) 1 = (ConcreteCategory.hom m) 1 * (ConcreteCategory.hom m) 1 hm h m:ℝ ⟶ ℝhm:∀ (x : ℝ), (ConcreteCategory.hom m) x = -x⊢ ¬-1 = -1 * -1] h m:ℝ ⟶ ℝhm:∀ (x : ℝ), (ConcreteCategory.hom m) x = -x⊢ ¬-1 = -1 * -1
linarith All goals completed! 🐙
(f) c has an invalid codomain.
abbrev ℝpos := { x : ℝ // x > 0 }
example {c : ℝ → ℝpos} (hc : ∀ x : ℝ, c x = x ^ 3)
: ∃ x : ℝ, ¬(∃ y : ℝpos, y.val = c x) := by c:ℝ → ℝposhc:∀ (x : ℝ), ↑(c x) = x ^ 3⊢ ∃ x, ¬∃ y, ↑y = ↑(c x)
push Not c:ℝ → ℝposhc:∀ (x : ℝ), ↑(c x) = x ^ 3⊢ ∃ x, ∀ (y : ℝpos), ↑y ≠ ↑(c x)
use -1 h c:ℝ → ℝposhc:∀ (x : ℝ), ↑(c x) = x ^ 3⊢ ∀ (y : ℝpos), ↑y ≠ ↑(c (-1))
rw [hc h c:ℝ → ℝposhc:∀ (x : ℝ), ↑(c x) = x ^ 3⊢ ∀ (y : ℝpos), ↑y ≠ (-1) ^ 3] h c:ℝ → ℝposhc:∀ (x : ℝ), ↑(c x) = x ^ 3⊢ ∀ (y : ℝpos), ↑y ≠ (-1) ^ 3
norm_num h c:ℝ → ℝposhc:∀ (x : ℝ), ↑(c x) = x ^ 3⊢ ∀ (a : ℝ), 0 < a → ¬a = -1
intros h c:ℝ → ℝposhc:∀ (x : ℝ), ↑(c x) = x ^ 3a✝:ℝb✝:0 < a✝⊢ ¬a✝ = -1
linarith All goals completed! 🐙