Pseudo-finite sets, pseudo-o-minimality

Nadav Meir

REVIEW 3 major objections 4 minor 12 references

Pseudo-finite sets, pseudo-o-minimality

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Two ordered structures with the same order and the same one-variable definable subsets can still differ on the common theory of o-minimality, because a definable injective non-surjective shift can be hidden on a discrete set.

desk verdict A genuinely stronger counterexample for pseudo-o-minimality, but the QE proof for T2 has a concrete error in Lemma 6.21 that needs repair before the main theorem is established. read the letter →

arxiv 1908.01660 v2 pith:QT2IJO7O submitted 2019-08-05 math.LO

Nadav Meir This is my paper · ORCID

classification math.LO MSC 03C64

keywords pseudo-o-minimalpseudo-finitesetsdefinablycompletetypepigeonholeprincipleo-minimalismquantifiereliminationcyclicorder

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes that the common first-order theory of o-minimal structures cannot be recognized from one-variable definable sets alone. It constructs two ordered structures $M$ and $N$ on the same universe, with the same order and the same one-variable definable subsets, where $M$ is pseudo-o-minimal and $N$ is not: $N$ has a definable closed, bounded, discrete set $Z$ and a definable injective map $f:Z\to Z$ that is not surjective. This gives negative answers to the question whether pseudo-o-minimality is axiomatizable by first-order conditions on one-variable formulas, and to the question whether definable completeness plus type completeness forces the pigeonhole principle. It matters because it delimits what one-variable definability can certify about an ordered structure and pinpoints the real-closed-field question as genuinely algebraic.

What carries the argument

The machine is the cyclic-order structure on the distinguished set $Z$, with successor $S$, predecessor $P$, and circular projection $\pi$, together with a shift $f$ that cyclically permutes two halves of $Z$. In $M_2$ the shift is changed on a tail so that $f(Z)=Z\setminus\{P(c_3)\}$; nevertheless $f$ commutes with $S$ up to finitely many exceptions, so the semigroup generated by $f,g,S,P,\pi$ is Abelian up to those exceptions. Quantifier elimination is then forced by a two-coordinate rank: terms with high $f,g$-degree are replaced by corrected terms of lower rank using one-variable comparisons on $Z$, and atomic formulas are eventually rewritten as comparisons of cyclic terms that involve no $f$ or $g$. The outcome is Corollary 6.25: the one-variable definable sets of $M_2$ coincide with those of $M_0$, while $f\upharpoonright Z$ witnesses the failure of pigeonhole.

What would settle it

Work in a model $M_0$ of $T_0$ and take any term $F$ built from $S$, $P$, and $\pi$. Lemma 6.12 says there are finitely many constants $\tau_1,\dots,\tau_k$ such that for every $x$ outside those constants, only finitely many elements of $Z$ lie between $x$ and $F(x)$. Finding one such $F$ and one input $x$ outside the constant exceptions with infinitely many $Z$-elements between $x$ and $F(x)$ would break the rank reduction and with it Corollary 6.25. More directly, exhibiting any one-variable $L_1$-definable subset of $M_2$ that is not definable in $M_0$ would refute the theorem.

Watch

Extended reading notes

Core claim

The central discovery, stated as Theorem 6.27, is a pair of ordered structures in one language that are indistinguishable by order and by one-variable definability but differ in pseudo-o-minimality. The pseudo-o-minimal member is a model $M_0$ of a theory $T_0$ that contains the common theory of o-minimal structures and carries a closed, bounded, discrete set $Z$ equipped with a cyclic successor structure. The second member $M_2$ is obtained by modifying a bijective cyclic shift $f$ on $Z$ so that $f$ becomes injective but omits one point; then $Z$ is a pseudo-finite set with a definable injective non-surjective self-map, so the pigeonhole principle fails, and $M_2$ is not pseudo-o-minimal. The proof that the two structures nevertheless have the same one-variable definable sets runs through a quantifier-elimination theorem for $M_2$: every $L_1$-definable subset in one free variable reduces, outside finitely many constants, to an $L_0$-definable set. Consequently no first-order scheme over one-variable formulas, and no second-order theory over the one-variable definable subsets, can axiomatize pseudo-o-minimality.

Load-bearing premise

Everything rests on the claim that every cyclic-order term moves any input past only finitely many points of $Z$, except at finitely many exceptional constants; if that claim fails, the mutated structure may acquire new one-variable definable sets, and the counterexample evaporates.

Editorial extensions

If this is right

No first-order scheme ranging over all one-variable formulas can axiomatize the common theory of o-minimal structures; any axiom system for pseudo-o-minimality must use several variables or higher-order data.
Definable completeness together with type completeness does not imply the pigeonhole principle: the class contains a pseudo-finite set with a definable injective non-surjective self-map.
There is no second-order axiomatization of pseudo-o-minimality in the language $\{<,\mathrm{Def}\}$ where $\mathrm{Def}$ names the one-variable definable sets.
The equivalence between pseudo-finite and pseudo-o-finite sets fails in the definably complete, type complete setting: a pseudo-finite set can behave unlike a finite set once a predicate for it is added.
The conjecture for definably complete expansions of real closed fields remains open, but the obstruction cannot be purely order-theoretic, since the ordered counterexample here refutes the analogous statement without field operations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural extension, not pursued in the paper, would be to preserve definable subsets in any fixed finite number of variables while still changing pigeonhole behavior; that would show no fixed arity of definable-set data can axiomatize pseudo-o-minimality.
The construction suggests a general coding phenomenon: on a definably complete structure with a definable discrete set, an injective non-surjective definable shift can be rendered invisible to one-variable definability by cyclic-order bookkeeping.
If the real-closed-field conjecture is true, its proof must use field-specific properties such as multiplication, because the construction removes the field operations and immediately produces a definably complete, type complete counterexample.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: if the Section 6 gap is fixed, this is a nice result. The construction of M2 is genuinely new: it shows that even naming all one-variable definable sets in a second-order way cannot axiomatize pseudo-o-minimality, which is strictly stronger than Rennet's non-axiomatizability result. The tail-shift modification of f is clever, and the paper is honest about what remains open (the real closed field case is still open).

What is solid: the consistency proof by finite approximations is plausible, Lemma 6.1 rigorously establishes the failure of the pigeonhole principle in M2, and the T0 quantifier elimination looks essentially right. The citations to Schoutens, Novak, and Rennet are appropriate, and the paper does not force constants or normalize to get its answer.

The soft spot is Section 6. Lemma 6.21 is not correct as written. For rank (0,k+1), Lemma 6.14 gives f^{k+1}(z)c2, but (21) gives the disjunction of c1≤f^i(z)≤c2, which is the negation of that condition. So the displayed equivalence fails for '<'. It also fails for '=' inside Z, where iterates cannot equal the starting point. For '>' the disjunction happens to match 'not <', but that does not save the lemma. Lemma 6.23 and Theorem 6.24 rely on Lemma 6.21, so Corollary 6.25 and Theorems 6.26–6.27 are unsupported as written.

I want to keep this in proportion: the error looks localized and repairable. Replace (21) with the correct conjunction for '<', handle '=' separately, and let '>' be the negation of '<' or '='. The induction strategy still seems viable. A smaller gap is that Proposition 3.3 asserts the finite models are o-minimal without spelling out the verification; that is probably routine but should be written down.

Who this is for: model theorists working on o-minimality, definable completeness, and tame structures. It deserves a serious referee despite the gap. I would not cite the main theorem until the QE proof is repaired, but I would encourage revision rather than rejection.

Referee Report

3 major / 4 minor

Summary. The paper constructs two ordered structures M and N in the same language L1, on the same universe, with the same order and the same one-variable definable subsets, such that M is pseudo-o-minimal (a model of the common theory of o-minimal structures) while N has a definable closed bounded discrete set Z and a definable injection Z → Z that is not surjective, hence N fails the pigeonhole principle. This is claimed to answer negatively Schoutens' questions about whether pseudo-o-minimality can be axiomatized by first-order conditions on one-variable formulas alone, whether definable completeness plus type completeness implies the pigeonhole principle, and to partially answer a question of Fornasiero. The construction proceeds by building a theory T0 with a discrete closed bounded set Z, adding a bijection f (theory T1), then modifying f to be injective but not surjective (structure M2), while proving quantifier elimination for T2 to show that every one-variable definable set in M2 is already definable in M0.

Significance. If the main theorem is established, it is a significant negative result: it refutes any axiomatization of pseudo-o-minimality by one-variable definability conditions, and even any second-order theory in the language LDef. The paper also gives a useful concrete counterexample to the discrete pigeonhole principle in a definably complete, type complete structure. The consistency proofs via finite approximations, the quantifier-elimination proof for T0, and the careful modification of f are valuable contributions, and the main construction is elegant. However, the central preservation theorem for one-variable definability rests on a long quantifier-elimination proof for T2, and that proof currently contains a gap; the contribution is therefore conditional on repair.

major comments (3)

[§6, Lemma 6.21, Eq. (20)–(21)] The displayed equivalence used to reduce rank (0,k+1) is false as stated. For ψ(x) ∈ Z, Lemma 6.14 gives f^{k+1}(z) < z ↔ ⋀_{i=0}^k (f^i(z) > c2), whereas the disjunction in (21), namely ⋁_{i=0}^k (c1 ≤ f^i(ψ(x)) ≤ c2), is the negation of that conjunction. Thus (21) is not equivalent to the '<' case. For '=', the left side f^{k+1}(z) = z is false for all z ∈ Z by Axiom 12, while the right side can be true depending on the iterates; for ψ(x) ∉ Z, f^{k+1}(x) = x, so the left side is false for '<' and '>' and true for '=', while the disjunct (ψ(x) ∉ Z ∧ ψ(x) = ψ(x)) makes the right side true for every □. Consequently the equivalence fails for all three order predicates in general. Since Lemma 6.23 and Theorem 6.24 invoke Lemma 6.21, the quantifier elimination for T2 and hence Corollary 6.25 are not established as written.
[§6, Lemma 6.21, case (2)] The same gap propagates to the g-case in Lemma 6.21, where the proof substitutes g^{k+1}(ψ(x)) into the false equivalence (20). Because (20) is invalid, the rank reduction for formulas of the form g^{k+1}(ψ(x)) □ ψ(x) is not justified. Since this is the only reduction step for rank (0,k+1), the induction in Lemma 6.23 is incomplete. The error appears localized and likely repairable by giving separate treatments of '<', '>', and '=', and by properly handling the cases ψ(x) ∈ Z and ψ(x) ∉ Z, but the current proof is not sound.
[§6, Lemma 6.16 and Lemma 6.21] The proof of Lemma 6.16 also depends on an unstated uniformity: the constant terms τ_i are chosen before fixing x, and the case split on ψ_1(x) and ψ_2(x) being equal to these constants is used to reduce all terms to a common rank. This is plausible, but when Lemma 6.21 is repaired, the interaction between these constant-term exceptions and the rank reduction must be re-checked, because the exceptional points are not themselves in Z and the order comparisons there require the 'outside Z' branch. The current text does not fully spell out this uniformity, and the gap in Lemma 6.21 makes it impossible to verify the induction.

minor comments (4)

[Throughout] The text has several OCR-style artifacts: 'By /suppress Los’ Theorem' in the introduction, 'if Sn(x) =c4' with missing spacing, and 'rank(φ,x )< rank(ϕ,x )' with inconsistent spacing. These should be cleaned up.
[Lemma 6.21, equation (20)] The displayed formula (20) writes f^k ◦ ψ(x) □ ψ(x) although the lemma concerns rank (0,k+1) and the subsequent text uses f^{k+1}; the index should be made consistent throughout.
[Definition 6.17] In the definition of rank, the cases for atomic formulas involving F(x) ∈ Z and F(x) □ τ use the same notation (−∞, deg(F)); this is fine, but it would help to explicitly say that the second coordinate is the degree of the outermost term, since the lexicographic ordering is then not immediately transparent from the notation.
[§3, Axiom 7] The axiom for π is written '(∀x)(π(x) ∈ Z) ∧ (∀y ∈ Z (¬C<(x,y,π(x))))', but the variable x in the second conjunct is not quantified; it should presumably be '(∀x)(∀y ∈ Z)(¬C<(x,y,π(x)))'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the counterexample is constructed from explicit axioms, and external citations are not load-bearing self-citations.

full rationale

The paper's derivation is not circular. The central counterexample is built explicitly: T0 is an expansion of a dense linear order by a closed, discrete set Z; T1 adds a bijection f with order-theoretic axioms; M2 modifies f on one tail so that f|Z is injective but not surjective (Lemma 6.1(4)). Pseudo-o-minimality of M0 is built in by the axiom T0 ⊇ T_omin^{L0}, which is an assumption, not a prediction; the substantive claim is that the modified structure M2 retains the same one-variable definable sets (Corollary 6.25), and that this forces M2 to be definably complete and type complete while failing the pigeonhole principle (Theorem 6.26). The transfer of one-variable definability rests on a quantifier-elimination argument for T2, not on any fitted parameter or on the target conclusion. Citations to Schoutens, Miller, Fornasiero, Novak, and Rennet are to independent prior work, not to the present author; none is used to forbid alternatives or to smuggle in the counterexample. The skeptical objection to Lemma 6.21 identifies a possible mathematical gap in the QE proof, but a gap is not circularity: the displayed equivalence, if false, is an error in a proof step, not a reduction of the theorem to its own assumptions. A similar possible concern is that the finite-satisfiability proof for T1 does not explicitly address Axiom 1 (T_omin), but that is again a completeness/correctness issue, not an input-output circularity. Under the hard rules, no specific equation or definition equates the claimed prediction with its input, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no free parameters or empirical entities. The central claim rests on model-theoretic assumptions inherited from Schoutens and on the correctness of the quantifier-elimination proofs for T0 and T2. The only pulled-in content is the standard framework of o-minimality, ultraproducts, and cyclic order theory.

assumptions (5)

domain assumption Pseudo-o-minimality is equivalent to elementary equivalence to an ultraproduct of o-minimal structures (Fact 1.3, from [Sch14, Corollary 10.2]).
Used to identify the theory T_omin with the theory of ultraproducts and to assert M0 is pseudo-o-minimal. The paper cites this from Schoutens without proof.
domain assumption The finite structures in Proposition 3.3 are o-minimal (satisfy T_omin^L0), so their ultraproduct is pseudo-o-minimal.
Proposition 3.3 asserts the finite models satisfy Axiom 1 'by definition', but the o-minimality of a dense linear order with a finite predicate Z and functions S, P, pi is not demonstrated.
domain assumption In any model of T1, the set X = {x : exists n S^n(x)=c4} is convex with order type omega* and maximum c4, and the modification of f on X yields a well-defined structure M2.
Definition 5.1 relies on this property to define the new functions f^{M2} and g^{M2}. It follows from the axioms of T1 and the fact that Z is discrete, closed, and bounded.
standard math The lexicographic order on ranks used in Lemma 6.23 is well-founded, so the induction terminates.
Standard well-ordering of the lexicographic order on pairs of natural numbers.
standard math Fact 2.4 from Novak: if two cuts satisfy the given order-isomorphism conditions, then the cyclic orders coincide.
Used in Lemma 5.2 to show f preserves the cyclic order on Z.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Pseudo-finite sets, pseudo-o-minimality." pith.science (2026). https://pith.science/paper/QT2IJO7O

@misc{pith2026190801660,
  author       = {Pith},
  title        = {Pith review of: Pseudo-finite sets, pseudo-o-minimality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QT2IJO7O}},
  note         = {Machine review of arXiv:1908.01660}
}

read the original abstract

We give an example of two ordered structures M, N in the same language L with the same universe, the same order and admitting the same one-variable definable subsets such that M is a model of the common theory of o-minimal L-structures and N admits a definable, closed, bounded, and discrete subset and a definable injective self-mapping of that subset which is not surjective. This answers negatively two questions by Schoutens; the first being whether there is an axiomatization of the common theory of o-minimal structures in a given language by conditions on one-variable definable sets alone. The second being whether definable completeness and type completeness imply the pigeonhole principle. It also partially answers a question by Fornasiero asking whether definable completeness of an expansion of a real closed field implies the pigeonhole principle.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

A fundamental dichotomy for definably complete expansions of ordered fields

Antongiulio Fornasiero and Philipp Hieronymi. A fundamental dichotomy for definably complete expansions of ordered fields. J. Symb. Log. , 80(4):1091--1115, 2015

work page 2015
[2]

Tame structures and open cores

Antongiulio Fornasiero . Tame structures and open cores . arXiv e-prints , page arXiv:1003.3557, Mar 2010

work page Pith review arXiv 2010
[3]

Locally o-minimal structures and structures with locally o-minimal open core

Antongiulio Fornasiero. Locally o-minimal structures and structures with locally o-minimal open core. Ann. Pure Appl. Logic , 164(3):211--229, 2013

work page 2013
[4]

Relative P faffian closure for definably complete B aire structures

Antongiulio Fornasiero and Tamara Servi. Relative P faffian closure for definably complete B aire structures. Illinois J. Math. , 55(3):1203--1219 (2013), 2011

work page 2013
[5]

Expansions of subfields of the real field by a discrete set

Philipp Hieronymi. Expansions of subfields of the real field by a discrete set. Fund. Math. , 215(2):167--175, 2011

work page 2011
[6]

An analogue of the B aire category theorem

Philipp Hieronymi. An analogue of the B aire category theorem. J. Symbolic Logic , 78(1):207--213, 2013

work page 2013
[7]

Huntington

Edward V. Huntington. Inter-relations among the four principal types of order. Trans. Amer. Math. Soc. , 38(1):1--9, 1935

work page 1935
[8]

Expansions of dense linear orders with the intermediate value property

Chris Miller. Expansions of dense linear orders with the intermediate value property. J. Symbolic Logic , 66(4):1783--1790, 2001

work page 2001

Show all 12 references

[9]

Cuts in cyclically ordered sets

V\' i t e zslav Nov\' a k. Cuts in cyclically ordered sets. Czechoslovak Math. J. , 34(109)(2):322--333, 1984

1984
[10]

The non-axiomatizability of o-minimality

Alex Rennet. The non-axiomatizability of o-minimality. J. Symb. Log. , 79(1):54--59, 2014

2014
[11]

o-minimalism

Hans Schoutens. o-minimalism. J. Symb. Log. , 79(2):355--409, 2014

2014
[12]

Bodov\' e mno z iny

Eduard C ech. Bodov\' e mno z iny . Academia Nakladatelstv\' i C eskoslovensk\' e Akademie V e d, Prague, 1966

1966

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

A fundamental dichotomy for definably complete expansions of ordered fields

Antongiulio Fornasiero and Philipp Hieronymi. A fundamental dichotomy for definably complete expansions of ordered fields. J. Symb. Log. , 80(4):1091--1115, 2015

work page 2015

[2] [2]

Tame structures and open cores

Antongiulio Fornasiero . Tame structures and open cores . arXiv e-prints , page arXiv:1003.3557, Mar 2010

work page Pith review arXiv 2010

[3] [3]

Locally o-minimal structures and structures with locally o-minimal open core

Antongiulio Fornasiero. Locally o-minimal structures and structures with locally o-minimal open core. Ann. Pure Appl. Logic , 164(3):211--229, 2013

work page 2013

[4] [4]

Relative P faffian closure for definably complete B aire structures

Antongiulio Fornasiero and Tamara Servi. Relative P faffian closure for definably complete B aire structures. Illinois J. Math. , 55(3):1203--1219 (2013), 2011

work page 2013

[5] [5]

Expansions of subfields of the real field by a discrete set

Philipp Hieronymi. Expansions of subfields of the real field by a discrete set. Fund. Math. , 215(2):167--175, 2011

work page 2011

[6] [6]

An analogue of the B aire category theorem

Philipp Hieronymi. An analogue of the B aire category theorem. J. Symbolic Logic , 78(1):207--213, 2013

work page 2013

[7] [7]

Huntington

Edward V. Huntington. Inter-relations among the four principal types of order. Trans. Amer. Math. Soc. , 38(1):1--9, 1935

work page 1935

[8] [8]

Expansions of dense linear orders with the intermediate value property

Chris Miller. Expansions of dense linear orders with the intermediate value property. J. Symbolic Logic , 66(4):1783--1790, 2001

work page 2001