Okada Tomoko and Nitta Takashi Graduate school of Mathematics, Nagoya University, Chikusa-ku, Nagoya, 464-8602, Japan, Department of Education, Mie University, Kamihama, Tsu, 514-8507, Japan In set theory, the foundation axiom (or regularity)(F) says that the re- lation ∈ is well-founded, that is, there is no infinite descending ∈-sequence : ··· E x 2 E x 1 E x 0 If we identify ∈ in a set with ← in a graph, the set is identified with a graph.  The set 1 is 1 = {φ}, that is, φ ∈ 1. It corresponds to a graph x 1 ← x 0 with nodes x 0 , x 1 . In terms of graphs and nodes, the well-foundedness is that there is no
x0 → x1 → x2 → · ·
Denote by ZFC- the Zermelo-Fraenkel set theory with choice, which does not satisfy (F). Usually we write (AF) to indicate an anti-foundation axiom, any statement refusing (F). In 1988, Aczel([A]) introdeced non-well-founded ZFC-+(AF) set theory, and studied various kinds of anti-foundation axioms and hence the associ- ated non-well-founded set theories, which include Aczel set theory, Scott set theory, Finsler set theory and Boffa set theory. In fact we know that Zermelo-Fraenkel set theory is a subclass of Aczel set theory, Aczel set theory is a subclass of Scott set theory and Scott set theory is a subclass of Finsler set theory. In 1962, Richard Peddicord([P]) computed the number of Zermelo-Fraenkel sets of f inite nodes. In 1990, Booth([Boo]) counted Finsler sets of node one, two and three, while pointing out that it is difficult to construct an algorithm to classify Finsler sets. In 1998, Milito and Zhang([M-Z]) proposed an algorithm to classify Aczel sets, and commented that Booth's list is wrong in the case of node three. In this paper, we not
11
only complete the nodes list, also give an algorithm of a classification of Scott sets, and hence obtain the number of Scott sets of node one, two and three. As a direct consequence we show that Scott sets and Finsler sets coincide with each other in the case of node one and two, and that only two Finsler sets are not Scott sets in the case of node three.  Generally speaking, it is very interesting to construct Finsler sets that are not Scott sets. Dougherty found the first example of finite nodes Finsler sets with nine nodes and 26 edges that is not a Scott set([A],55page). Later, Moss constructs a simple example with only three nodes and five edges([A],54page). See also [A] 55page where Johnson's example is given.  We construct examples of Finsler sets of any number of nodes that are not Scott sets.  In particuler, we obtain a new example with four nodes and eight edges. In Zermelo-Fraenkel set theory, there is no infinite descending E-sequence by the axiom of regularity.  However this is not true for Aczel set theory. In fact in this paper, we construct many examples of infinite descending E-sequences in Aczel set theory and show that there exist always infinite descending E-sequences in Aczel set theory.  Moreover, our examples are with any ordinal lengths, and both circular and non-circular type appear. In a sense, this is quite amasing as Tzouvaras([T]) shows that there are no infinite descending E-sequences with length On in Aczel set theory. Unlike the previous set theoris, in Boffa set theory, sets are not identified with graphs, despite that each set is associated with a graph. For these sets Ballard and Hrbacek([B-H]) develop a nonstandard analysis in the class of the so-called urelements ([B-H]) which satisfies an extension principle. In this paper we generalize their work to a larger class of sets, which we call "linear" and denote it by g z , furthermore we introduce an equivalence relation ～ in a class of linear sets. In particular, we show the following : EXTENSION PRINCIPLE : Let U be a universe and κ an infinite cardinal number.  Then there exists a κ -saturated universe W  and an ele- mentary embedding F : U → W. Moreover, if g x is a linear set equation of circular type and ( A g z /~) — ( A g  n U/~ ) is a proper class, then one can assume that F ( x ) is equal to x for all x ∈ Ag x ∩ U , and Ag x − W is a proper class. [A] Aczel, P., Non-Well-Founded Sets, CSLI Lecture Notes, No. 14, Stan- ford, (1988). [B-H] Ballard D. and Hrbacek, K., Standard Foundations for Nonstandard Analysis, The Journal of Symbolic Logic, 57 (1992), 741-748. [Bof] Boffa, M., Forcing et Negation de l'axiome de Fondement, Memoire Acad. Sci. Belg. tome XL, fasc. 7, (1972). [Boo] Booth, D., Hereditarily Finite Finsler Sets, The Journal of Symbolic Logic, 55 (1990), 700-706. [B-Z] Booth, D. and Ziegler, R., Editors. Finsler Set Theory : Platonism and Circularity, Birkhäuser Verlag, (1996). [C-K] Chang, C.C. and Keisler H.J., Model theory, North-Holland, Am- sterdam, (1973). [F] Finsler, P., Über die Grundlagen der Mengenlehre, I.,Math.  Zeitschrift, 25 (1926), 683-713. [M-Z] Milito, E. and Zhang, L., Classification of Minimal Finite Hyper- sets, Congressus Numerantium, 133 (1998), 85-93. [N-O-A] Nitta, T., Okada, T., Tzouvaras, A. ; Classification of non-well- founded sets and an application, Math. Log. Quart., 49 (2003), 187-200. [P] Peddicord, R., The Number of Full Sets with n Elements, Proc.  Amer. Math. Soc., 13 (1962), 825-828. [S] Scott, D., A Different Kind of Model of Set Theory, Unpublished paper given at t the 1960 Stanford Congress of Logic, Methodology and Philosophy of Science. [T] Tzouvaras, A., Non-Circular, Non-Well-Founded Set Universes, Math. Log.  Quart.  39 (1993), 454-460.