Undirecting membership in models of Anti-Foundation
- PDF / 283,266 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 161 Views
Aequationes Mathematicae
Undirecting membership in models of Anti-Foundation Bea Adam-Day
and Peter J. Cameron
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 x ∈ y or y ∈ x), we obtain the Erd˝ os–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 x ∈ x for some x) or multiple edges (if x ∈ y and y ∈ x for some distinct 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 ℵ0 -categorical and homogeneous), but if we keep multiple edges, the resulting graph is not ℵ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. Mathematics Subject Classification. Primary 05C63; Secondary 03E99. Keywords. Erd˝ os–R´ enyi random graph, Zermelo–Fraenkel axioms, Anti-Foundation Axiom.
1. Introduction According to the downward L¨ owenheim–Skolem theorem [9, Corollary 3.1.4], if a first-order theory in a countable language is consistent, then it has a countable model. In particular, Zermelo–Fraenkel set theory ZFC, if consistent, has a countable model. (This is the source of the Skolem paradox, since the existence of uncountable sets is a theorem of ZFC.) Indeed there are many different countable models, but they all have a common feature. To describe this, we briefly introduce the Erd˝ os–R´enyi random graph (sometimes referred to as Rado’s graph, for reasons we will see). Erd˝ os and R´enyi [7] showed that there is a countable graph R such that, if a random graph X on a fixed countable vertex set is chosen by selecting edges independently with probability 1/2 (or, indeed, any fixed p with 0 < p < 1), then X is isomorphic to R almost surely (that is, with probability 1). Moreover,
B. Adam-Day, P.J. Cameron
AEM
R is highly symmetric; they showed that such a graph has infinitely many automorphisms, but in fact it is homogeneous: any isomorphism between finite induced subgraphs extends to an automorphism. Erd˝ os and R´enyi gave a nonconstructive existence proof, based on the following property, called the Alice’s Restaurant property, or ARP: Given any two disjoint finite sets U and V of vertices, there is a vertex z joined to every vertex in U and no vertex in V . In other terminology, R is the Fra¨ıss´e limit of the class of finite graphs. For further discussion of the graph R, including the theorem below, we refer to [5]; for Fra¨ıss´e’s theorem, see [9, Theorem 6.1.2]. A model of Zermelo–Fraenkel set theory ZF consists of a collection of objects called sets, and a binary relation ∈ on this collection.
Data Loading...
