Zulip Chat Archive
Stream: mathlib4
Topic: Understanding Girard's Paradox
Devon Andrews (Jan 27 2025 at 02:26):
I am trying to understand the following formalization of Girard's Paradox from mathlib4:
theorem girard.{u} (pi : (Type u → Type u) → Type u)
(lam : ∀ {A : Type u → Type u}, (∀ x, A x) → pi A) (app : ∀ {A}, pi A → ∀ x, A x)
(beta : ∀ {A : Type u → Type u} (f : ∀ x, A x) (x), app (lam f) x = f x) : False :=
let F (X) := (Set (Set X) → X) → Set (Set X)
let U := pi F
let G (T : Set (Set U)) (X) : F X := fun f => {p | {x : U | f (app x X f) ∈ p} ∈ T}
let τ (T : Set (Set U)) : U := lam (G T)
let σ (S : U) : Set (Set U) := app S U τ
have στ : ∀ {s S}, s ∈ σ (τ S) ↔ {x | τ (σ x) ∈ s} ∈ S := fun {s S} =>
iff_of_eq (congr_arg (fun f : F U => s ∈ f τ) (beta (G S) U) :)
let ω : Set (Set U) := {p | ∀ x, p ∈ σ x → x ∈ p}
let δ (S : Set (Set U)) := ∀ p, p ∈ S → τ S ∈ p
have : δ ω := fun _p d => d (τ ω) <| στ.2 fun x h => d (τ (σ x)) (στ.2 h)
this {y | ¬δ (σ y)} (fun _x e f => f _ e fun _p h => f _ (στ.1 h)) fun _p h => this _ (στ.1 h)
I understand every line syntactically except for the last two lines. I would appreciate if someone could provide me with an explanation or a syntactically easier version of the last two lines, even if the proof ends up much longer
Aaron Liu (Jan 27 2025 at 02:59):
Does it help if I write it out like this?
have this : δ ω := by
intro _ d
apply d (τ ω)
rw [στ]
intro x h
apply d (τ (σ x))
rw [στ]
exact h
by
refine this {y | ¬δ (σ y)} ?_ ?_
· intro _ e f
apply f _ e
intro _ h
exact f _ (στ.mp h)
· intro _ h
exact this _ (στ.mp h)
Ruben Van de Velde (Jan 27 2025 at 08:24):
That's uh... Write-only code
Kevin Buzzard (Jan 27 2025 at 10:23):
yeah this was just Mario demonstrating how few lines he could get it into.
Last updated: May 02 2025 at 03:31 UTC