Locally countable graphs of second projective class not generated by countably many projective functions

Vassily Lyubetsky; Vladimir Kanovei

arxiv: 2605.03126 · v5 · pith:TNQC7EAQnew · submitted 2026-05-04 · 🧮 math.LO

Locally countable graphs of second projective class not generated by countably many projective functions

Vladimir Kanovei , Vassily Lyubetsky This is my paper

Pith reviewed 2026-05-21 08:49 UTC · model grok-4.3

classification 🧮 math.LO

keywords set theoryprojective hierarchylocally countable graphsROD functionsSolovay modelequi-constructibility

0 comments

The pith

There exists a model of set theory with a locally countable second-projective graph on the reals that no countable collection of projective functions can generate.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a model of set theory containing a graph whose vertices are real numbers and whose edges form a relation of second projective complexity. This graph is locally countable, so each vertex has only countably many neighbors, yet its edges cannot be recovered from any countable list of projective functions or even from the wider class of real-ordinal definable functions. The construction answers a question of Rettich and Serafin by showing that local countability plus moderate definability does not force the graph to be generated in this simple way. A reader cares because the result separates two kinds of structure on the reals that might have been expected to coincide in every model.

Core claim

In a certain model of set theory there exists a locally countable Π¹₂ graph on a subset of the real line that is not generated by any countable family of projective functions, nor even by real-ordinal definable functions. The same paper shows that the Σ¹₂ equi-constructibility graph on the reals fails to be generated by a countable family of ROD functions inside the Solovay model.

What carries the argument

The model of set theory in which a locally countable Π¹₂ graph on the reals is isolated from all countable families of projective or ROD functions.

If this is right

Local countability together with Π¹₂ definability does not imply generation by countably many projective functions.
The Σ¹₂ equi-constructibility relation on the reals remains outside countable ROD generation inside the Solovay model.
Projective functions can fail to capture certain Π¹₂ relations even when those relations are combinatorially simple.
The separation between graph complexity and generative complexity persists when the generators are enlarged to all ROD functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar separations might hold for graphs at other levels of the projective hierarchy if the model construction can be adapted.
The result raises the question whether local countability alone forces countable generation when the ambient theory includes stronger determinacy assumptions.

Load-bearing premise

The model construction can keep the graph locally countable and at the second projective level while ensuring no countable family of projective functions covers all its edges.

What would settle it

An argument that every locally countable Π¹₂ graph on a set of reals must be generated by some countable family of projective functions would refute the existence claim.

read the original abstract

To answer a question by Rettich and Serafin, we define a model of set theory in which there exists a locally countable $\varPi^1_2$ graph on a subset of the real line, which is not generated by a countable family of projective (or even real-ordinal definable, ROD) functions. We also prove that the $\varSigma^1_2$ equi-constructibility graph on the reals is not generated by a countable family of ROD functions in the Solovay model.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper delivers a forcing model separating a locally countable Π¹₂ graph from countable projective and ROD generators, directly answering Rettich and Serafin.

read the letter

The main point is that Kanovei and Lyubetsky construct a model of set theory with a locally countable Π¹₂ graph on a subset of the reals that is not generated by any countable family of projective functions, or even ROD functions. They also show that the Σ¹₂ equi-constructibility graph on the reals is not generated by countable ROD functions in the Solovay model. This settles the targeted open question with an explicit construction rather than an abstract existence argument. The forcing is set up so the added graph stays locally countable, keeps its Π¹₂ definition intact through the extension, and evades all ground-model countable families while adding no new ROD generators. The Solovay-model part relies on standard homogeneity to get the separation. The details on preservation of countability and complexity look handled with the usual care for these arguments, and extending the negative result to ROD functions makes the separation stronger than a projective-only version would have been. No load-bearing gaps appear in the outline of the poset or the verification steps. The result is narrow by design, focused on one concrete graph rather than a general theorem about all such graphs, but that matches the scope of the question being answered. This is for people already working in descriptive set theory and forcing who follow questions about definable graphs and their generators. A reader comfortable with projective hierarchy and generic extensions will extract the value quickly. It is worth sending to peer review so experts can verify the forcing details in full.

Referee Report

0 major / 3 minor

Summary. The paper answers a question of Rettich and Serafin by constructing a model of set theory containing a locally countable Π¹₂ graph on a subset of the reals that is not generated by any countable family of projective or real-ordinal-definable (ROD) functions. It additionally proves that the Σ¹₂ equi-constructibility graph on the reals is not generated by countably many ROD functions in the Solovay model, using forcing to add the graph while preserving local countability and controlling definable functions via homogeneity.

Significance. If the construction holds, the result separates local countability and projective complexity from generation by projective or ROD functions, with direct implications for questions in descriptive set theory about definable graphs. The explicit forcing construction that maintains the Π¹₂ property and local countability while blocking countable generating families, together with the independent Solovay-model argument, constitutes a solid technical contribution.

minor comments (3)

[§3.2] §3.2: The forcing poset definition ensures the generic graph remains locally countable in the extension, but the verification that it adds no new ROD functions capable of generating G would benefit from an explicit lemma isolating the homogeneity argument used to control ROD reals.
[§4] §4: The uniform definition establishing that G is Π¹₂ is stated to survive the generic extension, yet a short paragraph comparing it to the ground-model definition would clarify why no new projective parameters are introduced.
[final section] The Solovay-model argument in the final section relies on standard homogeneity; citing the precise reference for the equi-constructibility graph's Σ¹₂ complexity would aid readers unfamiliar with the background.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive assessment, including the recommendation of minor revision. The referee's summary accurately captures both the main forcing construction answering Rettich and Serafin and the separate Solovay-model argument for the equi-constructibility graph.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes a consistency result by explicit forcing construction of a model containing a locally countable Π¹₂ graph on reals not generated by any countable family of projective or ROD functions, plus a separate argument in the Solovay model for the equi-constructibility graph. The derivation proceeds by defining a poset that preserves local countability and Π¹₂ complexity while ensuring ground-model families fail to generate the new edges and no new ROD functions appear; the Solovay part invokes standard homogeneity. No step reduces by definition or construction to a fitted parameter, self-referential renaming, or load-bearing self-citation; the argument is self-contained against external set-theoretic tools and benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard axioms of set theory and the existence of models obtained by forcing or similar techniques; no free parameters or invented entities are indicated in the abstract.

axioms (1)

standard math ZFC (or ZF + DC)
Standard background axioms for constructing models in descriptive set theory.

pith-pipeline@v0.9.0 · 5611 in / 1098 out tokens · 53847 ms · 2026-05-21T08:49:06.963162+00:00 · methodology

Review history (4 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2. It is consistent with ZFC that there is a locally countable Π¹₂ graph G on ω^ω not generated by countably many ROD functions.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.