{"id":"00f98809-9754-4350-9d27-490fc26180c0","arxiv_id":"2411.17739","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The elementary theory of the Young-Fibonacci lattice is undecidable and non-finitely axiomatizable, and the lattice with a constant for 2 has the maximal definability property.","lead":"This paper proves that the first-order theory of the Young-Fibonacci lattice is undecidable and not finitely axiomatizable, by defining addition and multiplication inside the lattice. It also shows that the lattice with a constant for the element 2 has the maximal definability property, meaning every relation on the lattice is first-order definable.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 6's parent-set injectivity is asserted without proof; the singleton-definability induction collapses if any two rank-n vertices share a parent set.","rationale":"The reader's conditional verdict is well calibrated. Re-deriving the parent relation for a word w=2^r s shows that the parent set consists of the r words 2^{i-1}1 2^{r-i}s (i=1..r) together with 2^r t when s=1t, and for r=0 the unique parent is s. From this characterization the map w↦parents is injective for rank≥3, with the only rank-2 collision being {2,11}. Thus the asserted 'easy to notice' claim is true, but it is exactly the bridge that makes the induction in Proposition 6 work, and it is not proved in the text. Other potential concerns are weaker: the transfer from YF* to YF can be justified because {2,11} is definable and its two elements have the same 1-type, so decidability of Th(YF) would imply decidability of Th(YF*); Proposition 38 follows from the already-interpreted arithmetic since the nth-prime exponent relation is arithmetical. Therefore the missing lemma in Proposition 6 is the single load-bearing soft spot. A brute-force rank enumeration plus the simple case analysis would settle it and should be added before publication.","tokens_in":150,"tokens_out":23040,"duration_ms":816325,"concrete_test":"Enumerate all words over {1,2} with digit-sum n for n=3 through 20, compute parents by (a) replacing any 2 in the leading run of 2s by 1, and (b) deleting the leftmost 1 if present, and test whether the map w↦set-of-parents is injective on each rank. Equivalently, write a short proof from the characterization that if w=2^r s, the parent set determines r and s, and if r=0 the parent set is {tail(w)}. If the enumeration finds a collision, Proposition 6 and the main theorems fail; if not, the missing lemma should be added as an explicit proof before publication.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 6 builds the formula id_u(v) on the unproved assertion that for |u|=n≥3 no other rank-n vertex has the same set of parents. The proof only says 'it is easy to notice'. This assertion is load-bearing: the displayed formula defines the class of vertices whose parent set is exactly {u_1,...,u_k}, and without injectivity this class is not {u}. The induction therefore does not go through as written. The property is presumably true: writing w=2^r s, the parents are the r words obtained by replacing one initial 2 by 1, plus the word obtained by deleting the first 1 when s contains a 1, and for r=0 the unique parent is s. This data determines r and s for rank at least 3, with the only rank-2 collision being {2,11}. But none of this reasoning appears in the paper. Since every later definability result and both main theorems rely on Proposition 6, the proof is incomplete at exactly this point.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to prove that the elementary theory of the Young–Fibonacci lattice is undecidable and non-finitely axiomatizable (Theorem 2), and that the structure ⟨YF, ⩾, 2⟩ has the maximal definability property (Theorem 3). The proof strategy follows Wires's work on Young's lattice: the author first defines singletons and then defines addition and multiplication on the subset {1^n : n ≥ 0}, obtaining an interpretation of arithmetic in YF*. Undecidability is then transferred from Matiyasevich's theorem, and maximal definability is obtained by constructing a definable bijection b: YF → N0 and importing a definability result for the prime-exponent relation from Wires's paper.","tokens_in":9728,"tokens_out":34696,"duration_ms":289571,"significance":"If the proof is completed, the paper would extend Wires's undecidability and maximal-definability results from Young's lattice to the Young–Fibonacci lattice, a natural and widely studied differential poset. The overall architecture is plausible and the paper contains many explicit definability formulas, which is a strength. However, several load-bearing structural assertions are either unproved or imported without justification, and numerous displayed formulas contain apparent typos or undefined symbols. The central ideas are promising, but the manuscript in its current form is not self-contained enough for the claims to be accepted as proven.","major_comments":[{"comment":"Proposition 6 asserts, with only 'it is easy to notice', that for |u| = n ≥ 3 no other rank-n vertex has the same set of parents. This injectivity is load-bearing: the displayed formula id_u(v) defines the class of vertices whose set of lower covers is exactly {u_1, ..., u_k}, and without injectivity this class may be strictly larger than {u}. The induction defining all singletons therefore collapses, and with it the interpretation of arithmetic used for Theorems 1 and 2. A rigorous proof must be supplied, including the exact treatment of words with no digit 1, since the parent-set computation depends on the convention for such words.","section":"Proposition 6"},{"comment":"Proposition 38, the definability of the prime-exponent relation, is imported from Wires [5, section 4] with no proof and no explanation of why a result for Young's lattice transfers to Young–Fibonacci lattice. This proposition is used essentially in Propositions 44, 47, and 48 to define the bijection b and to prove Theorem 3. The author should either prove Proposition 38 directly from the already-established addition and multiplication definability (e.g., via a standard arithmetic coding of exponentiation and divisibility) or state precisely which theorem of Wires applies to YF and why.","section":"Proposition 38"},{"comment":"Theorem 1 establishes undecidability of the Σ_{m+1}-theory of YF*, the structure with constant 2, while Theorem 2 claims undecidability of the elementary theory of YF, the structure without that constant. Since {2} is not definable in YF (as the automorphism in Remark 2 shows), undecidability of Th(YF*) does not automatically imply undecidability of Th(YF). The proof as written only cites [4] and does not supply the needed reduction. One can repair this by observing that for every formula φ(2), YF* ⊨ φ(2) iff YF ⊨ ∀x(Def_{2,11}(x) → φ(x)), but this argument is absent and must be added for Theorem 2 to follow.","section":"Theorems 1 and 2"}],"minor_comments":[{"comment":"The terminology 'u is a child of v' is confusing because the formula r(u,v) has u ≥ v, so u is the upper cover; later 'parents' are identified with lower covers. Please adjust the terminology or clarify the intended reading.","section":"Proposition 2"},{"comment":"The displayed formula for ϕ_{1n,2n} contains the undefined symbol ϕ'_2; it should presumably be ϕ'_{1n,2n} from Proposition 16.","section":"Proposition 17"},{"comment":"As typeset, the formula for ϕ# uses ϕ_{2n,2n+1}(w,w') after fixing w' by ϕ_{1n,2n}(u,w'), which forces w' = 2^n and w' = 2^{n+1} simultaneously; the variable order or the relation used needs to be corrected.","section":"Proposition 20"},{"comment":"The formula for ϕ_r(u) contains 'u ⩾̸ v' where r(u,v) already implies u ≥ v, making the conjunct false; the intended condition is probably 'v ⩾̸ w' to express that the two parents are distinct.","section":"Proposition 25"},{"comment":"The exponent notation 'nm−1/2(m2−m)' is ambiguous; please add parentheses, e.g., nm − (m^2 − m)/2, to clarify the intended exponent.","section":"Remark 6 and Proposition 34"},{"comment":"The paper never defines 'maximal definability property'; a precise definition or a direct reference to Wires's definition should be included so that Theorem 3 is meaningful to the reader.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The overall strategy is credible and the gaps I identified seem repairable. However, the current manuscript has several unproved structural assertions and a number of apparent typos in formulas that are central to the definability constructions. I recommend major revision rather than rejection, since the main architecture is sound and the missing pieces are likely fillable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Glad you sent this. The paper proves the natural Young-Fibonacci analogue of Wires's theorem: the elementary theory of the Young-Fibonacci lattice is undecidable and non-finitely axiomatizable, and moreover ⟨YF, ⩾, 2⟩ has the maximal definability property. That is a real result, and it is not a routine translation of Wires: the lattice has a nontrivial automorphism swapping 2 and 11, so the paper adds a constant and rebuilds the definability machinery around it. The long chain of formulas defining order, rank, digit counts, addition, and multiplication on the chain of 1^n's is the right strategy, and I spot-checked enough of them to believe the architecture is sound.\n\nThe soft spots are real. Proposition 6, the singleton-definability induction, depends on an unproved assertion that distinct vertices of the same rank n≥3 have distinct parent sets. The proof says 'it is easy to notice' and leaves it at that. The stress-test note is right: if that injection fails, the induction collapses. The assertion is very likely true (the parent set determines the word via the count of initial 2s and the presence of a 1), but the argument has to be written out because every later definability claim rests on it.\n\nSecond, Proposition 38 — definability of the prime-exponent relation — is imported from Wires's paper with a one-line 'it follows'. That is not enough. Wires proved it for Young lattice, and the transfer to Young-Fibonacci needs at least a sketch. It may be that the paper's own definability of b supplies it, but the text doesn't show the work.\n\nThird, Theorem 2 claims undecidability for the theory of YF itself, while the interpretation is built in YF* (with a constant for 2). The transfer from YF* to YF is asserted via [4] but not explained. Since the constant is not definable without the automorphism, this step is not automatic and needs a proper argument.\n\nNone of this sinks the paper. The gaps are fillable, and the main claim is plausible. But as it stands the proof is incomplete at exactly the points that matter. A serious referee should be engaged; with a proper rewrite this could be a solid paper.","headline":"The Young-Fibonacci analogue of Wires's theorem is likely correct and the strategy is right, but two unproved load-bearing assertions and a terse transfer step mean the paper needs a serious referee and a careful revision before I'd trust the proof.","tokens_in":10243,"tokens_out":5380,"would_cite":false,"duration_ms":48898,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B25","06B99"],"pacs":[],"model":"deepseek-v4-flash","headline":"The elementary theory of the Young–Fibonacci lattice is undecidable and not finitely axiomatizable.","keywords":["Young–Fibonacci lattice","elementary theory","undecidability","first-order definability","maximal definability property","interpretation of arithmetic","graded lattice","domino tilings"],"falsifier":"Enumerate the immediate predecessors of all words of a fixed digit sum $n\\ge 3$ in the Young–Fibonacci lattice and compare the predecessor sets; if any two distinct words share the same set, the proof of Proposition 6 fails, and with it the arithmetic interpretation that carries both main theorems.","tokens_in":9370,"feed_emoji":"","tokens_out":13876,"duration_ms":119506,"temperature":0.7,"pith_summary":"The paper aims to establish that the first-order theory of the Young–Fibonacci lattice is undecidable and not finitely axiomatizable, and that the lattice becomes 'maximally definable' once a constant for the word $2$ is added to the language. The lattice is the graded poset of finite words over $\\{1,2\\}$ ordered by a suffix-removal rule, with rank equal to the digit sum. The proof encodes the natural numbers as the words $1^n$ and defines addition and multiplication on them inside the lattice language, so the known undecidability of arithmetic transfers to the lattice theory. If correct, no algorithm can decide the truth of first-order sentences about this natural combinatorial structure, and every relation on the lattice is definable. This matters because the Young–Fibonacci lattice is one of only two $1$-differential modular lattices, making it a central object in the study of graded lattices and their logical complexity.","feed_headline":"Young-Fibonacci lattice theory is undecidable","feed_subtitle":"Every arithmetical truth can be encoded as a sentence about the lattice, so no algorithm can decide them.","key_machinery":"The load-bearing mechanism is a first-order interpretation of arithmetic on the spine formed by the vertices $1^n$ for $n\\ge 0$ in the Young–Fibonacci lattice. The paper first defines the child relation and the set of words with no digit $2$; with the constant $2$ it can separate the otherwise indistinguishable words $2$ and $11$, define the families $1^n$, $1^n2$, $1^n21$, and then use order and length formulas to express digit counts, addition, and multiplication on the $1^n$ chain. The undecidability of the positive $\\Sigma_1$-theory of arithmetic then transfers to the theory of $\\langle YF,\\geqslant,2\\rangle$. The secondary mechanism is the bijection $b$ from words to natural numbers, built from the prime factorization of the block structure of a word; showing this bijection is definable gives the maximal definability property.","core_discovery":"The paper's central claim, stated as Theorem 2 and Theorem 3, is that the elementary theory of the Young–Fibonacci lattice is undecidable and non-finitely axiomatizable, while the structure $\\langle YF,\\geqslant,2\\rangle$ has the maximal definability property. The proof works by interpreting the arithmetic structure $\\langle\\mathbb{N}_0,+,\\times\\rangle$ in the lattice: the vertices $1^n$ are used as the numbers, and the paper builds first-order formulas that express $n=m+\\ell$ and $n=m\\ell$ for these vertices. Because the positive $\\Sigma_1$-theory of arithmetic is undecidable, the lattice theory inherits undecidability; completeness then gives non-finite axiomatizability. For maximal definability, the paper defines a bijection $b:YF\\to\\mathbb{N}_0$ from the lattice onto the natural numbers and shows it is first-order definable, which makes every subset of every power of the lattice definable.","pith_inferences":["The same encoding strategy may work for any graded lattice with a definable unbounded chain that behaves like the $1^n$ spine; the paper's formula constructions are a template for such transfers.","Since the constant $2$ is needed only to break the automorphism swapping $2$ and $11$, the pure poset language $\\langle YF,\\geqslant\\rangle$ alone may still be undecidable but would require a separate argument that treats the two vertices symmetrically.","The bijection $b$ from words to numbers may give a way to compute the definability rank of particular lattice subsets by reading off the complexity of the corresponding number-theoretic predicates, if the quantifier complexity of the bijection formulas is analyzed."],"forward_implications":["No algorithm can decide the truth of arbitrary first-order sentences about the Young–Fibonacci lattice.","The theory has no finite axiomatization, so no finite list of axioms captures all its true sentences.","The expanded structure $\\langle YF,\\geqslant,2\\rangle$ can define every relation on the lattice, not just order and equality.","The explicit formulas for addition and multiplication give a translation from arithmetical sentences to lattice sentences, making concrete undecidable problems available in the lattice language."],"supporting_citations":[{"why":"supplies the template for encoding arithmetic into a Young-type lattice and the notion of maximal definability that this paper transfers to the Young–Fibonacci lattice.","marker":"[5]"},{"why":"supplies the undecidability of the positive $\\Sigma_1$-theory of arithmetic, the target of the interpretation.","marker":"[3]"},{"why":"supplies the transfer theorem used to move undecidability from the interpreted arithmetic to the complete elementary theory of the lattice.","marker":"[4]"}],"fun_headline_variants":["Undecidable theory for Young-Fibonacci lattice","No algorithm can decide Young-Fibonacci lattice sentences","Young-Fibonacci lattice: no finite axiom set","Arithmetic interpretation makes Young-Fibonacci undecidable","First-order logic of Young-Fibonacci lattice is undecidable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that every vertex is first-order definable rests on the assertion, justified in the paper only by 'it is easy to notice,' that no two distinct words with the same digit sum $n\\ge 3$ ever have the same set of immediate predecessors; if that assertion fails, the induction defining singletons collapses and with it the interpretation of arithmetic.","fun_headline_variants_meta":{"raw":{"variants":["Undecidable theory for Young-Fibonacci lattice","No algorithm can decide Young-Fibonacci lattice sentences","Young-Fibonacci lattice: no finite axiom set","Arithmetic interpretation makes Young-Fibonacci undecidable","First-order logic of Young-Fibonacci lattice is undecidable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001859,"raw_usage":{"total_tokens":7251,"prompt_tokens":844,"completion_tokens":6407,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":460,"completion_tokens_details":{"reasoning_tokens":6327}},"tokens_in":460,"tokens_out":6407,"duration_ms":43235,"temperature":1.0,"reasoning_tokens":6327,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:57:05.630655+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate the immediate predecessors of all words of a fixed digit sum $n\\ge 3$ in the Young–Fibonacci lattice and compare the predecessor sets; if any two distinct words share the same set, the proof of Proposition 6 fails, and with it the arithmetic interpretation that carries both main theorems.","supporting_citations":[{"cited_title":"Annals of Pure and Applied Logic 173 (2022), paper 103075","cited_arxiv_id":null,"evidence_quote":"supplies the template for encoding arithmetic into a Young-type lattice and the notion of maximal definability that this paper transfers to the Young–Fibonacci lattice."},{"cited_title":"MIT Press, Cambridge, 1993","cited_arxiv_id":null,"evidence_quote":"supplies the undecidability of the positive $\\Sigma_1$-theory of arithmetic, the target of the interpretation."},{"cited_title":"Robinson,Undecidable The- ories","cited_arxiv_id":null,"evidence_quote":"supplies the transfer theorem used to move undecidability from the interpreted arithmetic to the complete elementary theory of the lattice."}],"review_version":1}