Notes to Non-wellfounded Set Theory
1. The interesting feature of the Thue-Morse sequence is that is has no three-in-a-row repeats: for every finite non-empty sequence w of 0s and 1s, the infinite sequence t does not contain www anywhere.
2. The main move in the theory of hypersets studied in this entry is to keep the standard modeling of pairs but to change the underlying set theory. Formulating matters this way suggests that it might be possible to keep the Foundation Axiom but alter the treatment of pairs. This point is made by Forster (1994) and Paulson (1999). We discuss this point further at the end of Section 4.5.
3. Incidentally, the most standard definition of the solution x† from equation (4) uses a different vocabulary altogether: the nth term of the sequence corresponding to x† is 0 or 1 depending on whether there are an even or odd number of 1s in the binary representation of n+1.
4. This is really but one species of tree. It would be more proper to use a fuller name for what we are studying, such as “finite or infinite trees whose leaves are labeled with x or y and whose interior nodes are either unary nodes labeled • or binary nodes labeled with the * sybmol.”
5. Both the applicability and the conceptual point are important: I am not aware of publications prior to Aczel's book that even hinted at applications. Also, the discussion of conceptual points is not developed at length there. Earlier papers such as Forti and Honsell (1983) do not mention conceptual points at all, and indeed amid the multiplicity of axioms studied it is hard to see whether earlier workers were even thinking in these terms.
6. In this entry, we sometimes write ⟨a,b⟩ as (a,b), especially in connection with structures like graphs (G,→).
7. Perhaps the similarity of “starting from nothing“, creatio ex nihilo, and the Big Bang are part of the appeal of the iterative conception.
8. I realize that my presentation of the iterative conception does mix temporal and spatial metaphors. In this connection, I mention from John Burgess (1985), review of papers (including Boolos (1971)): “The informal description of this [iterative or cumulative hierarchy] almost demands resort to a metaphor, spatial imagery being preferable to temporal as being less likely to be (mis)taken literally.” A criticism of the iterative conception and specifically of the metaphors used may be found in Parsons (1975).
9. As an interesting aside, note that the ordinals can be obtained via decoration of well-ordered sets. In ZF, one needs the Replacement Axioms for this.
10. The “in” stands for injection, and the “l” and “r” are from left and right.
11. Since we have cut all the corners, the treatment here would be inadequate as an introduction to category theory.
12. This point is weakened a bit when one considers the morphisms. For graphs, there are several natural notions of morphism; one is a map between the nodes that preserves edges (in one direction). The notion of a morphism of ℘-coalgebras gives a different concept.
13. There are some differences between our work and the treatment in Barwise and Moss (1996). The main one is that the book uses a set theory with urelements, objects which are not themselves sets but which might belong to sets. The presentation here was in terms of pure sets. On the other hand, the book shied away from any categorical terminology, and this entry went the other way. For a reader comfortable with category theory, much of the mathematics in that book could be presented much more compactly using results from coalgebra. The theory would also be more general that way.
14. Another interesting topic in this regard is the connection between domain theory and coalgebra. We mention this because many final coalgebras may be built with domain theoretic tools, and many of the applications of coalgebra mentioned in this entry could also be obtained via domain theory. One specific example concerns corecursion, and closer to fractals, there are interesting domain-theoretic constructions: see Hayashi (1985) and Edalat (1995).