Undirecting membership in models of anti-foundation

DOI10.1007/S00010-020-00763-WMaRDI QIDQ2662895zbMATH OpenOpenAlexFDO

Authors Bea Adam-Day, Peter J. Cameron

Publication date 15 April 2021

Published in Aequationes Mathematicae (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1708.07943

zbMATH Keywords

anti-foundation axiomErdős-Rényi random graphZermelo-Fraenkel axioms

Mathematics Subject Classification ID

Set theory (03E99) Infinite graphs (05C63) Random graphs (graph-theoretic aspects) (05C80)

Abstract: It is known that, if we take a countable model of Zermelo--Fraenkel set theory ZFC and "undirect" the membership relation (that is, make a graph by joining $x$ to $y$ if either $xiny$ or $yinx$), we obtain the ErdH{o}s--R'enyi random graph. The crucial axiom in the proof of this is the Axiom of Foundation, so it is natural to wonder what happens if we delete this axiom, or replace it by an alternative (such as Aczel's Anti-Foundation Axiom). The resulting graph may fail to be simple, it may have loops (if $xinx$ for some $x$) or multiple edges (if $xiny$ and $yinx$ for some $x,y$). We show that, in ZFA, if we keep the loops and ignore the multiple edges, we obtain the "random loopy graph" (which is $alep{h}_0$-categorical and homogeneous), but if we keep multiple edges, the resulting graph is not $alep{h}_0$-categorical, but has infinitely many $1$-types. Moreover, if we keep only loops and double edges and discard single edges, the resulting graph contains countably many connected components isomorphic to any given finite connected graph with loops.

Recommendations

• scientific article; zbMATH DE number 42735
• Antifoundation and transitive closure in the system of Zermelo
• Forcing and antifoundation
• Forcing with the anti-foundation axiom
• The graph conception of set

Cites work

• Asymmetric graphs
• scientific article; zbMATH DE number 3859115 (Why is no real title available?)
• scientific article; zbMATH DE number 42735 (Why is no real title available?)
• scientific article; zbMATH DE number 1249505 (Why is no real title available?)
• scientific article; zbMATH DE number 473381 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 952378 (Why is no real title available?)
• The mathematics of Paul Erdős II
• Universal graphs and universal functions

Cited in

(1)

• ON DOUBLE-MEMBERSHIP GRAPHS OF MODELS OF ANTI-FOUNDATION

This page was built for publication: Undirecting membership in models of anti-foundation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662895)