Session 29: Binary operations and diagonal arguments
2. Cantor's diagonal argument
(In any category with products) If Y is an object such that there exists an object T with enough points to parameterize all the maps {T \rightarrow Y} by means of some single map {T \times T \xrightarrow{f} Y}, then Y has the 'fixed point property': every endomap {Y \xrightarrow{\alpha} Y} of Y has at least one point {\mathbf{1} \xrightarrow{y} Y} for which {\alpha y = y}.
Assume Y, T, f, and \alpha given. Then there is the diagonal map {T \rightarrow T \times T} as always (which maps every element t to {\langle t,t \rangle}), so we can form the three-fold composite {g: T \rightarrow Y}. This new map by its construction satisfies
g(t) = \alpha(f(t,t))
for every point t of T. We have assumed that every map {T \rightarrow Y} is named as {f(-,x)} for some point {\mathbf{1} \xrightarrow{x} T}, and g is such a map {T \rightarrow Y}. So let {x = t_0} be a parameter value corresponding to our g, i.e. {g = f(-,t_0)}, so that
g(t) = f(t,t_0)
for all t. Taking the special case t = t_0, we have
g(t_0) = f(t_0,t_0)
which by the definition of g says
\alpha(f(t_0,t_0)) = f(t_0,t_0)
or, in other words, that {y_0 = f(t_0,t_0)} defines a point of Y which is fixed by \alpha:
\alpha(y_0) = y_0
Our implementation in Lean faithfully follows the argument of the book proof given above.
theorem diagonal_theorem {π : Type u} [Category.{v, u} π] {T Y : π}
[HasBinaryProduct T T] [HasTerminal π]
(h : β f : T β¨― T βΆ Y, β e : T βΆ Y, β x : β€_ π βΆ T,
e = f β prod.lift (π T) (x β terminal.from T)) :
β Ξ± : Y βΆ Y, β y : β€_ π βΆ Y, Ξ± β y = y := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)β’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)β’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yβ’ β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)β’ β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)β’ β y, Ξ± β y = y
have hgtβ : g β tβ = f β prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)β’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
have : prod.lift (π T) (tβ β terminal.from T) β tβ =
prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)β’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)β’ prod.fst β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.fst β prod.lift tβ tβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)β’ prod.snd β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.snd β prod.lift tβ tβ
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)β’ prod.fst β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.fst β prod.lift tβ tβ All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)β’ prod.snd β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.snd β prod.lift tβ tβ π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)β’ tβ β terminal.from T β tβ = tβ
nth_rw 3 [β Category.id_comp tβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)β’ tβ β terminal.from T β tβ = tβ β π (β€_ π)
All goals completed! π
All goals completed! π
have hΞ± : Ξ± β f β prod.lift tβ tβ = f β prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)β’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
have : prod.lift (π T) (π T) β tβ = prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)β’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)hgtβ:g β tβ = f β prod.lift tβ tββ’ prod.fst β prod.lift (π T) (π T) β tβ = prod.fst β prod.lift tβ tβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)hgtβ:g β tβ = f β prod.lift tβ tββ’ prod.snd β prod.lift (π T) (π T) β tβ = prod.snd β prod.lift tβ tβ
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)hgtβ:g β tβ = f β prod.lift tβ tββ’ prod.fst β prod.lift (π T) (π T) β tβ = prod.fst β prod.lift tβ tβ All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)hgtβ:g β tβ = f β prod.lift tβ tββ’ prod.snd β prod.lift (π T) (π T) β tβ = prod.snd β prod.lift tβ tβ All goals completed! π
nth_rw 2 [β hgtβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)hgtβ:g β tβ = f β prod.lift tβ tβthis:prod.lift (π T) (π T) β tβ = prod.lift tβ tββ’ Ξ± β f β prod.lift tβ tβ = g β tβ
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)hgtβ:g β tβ = f β prod.lift tβ tβthis:prod.lift (π T) (π T) β tβ = prod.lift tβ tββ’ Ξ± β f β prod.lift tβ tβ = (Ξ± β f β prod.lift (π T) (π T)) β tβ
All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, e = f β prod.lift (π T) (x β terminal.from T)Ξ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:g = f β prod.lift (π T) (tβ β terminal.from T)yβ:β€_ π βΆ Y := f β prod.lift tβ tβhgtβ:g β tβ = yβhΞ±:Ξ± β yβ = yββ’ β y, Ξ± β y = y
All goals completed! π
If Y is an object known to have at least one endomap \alpha which has no fixed points, then for every object T and for every attempt {f: T \times T \rightarrow Y} to parameterize maps {T \rightarrow Y} by points of T, there must be at least one map {T \rightarrow Y} which is left out of the family, i.e. does not occur as {f(-,x)} for any point x in T.
Use \alpha and the diagonal as above to make f itself produce an example g which f leaves out.
Our implementation in Lean follows the structure of the Diagonal Theorem proof.
theorem cantor's_contrapositive_corollary
{π : Type u} [Category.{v, u} π] {T Y : π}
[HasBinaryProduct T T] [HasTerminal π]
(h : β Ξ± : Y βΆ Y, β y : β€_ π βΆ Y, Ξ± β y β y) :
β f : T β¨― T βΆ Y, β g : T βΆ Y, β x : β€_ π βΆ T,
g β f β prod.lift (π T) (x β terminal.from T) := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β Ξ±, β (y : β€_ π βΆ Y), Ξ± β y β yβ’ β (f : T β¨― T βΆ Y), β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yβ’ β (f : T β¨― T βΆ Y), β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yβ’ β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)β’ β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)β’ β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
intro x π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)β’ False
have hgx : g β x = f β prod.lift x x := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β Ξ±, β (y : β€_ π βΆ Y), Ξ± β y β yβ’ β (f : T β¨― T βΆ Y), β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
have : prod.lift (π T) (x β terminal.from T) β x =
prod.lift x x := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β Ξ±, β (y : β€_ π βΆ Y), Ξ± β y β yβ’ β (f : T β¨― T βΆ Y), β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)β’ prod.fst β prod.lift (π T) (x β terminal.from T) β x = prod.fst β prod.lift x xπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)β’ prod.snd β prod.lift (π T) (x β terminal.from T) β x = prod.snd β prod.lift x x
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)β’ prod.fst β prod.lift (π T) (x β terminal.from T) β x = prod.fst β prod.lift x x All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)β’ prod.snd β prod.lift (π T) (x β terminal.from T) β x = prod.snd β prod.lift x x π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)β’ x β terminal.from T β x = x
nth_rw 3 [β Category.id_comp xπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)β’ x β terminal.from T β x = x β π (β€_ π)
All goals completed! π
All goals completed! π
have hΞ± : Ξ± β f β prod.lift x x = f β prod.lift x x := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β Ξ±, β (y : β€_ π βΆ Y), Ξ± β y β yβ’ β (f : T β¨― T βΆ Y), β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
have : prod.lift (π T) (π T) β x = prod.lift x x := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β Ξ±, β (y : β€_ π βΆ Y), Ξ± β y β yβ’ β (f : T β¨― T βΆ Y), β g, β (x : β€_ π βΆ T), g β f β prod.lift (π T) (x β terminal.from T)
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)hgx:g β x = f β prod.lift x xβ’ prod.fst β prod.lift (π T) (π T) β x = prod.fst β prod.lift x xπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)hgx:g β x = f β prod.lift x xβ’ prod.snd β prod.lift (π T) (π T) β x = prod.snd β prod.lift x x
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)hgx:g β x = f β prod.lift x xβ’ prod.fst β prod.lift (π T) (π T) β x = prod.fst β prod.lift x x All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)hgx:g β x = f β prod.lift x xβ’ prod.snd β prod.lift (π T) (π T) β x = prod.snd β prod.lift x x All goals completed! π
nth_rw 2 [β hgxπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)hgx:g β x = f β prod.lift x xthis:prod.lift (π T) (π T) β x = prod.lift x xβ’ Ξ± β f β prod.lift x x = g β x
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)hgx:g β x = f β prod.lift x xthis:prod.lift (π T) (π T) β x = prod.lift x xβ’ Ξ± β f β prod.lift x x = (Ξ± β f β prod.lift (π T) (π T)) β x
All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)yβ:β€_ π βΆ Y := f β prod.lift x xhgx:g β x = yβhΞ±:Ξ± β yβ = yββ’ False
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πΞ±:Y βΆ Yh':β (y : β€_ π βΆ Y), Ξ± β y β yf:T β¨― T βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)x:β€_ π βΆ Thg:g = f β prod.lift (π T) (x β terminal.from T)yβ:β€_ π βΆ Y := f β prod.lift x xhgx:g β x = yβhΞ±:Ξ± β yβ = yββ’ Ξ± β yβ = yβ
All goals completed! π
Cantor's proof, if you read it carefully, really tells us a bit more. Rewrite the proof to show that if {T \times T \xrightarrow{f} Y} weakly parameterizes all maps {T \rightarrow Y}, then Y has the fixed point property. To say that {T \times T \xrightarrow{f} Y} 'weakly' parameterizes all maps {T \rightarrow Y} means that for each {T \xrightarrow{g} Y} there is a point {\mathbf{1} \xrightarrow{x} X} such that (letting \xi stand for the map whose components are the identity and the constant map with value x) the composite map {h = f \circ \xi}
T \xrightarrow{\xi} T \times T \xrightarrow{f} Y
agrees with {T \xrightarrow{g} Y} on points; i.e. for each point {\mathbf{1} \xrightarrow{t} T}, {g \circ t = h \circ t}. (In the category of sets that says {g = h}; but as we have seen, in other categories it says much less.)
Solution: Exercise 1
cf. Our formalisation of the Diagonal Theorem above.
example {π : Type u} [Category.{v, u} π] {T Y : π}
[HasBinaryProduct T T] [HasTerminal π]
(h : β f : T β¨― T βΆ Y, β e : T βΆ Y, β x : β€_ π βΆ T,
β t : β€_ π βΆ T,
e β t = f β prod.lift (π T) (x β terminal.from T) β t) :
β Ξ± : Y βΆ Y, β y : β€_ π βΆ Y, Ξ± β y = y := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tβ’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tβ’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yβ’ β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)β’ β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tβ’ β y, Ξ± β y = y
have hgtβ : g β tβ = f β prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tβ’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
have : prod.lift (π T) (tβ β terminal.from T) β tβ =
prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tβ’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tβ’ prod.fst β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.fst β prod.lift tβ tβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tβ’ prod.snd β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.snd β prod.lift tβ tβ
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tβ’ prod.fst β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.fst β prod.lift tβ tβ All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tβ’ prod.snd β prod.lift (π T) (tβ β terminal.from T) β tβ = prod.snd β prod.lift tβ tβ π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tβ’ tβ β terminal.from T β tβ = tβ
nth_rw 3 [β Category.id_comp tβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tβ’ tβ β terminal.from T β tβ = tβ β π (β€_ π)
All goals completed! π
All goals completed! π
have hΞ± : Ξ± β f β prod.lift tβ tβ = f β prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tβ’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
have : prod.lift (π T) (π T) β tβ = prod.lift tβ tβ := π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πh:β f, β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tβ’ β (Ξ± : Y βΆ Y), β y, Ξ± β y = y
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β thgtβ:g β tβ = f β prod.lift tβ tββ’ prod.fst β prod.lift (π T) (π T) β tβ = prod.fst β prod.lift tβ tβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β thgtβ:g β tβ = f β prod.lift tβ tββ’ prod.snd β prod.lift (π T) (π T) β tβ = prod.snd β prod.lift tβ tβ
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β thgtβ:g β tβ = f β prod.lift tβ tββ’ prod.fst β prod.lift (π T) (π T) β tβ = prod.fst β prod.lift tβ tβ All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β thgtβ:g β tβ = f β prod.lift tβ tββ’ prod.snd β prod.lift (π T) (π T) β tβ = prod.snd β prod.lift tβ tβ All goals completed! π
nth_rw 2 [β hgtβπ:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β thgtβ:g β tβ = f β prod.lift tβ tβthis:prod.lift (π T) (π T) β tβ = prod.lift tβ tββ’ Ξ± β f β prod.lift tβ tβ = g β tβ
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β thgtβ:g β tβ = f β prod.lift tβ tβthis:prod.lift (π T) (π T) β tβ = prod.lift tβ tββ’ Ξ± β f β prod.lift tβ tβ = (Ξ± β f β prod.lift (π T) (π T)) β tβ
All goals completed! π
π:Type uinstβΒ²:Category.{v, u} πT:πY:πinstβΒΉ:HasBinaryProduct T Tinstβ:HasTerminal πf:T β¨― T βΆ Yh':β (e : T βΆ Y), β x, β (t : β€_ π βΆ T), e β t = f β prod.lift (π T) (x β terminal.from T) β tΞ±:Y βΆ Yg:T βΆ Y := Ξ± β f β prod.lift (π T) (π T)tβ:β€_ π βΆ Thg:β (t : β€_ π βΆ T), g β t = f β prod.lift (π T) (tβ β terminal.from T) β tyβ:β€_ π βΆ Y := f β prod.lift tβ tβhgtβ:g β tβ = yβhΞ±:Ξ± β yβ = yββ’ β y, Ξ± β y = y
All goals completed! π