Proposition 3.6 — invariant real parameters of countable graphs
ProvedFSCofinality.invariant_real_parametersLet h map simple countable graphs Borelly into Cantor space and be constant on graph-isomorphism classes. Then there exist one real r and a Borel self-reduction g of graph isomorphism such that h(g(G))=r for every graph G. A self-reduction preserves and reflects graph isomorphism on all pairs. No uniform dependence on h is required. The conclusion places a copy of the entire graph-isomorphism problem inside one invariant real-parameter fiber.
Writing for the specified graph space, the conclusion is
The map is assumed Borel and constant on graph-isomorphism classes.
import Definitions.Def_FSCofinalityStructures20261102 set_option autoImplicit false
theorem FSCofinality.invariant_real_parameters
(h : FSCofinality.GraphSpace → (ℕ → Bool)) (h_borel : Measurable h)
(h_invariant : ∀ G H, FSCofinality.GraphIsomorphic G H → h G = h H) :
∃ r : ℕ → Bool, ∃ g : FSCofinality.GraphSpace → FSCofinality.GraphSpace,
Measurable g ∧
(∀ G H, FSCofinality.GraphIsomorphic G H ↔
FSCofinality.GraphIsomorphic (g G) (g H)) ∧
∀ G, h (g G) = r := by sorry
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: FSCofinality.invariant_real_parameters
Read-back model: Codex; the exact underlying model identifier is unavailable to this auditor.
Scope: The target theorem, its imported Definitions/Def_FSCofinalityStructures20261102.lean, and Mathlib instance declarations needed to identify the measurable structures. No manuscript, informal statement, proposal metadata, or other theorem file was consulted.
For every function from the space of graphs described below to the space of Boolean sequences, if is measurable and if whenever and are isomorphic, there exist a Boolean sequence and a function such that all three of the following hold simultaneously: is measurable; for every pair , and are isomorphic if and only if and are isomorphic; and for every , . Here consists of all functions satisfying for every and for every . Thus its elements are all simple undirected graphs on the fixed vertex set , represented by their adjacency truth tables. Two such graphs are isomorphic precisely when there exists a bijection satisfying for every ; this is the meaning of isomorphism in both the hypothesis on and the conclusion about . The graph space has the subspace topology inherited from the product of discrete two-element spaces indexed by , and its measurable sets are exactly the Borel sets for that topology. Boolean sequences have the product sigma algebra of the full sigma algebra on each two-element coordinate, equivalently the Borel sigma algebra of their product topology. Consequently the measurability hypotheses and conclusion refer to these specific sigma algebras. The quantifier order is: choose any satisfying the two hypotheses, then choose , then choose , after which the isomorphism equivalence holds for all pairs of input graphs and the equation with holds for all input graphs. Neither witness is asserted to be unique. The graph space includes the edgeless graph, the graph having every off-diagonal adjacency true, and graphs with isolated vertices or with only finitely many edges; every graph still has the entire infinite vertex set , including vertex . The space is therefore nonempty, so the last equation is not vacuous and places the whole image of inside the single fiber . Constant measurable functions satisfy the hypotheses as well. There is no additional hypothesis of continuity, injectivity, surjectivity, or nonconstancy on , and the conclusion imposes no continuity or surjectivity requirement on and no injectivity requirement on labeled graph representatives beyond the stated preservation and reflection of isomorphism.
Confirmed by the mission captain (proposal self-audit).