{"id":"0435f70a-1ab5-4671-b79d-9cfcd27cf674","arxiv_id":"1908.01496","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Yablo's paradox, formalized as a monadic second-order sentence, is provably not equivalent to any first-order sentence or any first-order theory.","lead":"This paper proves that a formal version of Yablo's paradox, an infinite chain of sentences that seems to contradict itself, cannot be expressed in first-order logic. The proof links the paradox to a known undefinable property of directed graphs, showing that the paradox is genuinely second-order.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Core non-first-orderizability proof is sound, but the load-bearing identification of Y with Yablo's paradox is too broad: over strict linear orders Y is first-order equivalent to 'there is no maximum.'","rationale":"The central theorem is proven correctly: the reduction through the successor language and odd cycles is valid, and the compactness argument for non-finite-axiomatizability of S' is sound. I checked the step 'if Y were FO-definable then S' would be finitely axiomatizable': it is justified by Lemma 3.2 and the equivalence of theories; a finite equivalent would yield a finite subset of S' equivalent to S', which large odd cycles refute. Theorem 3.4 also follows via the standard complement-of-elementary-class lemma (van Dalen 4.2.10). The real weakness is the paper's scope. Section 2 deliberately abstracts away the order relation, and the non-FO-izability is a property of the arbitrary-relation kernel sentence, not of the usual linear-order formulation. I verified that on strict linear orders Y is equivalent to the FO sentence ∀x∃y(xRy): a kernel exists exactly when a maximum exists. Thus the natural ordering-theoretic version of Yablo's paradox is first-order expressible; the paper should explicitly restrict its title claim to the generalized formalization. The Theorem 2.3 proof has an invalid induction step (moving from θ_n(z) in the whole graph to the induced subgraph D_b), but this is not used in Section 3; it should be fixed or downgraded, which is what the reader's conditional verdict already asks. Since my main concern does not overturn the conditional verdict but sharpens the condition, I keep the reader's verdict unchanged.","tokens_in":6468,"tokens_out":27277,"duration_ms":306102,"concrete_test":"Derive the Yablo condition on strict linear orders: assume R is a strict total order and show that a set X is a kernel iff X is the singleton of the maximum element (if one exists). Then ¬Y is equivalent to ∃m∀y(y≠m → mRy) and Y is equivalent to ∀x∃y(xRy), which is first-order. This settles whether the non-first-orderizability claim extends to the natural ordering formulation: it does not.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorems of Section 3 are mathematically sound: if Y had a first-order equivalent, S' = S ∪ {¬∃x(s^{2n+1}(x)=x) : n∈N} would be finitely axiomatizable, but arbitrarily large odd cycles refute any finite axiomatization by compactness. The load-bearing gap is interpretive. In Definition 2.1 the paper replaces the 'later than' relation of Yablo's paradox with an arbitrary binary relation R, and the non-first-orderizability theorem is proved for this generalized kernel sentence. The abstraction is essential, not cosmetic. Restrict Y to the class of strict linear orders, with xRy meaning 'y is later than x.' A set X satisfies x∈X ↔ ∀y(xRy → y∉X) iff X is the singleton of a maximum element: if m is maximum, {m} works; if no maximum exists, any nonempty X gives x∈X and xRy, forcing y∉X and then some z>y in X, contradicting x∈X, while X=∅ also fails. Hence ¬Y is equivalent to 'there is a maximum' and Y is equivalent to the first-order sentence ∀x∃y(xRy). The usual order-theoretic content of Yablo's paradox is therefore first-order expressible. The result's validity depends on the deliberately non-arithmetical, arbitrary-relation formalization; the paper should state this limitation explicitly. (The induction step in Theorem 2.3 is also invalid—θ_n(z) in the full graph is transposed to the induced subgraph on D_b—but Section 3 does not use Theorem 2.3.)","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes Yablo's paradox as the second-order sentence Y := ¬∃X∀x(X(x) ↔ ∀y(xRy → ¬X(y))) over an arbitrary binary relation R. It claims that Y is not equivalent to any first-order sentence (Theorem 3.3) and not equivalent to any first-order theory (Theorem 3.4). The proof translates the problem into the language of unary functions with an injectivity axiom, connects the existence of a kernel in the associated directed graph to the absence of odd cycles, and uses a compactness argument to show that the resulting theory is not finitely axiomatizable. The paper also presents sufficient conditions under which Y is valid (Theorem 2.3).","tokens_in":6839,"tokens_out":7846,"duration_ms":73939,"significance":"The compactness argument in Section 3 is sound and establishes a genuine model-theoretic result: the statement that a directed graph has no kernel is not first-order expressible and not first-order axiomatizable. This is a valuable contribution to the model theory of directed graphs. However, the result is proved for the generalized arbitrary-relation sentence Y, not for the usual order-theoretic Yablo paradox. Over strict linear orders, Y is first-order equivalent to 'there is no maximum,' so the advertised relevance to Yablo's paradox is overstated. The paper would be strengthened by presenting the result as being about kernel existence in arbitrary directed graphs and by acknowledging this limitation explicitly. The proof of Theorem 2.3(1) also contains errors, although that theorem is not used in the main proof.","major_comments":[{"comment":"The non-first-orderizability claim is proved for the sentence Y with an arbitrary binary relation R, but the title and abstract present this as a result about Yablo's paradox. Over the class of strict linear orders—the natural formalization of the 'later than' relation—Y is first-order equivalent to ∀x∃y(xRy). Indeed, in a strict linear order, a set X satisfies the kernel condition iff it is the singleton of the maximum element when a maximum exists, and no such X exists otherwise; hence Y holds exactly when there is no maximum. Therefore the theorem does not show that the order-theoretic Yablo paradox is non-first-orderizable. The paper should state this limitation explicitly and adjust its framing accordingly; as it stands, the central claim is broader than what the proof actually supports.","section":"§2 (Definition 2.1) and §3 (Theorems 3.3–3.4)"}],"minor_comments":[{"comment":"The proof of Theorem 2.3(1) contains technical errors. In the induction step, from θ_{n+1}(a) = ∃y(aRy ∧ ∀z[yRz → θ_n(z)]) one only obtains θ_n(z) for all z with bRz, not aRz for all such z as the proof claims, and θ_n(z) is evaluated in the original graph, not in the induced subgraph on D_b. Thus the claim that ⟨D_b, R∩D_b²⟩ satisfies ∀xθ_n(x) is unsupported. In the base case, from b∉X the kernel condition yields ∃c(bRc ∧ c∈X), not c∉X as written. Since Section 3 does not depend on Theorem 2.3, these errors do not affect the main result, but the theorem's proof should be repaired or the theorem proved by a different argument.","section":"§2, Theorem 2.3(1)"},{"comment":"There are numerous typos and spacing errors, including 'Seconc-Order Logic' in the Section 2 heading, 'mathem atics' in the abstract, 'form' for 'from' in the introduction, and inconsistent spacing in 'nonfirstorderizability'. I recommend a careful proofreading pass before publication.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The core model-theoretic result (Theorems 3.3 and 3.4) is correct and interesting, but the advertised connection to Yablo's paradox is substantially overstated. The result is really about the non-first-orderizability of kernel existence in arbitrary digraphs, and the paper should be reframed accordingly. The flawed proof of Theorem 2.3(1) also needs correction, though it is not load-bearing. If the author is willing to make these changes, the paper could be a solid contribution to the model theory of graphs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The compactness argument in Section 3 is sound. If Y had a first-order equivalent, then S' would be finitely axiomatizable, and arbitrarily large odd cycles kill that. Lemma 3.2 checks out. The paper earns its keep as a short note on why kernel existence is not first-order definable, framed through a Yablo-like second-order sentence.\n\nWhat's genuinely new is the packaging: the connection between Yablo's paradox and graph kernels hasn't been made this way before, and the proof is self-contained. The writing is clear and the historical framing is pleasant.\n\nThe soft spots are real, and one is load-bearing for the title. Definition 2.1 deliberately replaces 'later than' with an arbitrary binary relation R. That's a big abstraction. On a strict linear order, the sentence Y is first-order equivalent to 'there is no maximum' (and ¬Y to 'there is a maximum'). I checked the odd-cycle argument in the stress-test; it's right. So the original Yablo paradox, with the usual 'later than' on the natural numbers, is first-order expressible. What the paper proves is non-first-orderizability of the generalized kernel sentence on arbitrary directed graphs. The author needs to say this plainly, and the title should be softened.\n\nThere's also a smaller technical flaw: the proof of Theorem 2.3(1) has a bad induction step. It slides from θ_{n+1} giving θ_n(z) for successors z of a chosen b to a conclusion about the induced subgraph on D_b, which doesn't follow. Theorem 2.3 is not used in the main proof, so the core result stands, but the author should fix or flag it.\n\nThe citation pattern is fine. The author cites relevant prior work on Yablo and non-first-orderizability; the kernel fact is attributed properly.\n\nBottom line: this is a correct and useful note on the model theory of graph kernels, but as a statement about Yablo's paradox it overreaches. A serious referee can send it back for revision: fix the induction proof, and add a section discussing the linear-order case. I'd take it to our reading group; the gap between the advertised result and the proved one is instructive.\n\nRecommendation: accept peer review, expect heavy revision.","headline":"Correct compactness proof for non-first-orderizability of a kernel sentence, but the identification with Yablo's paradox is too broad: over strict linear orders Y is first-order, so the headline claim needs qualification.","tokens_in":7290,"tokens_out":3215,"would_cite":true,"duration_ms":34425,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B05","03B10","03C07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Yablo's paradox, formalized in second-order logic, cannot be captured by any first-order sentence or theory.","keywords":["Yablo's paradox","non-first-orderizability","second-order logic","model theory","directed graph kernel","successor theory","axiomatizability","paradox as proof"],"falsifier":"A concrete way to test the claim: find a first-order sentence $\\eta$ in the language $\\{R\\}$ such that $\\eta\\leftrightarrow Y$ holds in every structure, or a first-order theory whose models are exactly the directed graphs satisfying $Y$. Equivalently, exhibit a finite axiomatization of the theory of a successor function with no odd cycles; the paper proves none exists, so such an exhibit would overturn Theorem 3.3.","tokens_in":6306,"feed_emoji":"🧩","tokens_out":6313,"duration_ms":55364,"temperature":0.7,"pith_summary":"Yablo's paradox is usually told as an infinite list of sentences, each saying that all later sentences are false. This paper proves that if the paradox is formalized as a second-order sentence about an arbitrary binary relation—the sentence asserts that no subset can be a 'kernel' in the associated directed graph—then it is not equivalent to any first-order sentence, or even to any infinite first-order theory. The proof translates the sentence into the language of a successor function, where models break into copies of the naturals, the integers, and finite cycles, and shows that the induced theory is axiomatizable but only by an infinite list of axioms. The upshot is a precise model-theoretic sense in which the paradox is genuinely second-order in nature, not just a puzzle that happens to be phrased with second-order quantifiers.","feed_headline":"Yablo's paradox provably escapes first-order logic","feed_subtitle":"A model-theoretic proof shows neither a sentence nor an infinite theory can express its content.","key_machinery":"The load-bearing object is the second-order sentence $Y$ together with its translation $Y^s$ into the language of a unary successor function. On any model of the successor axiom $\\forall x,y\\,(s(x)=s(y)\\to x=y)$, the universe splits into disjoint copies of $\\mathbb{N}$, $\\mathbb{Z}$, and finite cycles; a subset $K$ is a kernel (every element is in $K$ iff its successor is not) exactly when no odd cycle is present. That equivalence turns the question of whether $Y$ is first-order expressible into the question of whether the theory $\\{\\neg\\exists x\\,s^{2n+1}(x)=x\\}_{n\\in\\mathbb{N}}$ is finitely axiomatizable, and it is not: arbitrarily large odd cycles witness the failure of each finite subtheory.","core_discovery":"The paper's central claim is that the second-order sentence $Y$, defined as $\\neg\\exists X\\,\\forall x\\,(X(x)\\leftrightarrow \\forall y\\,[xRy\\to \\neg X(y)])$, is not logically equivalent to any first-order sentence in the language of the binary relation $R$ (Theorem 3.3), and not equivalent to any first-order theory whatsoever (Theorem 3.4). The sentence says that no subset of the universe can contain exactly the elements whose $R$-successors all lie outside it—that is, that the directed graph $\\langle D;R\\rangle$ has no kernel. The proof shows that after replacing $xRy$ by $s(x)=y$, the negation of the translated sentence says that a model of the successor axioms has a kernel, which exists exactly when the model has no odd cycles; the theory of 'successor with no odd cycles' is not finitely axiomatizable. Consequently any first-order approximation to $Y$ would have to either miss some model or admit some unwanted model.","pith_inferences":["If the generalized relation $R$ is essential to the proof, the theorem does not directly settle whether first-order treatments that build in the actual natural-number ordering of Yablo's original list are first-order definable; the paper's formulation deliberately abstracts away the order.","The same model-theoretic template—translate a paradox into a non-finitely-axiomatizable theory and invoke compactness—could apply to other infinite, non-self-referential paradoxes, isolating the order-type or graph property that generates the expressive gap.","One testable extension is to ask whether the conjecture that $\\neg Y$ is also not first-order-theory-equivalent holds; a counterexample would need a first-order theory whose models are precisely the directed graphs that possess a kernel.","For finite directed graphs, kernel existence is a combinatorial property whose first-order undefinability can be checked on arbitrarily large odd and even cycles; this gives a concrete finite-model-theoretic version of the result."],"forward_implications":["No first-order sentence or theory over the language of directed graphs can have exactly the same models as the second-order Yablo sentence; any first-order surrogate either admits a directed graph with no kernel or excludes one with a kernel.","The existence of a kernel in a directed graph, and the non-existence of such a kernel, are properties that are not first-order definable, since $\\neg Y$ is exactly the assertion that a kernel exists.","Formalizing Yablo's paradox as $Y$ does not by itself make a contradiction or a tautology; some condition on $R$ (such as $\\forall x\\exists y\\,(xRy\\wedge\\forall z\\,[yRz\\to xRz])$) is required to force the paradox.","The paradox yields a theorem of the same kind as Russell's or Liar's paradoxes: a logical impossibility result, here about the expressive boundary between first- and second-order logic."],"supporting_citations":[{"why":"Defines kernel of a directed graph, the combinatorial property equivalent to $\\neg Y$.","marker":"[1]"},{"why":"Defines the sense of non-first-orderizability (Boolos) that the paper uses.","marker":"[2]"},{"why":"Reinforces the criterion for when a second-order sentence cannot be replaced by a first-order one.","marker":"[3]"},{"why":"Supplies the non-arithmetical formulation of Yablo's paradox that motivates replacing the order relation by an arbitrary binary relation.","marker":"[6]"},{"why":"Provides sufficient conditions on R under which Yablo's sentence becomes a theorem.","marker":"[9]"},{"why":"Provides the model-theoretic lemmas connecting finite axiomatizability with equivalence to a first-order theory.","marker":"[11]"},{"why":"Source of Yablo's original formulation of the paradox in 'Truth and Reflection'.","marker":"[13]"},{"why":"Source of the self-reference-free version of Yablo's paradox that the paper formalizes.","marker":"[14]"}],"fun_headline_variants":["Yablo's paradox provably resists first-order logic","No first-order theory can capture Yablo's paradox","Proof: Yablo's paradox is inherently second-order","Yablo's paradox cannot be first-order defined"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that replacing the natural 'later than' ordering in Yablo's paradox with an arbitrary binary relation $R$ preserves the paradox's content; if the paradox only arises for the genuine ordering of the natural numbers, the non-first-orderizability proof would not apply to that standard formulation.","fun_headline_variants_meta":{"raw":{"variants":["Yablo's paradox provably resists first-order logic","No first-order theory can capture Yablo's paradox","Proof: Yablo's paradox is inherently second-order","Yablo's paradox cannot be first-order defined"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000808,"raw_usage":{"total_tokens":3548,"prompt_tokens":945,"completion_tokens":2603,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":2540}},"tokens_in":561,"tokens_out":2603,"duration_ms":17043,"temperature":1.0,"reasoning_tokens":2540,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:13:09.897292+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete way to test the claim: find a first-order sentence $\\eta$ in the language $\\{R\\}$ such that $\\eta\\leftrightarrow Y$ holds in every structure, or a first-order theory whose models are exactly the directed graphs satisfying $Y$. Equivalently, exhibit a finite axiomatization of the theory of a successor function with no odd cycles; the paper proves none exists, so such an exhibit would overturn Theorem 3.3.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines kernel of a directed graph, the combinatorial property equivalent to $\\neg Y$."},{"cited_title":"doi: 10.2307/2026308 Reprinted in: Boolos, G.; Logic, Logic and Logic (isbn: 9780674537668) Harvard University Press (1998) pp","cited_arxiv_id":null,"evidence_quote":"Defines the sense of non-first-orderizability (Boolos) that the paper uses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Reinforces the criterion for when a second-order sentence cannot be replaced by a first-order one."},{"cited_title":"doi: 10.1093/analys/anw062","cited_arxiv_id":null,"evidence_quote":"Supplies the non-arithmetical formulation of Yablo's paradox that motivates replacing the order relation by an arbitrary binary relation."},{"cited_title":"doi: 10.1007/s11229-005-6201-6","cited_arxiv_id":null,"evidence_quote":"Provides sufficient conditions on R under which Yablo's sentence becomes a theorem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the model-theoretic lemmas connecting finite axiomatizability with equivalence to a first-order theory."},{"cited_title":"doi: 10.1007/BF00249368","cited_arxiv_id":null,"evidence_quote":"Source of Yablo's original formulation of the paradox in 'Truth and Reflection'."},{"cited_title":"doi: 10.1093/analys/53.4.251","cited_arxiv_id":null,"evidence_quote":"Source of the self-reference-free version of Yablo's paradox that the paper formalizes."}],"review_version":1}