Countable structure spaces, graph codes, and Borel reductions
DefinitionFSCofinalityStructures20261102A countable relational language has finitely many arguments at each symbol, including arity zero. Its structures on the natural numbers are their Boolean relation truth tables with the canonical product Borel sigma algebra. Isomorphism is witnessed by one permutation preserving every relation value. An invariant class is closed under this isomorphism. Simple undirected graphs have the corresponding concrete adjacency codes. Borel reductions are measurable maps preserving and reflecting the compared relations on every pair; no Borelness of either relation graph is built into the interface. A coded relation bundles its actual carrier, measurable space and predicate.
import Mathlib.MeasureTheory.Constructions.Polish.Basic
import Mathlib.Topology.MetricSpace.Polish
set_option autoImplicit false
noncomputable section
open TopologicalSpace
namespace FSCofinality
/-- A countable relational language. Arity zero is allowed. -/
structure CountableRelationalLanguage where
Symbol : Type
arity : Symbol → ℕ
countable : Countable Symbol
attribute [instance] CountableRelationalLanguage.countable
/-- An atomic relation coordinate on the fixed domain `ℕ`. -/
def Coordinate (L : CountableRelationalLanguage) :=
Σ s : L.Symbol, Fin (L.arity s) → ℕ
instance (L : CountableRelationalLanguage) : Countable (Coordinate L) := by
unfold Coordinate
infer_instance
/-- All structures for `L` on `ℕ`, as their actual relation truth values. -/
def Structures (L : CountableRelationalLanguage) := Coordinate L → Bool
instance (L : CountableRelationalLanguage) : TopologicalSpace (Structures L) :=
inferInstanceAs (TopologicalSpace (Coordinate L → Bool))
instance (L : CountableRelationalLanguage) : PolishSpace (Structures L) where
toSecondCountableTopology :=
inferInstanceAs (SecondCountableTopology (Coordinate L → Bool))
toIsCompletelyMetrizableSpace :=
inferInstanceAs (IsCompletelyMetrizableSpace (Coordinate L → Bool))
instance (L : CountableRelationalLanguage) : MeasurableSpace (Structures L) :=
borel (Structures L)
instance (L : CountableRelationalLanguage) : BorelSpace (Structures L) := ⟨rfl⟩
/-- Isomorphism by one permutation of the fixed countable domain. -/
def Isomorphic {L : CountableRelationalLanguage} (M N : Structures L) : Prop :=
∃ e : ℕ ≃ ℕ, ∀ (s : L.Symbol) (a : Fin (L.arity s) → ℕ),
M ⟨s,a⟩ = N ⟨s,e ∘ a⟩
def IsInvariant {L : CountableRelationalLanguage} (K : Set (Structures L)) : Prop :=
∀ {M N}, M ∈ K → Isomorphic M N → N ∈ K
def IsomorphismOn {L : CountableRelationalLanguage} (K : Set (Structures L))
(M N : K) : Prop := Isomorphic M.val N.val
/-- Borel reduction: measurability and preservation and reflection on all pairs.
Neither input relation is required to have a Borel graph. -/
def BorelReducible {X Y : Type} [MeasurableSpace X] [MeasurableSpace Y]
(E : X → X → Prop) (F : Y → Y → Prop) : Prop :=
∃ f : X → Y, Measurable f ∧ ∀ x y, E x y ↔ F (f x) (f y)
/-- A concrete measurable code space together with its classified relation.
The bundle deliberately imposes no Borelness hypothesis on the relation. -/
structure CodedRelation where
Carrier : Type
measurableSpace : MeasurableSpace Carrier
rel : Carrier → Carrier → Prop
attribute [instance] CodedRelation.measurableSpace
def CodedRelation.Reduces (E F : CodedRelation) : Prop :=
@BorelReducible E.Carrier F.Carrier E.measurableSpace F.measurableSpace E.rel F.rel
def classRelation (L : CountableRelationalLanguage) (K : Set (Structures L)) :
CodedRelation where
Carrier := K
measurableSpace := inferInstance
rel := IsomorphismOn K
/-- Truth tables of simple undirected graphs on `ℕ`. -/
def GraphCondition (g : ℕ × ℕ → Bool) : Prop :=
(∀ n, g (n,n) = false) ∧ ∀ m n, g (m,n) = g (n,m)
def GraphSpace := {g : ℕ × ℕ → Bool // GraphCondition g}
instance : TopologicalSpace GraphSpace :=
inferInstanceAs (TopologicalSpace {g : ℕ × ℕ → Bool // GraphCondition g})
instance : MeasurableSpace GraphSpace := borel GraphSpace
instance : BorelSpace GraphSpace := ⟨rfl⟩
theorem isClosed_graphCondition : IsClosed {g : ℕ × ℕ → Bool | GraphCondition g} := by
have hd : IsClosed {g : ℕ × ℕ → Bool | ∀ n, g (n,n) = false} := by
simp only [Set.setOf_forall]
exact isClosed_iInter (fun n => isClosed_eq (continuous_apply (n,n)) continuous_const)
have hs : IsClosed {g : ℕ × ℕ → Bool | ∀ m n, g (m,n) = g (n,m)} := by
simp only [Set.setOf_forall]
exact isClosed_iInter (fun m => isClosed_iInter (fun n =>
isClosed_eq (continuous_apply (m,n)) (continuous_apply (n,m))))
exact hd.inter hs
instance : PolishSpace GraphSpace := by
letI : PolishSpace (ℕ × ℕ → Bool) := {
toSecondCountableTopology := inferInstance
toIsCompletelyMetrizableSpace := inferInstance }
exact isClosed_graphCondition.polishSpace
def GraphIsomorphic (g h : GraphSpace) : Prop :=
∃ e : ℕ ≃ ℕ, ∀ m n, g.val (m,n) = h.val (e m,e n)
def graphRelation : CodedRelation where
Carrier := GraphSpace
measurableSpace := inferInstance
rel := GraphIsomorphic
end FSCofinality
Read-back
What the Lean code literally says, in plain math · Codex (GPT-6 family; exact runtime model identifier not exposed to auditor)
Blind read-back: structures and coded relations
Model identity: exactmodelunavailable. The runtime does not expose an exact model identifier to this auditor. This read-back uses only the supplied auditor instructions and the designated Lean file; no intended informal statement or source material was supplied.
CountableRelationalLanguage. A countable relational language consists of a type of relation symbols, a function assigning each symbol a finite arity, and a proof that is at most countable. There is no assumption that is inhabited or infinite: the empty language, finite languages, and countably infinite languages are admitted. There is no lower bound on arity, so symbols of arity zero are admitted. The declaration supplies no function symbols, constants, axioms, or distinguished equality symbol.
Registered countability of the symbol type. For every language consisting of such a symbol type, arity function, and countability proof, its stored proof is made available as an instance asserting that the symbol type is at most countable. This adds no further restriction on a language.
Coordinate. For every countable relational language with symbol type and arity function , a coordinate is a pair where and is an ordered tuple of natural numbers of length . Repeated entries in a tuple are permitted. For , there is exactly one empty tuple, hence exactly one coordinate for that symbol. If is empty, the coordinate type is empty.
Countability of Coordinate. For every countable relational language , the type of all pairs , with a symbol and a natural-number tuple of length equal to its arity, is at most countable. This includes the empty coordinate type and languages with nullary symbols.
Structures. For every countable relational language , a structure is an arbitrary function from the coordinate type to the two Boolean values. Equivalently, it independently assigns a truth value to every symbol and every ordered natural-number tuple of the appropriate arity. The underlying domain is always all of , so finite or empty underlying domains are not represented. There are no imposed axioms, restrictions on repeated tuple entries, or compatibility requirements between coordinates. A nullary symbol receives a single freely chosen truth value. An empty language has exactly one such structure, the unique function from the empty coordinate type to the Booleans.
Topology on Structures. For each countable relational language , the space of all Boolean functions on its coordinates is given the product topology, using the usual discrete topology on the two Boolean values. Thus the topology records truth values on finitely many coordinates at a time. This is the topology assigned to the previously defined structure type, with no additional assumptions on its structures or on the language beyond the language bundle.
Polish-space instance on Structures. For every countable relational language , the space of all Boolean truth assignments to its coordinates, with the preceding product topology, is declared second countable and completely metrizable, hence Polish. The instance asserts existence of a compatible complete metric and does not select an explicit metric as part of the structure data. It also covers the singleton space arising from the empty language.
Measurable space on Structures. For every countable relational language , the measurable sets of structures are exactly the Borel sets of the product topology on all Boolean coordinate assignments.
Borel-space instance on Structures. For every countable relational language , the preceding measurable structure on its truth-assignment space agrees with the Borel sigma algebra of its topology. This instance supplies that agreement; it adds no condition on an individual structure or on a subset of structures.
Isomorphic. For every implicitly supplied countable relational language and every two structures for that same language on , the predicate says that there exists a bijection such that, for every symbol and every tuple , the truth value assigned by to equals the truth value assigned by to . A single bijection must work simultaneously for every symbol and tuple. For nullary symbols, composition leaves the empty tuple unchanged, so the corresponding Boolean values must agree. For the empty language the universal coordinate condition is vacuous, and the identity bijection supplies the existential witness.
IsInvariant. For every implicitly supplied countable relational language and every subset of its structures, this predicate says that for all structures , if and there exists a bijection of carrying every relation truth value of to that of as described above, then . Membership of is the conclusion; membership of and isomorphism of the pair are the hypotheses. No measurability, Borelness, nonemptiness, or other restriction on is required. The empty subset satisfies this condition vacuously.
IsomorphismOn. For every implicitly supplied countable relational language , every subset of its structures, and every two elements of the subtype consisting of members of , this relation holds precisely when their underlying structures admit a bijection preserving the Boolean value of every symbol on every tuple under simultaneous application of to the tuple entries. Both arguments must already belong to . No invariance or Borelness assumption on is made. If is empty, there are no arguments to which the relation can be applied.
BorelReducible. For every pair of implicitly supplied types , each equipped with an arbitrary measurable-space structure, and every pair of arbitrary binary predicates and , this predicate says that there exists a function which is measurable for those two specified measurable spaces and satisfies, for all , if and only if . Measurability means that the inverse image of each measurable subset of is measurable in . The condition both preserves and reflects the relations, with no restriction to almost every pair or to a selected subset of . The types need not be topological, Polish, standard Borel, inhabited, or countable. Neither relation is required to be an equivalence relation, measurable, or to have a Borel graph. Despite the predicate's name, only the supplied sigma algebras enter this definition. If is empty, a measurable empty function exists for every and the pair condition is vacuous, so the predicate holds; if is inhabited and is empty, no witnessing function exists.
CodedRelation. A coded relation consists of an arbitrary type , a measurable-space structure on , and an arbitrary binary predicate . These are the entire data: no topology, countability, nonemptiness, standard-Borel property, Borel or measurable graph, reflexivity, symmetry, or transitivity is required. In particular the carrier may be empty, and the relation need not be an equivalence relation.
Registered measurable space of CodedRelation. For every coded relation, its stored measurable-space structure on its carrier is made available as an instance. The declaration does not replace that sigma algebra with any topology-derived sigma algebra or impose further properties on it.
CodedRelation.Reduces. For every two coded relations , this predicate says that there exists a function from the carrier of to the carrier of which is measurable specifically for their stored sigma algebras and for which, for every two elements of the carrier of , the stored relation of holds on if and only if the stored relation of holds on . No Borelness or equivalence-relation hypothesis is added to either stored predicate. An empty source carrier always admits this reduction, including to an empty target; an inhabited source cannot reduce to an empty target.
classRelation. For every countable relational language and every subset of the space of its Boolean truth-assignment structures on , this construction returns a coded relation whose carrier is the subtype of structures belonging to , whose measurable-space structure is the subtype sigma algebra inherited from the ambient Borel sigma algebra, and whose binary predicate is isomorphism of the underlying structures. Concretely the measurable sets are traces on of ambient Borel sets, and the relation holds exactly when there exists one bijection of preserving the Boolean value at every symbol and tuple after relabeling all tuple entries. The construction requires neither invariance nor Borelness nor nonemptiness of . Thus an arbitrary non-Borel subset is admitted, without an assertion here that its measurable carrier is standard Borel, and the empty subset produces an empty carrier.
GraphCondition. For every function , this predicate is the conjunction of the following two requirements: for every , ; and for every , . There are no other restrictions. In particular all pairs, including diagonal pairs, are covered by the symmetry requirement, and isolated vertices and the graph with every value false are permitted.
GraphSpace. This is the subtype of all Boolean functions on which have false diagonal values and are symmetric on every ordered pair. Its vertices are always all natural numbers; a false-everywhere truth table represents the graph without edges on that fixed infinite vertex set. The definition includes membership proofs as subtype data and imposes no restriction beyond the stated diagonal and symmetry conditions.
Topology on GraphSpace. The graph space is given the subspace topology inherited from the product of discrete Boolean spaces indexed by . Thus it is the topology on symmetric, false-diagonal truth tables induced by the topology of all truth tables.
Measurable space on GraphSpace. The measurable-space structure on the graph subtype is its Borel sigma algebra for the preceding subspace topology.
Borel-space instance on GraphSpace. The assigned sigma algebra on the graph subtype agrees with the Borel sigma algebra of its assigned topology. This instance asserts that agreement and supplies no further restriction on graphs.
isClosed_graphCondition. In the product topology on all Boolean functions on , the set of functions satisfying both for every natural number and for every two natural numbers is closed. There are no additional parameters or hypotheses in this assertion. It concerns the set of valid graph truth tables inside the full truth-table space.
Polish-space instance on GraphSpace. The space of symmetric, false-diagonal Boolean truth tables on , with its inherited product subspace topology, is second countable and completely metrizable, hence Polish. The declaration supplies existence of a compatible complete metric, not a particular metric as stored graph data.
GraphIsomorphic. For every two elements of the graph space, this predicate says that there exists a bijection such that, for every , the underlying truth tables satisfy . The same bijection works for all pairs, so equality of both true and false adjacency values is required on the whole fixed vertex set. No vertices or pairs are excluded, and no extra hypotheses on the two graphs are present beyond their defining symmetry and false diagonals.
graphRelation. This coded relation has as carrier the space of all symmetric, false-diagonal Boolean truth tables on , as measurable structure the Borel sigma algebra of that space's product subspace topology, and as binary predicate the existence of a single bijection satisfying for every natural-number pair . The construction does not add a Borel-graph assertion for this binary predicate.
Scope and naming observations. The file provides these definitions, instances, and the closedness assertion; it states no cofinality claim and no comparison between classRelation and graphRelation. The generic reduction and coded-relation definitions permit arbitrary measurable spaces and arbitrary binary relations, including relations without Borel graphs; the word “Borel” in the generic reduction name does not add a topological assumption. The construction named classRelation accepts every subset, without requiring the separately defined invariance predicate. No comparison with an intended claim is possible from the supplied file alone.
Confirmed by the mission captain (proposal self-audit).