Constructibility coding and membership interfaces
DefinitionCH_ConstructibleGCH_Library01This library supplies the additional syntax, hierarchy, membership-model and internal-order interfaces required by the GCH development. The hierarchy is the external constructible hierarchy over ambient ZF sets. The existing platform-to-reference hierarchy equivalence is reused.
The original constructible-universe formalization is by Zike Liu, copyright 2026, Apache-2.0; see the pinned source. This Prove2Me adaptation preserves the original copyright notices.
This module includes supporting proofs required by its definitions and constructor data.
Mathematical references: Andrew Marks, Set Theory, Lemma 21.3 and Corollary 21.4, printed pp. 90–91; Kurt Gödel, “The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis,” PNAS 24 (1938), 556–557; and Gödel’s 1940 Princeton monograph, The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis with the Axioms of Set Theory (publisher note). The upstream textbook E/Df construction cites Wang Fangting, Axiomatic Set Theory, §§6.3–6.8.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from OpenAI Codex.
import Definitions.Def_CH_ConstructibleAC_Library15
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
import Mathlib.SetTheory.ZFC.Cardinal
import Mathlib.SetTheory.ZFC.Basic
import Mathlib.Data.Nat.Factorization.Basic
import Mathlib.Data.Fin.VecNotation
import Mathlib.SetTheory.Cardinal.Basic
/-
Prove2Me adaptation of the constructible-universe formalization by Zike Liu,
Apache-2.0, commit 7f5a7d03d63d9769172f17350bbe8303996e5b53.
Original copyright notices are preserved below.
**Formalization credit:** **Wentao Li (Victor)**, under the Prove2Me account **Victorized**, with assistance from OpenAI Codex.
-/
set_option Elab.async false
set_option maxHeartbeats 1000000
/- Source module: Solutions.Work_ConstructibleGCH_ReuseBase -/
section GCHSource_Work_ConstructibleGCH_ReuseBase
set_option autoImplicit false
/-!
# 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.Def -/
section CUAdapterModule0
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The relation-algebra definition of `Def`
This file formalizes the relation-algebra presentation of first-order
definability:
* `D 0 A n` consists of the atomic membership and equality relations;
* `D (k+1) A n` is closed under complement, intersection, and existential
projection, using relations from stage `k`;
* `Df A n` is the union of all finite stages;
* `definablePowerset A` consists of the sections of relations in `Df` obtained
by fixing finitely many parameters.
Here the underlying set `a` is represented by a Lean type `A`, equipped with
the binary relation which plays the role of membership. Thus `Tuple A n` is
the type-theoretic counterpart of `a^n`.
-/
open Set
universe u
namespace Constructible
/-! ## An independent syntax and satisfaction relation -/
namespace FOFormula
/-! ### Variable management -/
/-! ### Bounded quantifiers -/
end FOFormula
section Atomic
variable {A : Type u} (E : A → A → Prop)
/-! ### Equivalence with first-order formula semantics -/
end Atomic
/-! ## Specialization to Mathlib's ZFC universe -/
section ZFC
/-!
### An internal `ZFSet` version of the definable-powerset operation
The following construction uses the powerset and separation operations of
`ZFSet`. Consequently `DefZF a` is itself a genuine ZFC set, not merely an
external Lean predicate on `ZFSet`.
-/
/-! ### Basic structural properties of `DefZF` -/
/-!
### The internally represented constructible hierarchy
Every value of `LStageZF` is an actual `ZFSet`. At a limit ordinal `l`, the
index type `Set.Iio l` is small in universe `u`; `replacementRangeZF` first
forms the range of the preceding levels as a ZFC set and `limitUnionZF` then
applies internal union. This use of `ZFSet.image` is the ambient,
metatheoretic Replacement step in the standard external recursion defining
`L`. Mathlib's class `ZFSet.Definable` means that a function lifts to `PSet`;
it does not assert object-language first-order definability in `L`.
-/
end ZFC
end Constructible
end CUAdapterModule0
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Delta0 -/
section CUAdapterModule1
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Bounded formulas for the constructible hierarchy
This file introduces an intrinsically scoped syntax for `Δ₀` formulas in the
language of set theory. Quantifiers are bounded syntactically. The syntax is
translated to `Constructible.FOFormula`, and its semantics is proved absolute
between a transitive `ZFSet` and the ambient `ZFSet` universe.
-/
universe u
namespace Constructible
namespace Delta0Formula
/-! ## Absoluteness -/
/-- Absoluteness after embedding a bounded formula into `FOFormula`. -/
theorem satisfies_toFO_absolute {a : ZFSet.{u}} (ha : a.IsTransitive)
{n : Nat} (φ : Delta0Formula n) (s : Tuple (ZFCarrier a) n) :
FOFormula.Satisfies (zfCarrierMem a) φ.toFO s ↔
FOFormula.Satisfies (fun x y : ZFSet.{u} => x ∈ y) φ.toFO (val s) := by
rw [satisfies_toFO, satisfies_toFO, satisfies_absolute ha]
end Delta0Formula
end Constructible
end CUAdapterModule1
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Godel -/
section CUAdapterModule2
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Gödel operations and rudimentary closure
This file implements the standard Jensen--Devlin basis `F₀, ..., F₈` of
rudimentary (Gödel) operations on Mathlib's internal `ZFSet` universe. Tuples
are right-associated Kuratowski pairs:
`⟨x, y, z⟩ = ⟨x, ⟨y, z⟩⟩`.
The resulting `rudimentaryClosure U` starts from `U ∪ {U}`. The candidate
Gödel presentation of the definable powerset is then
`powerset U ∩ rudimentaryClosure U`.
Its equality with `Constructible.DefZF U` for transitive `U` is deliberately
not built into the definition; it is a theorem to be established separately.
-/
open Set
universe u
namespace Constructible.Godel
end Constructible.Godel
end CUAdapterModule2
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Delta0Godel -/
section CUAdapterModule3
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Bounded formulas for Gödel operations
This file supplies reusable `Δ₀` formulas for the finite set encodings used
by the Jensen--Devlin Gödel operations. All coordinate conventions are
intrinsically checked by the `Fin` indices.
-/
open Set
universe u
namespace Constructible.Delta0Formula
end Constructible.Delta0Formula
namespace Constructible.Godel
open Constructible.Delta0Formula
/-!
The fixed assignment convention for the following formulas is `![q,x,y]`:
coordinate `0` is the candidate member and coordinates `1,2` are the two
arguments of the Gödel operation.
-/
end Constructible.Godel
end CUAdapterModule3
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Delta0GodelGraph -/
section CUAdapterModule4
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Bounded graph formulas for the Gödel operations
Membership in every Jensen--Devlin operation is `Δ₀`. This file strengthens
that result to formulas for the full graphs `out = Fᵢ(x,y)`, using only bounded
quantifiers in both containment directions.
-/
open Set
universe u
namespace Constructible.Godel
open Constructible.Delta0Formula
/-! All graph formulas below use the fixed assignment `![out,x,y]`. -/
end Constructible.Godel
end CUAdapterModule4
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Bounding -/
section CUAdapterModule5
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Stage bounds in the constructible hierarchy
This file collects the external bounding facts used to turn set-indexed
families of constructible sets into constructions inside one level of `L`.
The index type of the members of a `ZFSet` is small, so a family of witnesses
in `Ordinal.{u}` has a supremum in the same universe.
-/
open Set
universe u
namespace Constructible
section ZFC
end ZFC
end Constructible
end CUAdapterModule5
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Ordinals -/
section CUAdapterModule6
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Ordinals in the constructible universe
The property of being a von Neumann ordinal is expressed by a bounded
first-order formula. Its absoluteness to a transitive level lets us prove,
simultaneously, that the ordinal elements of `LStageZF α` have rank below `α`
and that `α.toZFSet` is contained in that level.
-/
open Set
universe u
namespace Constructible
section ZFC
namespace OrdinalFormula
end OrdinalFormula
end ZFC
end Constructible
end CUAdapterModule6
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.FiniteSequenceZF -/
section CUAdapterModule7
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Finite sequences as ZF sets
This file gives a small, structural encoding of finite lists of `ZFSet`s.
The payload is a chain of Kuratowski ordered pairs terminated by the empty
set. The public sequence code also stores the von Neumann ordinal coding of
the list length.
The construction is deliberately recursive. In particular, it does not use
an external image and therefore its constructibility proof only needs the
already established closure of `L` under ordered pairs.
-/
universe u
namespace Constructible
namespace FiniteSequenceZF
end FiniteSequenceZF
end Constructible
end CUAdapterModule7
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.IndexedSequenceZF -/
section CUAdapterModule8
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Indexed finite-sequence codes
The structural list code in `FiniteSequenceZF` is convenient for recursion.
For first-order definitions of lexicographic order, however, direct access to
the entry at an internal natural-number index is more useful. This file codes
a list by the finite graph
`{ <xs[i], i> | i < xs.length }`
and stores its length alongside that graph. This indexed-sequence encoding
uses pairs `<output,input>`. It is intentionally distinct from Mathlib's
`ZFSet.IsFunc` convention, whose function graphs use `<input,output>`.
-/
universe u
namespace Constructible
namespace IndexedSequenceZF
open FiniteSequenceZF
end IndexedSequenceZF
end Constructible
end CUAdapterModule8
/- 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
namespace RudimentaryTerm
variable {α β : Type u}
end RudimentaryTerm
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
/-! ## The structural well-order -/
/-! ## Least representations -/
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
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
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
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
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
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
namespace RelationRep
end RelationRep
end Constructible.Godel
end CUAdapterModule16
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimpleSubstitution -/
section CUAdapterModule17
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Strong-simple substitution
This file implements the substitution machinery for the inclusion
`godelDef U ⊆ DefZF U`.
The key point is that a membership section is not stable under composition.
This file develops complete elimination cases for set difference, internal
union, and unordered pairing, together with the generic composition and
simultaneous-substitution machinery used by the remaining primitive operations.
-/
open Set
universe u
namespace Constructible.Godel
open Constructible.Delta0Formula
variable {n m k : Nat}
namespace DiffExpr
end DiffExpr
/-! ## A second complete case: internal union (`F₅`) -/
namespace UnionExpr
end UnionExpr
/-! ## A third complete case: unordered pairing (`F₀`) -/
namespace PairExpr
end PairExpr
/-! ## Checked composition -/
/-! ## Eliminating the distinguished universe constant -/
namespace EraseUniverse
end EraseUniverse
/-! ## Simultaneous substitutions and genuine term composition -/
end Constructible.Godel
end CUAdapterModule17
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimplePairSets -/
section CUAdapterModule18
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Simplicity of ordered pairs and pair sets
This file proves strong simplicity for Kuratowski ordered pairing and for the pair-set operations
used in the Gödel basis.
-/
open Set
universe u
namespace Constructible.Godel
open Constructible.Delta0Formula
variable {n m k : Nat}
section
/-! ## Ordered pairing is simple -/
/-! ## Eliminating a last-coordinate ordered-pair value -/
/-! ## A shared expression compiler for `F₂` and `F₇` -/
namespace PairSetKind
end PairSetKind
namespace PairSetExpr
end PairSetExpr
end
end Constructible.Godel
end CUAdapterModule18
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimpleComposition -/
section CUAdapterModule19
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Composition of simple set functions
This file proves that strong simplicity is preserved by unary and binary composition. The tuple
renamings below arrange arguments and intermediate values for the corresponding bounded formulas.
-/
universe u
namespace Constructible.Godel
end Constructible.Godel
end CUAdapterModule19
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimpleTerms -/
section CUAdapterModule20
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Simplicity of rudimentary terms
This file lifts simplicity from the basic Gödel operations to arbitrary finite rudimentary terms
and reifies their parameters over an internal carrier.
-/
universe u
namespace Constructible.Godel
end Constructible.Godel
end CUAdapterModule20
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimpleCompiler -/
section CUAdapterModule21
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Compiling simple set functions
This file packages the data needed to eliminate a binary set-valued operation from bounded
formulas and proves the generic correctness lemmas for that elimination procedure.
-/
open Set
universe u
namespace Constructible.Godel
open Constructible.Delta0Formula
variable {n m k : Nat}
namespace ValueExpr
end ValueExpr
end Constructible.Godel
end CUAdapterModule21
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimpleGenerated -/
section CUAdapterModule22
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Generated bounded formulas for simple set functions
This file derives reusable elimination formulas from `SimpleValueSpec` and proves the resulting
strong-simplicity theorem for ternary membership descriptions.
-/
open Set
universe u
namespace Constructible.Godel
open Constructible.Delta0Formula
variable {n : Nat}
end Constructible.Godel
end CUAdapterModule22
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimpleF3F4 -/
section CUAdapterModule23
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Simplicity of the Gödel operations F3 and F4
This file instantiates the generic simple-function compiler for the two operations that extract
triple components from Kuratowski-pair encodings.
-/
open Set
universe u
namespace Constructible.Godel
open Constructible.Delta0Formula
variable {n : Nat}
namespace TripleSetKind
end TripleSetKind
end Constructible.Godel
end CUAdapterModule23
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SimpleF6F8 -/
section CUAdapterModule24
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Simplicity of the Gödel operations F6 and F8
This file instantiates the generic simple-function compiler for component extraction, fibers, and
the remaining bounded pair-component operation represented here by F6 and F8.
-/
open Set
universe u
namespace Constructible.Godel
open Constructible.Delta0Formula
variable {n : Nat}
/-! ## Fibers are simple -/
/-! ## F8 is a bounded image by the simple fiber operation -/
end Constructible.Godel
end CUAdapterModule24
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Equivalence -/
section CUAdapterModule25
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Equivalence of formula and rudimentary definability
This file proves Jensen's equivalence between first-order definable subsets of a transitive set
and the powerset-bounded closure under the nine basic Gödel operations.
-/
open Set
universe u
namespace Constructible.Godel
end Constructible.Godel
end CUAdapterModule25
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryConstructible -/
section CUAdapterModule26
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Constructibility of rudimentary term values
Every primitive Gödel operation preserves constructibility. The proof first
shows that all members of an operation value are constructible, bounds those
members together with the two operands in one constructible stage, and then
uses the existing bounded definition of the operation to place its value in
the next stage.
It follows by structural induction that a rudimentary term whose generators
belong to `L` also evaluates to an element of `L`.
-/
open Set
universe u v
namespace Constructible
namespace Godel
namespace RudimentaryTerm
end RudimentaryTerm
end Godel
end Constructible
end CUAdapterModule26
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgram -/
section CUAdapterModule27
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Postfix stack programs for rudimentary evaluation
Prefix tree codes are useful for structural arguments, but a uniform
first-order evaluator would have to parse arbitrary subtree boundaries. A
postfix stack program has a local transition semantics instead:
* a variable token pushes its generator value;
* an operation token pops the right and left operands and pushes their value.
The token lists still carry a Shortlex well-order. Hence every value in one
Gödel-definability step has a least evaluating program, and these least
programs give a well-order of that step. The local transition semantics admits
internalization by a finite set-coded execution trace.
-/
universe u v
namespace Constructible.Godel
namespace RudimentaryTerm
/-! ## The structural program well-order -/
/-! ## Least programs representing definable values -/
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule27
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgramZFCode -/
section CUAdapterModule28
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internal codes for rudimentary stack programs
Postfix program tokens and whole instruction lists are encoded by genuine
`ZFSet`s. Variable tokens carry their generator value; operation tokens carry
the finite ordinal operation index. Whole programs use the indexed sequence
encoding, which is tailored to a first-order execution-trace predicate.
-/
universe u
namespace Constructible.Godel
namespace RudimentaryTerm
noncomputable section
end
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule28
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackStepFormula -/
section CUAdapterModule29
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A first-order transition formula for rudimentary stack programs
The fixed parameter layout is
`[U, varTag, appTag, empty, op0, ..., op8, token, input, output]`.
The last three coordinates are the instruction and the two stack states. A
variable instruction pushes its generator. An operation instruction pops the
right and left operands, applies the selected Gödel operation, and pushes the
result. Stack states use `FiniteSequenceZF.listCode`, whose cons constructor
is precisely a Kuratowski pair.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
open Constructible.Delta0Formula
/-! ## Fixed indices -/
/-! ## Variable and operation branches -/
/-! ## Assignments and semantics -/
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule29
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackStepDecode -/
section CUAdapterModule30
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Decoding arbitrary satisfying stack-step codes
The basic semantic theorem for `stackStepFormula` was first stated on genuine
token and stack codes. Whole-program soundness also needs the converse shape:
starting from a genuine input stack code, every arbitrary raw token/output pair
accepted by the formula must decode to a real instruction and a real output
stack. This file proves exactly that fact.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
open FiniteSequenceZF
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule30
/- Original module: ConstructibleUniverse.ModelTheory.SetTheory.Basic -/
section CUAdapterModule31
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The First-Order Language of Set Theory
This file defines the first-order language with a single binary relation symbol
for membership. Equality is provided by first-order logic itself.
## Main Definitions
- `FirstOrder.Language.setTheory` is the first-order language of set theory.
- `FirstOrder.Language.Term.mem` is the atomic formula asserting membership between two terms.
- `FirstOrder.Language.setTheoryStructure` interprets membership as a binary relation.
-/
universe u v
namespace FirstOrder.Language
open Structure
variable {M : Type u} {α : Type v} {n : ℕ}
end FirstOrder.Language
end CUAdapterModule31
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Semantics -/
section CUAdapterModule32
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Semantics for formulas in the language of set theory
This file provides relation-parametric term evaluation and formula realization
for Mathlib's first-order language of set theory.
The relation-parametric semantics below uses `BoundedFormula Empty n`: there are no
named free variables, and the `n` variables currently in scope are interpreted
by an assignment `Fin n -> A`.
-/
universe u
namespace Constructible
namespace Model
end Model
end Constructible
end CUAdapterModule32
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Model -/
section CUAdapterModule33
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The first-order structure carried by the constructible universe
This file connects the formula syntax used to construct `L` with Mathlib's
general model-theory API. The language has no function symbols and one binary
relation symbol, interpreted as membership.
The existing `Constructible.FOFormula n` treats all `n` variables uniformly
and appends a bound variable at the end of a tuple. Mathlib's
`BoundedFormula Empty n` has exactly the same convention, so the translation
below does not need a variable permutation.
-/
open Set
universe u
namespace Constructible
namespace Model
/-! ## Raw-domain semantics for external classes -/
/-- Closed construction formulas translate to Mathlib sentences. -/
abbrev toSentence (phi : FOFormula 0) : FirstOrder.Language.setTheory.Sentence :=
toBoundedFormula phi
section ArbitraryStructure
variable {A : Type u} (E : A -> A -> Prop)
/-- The forward translation stated through the canonical `realizes` wrapper. -/
theorem realizes_toBoundedFormula {n : Nat} (phi : FOFormula n)
(s : Tuple A n) :
realizes E (toBoundedFormula phi) s <->
FOFormula.Satisfies E phi s := by
simpa [translatedRealizes] using realize_toBoundedFormula E phi s
end ArbitraryStructure
/-!
## `DefZF` through Mathlib formulas
-/
end Model
end Constructible
end CUAdapterModule33
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.FiniteSequenceComparison -/
section CUAdapterModule34
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Bounded comparison formulas for finite-sequence codes
The von Neumann codes used for lengths are ordered by membership, so their
strict comparison has a fixed atomic formula. We also package the
lexicographic comparison of an operation token's three numeric components.
The equal-length branch of shortlex for `FiniteSequenceZF.sequenceCode` is
handled by the indexed-sequence validity and lookup infrastructure developed
in the companion modules. The formulas below provide the reusable numeric
and lexicographic components used by those constructions.
-/
universe u
namespace Constructible
namespace FiniteSequenceZF
/-! ## Natural-number codes -/
end FiniteSequenceZF
namespace Godel.RudimentaryTerm
/-! ## Numeric operation-token payloads -/
end Godel.RudimentaryTerm
end Constructible
end CUAdapterModule34
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.IndexedSequenceValidity -/
section CUAdapterModule35
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Validity and decoding of indexed finite-sequence codes
The indexed representation is useful only if object-language predicates cannot
accept spurious infinite or non-functional graphs as finite programs. This
file supplies a fixed first-order validity predicate and proves two
representation theorems:
* every genuine `sequenceCode xs` is valid;
* every valid code represents one actual finite Lean list.
The representing graph is allowed to contain irrelevant extra elements. At
each index below the recorded length, however, it must contain exactly one
value. Every predicate consuming this representation inspects only those
indexed values, so this is the precise invariant required for sound decoding.
-/
universe u
namespace Constructible.IndexedSequenceZF
open FiniteSequenceZF
/-! ## Natural members of omega and finite ordinals -/
/-! ## The fixed first-order predicate -/
/-
Assignment layout in the innermost context:
`[omega, sequence, length, graph, index, value, other]`.
-/
/-! ## External representation and decoding -/
end Constructible.IndexedSequenceZF
end CUAdapterModule35
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackTrace -/
section CUAdapterModule36
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Finite execution traces for rudimentary stack programs
The object-language evaluator quantifies over a set-coded finite trace. This
file isolates the corresponding external machine theorem: successful
evaluation is equivalent to a finite chain of local `runStackToken` steps.
It also records constructibility of every state and of the indexed trace code.
-/
universe u v
namespace Constructible.Godel.RudimentaryTerm
/-! ## Recursive traces and their endpoint semantics -/
/-! ## Indexed characterization -/
/-! ## Constructibility of successful traces -/
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule36
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackTraceDecode -/
section CUAdapterModule37
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Decoding raw formula-certified stack traces
Starting from a genuine input stack code, the one-step decoding theorem can
be iterated along raw token and state-code lists. This reconstructs an actual
typed stack program and an `ExecutionTrace`. Conversely, encoding any real
execution trace makes every adjacent triple satisfy `stackStepFormula`.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
open FiniteSequenceZF
noncomputable section
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule37
/- Original module: ConstructibleUniverse.ModelTheory.SetTheory.ZF -/
section CUAdapterModule38
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The First-Order Theory ZF
This file defines the Zermelo--Fraenkel axioms in the first-order language of set theory.
The Separation and Replacement schemes range over all formulas in that language, with finitely
many free variables.
## Main definitions
- `FirstOrder.SetTheory.ZFAxiom` indexes the finite axioms and the two axiom schemes.
- `FirstOrder.SetTheory.ZFAxiom.toSentence` is the sentence associated with a ZF axiom.
- `FirstOrder.SetTheory.ZFAxiom.toProp` gives the usual semantics of each axiom.
- `FirstOrder.Language.Theory.ZF` is the first-order theory of ZF.
-/
universe u
namespace FirstOrder.SetTheory
open Language Language.BoundedFormula Language.Structure
open scoped FirstOrder
/-- Universally close a formula whose free variables are indexed by `Fin n`. -/
def universalClosure {n : ℕ} (φ : Language.setTheory.Formula (Fin n)) :
Language.setTheory.Sentence :=
(BoundedFormula.relabel (β := Empty) Sum.inr φ).alls
/-! The following relabellings make the de Bruijn variable order in the two schemes explicit. -/
/-- Relabel `φ(params, x)` inside the Separation body, preserving the parameters. -/
def separationRelabel {n : ℕ} : Fin (n + 1) → Fin (n + 1) ⊕ Fin 2 :=
Fin.lastCases (.inr (Fin.last 1)) fun i => .inl i.castSucc
theorem comp_separationRelabel {M : Type*} {n : ℕ}
(params : Fin n → M) (a b x : M) :
(Sum.elim (Fin.snoc params a) (Fin.snoc (Fin.snoc default b) x) ∘
separationRelabel) =
Fin.snoc params x := by
funext i
refine Fin.lastCases ?_ (fun j => ?_) i
· simp only [Function.comp_apply, separationRelabel, Fin.lastCases_last, Sum.elim_inr,
Fin.snoc_last]
· simp only [Function.comp_apply, separationRelabel, Fin.lastCases_castSucc, Sum.elim_inl,
Fin.snoc_castSucc]
/-- The Separation body associated with `φ(params, x)`. -/
def separationBody {n : ℕ} (φ : Language.setTheory.Formula (Fin (n + 1))) :
Language.setTheory.Formula (Fin (n + 1)) :=
∃' ∀'
((&1).mem &0 ⇔
((&1).mem (Term.var (.inl (Fin.last n))) ⊓
BoundedFormula.relabel
separationRelabel φ))
/-- Relabel `φ(params, x, y)` after introducing the prospective value `y`. -/
def replacementWitnessRelabel {n : ℕ} : Fin (n + 2) → Fin (n + 1) ⊕ Fin 2 :=
Fin.lastCases (.inr (Fin.last 1)) fun j =>
Fin.lastCases (.inr (Fin.last 0).castSucc) (fun i => .inl i.castSucc) j
theorem comp_replacementWitnessRelabel {M : Type*} {n : ℕ}
(params : Fin n → M) (a x y : M) :
(Sum.elim (Fin.snoc params a) (Fin.snoc (Fin.snoc default x) y) ∘
replacementWitnessRelabel) =
Fin.snoc (Fin.snoc params x) y := by
funext i
refine Fin.lastCases ?_ (fun j => ?_) i
· simp only [Function.comp_apply, replacementWitnessRelabel, Fin.lastCases_last, Sum.elim_inr,
Fin.snoc_last]
· refine Fin.lastCases ?_ (fun k => ?_) j
· simp only [Function.comp_apply, replacementWitnessRelabel, Fin.lastCases_castSucc,
Fin.lastCases_last, Sum.elim_inr, Fin.snoc_castSucc, Fin.snoc_last]
· simp only [Function.comp_apply, replacementWitnessRelabel, Fin.lastCases_castSucc,
Sum.elim_inl, Fin.snoc_castSucc]
/-- Relabel `φ(params, x, z)` when asserting uniqueness of a prospective value. -/
def replacementUniquenessRelabel {n : ℕ} : Fin (n + 2) → Fin (n + 1) ⊕ Fin 3 :=
Fin.lastCases (.inr (Fin.last 2)) fun j =>
Fin.lastCases (.inr (Fin.last 0).castSucc.castSucc) (fun i => .inl i.castSucc) j
theorem comp_replacementUniquenessRelabel {M : Type*} {n : ℕ}
(params : Fin n → M) (a x y z : M) :
(Sum.elim (Fin.snoc params a) (Fin.snoc (Fin.snoc (Fin.snoc default x) y) z) ∘
replacementUniquenessRelabel) =
Fin.snoc (Fin.snoc params x) z := by
funext i
refine Fin.lastCases ?_ (fun j => ?_) i
· simp only [Function.comp_apply, replacementUniquenessRelabel, Fin.lastCases_last,
Sum.elim_inr, Fin.snoc_last]
· refine Fin.lastCases ?_ (fun k => ?_) j
· simp only [Function.comp_apply, replacementUniquenessRelabel, Fin.lastCases_castSucc,
Fin.lastCases_last, Sum.elim_inr, Fin.snoc_castSucc, Fin.snoc_last]
· simp only [Function.comp_apply, replacementUniquenessRelabel, Fin.lastCases_castSucc,
Sum.elim_inl, Fin.snoc_castSucc]
/-- Relabel `φ(params, x, y)` inside the exact-image conclusion of Replacement. -/
def replacementRangeRelabel {n : ℕ} : Fin (n + 2) → Fin (n + 1) ⊕ Fin 3 :=
Fin.lastCases (.inr (Fin.last 1).castSucc) fun j =>
Fin.lastCases (.inr (Fin.last 2)) (fun i => .inl i.castSucc) j
theorem comp_replacementRangeRelabel {M : Type*} {n : ℕ}
(params : Fin n → M) (a b y x : M) :
(Sum.elim (Fin.snoc params a) (Fin.snoc (Fin.snoc (Fin.snoc default b) y) x) ∘
replacementRangeRelabel) =
Fin.snoc (Fin.snoc params x) y := by
funext i
refine Fin.lastCases ?_ (fun j => ?_) i
· simp only [Function.comp_apply, replacementRangeRelabel, Fin.lastCases_last, Sum.elim_inr,
Fin.snoc_castSucc, Fin.snoc_last]
· refine Fin.lastCases ?_ (fun k => ?_) j
· simp only [Function.comp_apply, replacementRangeRelabel, Fin.lastCases_castSucc,
Fin.lastCases_last, Sum.elim_inr, Fin.snoc_last, Fin.snoc_castSucc]
· simp only [Function.comp_apply, replacementRangeRelabel, Fin.lastCases_castSucc,
Sum.elim_inl, Fin.snoc_castSucc]
/-- Under `(params, a, x)`, assert that `φ(params, x, -)` has exactly one value. -/
def replacementUnique {n : ℕ} (φ : Language.setTheory.Formula (Fin (n + 2))) :
Language.setTheory.BoundedFormula (Fin (n + 1)) 1 :=
∃'
(BoundedFormula.relabel
replacementWitnessRelabel φ ⊓
∀' (BoundedFormula.relabel
replacementUniquenessRelabel φ ⟹
(&2 =' &1)))
/-- The functional Replacement body associated with `φ(params, x, y)`. -/
def replacementBody {n : ℕ} (φ : Language.setTheory.Formula (Fin (n + 2))) :
Language.setTheory.Formula (Fin (n + 1)) :=
(∀' ((&0).mem (Term.var (.inl (Fin.last n))) ⟹ replacementUnique φ)) ⟹
∃' ∀'
((&1).mem &0 ⇔
∃' ((&2).mem (Term.var (.inl (Fin.last n))) ⊓
BoundedFormula.relabel
replacementRangeRelabel φ))
/-- Universal closure has the expected semantics. -/
@[simp]
theorem realize_universalClosure {M : Type u} [Language.setTheory.Structure M] {n : ℕ}
(φ : Language.setTheory.Formula (Fin n)) :
M ⊨ universalClosure φ ↔ ∀ v : Fin n → M, φ.Realize v := by
simp only [Sentence.Realize, universalClosure, BoundedFormula.realize_alls]
exact forall_congr' fun _ => Formula.realize_relabel_sumInr φ
/-- The Separation body has the usual semantics under an assignment of its parameters and set. -/
@[simp]
theorem realize_separationBody {M : Type u} [Language.setTheory.Structure M] {n : ℕ}
(φ : Language.setTheory.Formula (Fin (n + 1))) (params : Fin n → M) (a : M) :
(separationBody φ).Realize (Fin.snoc params a) ↔
∃ b : M, ∀ x : M,
RelMap memRel ![x, b] ↔ RelMap memRel ![x, a] ∧ φ.Realize (Fin.snoc params x) := by
have hzero (f : Fin 0 → M) : f = default := Subsingleton.elim _ _
simp [separationBody, Formula.Realize, Term.mem, Fin.snoc, hzero,
comp_separationRelabel]
/-- `replacementUnique` states that the scheme formula has exactly one value at `x`. -/
@[simp]
theorem realize_replacementUnique {M : Type u} [Language.setTheory.Structure M] {n : ℕ}
(φ : Language.setTheory.Formula (Fin (n + 2))) (params : Fin n → M) (a x : M) :
(replacementUnique φ).Realize (Fin.snoc params a) (Fin.snoc default x) ↔
∃! y : M, φ.Realize (Fin.snoc (Fin.snoc params x) y) := by
have hzero (f : Fin 0 → M) : f = default := Subsingleton.elim _ _
simp [replacementUnique, Formula.Realize, ExistsUnique, Fin.snoc, hzero,
comp_replacementWitnessRelabel, comp_replacementUniquenessRelabel]
/-- Functional Replacement has the usual exact-image semantics. -/
@[simp]
theorem realize_replacementBody {M : Type u} [Language.setTheory.Structure M] {n : ℕ}
(φ : Language.setTheory.Formula (Fin (n + 2))) (params : Fin n → M) (a : M) :
(replacementBody φ).Realize (Fin.snoc params a) ↔
((∀ x : M, RelMap memRel ![x, a] →
∃! y : M, φ.Realize (Fin.snoc (Fin.snoc params x) y)) →
∃ b : M, ∀ y : M, RelMap memRel ![y, b] ↔
∃ x : M, RelMap memRel ![x, a] ∧ φ.Realize (Fin.snoc (Fin.snoc params x) y)) := by
have hzero (f : Fin 0 → M) : f = default := Subsingleton.elim _ _
simp [replacementBody, Formula.Realize, Term.mem, Fin.snoc, hzero,
comp_replacementRangeRelabel]
/--
An index for each finite ZF axiom and each instance of Separation and Replacement.
In a Separation formula, the first `n` variables are parameters and the last variable is the
element being separated. In a Replacement formula, the final two variables are respectively the
argument and value of the relation.
-/
inductive ZFAxiom : Type
| extensionality
| emptySet
| pairing
| union
| powerSet
| infinity
| foundation
| separation (n : ℕ) (φ : Language.setTheory.Formula (Fin (n + 1)))
| replacement (n : ℕ) (φ : Language.setTheory.Formula (Fin (n + 2)))
/-- The first-order sentence corresponding to a ZF axiom. -/
@[simp]
def ZFAxiom.toSentence : ZFAxiom → Language.setTheory.Sentence
| .extensionality =>
∀' ∀' ((∀' ((&2).mem &0 ⇔ (&2).mem &1)) ⟹ (&0 =' &1))
| .emptySet =>
∃' ∀' ∼((&1).mem &0)
| .pairing =>
∀' ∀' ∃' ∀' ((&3).mem &2 ⇔ ((&3 =' &0) ⊔ (&3 =' &1)))
| .union =>
∀' ∃' ∀' ((&2).mem &1 ⇔ ∃' ((&3).mem &0 ⊓ (&2).mem &3))
| .powerSet =>
∀' ∃' ∀' ((&2).mem &1 ⇔ ∀' ((&3).mem &2 ⟹ (&3).mem &0))
| .infinity =>
∃' ((∃' ((&1).mem &0 ⊓ ∀' ∼((&2).mem &1))) ⊓
∀' ((&1).mem &0 ⟹
∃' ((&2).mem &0 ⊓
∀' ((&3).mem &2 ⇔ ((&3).mem &1 ⊔ (&3 =' &1))))))
| .foundation =>
∀' ((∃' (&1).mem &0) ⟹
∃' ((&1).mem &0 ⊓ ∀' ((&2).mem &0 ⟹ ∼((&2).mem &1))))
| .separation _ φ => universalClosure (separationBody φ)
| .replacement _ φ => universalClosure (replacementBody φ)
/-- The usual set-theoretic proposition corresponding to a ZF axiom. -/
@[simp]
def ZFAxiom.toProp (M : Type u) [Language.setTheory.Structure M] : ZFAxiom → Prop
| .extensionality =>
∀ x y : M, (∀ z : M, RelMap memRel ![z, x] ↔ RelMap memRel ![z, y]) → x = y
| .emptySet =>
∃ e : M, ∀ x : M, ¬RelMap memRel ![x, e]
| .pairing =>
∀ x y : M, ∃ p : M, ∀ z : M, RelMap memRel ![z, p] ↔ z = x ∨ z = y
| .union =>
∀ x : M, ∃ u : M, ∀ z : M,
RelMap memRel ![z, u] ↔ ∃ y : M, RelMap memRel ![y, x] ∧ RelMap memRel ![z, y]
| .powerSet =>
∀ x : M, ∃ p : M, ∀ y : M,
RelMap memRel ![y, p] ↔ ∀ z : M, RelMap memRel ![z, y] → RelMap memRel ![z, x]
| .infinity =>
∃ w : M,
(∃ e : M, RelMap memRel ![e, w] ∧ ∀ z : M, ¬RelMap memRel ![z, e]) ∧
∀ x : M, RelMap memRel ![x, w] → ∃ y : M, RelMap memRel ![y, w] ∧
∀ z : M, RelMap memRel ![z, y] ↔ RelMap memRel ![z, x] ∨ z = x
| .foundation =>
∀ x : M, (∃ y : M, RelMap memRel ![y, x]) →
∃ y : M, RelMap memRel ![y, x] ∧
∀ z : M, RelMap memRel ![z, x] → ¬RelMap memRel ![z, y]
| .separation n φ =>
∀ (params : Fin n → M) (a : M), ∃ b : M, ∀ x : M,
RelMap memRel ![x, b] ↔ RelMap memRel ![x, a] ∧ φ.Realize (Fin.snoc params x)
| .replacement n φ =>
∀ (params : Fin n → M) (a : M),
(∀ x : M, RelMap memRel ![x, a] →
∃! y : M, φ.Realize (Fin.snoc (Fin.snoc params x) y)) →
∃ b : M, ∀ y : M, RelMap memRel ![y, b] ↔
∃ x : M, RelMap memRel ![x, a] ∧ φ.Realize (Fin.snoc (Fin.snoc params x) y)
/-- A ZF axiom is realized exactly when its usual set-theoretic proposition holds. -/
theorem ZFAxiom.realize_toSentence_iff_toProp {M : Type u} [Language.setTheory.Structure M]
(ax : ZFAxiom) : M ⊨ ax.toSentence ↔ ax.toProp M := by
cases ax with
| extensionality =>
simp [ZFAxiom.toSentence, ZFAxiom.toProp, Sentence.Realize, Formula.Realize,
Term.mem, Fin.snoc]
| emptySet =>
simp [ZFAxiom.toSentence, ZFAxiom.toProp, Sentence.Realize, Formula.Realize,
Term.mem, Fin.snoc]
| pairing =>
simp [ZFAxiom.toSentence, ZFAxiom.toProp, Sentence.Realize, Formula.Realize,
Term.mem, Fin.snoc]
| union =>
simp [ZFAxiom.toSentence, ZFAxiom.toProp, Sentence.Realize, Formula.Realize,
Term.mem, Fin.snoc]
| powerSet =>
simp [ZFAxiom.toSentence, ZFAxiom.toProp, Sentence.Realize, Formula.Realize,
Term.mem, Fin.snoc]
| infinity =>
simp [ZFAxiom.toSentence, ZFAxiom.toProp, Sentence.Realize, Formula.Realize,
Term.mem, Fin.snoc]
| foundation =>
simp [ZFAxiom.toSentence, ZFAxiom.toProp, Sentence.Realize, Formula.Realize,
Term.mem, Fin.snoc]
| separation n φ =>
rw [ZFAxiom.toSentence, ZFAxiom.toProp, realize_universalClosure]
constructor
· intro h params a
exact (realize_separationBody φ params a).1 (h (Fin.snoc params a))
· intro h v
have hv := (realize_separationBody φ (Fin.init v) (v (Fin.last n))).2
(h (Fin.init v) (v (Fin.last n)))
simpa only [Fin.snoc_init_self] using hv
| replacement n φ =>
rw [ZFAxiom.toSentence, ZFAxiom.toProp, realize_universalClosure]
constructor
· intro h params a
exact (realize_replacementBody φ params a).1 (h (Fin.snoc params a))
· intro h v
have hv := (realize_replacementBody φ (Fin.init v) (v (Fin.last n))).2
(h (Fin.init v) (v (Fin.last n)))
simpa only [Fin.snoc_init_self] using hv
/-- Zermelo--Fraenkel set theory with full Separation and functional Replacement. -/
def _root_.FirstOrder.Language.Theory.ZF : Language.setTheory.Theory :=
Set.range ZFAxiom.toSentence
/-- Every indexed ZF axiom holds in a model of `Language.Theory.ZF`. -/
theorem ZFAxiom.toProp_of_model {M : Type u} [Language.setTheory.Structure M]
[Language.Theory.ZF.Model M] (ax : ZFAxiom) : ax.toProp M :=
(ZFAxiom.realize_toSentence_iff_toProp ax).1
(Language.Theory.ZF.realize_sentence_of_mem ⟨ax, rfl⟩)
end FirstOrder.SetTheory
end CUAdapterModule38
/- Original module: ConstructibleUniverse.ModelTheory.SetTheory.ZFC -/
section CUAdapterModule39
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The First-Order Theory ZFC
This file extends the first-order theory `Language.Theory.ZF` by the Axiom of Choice. We use the
standard disjoint-family formulation: every pairwise disjoint family of nonempty sets has a set
meeting each member of the family in exactly one element.
## Main definitions
- `FirstOrder.SetTheory.choiceSentence` is the Axiom of Choice in the language of set theory.
- `FirstOrder.SetTheory.ModelsChoice` is its usual disjoint-family semantics.
- `FirstOrder.Language.Theory.ZFC` is ZF together with `choiceSentence`.
- `FirstOrder.Language.Theory.model_ZFC_iff` characterizes models of ZFC.
-/
universe u
namespace FirstOrder.SetTheory
open Language Language.BoundedFormula Language.Structure
open scoped FirstOrder
end FirstOrder.SetTheory
end CUAdapterModule39
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.BasicAxioms -/
section CUAdapterModule40
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The elementary set axioms in the constructible universe
This file records the axioms which follow immediately from transitivity and
the basic closure properties of `L`. They are stated on `Model.LCarrier`, so
they connect directly to the sentences in the membership language.
-/
open Set
universe u
namespace Constructible.Model
end Constructible.Model
end CUAdapterModule40
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Infinity -/
section CUAdapterModule41
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Infinity in the constructible universe
The standard von Neumann code `omega0.toZFSet` is constructible. Its ordinal
membership characterization immediately gives the empty element and closure
under von Neumann successor.
-/
universe u
namespace Constructible.Model
/-- The standard von Neumann omega, packaged as a constructible set. -/
noncomputable def omegaLCarrier : LCarrier.{u} :=
⟨Ordinal.omega0.toZFSet, omega_mem_L⟩
theorem empty_mem_omegaLCarrier :
emptyLCarrier.1 ∈ omegaLCarrier.1 := by
simp only [emptyLCarrier, omegaLCarrier]
rw [← Ordinal.toZFSet_zero]
exact Ordinal.toZFSet_mem_toZFSet_iff.mpr Ordinal.omega0_pos
/-- Every member of omega has its von Neumann successor in omega. -/
theorem successor_mem_omegaLCarrier (x : LCarrier.{u})
(hx : x.1 ∈ omegaLCarrier.1) :
∃ s : LCarrier.{u}, s.1 ∈ omegaLCarrier.1 ∧
∀ z : LCarrier.{u}, z.1 ∈ s.1 ↔ z.1 ∈ x.1 ∨ z = x := by
change x.1 ∈ Ordinal.omega0.toZFSet at hx
rcases Ordinal.mem_toZFSet_iff.mp hx with ⟨beta, hbeta, hxbeta⟩
let s : LCarrier.{u} :=
⟨(Order.succ beta).toZFSet, ordinal_toZFSet_mem_L (Order.succ beta)⟩
refine ⟨s, ?_, ?_⟩
· exact Ordinal.toZFSet_mem_toZFSet_iff.mpr
(Ordinal.isSuccLimit_omega0.succ_lt hbeta)
· intro z
change z.1 ∈ (Order.succ beta).toZFSet ↔
z.1 ∈ x.1 ∨ z = x
rw [Order.succ_eq_add_one, Ordinal.toZFSet_add_one,
ZFSet.mem_insert_iff, hxbeta]
simp only [Subtype.ext_iff, or_comm]
end Constructible.Model
end CUAdapterModule41
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.PowerSet -/
section CUAdapterModule42
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The internal powerset axiom for the constructible universe
The ambient powerset of a constructible set need not itself be constructible.
The powerset computed by `L` contains exactly those ambient subsets which are
constructible. We first bound all such subsets in one level and then define
the required collection over that level.
This is the standard inner-model proof using the ambient set
`P(a) intersect L`. Here that ambient set is constructed by Mathlib's
predicate-valued `ZFSet.sep`. The resulting membership theorem is exact, but
this operation should not be confused with an already formalized invocation
of an object-language formula defining `L` in an arbitrary ZFC model.
-/
open Set
universe u
namespace Constructible
section ZFC
/--
Over a transitive carrier, the collection of its members which are subsets of
the parameter `a` is first-order definable over that carrier.
-/
theorem subsetSeparation_mem_DefZF {U a : ZFSet.{u}}
(hU : U.IsTransitive) (ha : a ∈ U) :
ZFSet.sep (fun x => x ⊆ a) U ∈ DefZF U := by
rw [mem_DefZF_iff_exists_satisfies]
let sa : ZFCarrier U := ⟨a, ha⟩
let params : Tuple (ZFCarrier U) 1 := ![sa]
let phi : FOFormula 2 :=
.neg (.ex (.conj
(.mem (2 : Fin 3) (1 : Fin 3))
(.neg (.mem (2 : Fin 3) (0 : Fin 3)))))
refine ⟨ZFSet.sep_subset, 1, params, phi, ?_⟩
intro x
simp only [ZFSet.mem_sep, phi, FOFormula.Satisfies]
change (x.1 ∈ U ∧ x.1 ⊆ a) ↔
¬ ∃ z : ZFCarrier U, z.1 ∈ x.1 ∧ z.1 ∉ a
rw [and_iff_right x.2]
constructor
· intro hxa ⟨z, hzx, hza⟩
exact hza (hxa hzx)
· intro hno z hzx
by_contra hza
exact hno ⟨⟨z, hU.mem_trans hzx x.2⟩, hzx, hza⟩
/--
The powerset axiom in its precise inner-model form. The witness contains
exactly the constructible subsets of `a`.
-/
theorem exists_internalPowerset {a : ZFSet.{u}} (ha : a ∈ L) :
∃ b : ZFSet.{u}, b ∈ L ∧
∀ x : ZFSet.{u}, x ∈ b ↔ x ∈ L ∧ x ⊆ a := by
have hconstructible :
∀ x ∈ constructibleSubsetsZF a, x ∈ L := by
intro x hx
exact (mem_constructibleSubsetsZF_iff.mp hx).1
rcases exists_LStage_for_members hconstructible with ⟨alpha, halpha⟩
let b : ZFSet.{u} :=
ZFSet.sep (fun x => x ⊆ a) (LStageZF alpha)
have haSubsets : a ∈ constructibleSubsetsZF a :=
mem_constructibleSubsetsZF_iff.mpr ⟨ha, Set.Subset.rfl⟩
have haStage : a ∈ LStageZF alpha := halpha a haSubsets
have hbDef : b ∈ DefZF (LStageZF alpha) := by
simpa only [b] using
subsetSeparation_mem_DefZF (LStageZF_isTransitive alpha) haStage
have hbL : b ∈ L := by
refine ⟨Order.succ alpha, ?_⟩
rw [LStageZF_succ]
exact hbDef
refine ⟨b, hbL, ?_⟩
intro x
constructor
· intro hxb
have hxStage : x ∈ LStageZF alpha := (ZFSet.mem_sep.mp hxb).1
exact ⟨LStageZF_subset_constructibleUniverse alpha hxStage,
(ZFSet.mem_sep.mp hxb).2⟩
· rintro ⟨hxL, hxa⟩
have hxSubsets : x ∈ constructibleSubsetsZF a :=
mem_constructibleSubsetsZF_iff.mpr ⟨hxL, hxa⟩
exact ZFSet.mem_sep.mpr ⟨halpha x hxSubsets, hxa⟩
/-- The powerset witness, packaged as an element of `Model.LCarrier`. -/
theorem Model.exists_powerSetLCarrier (a : Model.LCarrier.{u}) :
∃ b : Model.LCarrier.{u},
∀ x : Model.LCarrier.{u}, x.1 ∈ b.1 ↔ x.1 ⊆ a.1 := by
rcases exists_internalPowerset a.2 with ⟨b, hbL, hb⟩
refine ⟨⟨b, hbL⟩, ?_⟩
intro x
simpa only [x.2, true_and] using hb x.1
end ZFC
end Constructible
end CUAdapterModule42
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Reflection -/
section CUAdapterModule43
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Formula reflection for the constructible hierarchy
For a fixed first-order formula and a starting level, this file constructs an
omega-chain of levels. At every successor step, witnesses for all existential
subformulas with parameters in the current level are added. The union level
is then closed under the relevant witnesses, so the Tarski--Vaught induction
shows that the formula has the same truth value there as in the full class
`L`.
The witness selector below lives in Lean's ambient classical metatheory. It
is used only to obtain ordinal bounds in this semantic proof and is not an
internally represented choice function of `L`. Consequently this file
implements the standard reflection argument for the concrete `ZFSet`
universe; it is not by itself a syntactic reflection proof over an arbitrary
model of ZF.
-/
open Set
universe u
namespace Constructible
section ZFC
open Model
end ZFC
end Constructible
end CUAdapterModule43
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Separation -/
section CUAdapterModule44
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Full Separation in the constructible universe
For a formula with constructible parameters and a constructible set `a`, a
reflecting level turns truth in the proper class `L` into ordinary
first-order truth over one internal stage. The corresponding definable
subset of that stage lies in its `DefZF`; intersecting it with `a` gives the
required Separation set.
-/
open Set
universe u
namespace Constructible
section ZFC
end ZFC
end Constructible
end CUAdapterModule44
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Collection -/
section CUAdapterModule45
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Collection in the constructible universe
Ambient choice selects one constructible witness for each member of the
given internal set. Since that index type is small, the occurrence levels of
all selected witnesses have a supremum. The corresponding constructible
stage is itself an element of `L` and collects every selected witness.
The selected family is a function in Lean's classical metatheory, not a
function graph assumed to belong to `L`. Thus there is no circular use of
the target Axiom of Choice. A proof parameterized over arbitrary ZF models
would instead have to internalize the corresponding rank-bounding or
Collection argument.
-/
universe u
namespace Constructible
section ZFC
end ZFC
end Constructible
end CUAdapterModule45
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Replacement -/
section CUAdapterModule46
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Replacement in the constructible universe
Collection first gives a constructible set containing a value for every
input. Full Separation then cuts out the exact range. The formula
`replacementRangeFormula phi` expresses that its last variable is related by
`phi` to some member of the set parameter immediately preceding it.
-/
universe u
namespace Constructible
section ZFC
namespace Model
end Model
end ZFC
end Constructible
end CUAdapterModule46
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.ZFModel -/
section CUAdapterModule47
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The constructible universe is a model of ZF
This file packages the closure, reflection, bounding, and ordinal results for
the constructible universe into Mathlib's canonical first-order theory of ZF.
The Separation and Replacement schemes range over every formula in
`FirstOrder.Language.setTheory`.
-/
universe u
namespace Constructible.Model
end Constructible.Model
end CUAdapterModule47
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.Choice -/
section CUAdapterModule48
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The Axiom of Choice for the constructible universe
The canonical model-theoretic ZFC API supplies the disjoint-family formulation
of Choice. This file proves that a definable relation giving unique minima to
all nonempty constructible sets produces the required choice sets in `L`.
-/
universe u
namespace Constructible
namespace Model
end Model
namespace ChoiceSyntax
/-! ## Selecting minima -/
end ChoiceSyntax
namespace Model
end Model
end Constructible
end CUAdapterModule48
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.InternalWellOrder -/
section CUAdapterModule49
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internal well-orders and Choice in the constructible universe
An external Lean relation is not enough to prove Choice inside `L`: its graph
must itself be represented by a constructible set. This file isolates that
requirement. A constructible set `r` represents the relation
`x <_r y` when the Kuratowski pair `⟨x,y⟩` belongs to `r`.
We prove that if every constructible set is well-orderable by such a
constructible graph, then `L` satisfies the disjoint-family form of Choice and
hence Mathlib's canonical first-order theory ZFC. The proposition
`ModelsInternalWellOrdering` is the interface used to derive these results.
-/
open Set
universe u
namespace Constructible
namespace Delta0Formula
/-! ## Bounded absoluteness for the proper class `L` -/
end Delta0Formula
namespace Model
/-! ## Relations represented by constructible graphs -/
/-! ## The object-language graph predicate -/
/-! ## Unique minima from an internal well-order -/
/-- Every nonempty subset of an internally well-ordered set has a unique minimum. -/
theorem exists_unique_graph_minimum {a r x : LCarrier.{u}}
(hwo : InternallyWellOrders r a)
(hxsub : forall z : LCarrier.{u}, z.1 ∈ x.1 -> z.1 ∈ a.1)
(hxne : exists z : LCarrier.{u}, z.1 ∈ x.1) :
exists y : LCarrier.{u},
(y.1 ∈ x.1 /\
forall z : LCarrier.{u}, z.1 ∈ x.1 -> Not (GraphRel r z y)) /\
forall y' : LCarrier.{u},
(y'.1 ∈ x.1 /\
forall z : LCarrier.{u}, z.1 ∈ x.1 ->
Not (GraphRel r z y')) ->
y' = y := by
let candidates : Set (InternalCarrier a) :=
{z | z.1.1 ∈ x.1}
have hcandidates : candidates.Nonempty := by
rcases hxne with ⟨z, hzx⟩
exact ⟨⟨z, hxsub z hzx⟩, hzx⟩
letI : IsWellOrder (InternalCarrier a) (graphRelOn r a) := hwo
let minimum : InternalCarrier a :=
(IsWellFounded.wf : WellFounded (graphRelOn r a)).min
candidates hcandidates
have hminimumMem : minimum ∈ candidates :=
(IsWellFounded.wf : WellFounded (graphRelOn r a)).min_mem
candidates hcandidates
have hminimum : forall z : LCarrier.{u}, z.1 ∈ x.1 ->
Not (GraphRel r z minimum.1) := by
intro z hzx hzlt
let za : InternalCarrier a := ⟨z, hxsub z hzx⟩
exact
(IsWellFounded.wf : WellFounded (graphRelOn r a)).not_lt_min
candidates (show za ∈ candidates from hzx) hzlt
refine ⟨minimum.1, ⟨hminimumMem, hminimum⟩, ?_⟩
· intro y' hy'
let y'a : InternalCarrier a := ⟨y', hxsub y' hy'.1⟩
rcases trichotomous_of (graphRelOn r a) y'a minimum with
hy'lt | heq | hminlt
· exact False.elim (hminimum y' hy'.1 hy'lt)
· exact congrArg (fun z : InternalCarrier a => z.1) heq
· exact False.elim (hy'.2 minimum.1 hminimumMem hminlt)
/-! ## Choice and ZFC -/
end Model
end Constructible
end CUAdapterModule49
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.FiniteOrdinalSuccessorFormula -/
section CUAdapterModule50
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A bounded formula for von Neumann successor
This file defines an arity-polymorphic bounded formula saying that one
coordinate is the von Neumann successor of another. The formula is used for
the transition from index `k` to index `k + 1` in internally coded execution
traces.
-/
open Set
universe u
namespace Constructible
namespace Delta0Formula
end Delta0Formula
namespace FiniteSequenceZF
end FiniteSequenceZF
end Constructible
end CUAdapterModule50
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.IndexedSequenceOrderFormula -/
section CUAdapterModule51
/-
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 comparison of indexed finite-sequence codes
This file gives fixed object-language formulas for reading the indexed graph
stored by `IndexedSequenceZF.sequenceCode`, comparing prefixes, and building
shortlex comparisons. It uses the indexed representation throughout.
-/
universe u
namespace Constructible.IndexedSequenceZF
open FiniteSequenceZF
/-! ## Indexed access -/
/-! ## Equal prefixes -/
/-! ## Shortlex -/
/-
For `tokenLt : FOFormula (parameterCount + 2)`, the two last coordinates are
the compared values. The resulting shortlex formula has layout
`[token parameters..., omega, leftSequence, rightSequence]`.
-/
end Constructible.IndexedSequenceZF
end CUAdapterModule51
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.IndexedSequenceLookup -/
section CUAdapterModule52
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Lookup semantics for represented indexed sequences
The access formula checks both that the requested index is below the recorded
length and that the corresponding graph pair is present. Thus irrelevant
extra graph elements allowed by `Represents` cannot create out-of-range
lookups, and lookup is exactly equivalent to retrieving an entry of the
represented Lean list.
-/
universe u
namespace Constructible.IndexedSequenceZF
open FiniteSequenceZF
end Constructible.IndexedSequenceZF
end CUAdapterModule52
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackTraceStepFormula -/
section CUAdapterModule53
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# One indexed transition of a rudimentary stack trace
The outer assignment layout is
`[U, varTag, appTag, empty, op0, ..., op8, program, trace, index]`.
The formula appends witnesses `token`, `input`, `succ`, and `output`. It reads
the token and input state at `index`, verifies that `succ` is the finite
ordinal successor of `index`, reads the output state at `succ`, and applies
`stackStepFormula` to the decoded transition.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
/-! ## Fixed coordinates and renamings -/
/-! ## Formula -/
/-! ## Raw semantics -/
/-! ## Genuine indexed sequence codes -/
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule53
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgramEvalFormula -/
section CUAdapterModule54
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A fixed first-order evaluator for postfix rudimentary programs
Evaluation is certified by an internally quantified finite sequence of stack
states. Both program and trace satisfy the indexed-sequence validity
predicate; their recorded lengths differ by one; the first trace state is the
empty stack; the final state is the singleton result stack; and every program
index satisfies `traceStepFormula`.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open Constructible.IndexedSequenceZF
/-! ## Fixed layout and renamings -/
/-
The free layout is
`[U,varTag,appTag,empty,op0,...,op8,omega,program,result]`.
Thus the three final indices are `13,14,15`. The evaluator then quantifies
`trace, programLength, traceLength, finalStack`, at indices `16,...,19`.
-/
/-! ## Formula -/
/-! ## Assignment computations -/
/-! ## Raw semantic normal form -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule54
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackTraceEndpoints -/
section CUAdapterModule55
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Endpoint semantics of raw formula-certified stack traces
For a genuine typed program, existence of a raw formula chain from the empty
stack code to the singleton output-stack code is exactly successful execution
of that program. Soundness uses raw-chain decoding and injectivity of both
token and stack-state encodings; completeness encodes the canonical execution
trace of a successful run.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
open FiniteSequenceZF
noncomputable section
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule55
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgramEvalSemantics -/
section CUAdapterModule56
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Semantic correctness of the fixed postfix-program evaluator
The evaluator accepts arbitrary indexed-sequence representations, not only
the canonical graph produced by `sequenceCode`. This ensures correctness when
program codes are quantified over by a first-order formula.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open FiniteSequenceZF
open IndexedSequenceZF
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule56
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryTokenOrderFormula -/
section CUAdapterModule57
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A formula for the generator-token order
This file internalizes the variable-token branch of
`RudimentaryTerm.codeTokenRel`, where the distinguished generator `U` comes
first and ordinary generators are compared by membership of their Kuratowski
pair in an internal relation graph `r`.
The free-variable layout of `generatorTokenLtFormula` is
`[U, r, zeroTag, leftCode, rightCode]`.
The formula uses two unrestricted witnesses for the decoded generator
payloads. All structural checks on those witnesses are bounded formulas.
For actual variable tokens, `zeroTag` is instantiated by the empty set, which
is both `varTag` and the third component of the token code.
`RudimentaryStackTokenOrderFormula` combines this branch with operation-token
and mixed-token comparisons to obtain the full token order.
-/
universe u
namespace Constructible.Godel
namespace RudimentaryTerm
noncomputable section
end
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule57
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackTokenOrderFormula -/
section CUAdapterModule58
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A first-order formula for the postfix stack-token order
The free-variable layout of `stackTokenLtFormula` is
`[U, r, varTag, appTag, empty, leftCode, rightCode]`.
Two unrestricted witnesses decode the payloads of the two token codes. The
bounded body is the disjunction of the three possible strict-order branches:
* two variable tokens, ordered by `generatorTokenRel U r`;
* a variable token followed by an operation token;
* two operation tokens, ordered by membership of their finite ordinal codes.
There is deliberately no operation-variable branch. On genuine
`stackTokenZFCode`s, the formula is exactly `stackTokenRel
(generatorTokenRel U r)`.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
/-! ## Formula -/
/-! ## Exact semantics on genuine token codes -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule58
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgramOrderFormula -/
section CUAdapterModule59
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A first-order Shortlex order on postfix stack-program codes
The generic indexed-sequence comparison formula is specialized to the fixed
stack-token formula. The resulting object-language relation has exactly the
external `stackProgramRel` semantics on genuine program codes.
-/
universe u v
namespace Constructible
/-! ## Mapping lemmas for structural list orders -/
namespace Godel.RudimentaryTerm
noncomputable section
open IndexedSequenceZF
/-! ## The specialized formula -/
end
end Godel.RudimentaryTerm
end Constructible
end CUAdapterModule59
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgramOrderAbsolute -/
section CUAdapterModule60
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Absoluteness of the postfix-program order on genuine codes
`stackProgramLtFormula` contains unrestricted witnesses for decoded lengths,
graphs, entries, and token payloads. Consequently it is not a bounded formula
and no blanket absoluteness theorem applies. This file supplies constructible
witnesses for genuine program codes and proves the restricted semantics
directly.
-/
open Set
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open IndexedSequenceZF
open FiniteSequenceZF
/-! ## Component formulas over `LCarrier` -/
local notation "LMem" => Model.lCarrierMem
/-! ## Token comparison over `LCarrier` -/
/-! ## Program comparison over `LCarrier` -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule60
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackStepAbsolute -/
section CUAdapterModule61
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Absoluteness of one rudimentary stack-machine step
The ambient correctness theorem for `stackStepFormula` quantifies over all
`ZFSet`s. This file packages its fixed assignment in `LCarrier` and proves
the corresponding correctness theorem when all stack entries are
constructible. The results are stated using both subtype semantics and the
raw-domain semantics `Model.SatisfiesIn L`.
-/
open Set
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule61
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgramEvalAbsolute -/
section CUAdapterModule62
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Absoluteness of the fixed postfix-program evaluator
The ambient evaluator accepts arbitrary finite indexed codes. For the
constructible universe we need more: every unbounded witness used by an
evaluation certificate must itself belong to `L`. This file proves the
restricted semantics for genuine program codes by projecting restricted
certificates to the ambient universe and, conversely, by encoding the
canonical execution trace of a successful run.
-/
open Set
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open Constructible.IndexedSequenceZF
open Constructible.FiniteSequenceZF
local notation "LMem" => Model.lCarrierMem
/-! ## One-way projection to the ambient universe -/
/-! ## Genuine evaluator assignments -/
/-! ## Constructible canonical traces -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule62
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryParameters -/
section CUAdapterModule63
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Fixed parameters for constructible-stage histories
All local history rules share thirteen fixed constructible parameters. The
remaining four coordinates are `(history, index, stage, relation)`.
-/
universe u
namespace Constructible.Model
noncomputable section
end
end Constructible.Model
end CUAdapterModule63
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryBaseFormula -/
section CUAdapterModule64
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The zero-state clause for constructible-stage histories
In the shared layout `(fixed13, history, index, stage, relation)`, the zero
rule requires all three state coordinates other than the ignored history to
be the empty set.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
end
end Constructible.Model
end CUAdapterModule64
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.DefinableRelationGraph -/
section CUAdapterModule65
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Constructible graphs of definable relations
A binary relation given by one fixed first-order formula is not merely an
external Lean predicate. On a constructible domain, Full Separation produces
an actual Kuratowski-pair graph which belongs to `L`.
The separating set is taken from a sufficiently large constructible stage.
This avoids assuming in advance that the ambient product `d x d` itself is
constructible.
-/
universe u
namespace Constructible
namespace Model
end Model
namespace DefinableRelationGraph
/-!
The input formula has layout `(params, x, y)`. Under the two witnesses in
`graphFormula`, the larger layout is `(params, domain, pair, x, y)`.
-/
end DefinableRelationGraph
namespace Model
/--
Every fixed first-order relation on a constructible domain has a graph which
is itself a constructible set. The first part of the specification records
that every member of the constructed set is one of the intended Kuratowski
pairs; this stronger form is useful when the graph is subsequently treated
as an internal function.
-/
theorem exists_definableRelationGraph_with_support {n : Nat}
(phi : FOFormula (n + 2))
(params : Tuple LCarrier.{u} n) (domain : LCarrier.{u}) :
∃ relation : LCarrier.{u},
(∀ pair : LCarrier.{u}, pair.1 ∈ relation.1 →
∃ x y : LCarrier.{u},
x.1 ∈ domain.1 ∧ y.1 ∈ domain.1 ∧
pair.1 = ZFSet.pair x.1 y.1 ∧
FOFormula.Satisfies
(fun z w : LCarrier.{u} => z.1 ∈ w.1)
phi (snoc (snoc params x) y)) ∧
∀ x y : LCarrier.{u},
GraphRel relation x y ↔
x.1 ∈ domain.1 ∧ y.1 ∈ domain.1 ∧
FOFormula.Satisfies
(fun z w : LCarrier.{u} => z.1 ∈ w.1)
phi (snoc (snoc params x) y) := by
have hpairs : ∀ q ∈ ZFSet.prod domain.1 domain.1, q ∈ L := by
intro q hq
rcases ZFSet.mem_prod.mp hq with ⟨x, hx, y, hy, rfl⟩
exact orderedPair_mem_L
(mem_L_of_mem hx domain.2) (mem_L_of_mem hy domain.2)
rcases exists_LStage_for_members hpairs with ⟨alpha, halpha⟩
let container : LCarrier.{u} :=
⟨LStageZF alpha, LStageZF_mem_L alpha⟩
let extendedParams : Tuple LCarrier.{u} (n + 1) :=
snoc params domain
rcases exists_separationLCarrier
(DefinableRelationGraph.graphFormula phi)
extendedParams container with ⟨relation, hrelation⟩
refine ⟨relation, ?_, ?_⟩
· intro pair hpairRelation
rcases (hrelation pair).mp hpairRelation with
⟨_hpairContainer, hformula⟩
rcases (DefinableRelationGraph.satisfies_graphFormula
phi params domain pair).mp
(by simpa only [extendedParams] using hformula) with
⟨x, y, hx, hy, hpair, hphi⟩
exact ⟨x, y, hx, hy, hpair, hphi⟩
intro x y
let pair : LCarrier.{u} := orderedPairLCarrier x y
rw [GraphRel, ← orderedPairLCarrier_val x y]
rw [hrelation pair]
constructor
· rintro ⟨_hpairContainer, hformula⟩
rcases (DefinableRelationGraph.satisfies_graphFormula
phi params domain pair).mp
(by simpa only [extendedParams] using hformula) with
⟨x', y', hx', hy', hpair, hphi⟩
have hpairRaw :
ZFSet.pair x.1 y.1 = ZFSet.pair x'.1 y'.1 := by
simpa only [pair, orderedPairLCarrier_val] using hpair
have hxyRaw : x.1 = x'.1 ∧ y.1 = y'.1 :=
ZFSet.pair_inj.mp hpairRaw
have hxy : x = x' ∧ y = y' :=
⟨Subtype.ext hxyRaw.1, Subtype.ext hxyRaw.2⟩
rcases hxy with ⟨rfl, rfl⟩
exact ⟨hx', hy', hphi⟩
· rintro ⟨hx, hy, hphi⟩
have hpairProd : pair.1 ∈ ZFSet.prod domain.1 domain.1 := by
change ZFSet.pair x.1 y.1 ∈ ZFSet.prod domain.1 domain.1
rw [ZFSet.pair_mem_prod]
exact ⟨hx, hy⟩
have hpairContainer : pair.1 ∈ container.1 := by
exact halpha pair.1 hpairProd
refine ⟨hpairContainer, ?_⟩
apply (DefinableRelationGraph.satisfies_graphFormula
phi params domain pair).mpr
exact ⟨x, y, hx, hy, rfl, hphi⟩
end Model
end Constructible
end CUAdapterModule65
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryEntry -/
section CUAdapterModule66
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Constructible codes for stage-history entries
A stage history records triples `(index, stage, relation)`. This file gives
the constructible triple code and a four-variable first-order lookup formula
whose semantics is exact in `LCarrier`.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-!
The free-variable layout of `historyEntryFormula` is
`(history, index, stage, relation)`. The existentially bound last variable
is the encoded triple itself.
-/
end
end Constructible.Model
end CUAdapterModule66
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryLimitFormula -/
section CUAdapterModule67
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The limit-state clause for constructible-stage histories
At a limit index, both the stage and its coherent order graph are internal
unions of their earlier values. The formulas here express those two
extensional union clauses using only membership and the verified history-entry
predicate.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-!
All formulas in this file have the outer layout
`(history, index, stage, relation)`.
After binding a candidate member `z`, the union witness layout is
`(history, index, stage, relation, z, earlierIndex, earlierStage,
earlierRelation)`.
-/
end
end Constructible.Model
end CUAdapterModule67
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.CanonicalDefinableRelationGraph -/
section CUAdapterModule68
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Canonical graphs of formula-defined relations
The existential graph construction is sufficient for Separation, but a
transfinite recursion needs a graph uniquely determined by its inputs. This
file separates directly inside the constructible Cartesian square and keeps
the resulting exact membership specification.
-/
universe u
namespace Constructible.Model
noncomputable section
/-! ## An object-language formula specifying the exact output graph -/
end
end Constructible.Model
end CUAdapterModule68
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.InitialSegmentOrder -/
section CUAdapterModule69
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Extending a well-order by a final block
This file contains the order-theoretic device used to keep successive
constructible-stage orders coherent. A carrier is split into an old part
and its complement. The old part is ordered first, the new part second.
Thus the old part is an initial segment by construction.
-/
universe u
namespace Constructible
noncomputable section
end
end Constructible
end CUAdapterModule69
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryLeastProgramFormula -/
section CUAdapterModule70
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The least-successful-program order on rudimentary values
This file combines the fixed postfix-program evaluator with the fixed
Shortlex program order. The free-variable layout is
`[U, varTag, appTag, empty, op0, ..., op8, omega, relation, left, right]`.
The first fifteen coordinates are parameters. The final two coordinates are
the values being compared, so the formula can be passed directly to the
definable-relation graph construction. Internally it says
`exists p, Eval(p, left) and forall q, Eval(q, right) -> ProgramLt(p, q)`.
When the program order is a well-order and both values have successful
programs, this is equivalent to comparing their least successful programs.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open Constructible.IndexedSequenceZF
/-! ## Fixed layout and assignments -/
/-! ## Renamings -/
/-! ## Formula -/
/-! ## Assignment computations -/
/-! ## Ambient raw semantic normal form -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule70
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryStackProgramOrderRepresented -/
section CUAdapterModule71
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Program order on arbitrary valid indexed representations
The first-order order formula compares the finite sequence represented by a
code. It must therefore be insensitive to harmless extra graph entries in a
valid code, rather than being correct only for `sequenceCode` itself.
-/
open Set
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open IndexedSequenceZF
open FiniteSequenceZF
local notation "LMem" => Model.lCarrierMem
/-! ## Constructible witnesses for represented sequences -/
/-! ## Restricted Shortlex on arbitrary representations -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule71
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryLeastProgramSemantics -/
section CUAdapterModule72
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Semantics of the least-successful-program value order
The formula from `RudimentaryLeastProgramFormula` quantifies over arbitrary
set codes. Evaluator satisfaction first decodes such a code to a genuine
postfix program; represented-code invariance of the program-order formula then
compares those decoded programs. This proves that the formula is exactly the
existing `defCarrierStackRel` defined using `leastStackProgram`.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open Constructible.IndexedSequenceZF
/-! ## Assignment compatibility -/
/-! ## Minimality of successful programs -/
/-! ## Exact ambient semantics -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule72
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.MinimalStage -/
section CUAdapterModule73
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Minimal constructible stages
Every constructible set has a least stage at which it occurs. That stage is
never zero or a limit, hence is a successor. Its predecessor is the canonical
stage over which the set receives a `DefZF` (equivalently, Gödel-operation)
representation.
-/
open Set
universe u
namespace Constructible
end Constructible
end CUAdapterModule73
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageOrder -/
section CUAdapterModule74
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# External birth-layer orders for constructible stages
This file decomposes each constructible stage into the disjoint layers of
sets born at earlier ordinals. A well-order on each layer can then be combined
lexicographically and transported back to the stage carrier.
All orders in this file are external Lean relations. No claim is made here
that their graphs are internally represented `ZFSet`s or belong to `L`.
-/
open Set
universe u v
namespace Constructible
/-! ## Birth layers -/
namespace BornAt
end BornAt
/-! ## The local least-term order -/
/-! ## Decomposing a stage by birth ordinal -/
/-! ## Lexicographically combining external layer orders -/
end Constructible
end CUAdapterModule74
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.CanonicalStageOrder -/
section CUAdapterModule75
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Canonical external orders on constructible stages
The order on a birth layer must use the already constructed order on the
preceding stage, rather than an unrelated application of external Choice.
This file performs that well-founded recursion on the birth ordinal.
The resulting relations are still external Lean predicates. Their
Kuratowski-pair graphs must subsequently be shown constructible; no such
internalization claim is made here.
-/
open Set
universe u
namespace Constructible
/-! ## Adding the distinguished stage generator -/
/-! ## Simultaneous stage/layer recursion -/
end Constructible
end CUAdapterModule75
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryGeneratorInternalOrder -/
section CUAdapterModule76
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Generator orders from internally represented well-orders
An internal relation graph on a constructible set `U` orders
`Model.InternalCarrier U`, while rudimentary programs use
`ZFCarrier U.1` as their ordinary generator type. These two carriers are
canonically equivalent. This file transports the represented well-order
across that equivalence, adds the distinguished `none` generator at the
front, and finally lifts the order to postfix stack programs by Shortlex.
-/
universe u
namespace Constructible
namespace Godel
namespace RudimentaryTerm
noncomputable section
end
end RudimentaryTerm
end Godel
end Constructible
end CUAdapterModule76
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentarySuccessfulProgramOrder -/
section CUAdapterModule77
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Ordering definable values by successful stack programs
This module gives a formula-independent presentation of the canonical order
on one Gödel-definability step. A value `x` precedes `y` when some program
evaluating to `x` precedes every program evaluating to `y`. Once the
generator relation is a well-order, this is exactly the existing order by
least successful programs, `defCarrierStackRel`.
-/
universe u
namespace Constructible.Godel
namespace RudimentaryTerm
noncomputable section
end
end RudimentaryTerm
end Constructible.Godel
end CUAdapterModule77
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryLeastProgramAbsolute -/
section CUAdapterModule78
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Absoluteness of the least-successful-program value order
The combined least-program formula has unbounded program-code quantifiers.
This file proves its exact semantics in `Model.LCarrier`. Arbitrary internal
codes are projected to the ambient evaluator and decoded; canonical codes
supply the converse witnesses.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
open Constructible.IndexedSequenceZF
local notation "LMem" => Model.lCarrierMem
/-! ## Constructible assignments -/
/-! ## Constructible values of the definability step -/
/-! ## Exact restricted semantics -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule78
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageInternalOrder -/
section CUAdapterModule79
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# From internally represented stage orders to Choice
Every constructible set is contained in some level `L_alpha`. Consequently,
it is enough to construct, for every level, a well-order whose Kuratowski-pair
graph is itself a member of `L`. This file proves that reduction and states
the exact internalization obligation for the external birth-layer order from
`StageOrder`.
-/
open Set
universe u
namespace Constructible
namespace Model
/-! ## Alternative conditional birth-layer route
This section gives a conditional reduction through an externally specified
birth-layer order. The model theorem in `StageHistoryGraphSystem.lean` is
independent of this interface and constructs coherent internal graphs through
stage histories.
-/
end Model
end Constructible
end CUAdapterModule79
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentarySuccessorInternalOrder -/
section CUAdapterModule80
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internally represented well-orders of successor stages
Assume an actual constructible graph internally well-orders `L_alpha`.
The fixed least-successful-program formula then well-orders
`L_(alpha+1) = Def(L_alpha)`. Full Separation turns that formula-defined
relation into an actual Kuratowski graph belonging to `L`.
-/
universe u
namespace Constructible
namespace Model
noncomputable section
end
end Model
end Constructible
end CUAdapterModule80
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentarySuccessorExtensionOrder -/
section CUAdapterModule81
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Coherent internally represented successor-stage orders
The raw least-program order need not extend the order on the previous stage.
For limit unions we instead put the old stage first, preserving its given
relation, and order only the genuinely new values by least successful
programs. The old stage is therefore an initial segment by construction.
-/
universe u
namespace Constructible
namespace Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-! ## The fixed extension formula -/
/-! ## The corresponding external block order -/
/-! ## Formula semantics and internalization -/
end
end Model
end Constructible
end CUAdapterModule81
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.CanonicalSuccessorOrder -/
section CUAdapterModule82
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The canonical coherent successor-stage order
The successor extension formula determines an exact graph by Separation in
the constructible Cartesian square. Unlike an existential graph witness,
this graph is a genuine function of the preceding stage and relation, which
is the form used by the transfinite recursion.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
end
end Constructible.Model
end CUAdapterModule82
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.RudimentaryDefOutputFormula -/
section CUAdapterModule83
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A first-order output formula for one Gödel definability step
The fixed stack evaluator recognizes the rudimentary closure of `U`. Adding
the bounded requirement that the output be a subset of `U` therefore gives a
single first-order definition of `godelDef U`. This file packages that
definition with an exact `LCarrier` semantics and the unique-output interface
needed by function-form Replacement.
-/
universe u
namespace Constructible.Godel.RudimentaryTerm
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-! ## Successful programs land in the rudimentary closure -/
/-! ## The fixed output formula -/
/-
The outer free-variable layout is
`[U,varTag,appTag,empty,op0,...,op8,omega,nextU]`.
After universally binding `result` and existentially binding `program`, the
evaluator expects `program` before `result`. The following renaming swaps
those two final coordinates and skips `nextU`.
-/
/-! ## Exactness and uniqueness -/
end
end Constructible.Godel.RudimentaryTerm
end CUAdapterModule83
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.SuccessorStageStateFormula -/
section CUAdapterModule84
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A deterministic first-order successor step for stage/order states
A recursion state consists of a constructible domain `U` and a constructible
relation graph `oldRelation`. Its successor consists of `nextU = godelDef U`
and the canonical graph selected by the coherent successor-order formula on
`nextU`. Both outputs are specified by one fixed first-order formula.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-! ## Formula and assignments -/
/-
The combined layout is
`[U,varTag,appTag,empty,op0,...,op8,omega,oldRelation,nextU,nextRelation]`.
The `godelDef` output formula omits coordinates `oldRelation` and
`nextRelation`; its final output coordinate is therefore sent to `nextU`.
-/
/-! ## Exact semantics -/
/-! ## Functionality and existence -/
end
end Constructible.Model
end CUAdapterModule84
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistorySuccessorFormula -/
section CUAdapterModule85
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The successor-state clause for constructible-stage histories
The outer layout is `(fixed13, history, index, stage, relation)`. Three
existential witnesses append `(predecessorIndex, predecessorStage,
predecessorRelation)`. The existing deterministic successor-state formula
is then renamed into this combined context.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
end
end Constructible.Model
end CUAdapterModule85
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryFunctionality -/
section CUAdapterModule86
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Functionality of stage-history lookup
A stage history is functional at an index when it contains exactly one pair
of stage and relation coordinates at that index. The formula in this file
expresses that property entirely in the first-order membership language.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-!
The free-variable layout is `(history, index)`. The first two existential
variables are `(stage, relation)`. Inside the two universal quantifiers the
layout is
`(history, index, stage, relation, otherStage, otherRelation)`.
-/
end
end Constructible.Model
end CUAdapterModule86
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.ValidStageHistoryFormula -/
section CUAdapterModule87
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# A fixed validity formula for constructible-stage histories
The local rule combines the zero, successor, and nonzero-limit clauses in the
shared seventeen-coordinate layout
`(fixed13, history, index, stage, relation)`.
The global validity formula has layout `(fixed13, history, bound)`. It says
that every index at most `bound` has exactly one history entry, and that its
stage and relation coordinates obey the appropriate local rule. As in the
indexed-sequence validity predicate, irrelevant extra members of the history
set are permitted; every lookup uses only the total functional part below the
stated bound.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-! ## The unified local rule -/
/-! ## Total functional validity through a bound -/
end
end Constructible.Model
end CUAdapterModule87
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryOrdinal -/
section CUAdapterModule88
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Constructible ordinal indices for stage histories
Every ambient ordinal has a canonical von Neumann code in `L`. Packaging
that code once keeps the history and Replacement interfaces on `LCarrier`.
-/
universe u
namespace Constructible.Model
noncomputable section
end
end Constructible.Model
end CUAdapterModule88
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageStateAtFormula -/
section CUAdapterModule89
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Fixed output formulas for constructible-stage recursion
The formulas in this file hide a valid history witness and expose the forms
needed by Replacement. Their thirteen leading coordinates are always the
fixed evaluator parameters.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
/-! ## A stage/relation state at one index -/
/-! ## A relation-only output for Replacement -/
/-! ## A canonical triple output for Replacement -/
end
end Constructible.Model
end CUAdapterModule89
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryOperations -/
section CUAdapterModule90
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internal operations on constructible stage histories
A history is an actual member of `L`, not an external Lean set. This file
constructs the internal operation which adjoins one canonical triple and
records its exact lookup behavior.
-/
universe u
namespace Constructible.Model
noncomputable section
end
end Constructible.Model
end CUAdapterModule90
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryReplacement -/
section CUAdapterModule91
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internal replacement families for constructible-stage recursion
Assuming that every earlier ordinal index has a unique stage/relation state,
the fixed formulas from `StageStateAtFormula` turn the earlier history entries
and relation graphs into actual members of `L` by Replacement.
-/
universe u
namespace Constructible.Model
noncomputable section
local notation "LMem" => Model.lCarrierMem
end
end Constructible.Model
end CUAdapterModule91
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageStateUniqueness -/
section CUAdapterModule92
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Uniqueness of ordinal-indexed stage states
The local history rule is deterministic on canonical ordinal indices. This
file first normalizes the zero, successor, and limit cases, then uses ordinal
induction to compare states coming from different valid internal histories.
-/
universe u
namespace Constructible.Model
noncomputable section
end
end Constructible.Model
end CUAdapterModule92
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryRecursion -/
section CUAdapterModule93
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Internal transfinite recursion of constructible-stage histories
At every ordinal this file constructs an actual `LCarrier` history together
with its top relation. The history is valid through the canonical ordinal
index, and its top stage coordinate is exactly `stageLCarrier ordinal`.
-/
universe u
namespace Constructible.Model
noncomputable section
/-- Every canonical ordinal index has an internally witnessed state whose
stage coordinate is exactly `L_ordinal`. -/
theorem exists_stageStateAt_ordinal (ordinal : Ordinal.{u}) :
∃ relation : LCarrier.{u},
StageStateAt (ordinalLCarrier ordinal)
(stageLCarrier ordinal) relation :=
⟨(stageHistoryData ordinal).relation,
(stageHistoryData ordinal).state⟩
end
end Constructible.Model
end CUAdapterModule93
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.CoherentLimitOrder -/
section CUAdapterModule94
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Coherent unions of internally represented stage orders
At a limit stage, a union of arbitrary external well-orders is not enough.
This file records the exact coherence and initial-segment hypotheses under
which the union relation well-orders the limit carrier. If the family of
graphs is itself represented by a constructible set, its internal union is
then the required graph in `L`.
-/
open Set
universe u
namespace Constructible.Model
noncomputable section
/-! ## Internalizing the union graph -/
/-! ## Retaining coherence after the limit step -/
end
end Constructible.Model
end CUAdapterModule94
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageZeroInternalOrder -/
section CUAdapterModule95
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The internally represented order on the zero constructible stage
The carrier of `L_0` is empty, so the empty constructible set represents its
unique strict well-order.
-/
universe u
namespace Constructible.Model
end Constructible.Model
end CUAdapterModule95
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.CoherentStageGraphExtension -/
section CUAdapterModule96
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Adjoining one graph to a coherent stage system
Successor and limit constructions both produce a graph at one new ordinal,
together with support, agreement, and initial-segment facts relative to all
earlier stages. This file packages that common interface and proves that
adjoining such a graph preserves the complete coherent-system invariant.
-/
open Set
universe u
namespace Constructible.Model
noncomputable section
/-- Adjoining a valid extension preserves well-ordering, support, coherence,
and all earlier initial segments. -/
theorem coherentStageGraphSystem_append
(alpha : Ordinal.{u})
(graphs : Set.Iio alpha → LCarrier.{u})
(hsystem : CoherentStageGraphSystem alpha graphs)
(extension : StageGraphExtension alpha graphs) :
CoherentStageGraphSystem (Order.succ alpha)
(appendStageGraph alpha graphs extension.nextRelation) := by
refine
{ wellOrders := ?_
supported := ?_
coherent := ?_
initial := ?_ }
· intro beta
by_cases hbeta : beta.1 < alpha
· simpa only [appendStageGraph, dif_pos hbeta] using
hsystem.wellOrders ⟨beta.1, hbeta⟩
· have hbetaLe : beta.1 ≤ alpha :=
Order.lt_succ_iff.mp beta.2
have hbetaEq : beta.1 = alpha :=
le_antisymm hbetaLe (le_of_not_gt hbeta)
have happend :
appendStageGraph alpha graphs extension.nextRelation beta =
extension.nextRelation := by
rw [appendStageGraph, dif_neg hbeta]
rw [happend, hbetaEq]
exact extension.wellOrders
· intro beta x y hxy
by_cases hbeta : beta.1 < alpha
· have hxyEarlier :
GraphRel (graphs ⟨beta.1, hbeta⟩) x y := by
simpa only [appendStageGraph, dif_pos hbeta] using hxy
exact hsystem.supported ⟨beta.1, hbeta⟩ x y hxyEarlier
· have hbetaLe : beta.1 ≤ alpha :=
Order.lt_succ_iff.mp beta.2
have hbetaEq : beta.1 = alpha :=
le_antisymm hbetaLe (le_of_not_gt hbeta)
have hxyTop : GraphRel extension.nextRelation x y := by
simpa only [appendStageGraph, dif_neg hbeta] using hxy
simpa only [hbetaEq] using extension.supported x y hxyTop
· intro beta gamma hbetaGamma x y hx hy
by_cases hgamma : gamma.1 < alpha
· have hbeta : beta.1 < alpha :=
lt_of_le_of_lt hbetaGamma hgamma
simpa only [appendStageGraph, dif_pos hbeta, dif_pos hgamma] using
hsystem.coherent
⟨beta.1, hbeta⟩ ⟨gamma.1, hgamma⟩
hbetaGamma x y hx hy
· have hgammaLe : gamma.1 ≤ alpha :=
Order.lt_succ_iff.mp gamma.2
have hgammaEq : gamma.1 = alpha :=
le_antisymm hgammaLe (le_of_not_gt hgamma)
by_cases hbeta : beta.1 < alpha
· simpa only [appendStageGraph, dif_pos hbeta, dif_neg hgamma] using
extension.agreesOnEarlier ⟨beta.1, hbeta⟩ x y hx hy
· simp only [appendStageGraph, dif_neg hbeta, dif_neg hgamma]
· intro beta gamma hbetaGamma x y hx hy hgraph
by_cases hgamma : gamma.1 < alpha
· have hbeta : beta.1 < alpha :=
lt_of_le_of_lt hbetaGamma hgamma
have hgraphEarlier :
GraphRel (graphs ⟨gamma.1, hgamma⟩) y x := by
simpa only [appendStageGraph, dif_pos hgamma] using hgraph
exact hsystem.initial
⟨beta.1, hbeta⟩ ⟨gamma.1, hgamma⟩
hbetaGamma x y hx hy hgraphEarlier
· have hgammaLe : gamma.1 ≤ alpha :=
Order.lt_succ_iff.mp gamma.2
have hgammaEq : gamma.1 = alpha :=
le_antisymm hgammaLe (le_of_not_gt hgamma)
by_cases hbeta : beta.1 < alpha
· have hgraphTop : GraphRel extension.nextRelation y x := by
simpa only [appendStageGraph, dif_neg hgamma] using hgraph
have hyTop : y.1 ∈ LStageZF alpha := by
simpa only [hgammaEq] using hy
exact extension.earlierIsInitial
⟨beta.1, hbeta⟩ x y hx hyTop hgraphTop
· have hbetaLe : beta.1 ≤ alpha :=
hbetaGamma.trans hgammaLe
have hbetaEq : beta.1 = alpha :=
le_antisymm hbetaLe (le_of_not_gt hbeta)
simpa only [hbetaEq, hgammaEq] using hy
/-! ## The zero and successor extensions -/
end
end Constructible.Model
end CUAdapterModule96
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryCoherence -/
section CUAdapterModule97
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# Coherence of the internally recursive stage graphs
The relation coordinate of `stageHistoryData` is now assembled into a graph
system. Successors use the canonical extension theorem and limits use the
internally represented relation family constructed by Replacement.
-/
universe u
namespace Constructible.Model
noncomputable section
end
end Constructible.Model
end CUAdapterModule97
/- Original module: ConstructibleUniverse.SetTheory.ZFC.Constructible.StageHistoryGraphSystem -/
section CUAdapterModule98
/-
Copyright (c) 2026 Zike Liu. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Zike Liu
-/
/-!
# The coherent graph system generated by stage histories
The local extension theorem is iterated over all ordinals. At a limit bound,
each required pair of graphs already occurs together in the coherent system
through the successor of the later index.
-/
open Set
universe u
namespace Constructible.Model
noncomputable section
/-- Restricting the global graph assignment to a successor bound is the same
as appending the graph at its last index. -/
theorem historyStageGraphs_succ_eq_append (alpha : Ordinal.{u}) :
historyStageGraphs (Order.succ alpha) =
appendStageGraph alpha (historyStageGraphs alpha)
(stageHistoryData alpha).relation := by
funext beta
by_cases hbeta : beta.1 < alpha
· rw [appendStageGraph, dif_pos hbeta]
rfl
· have hbetaLe : beta.1 ≤ alpha :=
Order.lt_succ_iff.mp (Set.mem_Iio.mp beta.2)
have hbetaEq : beta.1 = alpha :=
le_antisymm hbetaLe (le_of_not_gt hbeta)
rw [appendStageGraph, dif_neg hbeta]
exact congrArg (fun ordinal => (stageHistoryData ordinal).relation)
hbetaEq
/-- The internally recursive stage graphs form a coherent system below every
ordinal bound. -/
theorem historyStageGraphs_coherent (bound : Ordinal.{u}) :
CoherentStageGraphSystem bound (historyStageGraphs bound) := by
induction bound using Ordinal.limitRecOn with
| zero =>
refine
{ wellOrders := ?_
supported := ?_
coherent := ?_
initial := ?_ }
· intro beta
exact (not_lt_of_ge bot_le (Set.mem_Iio.mp beta.2)).elim
· intro beta
exact (not_lt_of_ge bot_le (Set.mem_Iio.mp beta.2)).elim
· intro beta
exact (not_lt_of_ge bot_le (Set.mem_Iio.mp beta.2)).elim
· intro beta
exact (not_lt_of_ge bot_le (Set.mem_Iio.mp beta.2)).elim
| add_one alpha ih =>
rw [← Order.succ_eq_add_one]
let extensionData := historyStageGraphExtension alpha ih
have happend : CoherentStageGraphSystem (Order.succ alpha)
(appendStageGraph alpha (historyStageGraphs alpha)
extensionData.extension.nextRelation) :=
coherentStageGraphSystem_append alpha
(historyStageGraphs alpha) ih extensionData.extension
rw [extensionData.nextRelation_eq] at happend
rw [← historyStageGraphs_succ_eq_append alpha] at happend
exact happend
| limit limit hl ih =>
refine
{ wellOrders := ?_
supported := ?_
coherent := ?_
initial := ?_ }
· intro beta
have hsucc : Order.succ beta.1 < limit :=
hl.succ_lt (Set.mem_Iio.mp beta.2)
have hlocal :=
(ih (Order.succ beta.1) hsucc).wellOrders
(lastStageIndex beta.1)
simpa only [historyStageGraphs_last, historyStageGraphs_apply,
lastStageIndex_val] using hlocal
· intro beta x y hxy
have hsucc : Order.succ beta.1 < limit :=
hl.succ_lt (Set.mem_Iio.mp beta.2)
have hlocal :=
(ih (Order.succ beta.1) hsucc).supported
(lastStageIndex beta.1) x y
apply hlocal
simpa only [historyStageGraphs_apply, lastStageIndex_val] using hxy
· intro beta gamma hbetaGamma x y hx hy
have hsucc : Order.succ gamma.1 < limit :=
hl.succ_lt (Set.mem_Iio.mp gamma.2)
let beta' : Set.Iio (Order.succ gamma.1) :=
⟨beta.1, lt_of_le_of_lt hbetaGamma (Order.lt_succ gamma.1)⟩
let gamma' : Set.Iio (Order.succ gamma.1) :=
lastStageIndex gamma.1
have hlocal :=
(ih (Order.succ gamma.1) hsucc).coherent
beta' gamma' hbetaGamma x y hx hy
simpa only [historyStageGraphs, beta', gamma',
lastStageIndex_val] using hlocal
· intro beta gamma hbetaGamma x y hx hy hgraph
have hsucc : Order.succ gamma.1 < limit :=
hl.succ_lt (Set.mem_Iio.mp gamma.2)
let beta' : Set.Iio (Order.succ gamma.1) :=
⟨beta.1, lt_of_le_of_lt hbetaGamma (Order.lt_succ gamma.1)⟩
let gamma' : Set.Iio (Order.succ gamma.1) :=
lastStageIndex gamma.1
have hlocal :=
(ih (Order.succ gamma.1) hsucc).initial
beta' gamma' hbetaGamma x y hx hy
apply hlocal
simpa only [historyStageGraphs, gamma',
lastStageIndex_val] using hgraph
end
end Constructible.Model
end CUAdapterModule98
/-! # Bridge to the existing Prove2Me constructible universe -/
end GCHSource_Work_ConstructibleGCH_ReuseBase