{"id":"4308545c-95c9-45bf-b078-10eda5689897","arxiv_id":"1908.02708","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Double-membership graphs of countable models of Anti-Foundation come in continuum-many isomorphism types, and their complete theories are classified by collections of consistency statements.","lead":"This paper studies the graphs made by linking two sets when each belongs to the other, inside models of Anti-Foundation set theory, where circular membership is allowed. It proves such graphs come in continuum-many non-isomorphic forms, classifies their complete theories, and shows that some elementarily equivalent graphs cannot arise this way.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.7 does not verify that the Hodges translation θ′ lies in Φ; Lemma 4.5 may fail for asymmetric θ′, but conjoining symmetry repairs the proof.","rationale":"The reader's weakest_assumption (AFA) is actually the intended hypothesis and is used only through its existence part, not uniqueness; Proposition 2.3 is the engine and is sound. The only soft spot I find is the unstated Φ hypothesis in Corollary 4.7. It is a proof gap, not a counterexample to the theorems. The fix is straightforward, so the verdict should remain ACCEPT. I agree partially with the reader: they noticed the same point as minor.","tokens_in":12488,"tokens_out":41300,"duration_ms":425325,"concrete_test":"Re-derive Corollary 4.7 with ϕ := θ′∧Sym, where Sym is ∀x∀y(D(x,y)→D(y,x)). Check that (a) Con(θ) iff Con(θ′∧Sym) using Fact 4.6, and (b) Lemma 4.5 applies because the conjunction is in Φ. If both hold, the concern is settled and no substantive change is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central characterization in Theorem 4.14 (elementary equivalence of D-graphs iff same consistency statements) passes through Corollary 4.7, which applies Lemma 4.5 to ϕ := θ′. Lemma 4.5 is only proved for ϕ ∈ Φ, i.e. sentences implying ∀x∀y(D(x,y)→D(y,x)). The translation θ′ from Fact 4.6 need not imply symmetry: a consistent asymmetric digraph sentence (e.g. ∃x∃y(E(x,y)∧¬E(y,x))) translates to an L1-sentence satisfiable in non-symmetric L1-structures. For such ϕ, M⊨Con(ϕ) does not imply M1⊨µ(ϕ), because a neighbour set in the symmetric relation D cannot be a model of an asymmetric sentence. Thus the proof of (2)⇔(3) in Theorem 4.14, and Corollaries 4.8/4.11 that use Corollary 4.7, contain a genuine gap. The gap is not fatal: replacing θ′ by θ′∧∀x∀y(D(x,y)→D(y,x)) preserves consistency equivalence, since the standard graph interpretation of any digraph is symmetric, and all subsequent uses go through unchanged.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the double-membership graphs (D-graphs) and single-double-membership graphs (SD-graphs) of models of ZFA, i.e. the reducts obtained from the relations x∈y∧y∈x and its symmetrization. The main results are: (i) a characterization of the connected components of D-graphs as exactly the metatheoretic connected components of graphs in the sense of M, each appearing infinitely often (Theorem 2.4); (ii) the existence of 2^ℵ0 non-isomorphic countable D-graphs elementarily equivalent to a given one, and 2^ℵ0 countable models of each of their theories (Corollary 3.5); (iii) the incompleteness of the common theory of D-graphs and a description of its completions in terms of consistency statements (Theorem 4.14, Corollary 4.15); and (iv) a negative answer to the question whether every countable structure elementarily equivalent to an SD-graph (or D-graph) of a model of ZFA is itself such a reduct (Corollary 4.17). The proofs use the Solution Lemma form of AFA, type-counting, and Ehrenfeucht-Fraïssé games.","tokens_in":12650,"tokens_out":11091,"duration_ms":109503,"significance":"If the results hold, they substantially advance the model-theoretic study of non-well-founded set-theoretic graphs initiated in [ADC17], giving a structural description of connected components and a classification of the theories involved in terms of consistency statements. The paper also contains a negative result showing that the class of D-graphs (and SD-graphs) is not closed under elementary equivalence among countable structures, and that these theories are wild from the neostability perspective. A particular strength is the use of the Solution Lemma to transfer arbitrary internal graphs into actual connected components, and the self-contained EF-game argument in Theorem 4.16. The proofs are detailed and largely self-contained, with standard references cited for background facts. However, one load-bearing step in the consistency-statement correspondence is not proved as stated, as detailed below.","major_comments":[{"comment":"The proof of Corollary 4.7 applies Lemma 4.5 to ϕ := θ′, but Lemma 4.5 is proved only for ϕ ∈ Φ, i.e., L1-sentences that imply ∀x∀y(D(x,y)→D(y,x)). Fact 4.6 does not guarantee that θ′ lies in Φ: an LNBG-sentence such as ∃x∃y(E(x,y)∧¬E(y,x)) is consistent and has no symmetric model, so its translation θ′ is consistent in L1 but is not in Φ. For such θ′, M⊨Con(θ) need not imply M1⊨μ(θ′), because the neighbour set of any point in M1 is symmetric. Consequently the proof of the equivalence (2)⇔(3) in Theorem 4.14, as well as Corollaries 4.8, 4.11, and 4.15, is incomplete as written. This is repairable: replacing θ′ by θ′∧∀x∀y(D(x,y)→D(y,x)) preserves consistency equivalence, since the graph interpretation in Fact 4.6 is always symmetric, and brings the sentence into Φ. The authors should state this modification explicitly and verify that all later applications go through with the strengthened sentence.","section":"§4, Corollary 4.7"}],"minor_comments":[{"comment":"The definition 'r_j := (3j−1)/2' appears to be a typo; the subsequent inclusion argument requires r_{j+1} ≥ 3r_j+1, which holds for r_j = (3^j−1)/2, not for the linear expression written.","section":"§4, Theorem 4.16"},{"comment":"The phrase 'models of ZFC with Foundation replaced by AFA1' should be 'models of ZFC without Foundation and with AFA1' to avoid ambiguity about whether Foundation is kept.","section":"§1, Remark 1.3"},{"comment":"The notation '~ψ' for the associated arithmetical statement is awkward; using a tilde accent (e.g. ψ̃) or a different symbol would improve readability.","section":"§4, Fact 4.10"}],"recommendation":"major_revision","confidential_remarks":"The gap in Corollary 4.7 is localized and easily fixed by conjoining the symmetry axiom, so the central claims are very likely correct. I recommend major revision rather than rejection. The r_j typo in Theorem 4.16 should also be corrected. The paper is otherwise well-organized and the arguments are substantive."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper is worth a look. It answers open questions from Adam-Day and Cameron's earlier work: what the connected components of double-membership graphs of models of ZFA look like, how many countable such graphs there are, and what their complete theories are. The answers are genuinely new: up to isomorphism the components are exactly the connected components of graphs living inside the model, there are continuum-many countable D-graphs, and two D-graphs are elementarily equivalent iff their parent models satisfy the same consistency statements. The machinery is standard but deployed with care: the Solution Lemma, type-counting via flowers and bouquets, Ehrenfeucht-Fraïssé games, and Rieger permutations. The paper is well written and mostly self-contained.\n\nThe one real soft spot is Corollary 4.7. Lemma 4.5 is proved only for sentences that imply the symmetry of D. The Hodges translation θ′ from digraphs to graphs does not generally imply symmetry; it can be satisfied by non-symmetric L1-structures. So \"apply Lemma 4.5 to θ′\" is not legitimate as written. The fix is easy: replace θ′ by θ′∧∀x∀y(D(x,y)→D(y,x)). Consistency is preserved because the graph interpretation of any digraph is symmetric, and µ is unchanged on symmetric neighbor sets. This patch repairs the proof of Theorem 4.14 and the corollaries that depend on it. It is a genuine gap but a minor one.\n\nThe rest of the proofs look solid. The type-counting argument in Section 3 is clean, and the EF-game argument has the symmetry issue handled explicitly at the point it matters. The paper's claims about neostability follow from the same machinery. No circularity: the new results are derived from ZFA and standard model theory, not repackaged from the earlier paper.\n\nWho should read this: people working on non-well-founded set theory and the model theory of reducts of set-theoretic structures. It is niche, but the results answer explicit open questions and the proofs are writeable. I would send it to a referee; with the Corollary 4.7 patch it is publishable essentially as is.","headline":"A well-written, niche paper with genuinely new results and one easily fixed proof gap in Corollary 4.7.","tokens_in":13229,"tokens_out":9275,"would_cite":true,"duration_ms":96319,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03C62","03C13","03E30","03E65"],"pacs":[],"model":"deepseek-v4-flash","headline":"The double-membership graph of a model of Anti-Foundation has exactly the connected components of the graphs that live inside that model, and its complete theory is the set of consistency statements the model satisfies.","keywords":["Anti-Foundation Axiom","double-membership graph","non-well-founded set theory","consistency statements","Ehrenfeucht-Fraïssé games","regions","reducts of set theory","neostability"],"falsifier":"Find a model M of ZFA whose D-graph has a connected component not isomorphic to any connected component of a graph internal to M, which would falsify Theorem 2.4; or find two models M and N of ZFA satisfying exactly the same consistency statements whose D-graphs are not elementarily equivalent, which would falsify Theorem 4.14.","tokens_in":12216,"feed_emoji":"🕸️","tokens_out":6140,"duration_ms":63811,"temperature":0.7,"pith_summary":"This paper studies the graph obtained from a model of the set theory ZFA (ZFC with the Axiom of Foundation replaced by Anti-Foundation) by joining two sets x and y with an edge exactly when x ∈ y and y ∈ x. The main structural result is that, up to isomorphism, the connected components of this double-membership graph are precisely the connected components (computed in the metatheory) of graphs that exist inside the model, and that each such component occurs infinitely often. The paper also proves that the first-order theory of such a graph is completely determined by which consistency statements the underlying model satisfies: two D-graphs are elementarily equivalent exactly when their models of ZFA satisfy the same consistency statements. This yields continuum-many non-isomorphic countable D-graphs, continuum-many countable models of each of their theories, and countable elementarily equivalent graphs that are not D-graphs of any model of ZFA.","feed_headline":"Double-membership graph components come from inside the model","feed_subtitle":"An edge means x∈y∈x; internal graphs determine the components, and theories reduce to consistency statements.","key_machinery":"The two load-bearing devices are flat systems of equations and regions. Anti-Foundation in the form of the Solution Lemma (Definition 1.1) says every flat system {x_i = S_i} has a unique solution; Proposition 2.3 uses this to turn any graph G internal to M into an isomorphic copy of G inside M1 that is a union of regions and is an M-set, where the region of a is the set of points reachable from a by D in the sense of M. This one proposition carries the component classification and also, via the sentence μ(φ) = 'there is a loopless point whose neighbours form a model of φ', translates internal consistency statements into first-order sentences of the graph. The proof of Theorem 4.14 then runs an Ehrenfeucht-Fraïssé game in which the Duplicator answers each move by replicating the ≡k-class of a region, using Lemma 4.5 to replace an internal graph satisfying φ by an isomorphic union of regions in the other model.","core_discovery":"The central discovery is a precise correspondence between the external double-membership graph M1 of a model M of ZFA and the internal graphs of M. Theorem 2.4 states that the connected components of M1, taken in the metatheory, are up to isomorphism exactly the connected components of graphs in the sense of M, each appearing infinitely often. The second main theorem, Theorem 4.14, states that for models M and N of ZFA, M1 ≡ N1 if and only if M and N satisfy the same consistency statements—i.e. the same sentences of the form 'the L1-sentence φ has a model'—and equivalently the same sentences μ(φ) asserting that some loopless point has a neighbour set that is a model of φ. A corollary is that the common theory of all D-graphs is incomplete, its completions are indexed by consistent collections of consistency statements, and every completion is neostability-wild: each of its models interprets arbitrarily large finite fragments of ZFC with parameters.","pith_inferences":["Because the paper notes that uniqueness of solutions is never used, the component classification and the consistency-statement correspondence should survive if ZFA is weakened to the existence-only axiom AFA1 (axiom X); the same statements can be tested there.","The proof strategy of Theorem 4.14 resembles a Gaifman/Hanf argument, so one could presumably axiomatize the completions by all local sentences rather than only the μ(φ) subclass, though such an axiomatization would likely be less informative than Corollary 4.15.","The construction in Theorem 4.16—deleting infinite-diameter components—suggests a general recipe for building elementarily equivalent non-reducts for other reducts of set theory, as long as an internal-graph-existence principle analogous to Proposition 2.3 holds."],"forward_implications":["Component classification reduces the existence question to internal graph theory: an isomorphism type appears as a component of M1 exactly when some connected graph of that type exists inside M, and it appears infinitely many times.","Because each completion is realized by continuum-many countable pairwise non-isomorphic models and some countable elementarily equivalent graph is not a reduct, the D-graph and SD-graph classes are not ℵ0-categorical and their theories are not the theories of a single structure up to isomorphism.","Every model of every D-graph theory interprets arbitrarily large finite fragments of ZFC, so these theories have the strict order property, TP2, and the independence property for every k; the class is wild in neostability terms.","The negative answer to Question 5 means that being elementarily equivalent to a reduct does not guarantee being a reduct: there are countable graph structures with the same first-order theory that no model of ZFA produces."],"supporting_citations":[{"why":"Supplies the predecessor results on membership graphs and double-membership graphs of ZFA, including the questions answered here and the non-ℵ0-categoricity of D-graphs.","marker":"[ADC17]"},{"why":"Provides the Anti-Foundation Axiom in terms of flat systems of equations and the Solution Lemma, the central set-theoretic principle used throughout.","marker":"[Acz88]"},{"why":"Introduced the existence-only version of Anti-Foundation and the equiconsistency results that justify working with models of ZFA.","marker":"[FH83]"},{"why":"Gives the uniform interpretation of arbitrary digraphs in graphs, used in Fact 4.6 to turn consistency statements about digraphs into graph sentences μ(θ').","marker":"[Hod93]"},{"why":"Supplies the Ehrenfeucht-Fraïssé background, k-equivalence classes, and game lemmas used in Lemma 4.13 and the main Theorem 4.14.","marker":"[EF95]"},{"why":"Provides Rosser's Theorem and the related fact that every Π^0_1 statement is equivalent over ZFA to a consistency statement about NBG−, used to prove the incompleteness of the common D-graph theory.","marker":"[Smo85]"},{"why":"Used by the paper for the exact Rieger-permutation exercise that shows, without Foundation, double-membership graphs can be essentially arbitrary.","marker":"[Kun80]"},{"why":"Supplies the Hanf-style ball argument adapted in Theorem 4.16 to build an elementarily equivalent graph with no infinite-diameter components.","marker":"[Ott06]"}],"fun_headline_variants":["External double-membership graph components are internal graph copies","Theories of double-membership models determined by consistency statements","Double-membership completions are all neostability-wild","Components from inside: double-membership graphs mirror internal graphs","Each completion of D-graph theory has continuum many models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof needs the existence half of the Anti-Foundation Axiom—every flat system of equations has a solution—and without such solutions the constructions that embed internal graphs into the double-membership graph collapse.","fun_headline_variants_meta":{"raw":{"variants":["External double-membership graph components are internal graph copies","Theories of double-membership models determined by consistency statements","Double-membership completions are all neostability-wild","Components from inside: double-membership graphs mirror internal graphs","Each completion of D-graph theory has continuum many models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000273,"raw_usage":{"total_tokens":1567,"prompt_tokens":810,"completion_tokens":757,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":426,"completion_tokens_details":{"reasoning_tokens":672}},"tokens_in":426,"tokens_out":757,"duration_ms":9676,"temperature":1.0,"reasoning_tokens":672,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:39:08.393027+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a model M of ZFA whose D-graph has a connected component not isomorphic to any connected component of a graph internal to M, which would falsify Theorem 2.4; or find two models M and N of ZFA satisfying exactly the same consistency statements whose D-graphs are not elementarily equivalent, which would falsify Theorem 4.14.","supporting_citations":[],"review_version":1}