Rudimentary programs and finite syntax
DefinitionCH_ConstructibleAC_Library03Rudimentary set operations can be composed into finite programs and represented by set-theoretic syntax. This library defines those operations, their term and prefix codes, and their evaluation graphs. It also supplies the representation interfaces relating simple set operations to first-order formulas, which are used to order the possible descriptions of constructible sets.
The original formalization is by Zike Liu, copyright 2026, Apache-2.0; see the pinned source. The Prove2Me packaging preserves the original copyright notices. This module includes supporting proofs needed by its definitions and constructor data.
The construction uses the external constructible universe over ambient ZFSet sets.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from OpenAI Codex.
import Definitions.Def_CH_ConstructibleAC_Library02
import Definitions.Def_CH_Constructible
import Mathlib.Data.List.Shortlex
import Mathlib.Data.Set.Finite.Basic
import Mathlib.Data.Sigma.Lex
import Mathlib.Data.Sum.Order
import Mathlib.ModelTheory.Semantics
import Mathlib.ModelTheory.Syntax
import Mathlib.SetTheory.Ordinal.Arithmetic
import Mathlib.SetTheory.ZFC.Ordinal
import Mathlib.Tactic.FinCases
/-!
# Adaptation of Zike Liu's constructible-universe Choice proof
Original formalization: Copyright (c) 2026 Zike Liu, Apache-2.0.
Source: https://github.com/05-02-07/lean-constructible-universe
Commit: 7f5a7d03d63d9769172f17350bbe8303996e5b53.
All original per-file copyright notices are retained below.
**Formalization credit:** **Wentao Li (Victor)**, under the Prove2Me account **Victorized**, with assistance from OpenAI Codex.
This credit concerns the Prove2Me adaptation and semantic bridge. The original
well-ordering formalization is by Zike Liu, credited above and in each source section.
-/
set_option autoImplicit false
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Rudimentary -/
section CUAdapterModule9
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Formal terms for rudimentary closure
The closure in `Godel.lean` is defined by finite iteration. This
file gives the equivalent finite term syntax. The generic theorem applies to
any internally represented seed; its specialization to `U ∪ {U}` uses `none`
for the generator `U` and `some x` for a parameter `x ∈ U`.
-/
universe u v
namespace Constructible.Godel
/-- Finite terms generated by variables and the nine Gödel operations. -/
inductive RudimentaryTerm (α : Type u) : Type u where
| var (a : α)
| app (i : Fin 9) (left right : RudimentaryTerm α)
namespace RudimentaryTerm
variable {α β : Type u}
/-- Evaluation of a rudimentary term under an assignment of its variables. -/
noncomputable def eval (ρ : α → ZFSet.{v}) :
RudimentaryTerm α → ZFSet.{v}
| .var a => ρ a
| .app i left right => op i (eval ρ left) (eval ρ right)
/-- Rename the variables occurring in a rudimentary term. -/
def rename (f : α → β) : RudimentaryTerm α → RudimentaryTerm β
| .var a => .var (f a)
| .app i left right => .app i (rename f left) (rename f right)
/-- Simultaneously substitute a term for every variable. -/
def subst (f : α → RudimentaryTerm β) :
RudimentaryTerm α → RudimentaryTerm β
| .var a => f a
| .app i left right => .app i (subst f left) (subst f right)
@[simp]
theorem eval_rename (f : α → β) (ρ : β → ZFSet.{v})
(t : RudimentaryTerm α) :
eval ρ (rename f t) = eval (ρ ∘ f) t := by
induction t with
| var a => rfl
| app i left right ihLeft ihRight => simp [rename, eval, ihLeft, ihRight]
@[simp]
theorem eval_subst (f : α → RudimentaryTerm β) (ρ : β → ZFSet.{v})
(t : RudimentaryTerm α) :
eval ρ (subst f t) = eval (fun a => eval ρ (f a)) t := by
induction t with
| var a => rfl
| app i left right ihLeft ihRight => simp [subst, eval, ihLeft, ihRight]
/-- If every generator lies in the seed, every term value lies in its closure. -/
theorem eval_mem_closure_of_mem_seed {seed : ZFSet.{v}}
{ρ : α → ZFSet.{v}} (hρ : ∀ a, ρ a ∈ seed)
(t : RudimentaryTerm α) : eval ρ t ∈ closure seed := by
induction t with
| var a => exact seed_subset_closure seed (hρ a)
| app i left right hleft hright =>
exact op_mem_closure hleft hright
/--
Every member of a finite closure stage is the value of a term, provided the
assignment names every member of the seed.
-/
theorem exists_term_eval_eq_of_mem_rudimentaryIter
{seed z : ZFSet.{v}} {ρ : α → ZFSet.{v}}
(hρ : ∀ x, x ∈ seed → ∃ a, ρ a = x) :
∀ n, z ∈ rudimentaryIter seed n →
∃ t : RudimentaryTerm α, eval ρ t = z := by
intro n
induction n generalizing z with
| zero =>
intro hz
rcases hρ z hz with ⟨a, ha⟩
exact ⟨.var a, ha⟩
| succ n ih =>
intro hz
rcases mem_rudimentaryStep_iff.mp hz with
hz | ⟨i, x, hx, y, hy, rfl⟩
· exact ih hz
· rcases ih hx with ⟨left, hleft⟩
rcases ih hy with ⟨right, hright⟩
refine ⟨.app i left right, ?_⟩
simp only [eval]
rw [hleft, hright]
/--
The closure generated by an assignment is exactly the set of values of finite
rudimentary terms, when that assignment names the seed precisely.
-/
theorem mem_closure_iff_exists_term_eval {seed z : ZFSet.{v}}
{ρ : α → ZFSet.{v}}
(hmem : ∀ a, ρ a ∈ seed)
(hnames : ∀ x, x ∈ seed → ∃ a, ρ a = x) :
z ∈ closure seed ↔ ∃ t : RudimentaryTerm α, eval ρ t = z := by
constructor
· intro hz
rcases mem_closure_iff.mp hz with ⟨n, hn⟩
exact exists_term_eval_eq_of_mem_rudimentaryIter hnames n hn
· rintro ⟨t, rfl⟩
exact eval_mem_closure_of_mem_seed hmem t
end RudimentaryTerm
/--
Variables for `rudimentaryClosure U`: `none` names `U`, while `some x` names
the parameter `x ∈ U`.
-/
abbrev RudimentaryClosureTerm (U : ZFSet.{u}) :=
RudimentaryTerm (Option (Constructible.ZFCarrier U))
/-- The natural interpretation of the generators `U ∪ {U}`. -/
def rudimentaryGenerator (U : ZFSet.{u}) :
Option (Constructible.ZFCarrier U) → ZFSet.{u}
| none => U
| some x => x.1
/-- Evaluation of a term over `U ∪ {U}`. -/
noncomputable abbrev RudimentaryClosureTerm.eval {U : ZFSet.{u}}
(t : RudimentaryClosureTerm U) : ZFSet.{u} :=
RudimentaryTerm.eval (rudimentaryGenerator U) t
@[simp]
theorem mem_rudimentaryClosure_iff_exists_term {U z : ZFSet.{u}} :
z ∈ rudimentaryClosure U ↔
∃ t : RudimentaryClosureTerm U, t.eval = z := by
apply RudimentaryTerm.mem_closure_iff_exists_term_eval
· intro a
cases a with
| none => exact mem_rudimentarySeed_iff.mpr (Or.inl rfl)
| some x => exact mem_rudimentarySeed_iff.mpr (Or.inr x.2)
· intro x hx
rcases mem_rudimentarySeed_iff.mp hx with rfl | hx
· exact ⟨none, rfl⟩
· exact ⟨some ⟨x, hx⟩, rfl⟩
/-- Term-syntax characterization of the Gödel presentation of `Def(U)`. -/
theorem mem_godelDef_iff_exists_rudimentaryTerm {U z : ZFSet.{u}} :
z ∈ godelDef U ↔
z ⊆ U ∧ ∃ t : RudimentaryClosureTerm U, t.eval = z := by
rw [mem_godelDef_iff, mem_rudimentaryClosure_iff_exists_term]
end Constructible.Godel
end CUAdapterModule9
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryCode -/
section CUAdapterModule10
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Canonical codes for rudimentary terms
A term is encoded in prefix form. An application token stores the lengths of
both encoded subterms, making the code unambiguously decodable. Shortlex on
these finite token lists gives a well-order whenever the variable labels are
well-ordered. Consequently every value in a rudimentary closure has a unique
least representing term.
-/
universe u
namespace Constructible.Godel
namespace RudimentaryTerm
/--
Tokens for prefix codes. A left token is a variable; a right token records
an operation together with the lengths of its two subterm codes.
-/
abbrev CodeToken (alpha : Type u) :=
alpha ⊕ (Fin 9 × Nat × Nat)
/-- An injective, length-delimited prefix code for rudimentary terms. -/
def code {alpha : Type u} : RudimentaryTerm alpha -> List (CodeToken alpha)
| .var a => [Sum.inl a]
| .app i left right =>
let leftCode := code left
let rightCode := code right
Sum.inr (i, leftCode.length, rightCode.length) ::
(leftCode ++ rightCode)
@[simp]
theorem code_var {alpha : Type u} (a : alpha) :
code (.var a : RudimentaryTerm alpha) = [Sum.inl a] :=
rfl
@[simp]
theorem code_app {alpha : Type u} (i : Fin 9)
(left right : RudimentaryTerm alpha) :
code (.app i left right) =
Sum.inr (i, (code left).length, (code right).length) ::
(code left ++ code right) :=
rfl
/-- The prefix code determines the term uniquely. -/
theorem code_injective {alpha : Type u} :
Function.Injective (@code alpha) := by
intro first second hcode
induction first generalizing second with
| var a =>
cases second with
| var b =>
have hab : a = b := Sum.inl.inj (List.cons.inj hcode).1
subst b
rfl
| app i left right =>
have hhead := (List.cons.inj hcode).1
cases hhead
| app i left right ihLeft ihRight =>
cases second with
| var b =>
have hhead := (List.cons.inj hcode).1
cases hhead
| app j left' right' =>
have hcons := List.cons.inj hcode
have htuple := Sum.inr.inj hcons.1
have hij : i = j := congrArg Prod.fst htuple
have hlengths := congrArg Prod.snd htuple
have hleftLength : (code left).length = (code left').length :=
congrArg Prod.fst hlengths
have hrightLength : (code right).length = (code right').length :=
congrArg Prod.snd hlengths
have htail := hcons.2
have hleftCode : code left = code left' := by
calc
code left =
List.take (code left).length (code left ++ code right) := by
simp
_ = List.take (code left).length
(code left' ++ code right') :=
congrArg (List.take (code left).length) htail
_ = code left' := by
rw [hleftLength]
simp
have hrightCode : code right = code right' := by
calc
code right =
List.drop (code left).length (code left ++ code right) := by
simp
_ = List.drop (code left).length
(code left' ++ code right') :=
congrArg (List.drop (code left).length) htail
_ = code right' := by
rw [hleftLength]
simp
have hleft : left = left' := ihLeft hleftCode
have hright : right = right' := ihRight hrightCode
subst j
subst left'
subst right'
rfl
/-! ## The structural well-order -/
/-- Lexicographic order on operation tokens. -/
def operationTokenRel :
(Fin 9 × Nat × Nat) -> (Fin 9 × Nat × Nat) -> Prop :=
Prod.Lex (fun i j : Fin 9 => i < j)
(Prod.Lex (fun m n : Nat => m < n) (fun m n : Nat => m < n))
/-- Variables precede applications; each part uses its canonical order. -/
def codeTokenRel {alpha : Type u} (r : alpha -> alpha -> Prop) :
CodeToken alpha -> CodeToken alpha -> Prop :=
Sum.Lex r operationTokenRel
/-- Shortlex order pulled back along the injective term code. -/
def codeRel {alpha : Type u} (r : alpha -> alpha -> Prop) :
RudimentaryTerm alpha -> RudimentaryTerm alpha -> Prop :=
InvImage (List.Shortlex (codeTokenRel r)) code
theorem operationTokenRel_isWellOrder :
IsWellOrder (Fin 9 × Nat × Nat) operationTokenRel := by
unfold operationTokenRel
infer_instance
theorem codeTokenRel_isWellOrder {alpha : Type u}
(r : alpha -> alpha -> Prop) [IsWellOrder alpha r] :
IsWellOrder (CodeToken alpha) (codeTokenRel r) := by
unfold codeTokenRel
letI : IsWellOrder (Fin 9 × Nat × Nat) operationTokenRel :=
operationTokenRel_isWellOrder
infer_instance
/-- The structural order on terms is a well-order. -/
theorem codeRel_isWellOrder {alpha : Type u}
(r : alpha -> alpha -> Prop) [IsWellOrder alpha r] :
IsWellOrder (RudimentaryTerm alpha) (codeRel r) := by
letI : IsWellOrder (CodeToken alpha) (codeTokenRel r) :=
codeTokenRel_isWellOrder r
refine
{ wf := InvImage.wf code
(List.Shortlex.wf (IsWellFounded.wf :
WellFounded (codeTokenRel r)))
trichotomous :=
(InvImage.trichotomous (r := List.Shortlex (codeTokenRel r))
code_injective).trichotomous }
/-! ## Least representations -/
/-- The set of rudimentary terms evaluating to `z`. -/
def representingTerms (U z : ZFSet.{u}) :
Set (RudimentaryClosureTerm U) :=
{term | term.eval = z}
theorem representingTerms_nonempty {U z : ZFSet.{u}}
(hz : z ∈ godelDef U) :
(representingTerms U z).Nonempty := by
rcases (mem_godelDef_iff_exists_rudimentaryTerm.mp hz).2 with
⟨term, hterm⟩
exact ⟨term, hterm⟩
/--
The least term representing `z`, relative to a well-order of the generators
`Option (ZFCarrier U)`.
-/
noncomputable def leastRepresentingTerm (U z : ZFSet.{u})
(hz : z ∈ godelDef U)
(r : Option (Constructible.ZFCarrier U) ->
Option (Constructible.ZFCarrier U) -> Prop)
[IsWellOrder (Option (Constructible.ZFCarrier U)) r] :
RudimentaryClosureTerm U :=
letI : IsWellOrder (RudimentaryClosureTerm U) (codeRel r) :=
codeRel_isWellOrder r
(IsWellFounded.wf : WellFounded (codeRel r)).min (representingTerms U z)
(representingTerms_nonempty hz)
@[simp]
theorem eval_leastRepresentingTerm (U z : ZFSet.{u})
(hz : z ∈ godelDef U)
(r : Option (Constructible.ZFCarrier U) ->
Option (Constructible.ZFCarrier U) -> Prop)
[IsWellOrder (Option (Constructible.ZFCarrier U)) r] :
(leastRepresentingTerm U z hz r).eval = z := by
letI : IsWellOrder (RudimentaryClosureTerm U) (codeRel r) :=
codeRel_isWellOrder r
exact (IsWellFounded.wf : WellFounded (codeRel r)).min_mem
(representingTerms U z)
(representingTerms_nonempty hz)
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule10
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryTermZFCode -/
section CUAdapterModule11
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internal ZF codes for rudimentary terms
This file encodes the external inductive syntax `RudimentaryTerm alpha` by
genuine `ZFSet`s. A variable encoding `rho` supplies the internal code for
each variable:
* `var a` is coded by the triple `⟨0, rho a, ∅⟩`;
* `app i left right` is coded by
`⟨1, i, ⟨code left, code right⟩⟩`.
All pairs and triples are Kuratowski pairs. The encoding is injective when
`rho` is injective, and its values are constructible when the variable codes
are constructible.
-/
universe u v
namespace Constructible.Godel
namespace RudimentaryTerm
noncomputable section
/-- The node tag used for variables. -/
def varTag : ZFSet.{v} :=
(0 : Ordinal.{v}).toZFSet
/-- The node tag used for applications. -/
def appTag : ZFSet.{v} :=
(1 : Ordinal.{v}).toZFSet
/-- The internal finite-ordinal code of one of the nine rudimentary operations. -/
def operationCode (i : Fin 9) : ZFSet.{v} :=
(i.1 : Ordinal.{v}).toZFSet
/--
Encode a rudimentary term as a genuine ZF set, relative to codes for its
variables.
-/
def zfCode {alpha : Type u} (rho : alpha -> ZFSet.{v}) :
RudimentaryTerm alpha -> ZFSet.{v}
| .var a => triple varTag (rho a) ∅
| .app i left right =>
triple appTag (operationCode i)
(ZFSet.pair (zfCode rho left) (zfCode rho right))
@[simp]
theorem zfCode_var {alpha : Type u} (rho : alpha -> ZFSet.{v}) (a : alpha) :
zfCode rho (.var a) = triple varTag (rho a) ∅ :=
rfl
@[simp]
theorem zfCode_app {alpha : Type u} (rho : alpha -> ZFSet.{v})
(i : Fin 9) (left right : RudimentaryTerm alpha) :
zfCode rho (.app i left right) =
triple appTag (operationCode i)
(ZFSet.pair (zfCode rho left) (zfCode rho right)) :=
rfl
/-- The two constructor tags have distinct internal codes. -/
theorem varTag_ne_appTag :
(varTag : ZFSet.{v}) ≠ appTag := by
intro h
exact zero_ne_one (Ordinal.toZFSet_injective h)
/-- The finite-ordinal operation code remembers the operation index. -/
theorem operationCode_injective :
Function.Injective (operationCode : Fin 9 -> ZFSet.{v}) := by
intro i j h
apply Fin.ext
exact Nat.cast_injective (Ordinal.toZFSet_injective h)
/-- A Kuratowski triple of constructible sets is constructible. -/
theorem triple_mem_L {x y z : ZFSet.{v}}
(hx : x ∈ L) (hy : y ∈ L) (hz : z ∈ L) :
triple x y z ∈ L := by
exact orderedPair_mem_L hx (orderedPair_mem_L hy hz)
/-- The variable constructor tag belongs to `L`. -/
theorem varTag_mem_L : (varTag : ZFSet.{v}) ∈ L :=
ordinal_toZFSet_mem_L 0
/-- The application constructor tag belongs to `L`. -/
theorem appTag_mem_L : (appTag : ZFSet.{v}) ∈ L :=
ordinal_toZFSet_mem_L 1
/-- Every finite operation code belongs to `L`. -/
theorem operationCode_mem_L (i : Fin 9) :
(operationCode i : ZFSet.{v}) ∈ L :=
ordinal_toZFSet_mem_L (i.1 : Ordinal.{v})
end
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule11
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryPrefixZFCode -/
section CUAdapterModule12
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internal ZF codes for rudimentary prefix syntax
`RudimentaryTerm.code` is an external Lean list of prefix tokens. This file
turns each token into a genuine `ZFSet`, then applies
`FiniteSequenceZF.sequenceCode` to internalize the whole finite prefix list.
Variable tokens carry the actual value of `rudimentaryGenerator`: `none` is
coded by `U`, while `some x` is coded by `x`. These values are distinct by
foundation because every such `x` belongs to `U`. Operation tokens carry the
operation index and the two subterm-code lengths.
This file only establishes faithful internal coding and constructibility. It
does not internalize the shortlex comparison or term evaluation relation.
-/
universe u
namespace Constructible.Godel
namespace RudimentaryTerm
noncomputable section
/-- The generator interpretation distinguishes all closure variables. -/
theorem rudimentaryGenerator_injective (U : ZFSet.{u}) :
Function.Injective (rudimentaryGenerator U) := by
intro first second h
cases first with
| none =>
cases second with
| none => rfl
| some x =>
exfalso
have hUx : U = x.1 := by
simpa only [rudimentaryGenerator] using h
have hself : x.1 ∈ x.1 := by
exact hUx ▸ x.2
exact ZFSet.mem_irrefl x.1 hself
| some x =>
cases second with
| none =>
exfalso
have hxU : x.1 = U := by
simpa only [rudimentaryGenerator] using h
have hself : x.1 ∈ x.1 := by
exact hxU.symm ▸ x.2
exact ZFSet.mem_irrefl x.1 hself
| some y =>
have hxy : x.1 = y.1 := by
simpa only [rudimentaryGenerator] using h
exact congrArg Option.some (Subtype.ext hxy)
/--
Encode one external prefix token as a genuine ZF set. Constructor tags are
the same tags used by the direct structural term encoding.
-/
def tokenZFCode (U : ZFSet.{u}) :
CodeToken (Option (Constructible.ZFCarrier U)) -> ZFSet.{u}
| .inl generator =>
triple varTag (rudimentaryGenerator U generator) ∅
| .inr operation =>
triple appTag (operationCode operation.1)
(ZFSet.pair
(FiniteSequenceZF.natCode operation.2.1)
(FiniteSequenceZF.natCode operation.2.2))
@[simp]
theorem tokenZFCode_variable (U : ZFSet.{u})
(generator : Option (Constructible.ZFCarrier U)) :
tokenZFCode U (.inl generator) =
triple varTag (rudimentaryGenerator U generator) ∅ :=
rfl
@[simp]
theorem tokenZFCode_operation (U : ZFSet.{u})
(i : Fin 9) (leftLength rightLength : Nat) :
tokenZFCode U (.inr (i, leftLength, rightLength)) =
triple appTag (operationCode i)
(ZFSet.pair
(FiniteSequenceZF.natCode leftLength)
(FiniteSequenceZF.natCode rightLength)) :=
rfl
/-- Every generator value is constructible when `U` is constructible. -/
theorem rudimentaryGenerator_mem_L {U : ZFSet.{u}} (hU : U ∈ L)
(generator : Option (Constructible.ZFCarrier U)) :
rudimentaryGenerator U generator ∈ L := by
cases generator with
| none => exact hU
| some x => exact mem_L_of_mem x.2 hU
end
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule12
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.DefWellOrder -/
section CUAdapterModule13
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A well-order on one definability step
Every member of `godelDef U` has a least rudimentary term representing it,
relative to a well-order of the generators `Option (ZFCarrier U)`. Distinct
sets have distinct least terms because evaluating such a term recovers the
set. Pulling the structural term order back along this injection therefore
well-orders `godelDef U`.
-/
universe u
namespace Constructible.Godel
open RudimentaryTerm
/-- The subtype of sets produced by one Gödel-definability step over `U`. -/
abbrev DefCarrier (U : ZFSet.{u}) :=
{z : ZFSet.{u} // z ∈ godelDef U}
/-- The least rudimentary term representing an element of `godelDef U`. -/
noncomputable def leastTermMap (U : ZFSet.{u})
(r : Option (Constructible.ZFCarrier U) →
Option (Constructible.ZFCarrier U) → Prop)
[IsWellOrder (Option (Constructible.ZFCarrier U)) r] :
DefCarrier U → RudimentaryClosureTerm U :=
fun z => leastRepresentingTerm U z.1 z.2 r
@[simp]
theorem eval_leastTermMap (U : ZFSet.{u})
(r : Option (Constructible.ZFCarrier U) →
Option (Constructible.ZFCarrier U) → Prop)
[IsWellOrder (Option (Constructible.ZFCarrier U)) r]
(z : DefCarrier U) :
(leastTermMap U r z).eval = z.1 :=
eval_leastRepresentingTerm U z.1 z.2 r
end Constructible.Godel
end CUAdapterModule13
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryGraph -/
section CUAdapterModule14
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# First-order graph formulas for rudimentary terms
Every rudimentary term with finitely many variables has an exact graph formula
in the ambient `ZFSet` universe. Terms over an arbitrary variable type are
first reified using one finite parameter slot for each variable occurrence.
The application case below deliberately uses two unrestricted existential
quantifiers. Thus the resulting formula is an ambient first-order graph; it
does not assert that all intermediate term values belong to a prescribed
transitive set.
-/
universe u v
namespace Constructible.Godel
open Constructible.Delta0Formula
namespace RudimentaryTerm
/--
A finite reification of a rudimentary term. The tuple contains one parameter
for each variable occurrence, so no decidable equality on the variable type
is required.
-/
def finiteReification {α : Type u} :
RudimentaryTerm α →
Σ n : Nat, Tuple α n × RudimentaryTerm (Fin n)
| .var a =>
⟨1, (fun _ => a), .var 0⟩
| .app i left right =>
match finiteReification left, finiteReification right with
| ⟨nl, leftParams, leftTerm⟩, ⟨nr, rightParams, rightTerm⟩ =>
⟨nl + nr,
Fin.addCases leftParams rightParams,
.app i
(leftTerm.rename (Fin.castAdd nr))
(rightTerm.rename (Fin.natAdd nl))⟩
/-- Reification preserves the value of a term under every assignment. -/
@[simp]
theorem eval_finiteReification {α : Type u} (t : RudimentaryTerm α)
(ρ : α → ZFSet.{v}) :
let result := finiteReification t
eval (ρ ∘ result.2.1) result.2.2 = eval ρ t := by
induction t with
| var a => rfl
| app i left right ihLeft ihRight =>
simp only [finiteReification, eval, eval_rename]
rw [← ihLeft, ← ihRight]
congr 2
· funext j
simp [Function.comp_def]
· funext j
simp [Function.comp_def]
/-- Every term admits a finite-variable presentation with identical evaluation. -/
theorem exists_finiteReification {α : Type u} (t : RudimentaryTerm α) :
∃ n : Nat, ∃ params : Tuple α n,
∃ body : RudimentaryTerm (Fin n),
∀ ρ : α → ZFSet.{v}, eval (ρ ∘ params) body = eval ρ t := by
let result := finiteReification t
refine ⟨result.1, result.2.1, result.2.2, ?_⟩
intro ρ
exact eval_finiteReification t ρ
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule14
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Simple -/
section CUAdapterModule15
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The bounded-section interface for the Gödel/Def bridge
The ambient graph of a composed rudimentary term may use intermediate values
outside a transitive carrier `U`. The bridge to `DefZF U` therefore targets a
stronger certificate: an ambient `Δ₀` formula defining membership in the final
set, using only genuine members of `U` as parameters.
The substitution and generated-formula modules produce `Delta0Section` values;
`Delta0Section.mem_DefZF` is the final absoluteness step.
-/
universe u
namespace Constructible
open Delta0Formula
/--
A finite ambient `Δ₀` definition of the section of `z` over `U`. Every entry
of `params` is a genuine member of `U`.
-/
structure Delta0Section (U z : ZFSet.{u}) where
/-- The number of parameters in the defining formula. -/
arity : Nat
/-- The parameters of the defining formula. -/
params : Tuple (ZFCarrier U) arity
/-- The bounded formula defining the section. -/
formula : Delta0Formula (arity + 1)
correct : ∀ q : ZFCarrier U,
Satisfies (fun x y : ZFSet.{u} => x ∈ y) formula
(snoc (Delta0Formula.val params) q.1) ↔
q.1 ∈ z
/--
For a transitive carrier, bounded absoluteness turns a `Delta0Section`
certificate into membership in the internally represented `DefZF U`.
-/
theorem Delta0Section.mem_DefZF {U z : ZFSet.{u}}
(sec : Delta0Section U z) (hU : U.IsTransitive) (hzU : z ⊆ U) :
z ∈ DefZF U := by
rw [mem_DefZF_iff_exists_satisfies]
refine ⟨hzU, sec.arity, sec.params, sec.formula.toFO, ?_⟩
intro q
rw [Delta0Formula.satisfies_toFO]
have habs := Delta0Formula.satisfies_absolute hU sec.formula
(snoc sec.params q)
have habs' :
Satisfies (zfCarrierMem U) sec.formula (snoc sec.params q) ↔
Satisfies (fun x y : ZFSet.{u} => x ∈ y) sec.formula
(snoc (Delta0Formula.val sec.params) q.1) := by
simpa only [Delta0Formula.val_snoc] using habs
exact (sec.correct q).symm.trans habs'.symm
namespace Godel
end Godel
end Constructible
end CUAdapterModule15
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.FormulaGodel -/
section CUAdapterModule16
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Formula relations as rudimentary sets
This module compiles every internally scoped first-order formula over a
transitive `ZFSet` into a rudimentary relation set. Taking a parameter fiber
then proves the formula-to-Gödel inclusion for `Def(U)`.
-/
open Set
universe u
namespace Constructible.Godel
/-- Reverse-snoc coding of a nonempty tuple by right-associated ordered pairs. -/
def positiveTupleCode : (n : Nat) → Tuple ZFSet.{u} (n + 1) → ZFSet.{u}
| 0, s => s 0
| n + 1, s =>
ZFSet.pair (s (Fin.last (n + 1)))
(positiveTupleCode n (fun i => s i.castSucc))
/-- The set of codes of nonempty tuples over `U`. -/
noncomputable def positiveTupleSpace (U : ZFSet.{u}) : Nat → ZFSet.{u}
| 0 => U
| n + 1 => F2 U (positiveTupleSpace U n)
@[simp]
theorem positiveTupleCode_snoc {n : Nat}
(s : Tuple ZFSet.{u} (n + 1)) (x : ZFSet.{u}) :
positiveTupleCode (n + 1) (snoc s x) =
ZFSet.pair x (positiveTupleCode n s) := by
simp [positiveTupleCode]
@[simp]
theorem mem_positiveTupleSpace_iff {U : ZFSet.{u}} {n : Nat}
(s : Tuple ZFSet.{u} (n + 1)) :
positiveTupleCode n s ∈ positiveTupleSpace U n ↔
∀ i, s i ∈ U := by
induction n with
| zero =>
simp only [positiveTupleCode, positiveTupleSpace]
constructor
· intro h i
fin_cases i
exact h
· intro h
exact h 0
| succ n ih =>
rw [positiveTupleSpace, positiveTupleCode]
rw [F2, ZFSet.pair_mem_prod, ih]
constructor
· rintro ⟨hlast, hprefix⟩ i
refine Fin.lastCases hlast (fun j => hprefix j) i
· intro h
exact ⟨h (Fin.last (n + 1)), fun j => h j.castSucc⟩
theorem F0_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F0 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (0 : Fin 9)) hx hy)
theorem F1_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F1 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (1 : Fin 9)) hx hy)
theorem F2_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F2 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (2 : Fin 9)) hx hy)
theorem F3_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F3 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (3 : Fin 9)) hx hy)
theorem F4_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F4 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (4 : Fin 9)) hx hy)
theorem F5_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F5 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (5 : Fin 9)) hx hy)
theorem F6_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F6 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (6 : Fin 9)) hx hy)
theorem F7_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F7 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (7 : Fin 9)) hx hy)
theorem F8_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
F8 x y ∈ rudimentaryClosure U := by
simpa [op] using
(op_mem_rudimentaryClosure (i := (8 : Fin 9)) hx hy)
theorem positiveTupleSpace_mem_rudimentaryClosure (U : ZFSet.{u}) :
∀ n, positiveTupleSpace U n ∈ rudimentaryClosure U := by
intro n
induction n with
| zero => exact self_mem_rudimentaryClosure U
| succ n ih =>
exact F2_mem_rudimentaryClosure
(self_mem_rudimentaryClosure U) ih
/-- Kuratowski ordered pairs stay inside the rudimentary closure. -/
theorem orderedPair_mem_rudimentaryClosure {U x y : ZFSet.{u}}
(hx : x ∈ rudimentaryClosure U) (hy : y ∈ rudimentaryClosure U) :
ZFSet.pair x y ∈ rudimentaryClosure U := by
have hs : F0 x x ∈ rudimentaryClosure U :=
F0_mem_rudimentaryClosure hx hx
have hp : F0 x y ∈ rudimentaryClosure U :=
F0_mem_rudimentaryClosure hx hy
have h := F0_mem_rudimentaryClosure hs hp
simpa [F0, ZFSet.pair] using h
/-- Every concrete tuple of members of `U` has its code in the closure. -/
theorem positiveTupleCode_mem_rudimentaryClosure {U : ZFSet.{u}} :
∀ {n : Nat} (s : Tuple (ZFCarrier U) (n + 1)),
positiveTupleCode n (Constructible.Delta0Formula.val s) ∈
rudimentaryClosure U := by
intro n
induction n with
| zero =>
intro s
exact subset_rudimentaryClosure U (s 0).2
| succ n ih =>
intro s
let pref : Tuple (ZFCarrier U) (n + 1) := fun i => s i.castSucc
let x : ZFCarrier U := s (Fin.last (n + 1))
have hs : snoc pref x = s := by
funext i
refine Fin.lastCases ?_ (fun j => ?_) i
· simp [x]
· simp [pref]
rw [← hs]
simp only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc]
exact orderedPair_mem_rudimentaryClosure
(subset_rudimentaryClosure U x.2) (ih pref)
/-- Taking the unique fiber indexed by a singleton is a rudimentary operation. -/
theorem fiber_mem_rudimentaryClosure {U r p : ZFSet.{u}}
(hr : r ∈ rudimentaryClosure U) (hp : p ∈ rudimentaryClosure U) :
fiber r p ∈ rudimentaryClosure U := by
have hsingle : F0 p p ∈ rudimentaryClosure U :=
F0_mem_rudimentaryClosure hp hp
have hfibers : F8 r (F0 p p) ∈ rudimentaryClosure U :=
F8_mem_rudimentaryClosure hr hsingle
have hunion : F5 (F8 r (F0 p p)) U ∈ rudimentaryClosure U :=
F5_mem_rudimentaryClosure hfibers (self_mem_rudimentaryClosure U)
have heq : F5 (F8 r (F0 p p)) U = fiber r p := by
apply ZFSet.ext
intro q
simp [F0]
rwa [heq] at hunion
/-- A rudimentary set coding a relation on nonempty tuples over `U`. -/
structure RelationRep (U : ZFSet.{u}) (n : Nat)
(P : Tuple (ZFCarrier U) (n + 1) → Prop) where
/-- The set coding the represented relation. -/
set : ZFSet.{u}
set_mem : set ∈ rudimentaryClosure U
subset_space : set ⊆ positiveTupleSpace U n
correct : ∀ s : Tuple (ZFCarrier U) (n + 1),
positiveTupleCode n (Constructible.Delta0Formula.val s) ∈ set ↔ P s
namespace RelationRep
/-- Every tuple is its prefix followed by its last coordinate. -/
theorem tuple_snoc_eta {A : Type u} {n : Nat} (s : Tuple A (n + 1)) :
snoc (fun i => s i.castSucc) (s (Fin.last n)) = s := by
funext i
refine Fin.lastCases ?_ (fun j => ?_) i
· simp
· simp
/-- Change only the external predicate characterized by a representation. -/
def congr {U : ZFSet.{u}} {n : Nat}
{P Q : Tuple (ZFCarrier U) (n + 1) → Prop}
(r : RelationRep U n P) (h : ∀ s, P s ↔ Q s) :
RelationRep U n Q where
set := r.set
set_mem := r.set_mem
subset_space := r.subset_space
correct := fun s => (r.correct s).trans (h s)
theorem mem_F3_triple_iff {x r a b c : ZFSet.{u}} :
triple a b c ∈ F3 x r ↔ b ∈ x ∧ ZFSet.pair a c ∈ r := by
rw [mem_F3_iff]
constructor
· rintro ⟨a', b', c', hb', hac', h⟩
rcases ZFSet.pair_inj.mp h with ⟨rfl, htail⟩
rcases ZFSet.pair_inj.mp htail with ⟨rfl, rfl⟩
exact ⟨hb', hac'⟩
· rintro ⟨hb, hac⟩
exact ⟨a, b, c, hb, hac, rfl⟩
theorem mem_F4_triple_iff {x r a b c : ZFSet.{u}} :
triple a b c ∈ F4 x r ↔ c ∈ x ∧ ZFSet.pair a b ∈ r := by
rw [mem_F4_iff]
constructor
· rintro ⟨a', b', c', hc', hab', h⟩
rcases ZFSet.pair_inj.mp h with ⟨rfl, htail⟩
rcases ZFSet.pair_inj.mp htail with ⟨rfl, rfl⟩
exact ⟨hc', hab'⟩
· rintro ⟨hc, hab⟩
exact ⟨a, b, c, hc, hab, rfl⟩
theorem pair_mem_F7_iff {U a b : ZFSet.{u}} (ha : a ∈ U) (hb : b ∈ U) :
ZFSet.pair a b ∈ F7 U U ↔ a ∈ b := by
rw [mem_F7_iff]
constructor
· rintro ⟨a', ha', b', hb', hp, hab⟩
rcases ZFSet.pair_inj.mp hp with ⟨h₁, h₂⟩
simpa [← h₁, ← h₂] using hab
· intro hab
exact ⟨a, ha, b, hb, rfl, hab⟩
/-- The primitive membership relation represents `last ∈ first` on pairs. -/
noncomputable def lastMemRepZero (U : ZFSet.{u}) :
RelationRep U 1
(fun s => (s (Fin.last 1)).1 ∈ (s 0).1) where
set := F7 U U
set_mem := F7_mem_rudimentaryClosure
(self_mem_rudimentaryClosure U) (self_mem_rudimentaryClosure U)
subset_space := by
intro q hq
rcases mem_F7_iff.mp hq with ⟨a, ha, b, hb, rfl, hab⟩
rw [positiveTupleSpace, positiveTupleSpace, F2,
ZFSet.pair_mem_prod]
exact ⟨ha, hb⟩
correct := by
intro s
simp only [positiveTupleCode]
rw [mem_F7_iff]
constructor
· rintro ⟨a, ha, b, hb, hp, hab⟩
rcases ZFSet.pair_inj.mp hp with ⟨h₁, h₂⟩
simpa [← h₁, ← h₂] using hab
· intro h
exact ⟨(s (Fin.last 1)).1, (s (Fin.last 1)).2,
(s 0).1, (s 0).2, rfl, h⟩
/-- Membership of the new last coordinate in the previous last coordinate. -/
noncomputable def lastMemRepLast (U : ZFSet.{u}) (n : Nat) :
RelationRep U (n + 2)
(fun s =>
(s (Fin.last (n + 2))).1 ∈
(s (Fin.last (n + 1)).castSucc).1) where
set := F4 (positiveTupleSpace U n) (F7 U U)
set_mem := F4_mem_rudimentaryClosure
(positiveTupleSpace_mem_rudimentaryClosure U n)
(F7_mem_rudimentaryClosure
(self_mem_rudimentaryClosure U) (self_mem_rudimentaryClosure U))
subset_space := by
intro q hq
rcases mem_F4_iff.mp hq with ⟨a, b, c, hc, hab, rfl⟩
rw [positiveTupleSpace, F2, triple, ZFSet.pair_mem_prod]
have hab' := (mem_F7_iff.mp hab)
rcases hab' with ⟨a', ha', b', hb', hp, _⟩
rcases ZFSet.pair_inj.mp hp with ⟨rfl, rfl⟩
refine ⟨ha', ?_⟩
rw [positiveTupleSpace, F2, ZFSet.pair_mem_prod]
exact ⟨hb', hc⟩
correct := by
intro s
let tail : Tuple (ZFCarrier U) (n + 2) := fun i => s i.castSucc
let rest : Tuple (ZFCarrier U) (n + 1) := fun i => tail i.castSucc
let a : ZFCarrier U := s (Fin.last (n + 2))
let b : ZFCarrier U := tail (Fin.last (n + 1))
have hs : snoc tail a = s := tuple_snoc_eta s
have ht : snoc rest b = tail := tuple_snoc_eta tail
rw [← hs, ← ht]
simp only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc, snoc_last, snoc_castSucc]
change triple a.1 b.1
(positiveTupleCode n (Constructible.Delta0Formula.val rest)) ∈
F4 (positiveTupleSpace U n) (F7 U U) ↔ a.1 ∈ b.1
rw [mem_F4_triple_iff,
mem_positiveTupleSpace_iff, pair_mem_F7_iff a.2 b.2]
simp
/-- Direct membership: the newest coordinate belongs to any older coordinate. -/
theorem exists_lastMemRep (U : ZFSet.{u}) :
∀ (n : Nat) (j : Fin (n + 1)),
Nonempty <| RelationRep U (n + 1)
(fun s =>
(s (Fin.last (n + 1))).1 ∈ (s j.castSucc).1) := by
intro n
induction n with
| zero =>
intro j
fin_cases j
exact ⟨lastMemRepZero U⟩
| succ n ih =>
intro j
refine Fin.lastCases ?_ (fun k => ?_) j
· exact ⟨lastMemRepLast U n⟩
· rcases ih k with ⟨r⟩
refine ⟨{
set := F3 U r.set
set_mem := F3_mem_rudimentaryClosure
(self_mem_rudimentaryClosure U) r.set_mem
subset_space := ?_
correct := ?_
}⟩
· intro q hq
rcases mem_F3_iff.mp hq with ⟨a, b, c, hb, hac, rfl⟩
have hspace := r.subset_space hac
rw [positiveTupleSpace, F2, ZFSet.pair_mem_prod] at hspace
rw [positiveTupleSpace, F2, triple, ZFSet.pair_mem_prod]
refine ⟨hspace.1, ?_⟩
rw [positiveTupleSpace, F2, ZFSet.pair_mem_prod]
exact ⟨hb, hspace.2⟩
· intro s
let tail : Tuple (ZFCarrier U) (n + 2) := fun i => s i.castSucc
let rest : Tuple (ZFCarrier U) (n + 1) := fun i => tail i.castSucc
let a : ZFCarrier U := s (Fin.last (n + 2))
let b : ZFCarrier U := tail (Fin.last (n + 1))
have hs : snoc tail a = s := tuple_snoc_eta s
have ht : snoc rest b = tail := tuple_snoc_eta tail
rw [← hs, ← ht]
simp only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc, snoc_last, snoc_castSucc]
change triple a.1 b.1
(positiveTupleCode n (Constructible.Delta0Formula.val rest)) ∈
F3 U r.set ↔ a.1 ∈ (rest k).1
rw [mem_F3_triple_iff]
have hr := r.correct (snoc rest a)
simp only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc, snoc_last, snoc_castSucc] at hr
rw [hr]
simp [b.2]
/-- Chosen direct-membership representative. -/
noncomputable def lastMemRep (U : ZFSet.{u}) (n : Nat)
(j : Fin (n + 1)) :
RelationRep U (n + 1)
(fun s =>
(s (Fin.last (n + 1))).1 ∈ (s j.castSucc).1) :=
Classical.choice (exists_lastMemRep U n j)
/-- Complement a represented relation inside the tuple space. -/
noncomputable def neg {U : ZFSet.{u}} {n : Nat}
{P : Tuple (ZFCarrier U) (n + 1) → Prop}
(r : RelationRep U n P) : RelationRep U n (fun s => ¬P s) where
set := F1 (positiveTupleSpace U n) r.set
set_mem := F1_mem_rudimentaryClosure
(positiveTupleSpace_mem_rudimentaryClosure U n) r.set_mem
subset_space := by
intro z hz
exact (mem_F1_iff.mp hz).1
correct := by
intro s
rw [mem_F1_iff, r.correct, mem_positiveTupleSpace_iff]
simp
/-- Intersect two represented relations. -/
noncomputable def conj {U : ZFSet.{u}} {n : Nat}
{P Q : Tuple (ZFCarrier U) (n + 1) → Prop}
(r : RelationRep U n P) (t : RelationRep U n Q) :
RelationRep U n (fun s => P s ∧ Q s) where
set := F1 r.set (F1 r.set t.set)
set_mem := F1_mem_rudimentaryClosure r.set_mem
(F1_mem_rudimentaryClosure r.set_mem t.set_mem)
subset_space := by
intro z hz
exact r.subset_space (mem_F1_iff.mp hz).1
correct := by
intro s
simp only [mem_F1_iff, r.correct, t.correct]
tauto
/-- Union/disjunction of two represented relations. -/
noncomputable def disj {U : ZFSet.{u}} {n : Nat}
{P Q : Tuple (ZFCarrier U) (n + 1) → Prop}
(r : RelationRep U n P) (t : RelationRep U n Q) :
RelationRep U n (fun s => P s ∨ Q s) := by
apply congr (neg (conj (neg r) (neg t)))
intro s
tauto
/-- Project away the newest (last syntactic, outermost coded) coordinate. -/
noncomputable def ex {U : ZFSet.{u}} {n : Nat}
{P : Tuple (ZFCarrier U) (n + 2) → Prop}
(r : RelationRep U (n + 1) P) :
RelationRep U n (fun s => ∃ x : ZFCarrier U, P (snoc s x)) where
set := F6 r.set U
set_mem := F6_mem_rudimentaryClosure r.set_mem
(self_mem_rudimentaryClosure U)
subset_space := by
intro z hz
rcases mem_F6_iff.mp hz with ⟨w, hw⟩
have hspace := r.subset_space hw
rw [positiveTupleSpace, F2, ZFSet.pair_mem_prod] at hspace
exact hspace.2
correct := by
intro s
constructor
· intro h
rcases mem_F6_iff.mp h with ⟨w, hw⟩
have hspace := r.subset_space hw
rw [positiveTupleSpace, F2, ZFSet.pair_mem_prod] at hspace
let x : ZFCarrier U := ⟨w, hspace.1⟩
refine ⟨x, ?_⟩
apply (r.correct (snoc s x)).mp
simpa only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc, x] using hw
· rintro ⟨x, hx⟩
apply mem_F6_iff.mpr
refine ⟨x.1, ?_⟩
have hcode := (r.correct (snoc s x)).mpr hx
simpa only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc] using hcode
/-- Equality of two coordinates, obtained extensionally from direct membership. -/
noncomputable def eqRep (U : ZFSet.{u}) (hU : U.IsTransitive)
{n : Nat} (i j : Fin (n + 1)) :
RelationRep U n (fun s => (s i).1 = (s j).1) := by
let ri := lastMemRep U n i
let rj := lastMemRep U n j
let differing := disj (conj ri (neg rj)) (conj rj (neg ri))
apply congr (neg (ex differing))
intro s
simp only [snoc_last, snoc_castSucc]
change
(¬∃ y : ZFCarrier U,
((y.1 ∈ (s i).1 ∧ y.1 ∉ (s j).1) ∨
(y.1 ∈ (s j).1 ∧ y.1 ∉ (s i).1))) ↔
(s i).1 = (s j).1
constructor
· intro h
apply ZFSet.ext
intro y
constructor
· intro hyi
by_contra hyj
have hyU : y ∈ U := hU.mem_trans hyi (s i).2
exact h ⟨⟨y, hyU⟩, Or.inl ⟨hyi, hyj⟩⟩
· intro hyj
by_contra hyi
have hyU : y ∈ U := hU.mem_trans hyj (s j).2
exact h ⟨⟨y, hyU⟩, Or.inr ⟨hyj, hyi⟩⟩
· intro hij h
rcases h with ⟨y, h | h⟩
· exact h.2 (hij ▸ h.1)
· exact h.2 (hij.symm ▸ h.1)
/-- An arbitrary membership atom, reduced to direct membership plus equality. -/
noncomputable def memRep (U : ZFSet.{u}) (hU : U.IsTransitive)
{n : Nat} (i j : Fin (n + 1)) :
RelationRep U n (fun s => (s i).1 ∈ (s j).1) := by
let zIndex : Fin (n + 3) := (Fin.last (n + 1)).castSucc
let yIndex : Fin (n + 3) := Fin.last (n + 2)
let direct := lastMemRep U (n + 1) (Fin.last (n + 1))
let yEq := eqRep U hU yIndex i.castSucc.castSucc
let zEq := eqRep U hU zIndex j.castSucc.castSucc
apply congr (ex (ex (conj direct (conj yEq zEq))))
intro s
simp only [zIndex, yIndex, snoc_last, snoc_castSucc]
change
(∃ z : ZFCarrier U, ∃ y : ZFCarrier U,
y.1 ∈ z.1 ∧ y.1 = (s i).1 ∧ z.1 = (s j).1) ↔
(s i).1 ∈ (s j).1
constructor
· rintro ⟨z, y, hyz, hy, hz⟩
simpa [hy, hz] using hyz
· intro h
exact ⟨s j, s i, h, rfl, rfl⟩
/-- Compile every positive-arity first-order relation over `U` to a rudimentary set. -/
noncomputable def formulaRep (U : ZFSet.{u}) (hU : U.IsTransitive) :
{n : Nat} → (φ : FOFormula (n + 1)) →
RelationRep U n
(fun s => FOFormula.Satisfies (zfCarrierMem U) φ s)
| _, .mem i j => memRep U hU i j
| _, .eq i j => by
apply congr (eqRep U hU i j)
intro s
change (s i).1 = (s j).1 ↔ s i = s j
exact Subtype.ext_iff.symm
| _, .neg φ => neg (formulaRep U hU φ)
| _, .conj φ ψ => conj (formulaRep U hU φ) (formulaRep U hU ψ)
| _, .ex φ => ex (formulaRep U hU φ)
/-- Every formula-defined subset of a transitive `U` belongs to its rudimentary closure. -/
theorem definableSection_mem_rudimentaryClosure {U z : ZFSet.{u}}
(hU : U.IsTransitive) (hzU : z ⊆ U) {n : Nat}
(params : Tuple (ZFCarrier U) n) (φ : FOFormula (n + 1))
(hdef : ∀ q : ZFCarrier U,
q.1 ∈ z ↔ FOFormula.Satisfies (zfCarrierMem U) φ (snoc params q)) :
z ∈ rudimentaryClosure U := by
cases n with
| zero =>
let r := formulaRep U hU φ
have heq : z = r.set := by
apply ZFSet.ext
intro y
constructor
· intro hy
let q : ZFCarrier U := ⟨y, hzU hy⟩
have hsat := (hdef q).mp hy
have hcode := (r.correct (snoc params q)).mpr hsat
change y ∈ r.set at hcode
exact hcode
· intro hy
have hyU : y ∈ U := by
have hspace := r.subset_space hy
simpa [positiveTupleSpace] using hspace
let q : ZFCarrier U := ⟨y, hyU⟩
apply (hdef q).mpr
apply (r.correct (snoc params q)).mp
change y ∈ r.set
exact hy
rw [heq]
exact r.set_mem
| succ n =>
let r := formulaRep U hU φ
let p := positiveTupleCode n (Constructible.Delta0Formula.val params)
have hp : p ∈ rudimentaryClosure U :=
positiveTupleCode_mem_rudimentaryClosure params
have hfiber : fiber r.set p ∈ rudimentaryClosure U :=
fiber_mem_rudimentaryClosure r.set_mem hp
have heq : z = fiber r.set p := by
apply ZFSet.ext
intro y
constructor
· intro hy
let q : ZFCarrier U := ⟨y, hzU hy⟩
apply mem_fiber_iff.mpr
have hsat := (hdef q).mp hy
have hcode := (r.correct (snoc params q)).mpr hsat
simpa only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc, p] using hcode
· intro hy
have hpair : ZFSet.pair y p ∈ r.set := mem_fiber_iff.mp hy
have hspace := r.subset_space hpair
rw [positiveTupleSpace, F2, ZFSet.pair_mem_prod] at hspace
let q : ZFCarrier U := ⟨y, hspace.1⟩
apply (hdef q).mpr
apply (r.correct (snoc params q)).mp
simpa only [Constructible.Delta0Formula.val_snoc,
positiveTupleCode_snoc, p, q] using hpair
rw [heq]
exact hfiber
theorem defZF_subset_godelDef_aux {U : ZFSet.{u}}
(hU : U.IsTransitive) :
Constructible.DefZF U ⊆ godelDef U := by
intro z hz
rcases Constructible.mem_DefZF_iff_exists_satisfies.mp hz with
⟨hzU, n, params, φ, hdef⟩
apply mem_godelDef_iff.mpr
exact ⟨hzU,
definableSection_mem_rudimentaryClosure hU hzU params φ hdef⟩
end RelationRep
/-- Formula definability implies membership in the Gödel-operation
presentation. -/
theorem DefZF_subset_godelDef {U : ZFSet.{u}} (hU : U.IsTransitive) :
Constructible.DefZF U ⊆ godelDef U :=
RelationRep.defZF_subset_godelDef_aux hU
end Constructible.Godel
end CUAdapterModule16