Test 2
Suppose
X^{↻\alpha} \xrightarrow{f} Y^{↻\beta}
is a map in 𝑺↻. Show that if \alpha has a fixed point, then \beta must also have a fixed point.
Solution: Problem 1
The sequence of rewrites in the example below mirrors Danilo's solution on p. 205.
example (X Y : SetWithEndomap) (f : X ⟶ Y) :
(∃ x : X.carrier, X.toEnd x = x) →
(∃ y : Y.carrier, Y.toEnd y = y) := X:SetWithEndomapY:SetWithEndomapf:X ⟶ Y⊢ (∃ x, (ConcreteCategory.hom X.toEnd) x = x) → ∃ y, (ConcreteCategory.hom Y.toEnd) y = y
X:SetWithEndomapY:SetWithEndomapf:X.carrier ⟶ Y.carrierhf_comm:f ⊚ X.toEnd = Y.toEnd ⊚ f⊢ (∃ x, (ConcreteCategory.hom X.toEnd) x = x) → ∃ y, (ConcreteCategory.hom Y.toEnd) y = y
X:SetWithEndomapY:SetWithEndomapf:X.carrier ⟶ Y.carrierhf_comm:f ⊚ X.toEnd = Y.toEnd ⊚ fx:X.carrierhα:(ConcreteCategory.hom X.toEnd) x = x⊢ ∃ y, (ConcreteCategory.hom Y.toEnd) y = y
X:SetWithEndomapY:SetWithEndomapf:X.carrier ⟶ Y.carrierhf_comm:f ⊚ X.toEnd = Y.toEnd ⊚ fx:X.carrierhα:(ConcreteCategory.hom X.toEnd) x = x⊢ (ConcreteCategory.hom Y.toEnd) ((ConcreteCategory.hom f) x) = (ConcreteCategory.hom f) x
All goals completed! 🐙
Find all maps of (irreflexive) graphs from
inductive A₁
| a | b
inductive D₁
| p | q | r
def G₁ : IrreflexiveGraph := {
carrierA := A₁
carrierD := D₁
toSrc := ↾fun
| A₁.a => D₁.p
| A₁.b => D₁.q
toTgt := ↾fun
| A₁.a => D₁.r
| A₁.b => D₁.r
}
to
inductive A₂
| c | d
inductive D₂
| v | w
def G₂ : IrreflexiveGraph := {
carrierA := A₂
carrierD := D₂
toSrc := ↾fun
| A₂.c => D₂.w
| A₂.d => D₂.v
toTgt := ↾fun
| A₂.c => D₂.w
| A₂.d => D₂.w
}
(There are not more than a half-dozen of them.)
Solution: Problem 2
There are four maps, as given below (cf. the discussion of Omer's solution on pp. 207–210):
def f₁ : G₁ ⟶ G₂ := {
val := (
↾fun -- maps arrows
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun -- maps dots
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w
)
property := by ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1 ∧
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1
constructor left ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1right ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1
all_goals
ext x right x:G₁.carrierA⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
x =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
x
cases x right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.b <;> right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.b rfl All goals completed! 🐙
}
def f₂ : G₁ ⟶ G₂ := {
val := (
↾fun -- maps arrows
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun -- maps dots
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w
)
property := by ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1 ∧
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1
constructor left ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1right ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1
all_goals
ext x right x:G₁.carrierA⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
x =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
x
cases x right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.b <;> right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.b rfl All goals completed! 🐙
}
def f₃ : G₁ ⟶ G₂ := {
val := (
↾fun -- maps arrows
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun -- maps dots
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w
)
property := by ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1 ∧
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1
constructor left ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1right ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1
all_goals
ext x right x:G₁.carrierA⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
x =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
x
cases x right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.b <;> right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.c
| A₁.b => A₂.d,
↾fun x ↦
match x with
| D₁.p => D₂.w
| D₁.q => D₂.v
| D₁.r => D₂.w).1)).toFun
A₁.b rfl All goals completed! 🐙
}
def f₄ : G₁ ⟶ G₂ := {
val := (
↾fun -- maps arrows
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun -- maps dots
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w
)
property := by ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1 ∧
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1
constructor left ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toSrc =
G₂.toSrc ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1right ⊢ (↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt =
G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1
all_goals
ext x right x:G₁.carrierA⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
x =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
x
cases x right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.b <;> right.a ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.a =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.aright.b ⊢ (ConcreteCategory.hom
((↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).2 ⊚
G₁.toTgt)).toFun
A₁.b =
(ConcreteCategory.hom
(G₂.toTgt ⊚
(↾fun x ↦
match x with
| A₁.a => A₂.d
| A₁.b => A₂.c,
↾fun x ↦
match x with
| D₁.p => D₂.v
| D₁.q => D₂.w
| D₁.r => D₂.w).1)).toFun
A₁.b rfl All goals completed! 🐙
}
Find an example of a set X and an endomap {X \xrightarrow{\alpha} X} with {\alpha^2 = \alpha^3} but {\alpha \neq \alpha^2}.
Solution: Problem 3
cf. the discussion of Katie's attempted solution on pp. 205–207.
inductive X
| x₁ | x₂ | x₃
def α : End X := ↾fun
| X.x₁ => X.x₂
| X.x₂ => X.x₃
| X.x₃ => X.x₃
open ConcreteCategory in
example : α ^ 2 = α ^ 3 ∧ α ≠ α ^ 2 := by ⊢ α ^ 2 = α ^ 3 ∧ α ≠ α ^ 2
constructor left ⊢ α ^ 2 = α ^ 3right ⊢ α ≠ α ^ 2
· left ⊢ α ^ 2 = α ^ 3 change (α ^ 2 : X ⟶ X) = _ left ⊢ α ^ 2 = α ^ 3
ext x left x:X⊢ (hom (α ^ 2)).toFun x = (hom (α ^ 3)).toFun x
cases x left.x₁ ⊢ (hom (α ^ 2)).toFun X.x₁ = (hom (α ^ 3)).toFun X.x₁left.x₂ ⊢ (hom (α ^ 2)).toFun X.x₂ = (hom (α ^ 3)).toFun X.x₂left.x₃ ⊢ (hom (α ^ 2)).toFun X.x₃ = (hom (α ^ 3)).toFun X.x₃ <;> left.x₁ ⊢ (hom (α ^ 2)).toFun X.x₁ = (hom (α ^ 3)).toFun X.x₁left.x₂ ⊢ (hom (α ^ 2)).toFun X.x₂ = (hom (α ^ 3)).toFun X.x₂left.x₃ ⊢ (hom (α ^ 2)).toFun X.x₃ = (hom (α ^ 3)).toFun X.x₃ rfl All goals completed! 🐙
· right ⊢ α ≠ α ^ 2 by_contra h right h:α = α ^ 2⊢ False
have h_false : α X.x₁ = (α ^ 2) X.x₁ := congr_hom h X.x₁ right h:α = α ^ 2h_false:(hom α) X.x₁ = (hom (α ^ 2)) X.x₁⊢ False
have hα : α X.x₁ = X.x₂ := rfl right h:α = α ^ 2h_false:(hom α) X.x₁ = (hom (α ^ 2)) X.x₁hα:(hom α) X.x₁ = X.x₂⊢ False
have hαα : (α ^ 2) X.x₁ = X.x₃ := rfl right h:α = α ^ 2h_false:(hom α) X.x₁ = (hom (α ^ 2)) X.x₁hα:(hom α) X.x₁ = X.x₂hαα:(hom (α ^ 2)) X.x₁ = X.x₃⊢ False
rw [hα, right h:α = α ^ 2h_false:X.x₂ = (hom (α ^ 2)) X.x₁hα:(hom α) X.x₁ = X.x₂hαα:(hom (α ^ 2)) X.x₁ = X.x₃⊢ False hαα right h:α = α ^ 2h_false:X.x₂ = X.x₃hα:(hom α) X.x₁ = X.x₂hαα:(hom (α ^ 2)) X.x₁ = X.x₃⊢ False] at h_false right h:α = α ^ 2h_false:X.x₂ = X.x₃hα:(hom α) X.x₁ = X.x₂hαα:(hom (α ^ 2)) X.x₁ = X.x₃⊢ False
contradiction All goals completed! 🐙
In fact, since hα and hαα just establish definitional equalities, the contradiction tactic can take care of the last few steps automatically.
open ConcreteCategory in
example : α ^ 2 = α ^ 3 ∧ α ≠ α ^ 2 := by ⊢ α ^ 2 = α ^ 3 ∧ α ≠ α ^ 2
constructor left ⊢ α ^ 2 = α ^ 3right ⊢ α ≠ α ^ 2
· left ⊢ α ^ 2 = α ^ 3 change (α ^ 2 : X ⟶ X) = _ left ⊢ α ^ 2 = α ^ 3
ext x left x:X⊢ (hom (α ^ 2)).toFun x = (hom (α ^ 3)).toFun x
cases x left.x₁ ⊢ (hom (α ^ 2)).toFun X.x₁ = (hom (α ^ 3)).toFun X.x₁left.x₂ ⊢ (hom (α ^ 2)).toFun X.x₂ = (hom (α ^ 3)).toFun X.x₂left.x₃ ⊢ (hom (α ^ 2)).toFun X.x₃ = (hom (α ^ 3)).toFun X.x₃ <;> left.x₁ ⊢ (hom (α ^ 2)).toFun X.x₁ = (hom (α ^ 3)).toFun X.x₁left.x₂ ⊢ (hom (α ^ 2)).toFun X.x₂ = (hom (α ^ 3)).toFun X.x₂left.x₃ ⊢ (hom (α ^ 2)).toFun X.x₃ = (hom (α ^ 3)).toFun X.x₃ rfl All goals completed! 🐙
· right ⊢ α ≠ α ^ 2 by_contra h right h:α = α ^ 2⊢ False
have h_false : α X.x₁ = (α ^ 2) X.x₁ := congr_hom h X.x₁ right h:α = α ^ 2h_false:(hom α) X.x₁ = (hom (α ^ 2)) X.x₁⊢ False
-- have hα : α X.x₁ = X.x₂ := rfl
-- have hαα : (α ^ 2) X.x₁ = X.x₃ := rfl
-- rw [hα, hαα] at h_false
contradiction All goals completed! 🐙