15
$\begingroup$

(Prompted by reflection on this old answer, and its suggestion of the “harmlessness” of the axiom of regularity.)

In ZFC, one may justify the axiom of foundation (AF, aka the axiom of regularity) as being “convenient, and harmless”, as follows. If $V = (V,\epsilon)$ is a model of ZFC–AF, then its well-founded part $V_{wf}$ models ZFC. Moreover, ZFC–AF suffices for the standard proof of the well-ordering principle, so $V$ believes that every set is isomorphic to some von Neumann ordinal, which will lie in $V_{wf}$. Hence the inclusion $V_{wf} \hookrightarrow V$ underlies an equivalence of their (internal, large) categories of sets; so any “purely structural” statement should hold in $V$ if and only if it holds in $V_{wf}$. “Purely structural” can be made precise in various reasonable ways (e.g. any statement expressible in the language of categories/elementary toposes/higher-order logic/type theory, interpreted into set theory), and includes essentially all of ordinary mathematics, excluding only a few explicitly material-set-theoretic statements such as AF itself.

Summing up: given any model of ZFC–AF, one can replace it by its well-founded part, which is now a model of ZFC, believing the same purely structural statements as the original model. So relative to ZFC–AF, AF has no purely structural consequences — i.e. it’s not quite conservative, but pretty close to it.

However, this argument relied essentially on the axiom of choice! Relative to ZF–AF, is AF still harmless, or does it have some structural consequences? Precisely: is there some “purely structural” statement $\varphi$ (in one of the senses above, or some similar sense), such that $ZF \vdash \varphi$, but $ZF-AF \not \vdash \varphi$?

I’m also interested in the same question with ZF weakened to IZF, CZF, and similar theories. Over these of course AF should be replaced by $\in$-induction (a classically equivalent and constructively better statement), as described in this older question (which considers closely related issues to the present question, but doesn’t as far as I can see directly imply an answer here).

Improve this question
$\endgroup$
3
  • $\begingroup$ It seems to me that your question may amount to the following purely set-theoretic question: does ZF-AF prove that every set is bijective with a set in $V_{\rm wf}$? The idea being that if so, then any structure arising with ill-founded sets could be taken to arise in the well-founded part. But I think that the answer to this way of asking the question is negative, since I think one can have AC for the well-founded sets, even if there are non-well-orderable sets in the non-well-founded part. $\endgroup$
    – Joel David Hamkins
    Commented May 12, 2018 at 14:55
  • $\begingroup$ Does ZF have any more arithmetical consequences than ZF-AF? $\endgroup$
    – user44143
    Commented May 13, 2018 at 15:24
  • 1
    $\begingroup$ No Matt, arithmetic is carried out in $\omega,$ which exists in $V_{\text{wf}}.$ $\endgroup$
    – Elliot Glazer
    Commented May 13, 2018 at 15:38

2 Answers 2

Reset to default
17
$\begingroup$

Yes, the axiom of foundation has structuralist consequences.

Let $\phi$ be the assertion, "if every well-founded set is well-orderable, then every set is well-orderable."

This statement, I claim, can be made in a (technically) structuralist manner, since it is a statement about all nodes in a certain kind of digraph, namely, the graphs that are stratified by a well-ordered sequence of levels, such that every new level has a unique node for every subset of the nodes on the previous levels. And then assert that every node in such a graph has another node that amounts to a well-order of the set pointing at that node. That is, just make a structuralist description of the $V_\alpha$ hierarchy, and assert that if all the sets arising in it are well-orderable, then every set is well-orderable.

Certainly ZF proves the statement $\phi$, since ZF proves that every set arises in the well-founded $V_\alpha$ hierarchy.

But ZF-AF does not prove the statement, since, I believe, it is consistent with ZF-FA that the well-founded part of the universe satisfies AC, even if there is a non-well-orderable set of Quine atoms in the non-well-founded part of the universe. One can build such a model, I believe, as a symmetric extension of a model of ZFC, by adding a collection of urelements, considered as Quine atoms.

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ Thankyou: yes, this is exactly the sort of thing I was looking for. Indeed, your 3rd paragraph suggests to an even simpler example consequence of foundation, since it points out that the property of “being isomorphic to some set in the well-founded part” can be expressed in a structural way, and hence so can “every set is isomorphic to one in the well-foudned part”. (A quick way of expressing this, based on the Mostowski collapse conditions: “every set is isomorphic to the set of children of the root in some extensional, well-founded, rooted relation”.) $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented May 12, 2018 at 16:19
  • 2
    $\begingroup$ @ElliotGlazer Peter is using the term "root" to refer to the top element, the node that is not in any other node, rather than the bottom node, which is the node (coding the empty set) which has no elements. This is the kind of relation that you get from the transitive closure of a set $\{a\}$, and the node coding $a$ is the unique maximal node. But if you just code a transitive set, not a singleton, then it will not generally have a unique maximal node. $\endgroup$
    – Joel David Hamkins
    Commented May 12, 2018 at 20:15
  • 2
    $\begingroup$ @ElliotGlazer: As Joel says, I was meaning the root as the top — slightly misguidedly and unthinkingly mixing mathematical and CS-ical conventions about trees, in the cause of brevity. But I was overcomplicating the statement anyway — “Every set is isomorphic to the set of children of some element in some well-founded extensional relation” is already enough. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented May 13, 2018 at 9:03
  • 4
    $\begingroup$ I think there's actually an even simpler version: "Every set can be embedded into one carrying a well-founded extensional relation", since if this holds you can always add a new root with exactly those children. In arxiv.org/abs/1004.3802 I called this the "axiom of well-founded materialization". $\endgroup$
    – Mike Shulman
    Commented May 13, 2018 at 9:41
  • 7
    $\begingroup$ I wonder whether one can revive the idea of the harmlessness of foundation, however, by proving that every model of ZF-AF has an extension, with the same well-founded part, in which every set is bijective with a well-founded set. A warm-up would be to make this true for at any given set. This would be analogous to forcing to make a given set well-orderable, for example, by forcing to make it countable. Vote up this comment if I should ask this as a MO question. $\endgroup$
    – Joel David Hamkins
    Commented May 13, 2018 at 17:57
8
$\begingroup$

The following provides an "engine" for generating many structural statements provable in ZF but not in ZF without foundation:

Theorem. Let $S$ be any structural equivalent of the axiom of choice within ZF without foundation (e.g., Zorn's Lemma or Tychonoff's compactness theorem). Then the following structural statement $R_{S}$ (in honor of Herman and Jean Rubin) is provable in ZF; but NOT in ZF without foundation:

$R_{S}$ := "$S$ holds iff every linearly orderable set is well-orderdable".

Explanation. The nontrivial direction ($\leftarrow$) of $R_{S}$ follows from the theorem below, and the observation that the powerset of every well-orderable set $S$ is linearly orderable (by deeming $X$ to be less than $Y$, where $X$ and $Y$ are subsets of $S$, and $S$ well-ordered by $<$, if the $<$-first element in the symmetric difference of $X$ and $Y$ is in $Y$. The proof is readily implementable in Zermelo set theory, i.e., ZF without the foundation axiom and without the replacement cheme, but with the separation scheme).

Theorem (H. Rubin & J. Rubin). ZF proves that if the powerset of every well-orderable set is well-orderable, then the axiom of choice holds.

The above theorem was first published the 1963 book Equivalents of the Axiom of Choice, by Herman and Jean Rubin. A proof can also be found in these lecture notes by Andrés E. Caicedo (see Theorem 13). Later, in this 1973 paper of Felgner & Jech, a model of ZF with atoms was built in which the powerset of every ordinal is well-orderable, but the axiom of choice fails; this proof also appears in chapter 9 of the book Axiom of Choice by Jech.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Uhh, every permutation model in a classical setting satisfying "The power set of an ordinal is well-orderable", since the power set of an ordinal is always a pure set, and permutation constructions cannot violate choice on the kernel. So in practice it was Fraenkel, or at least Mostowski, who actually construct the first models in which the power set of a well-orderable set is well-orderable, but choice fails. (I'm writing this because currently the phrasing hints that it was Jech and Felgner were first to produce a specific example.) $\endgroup$
    – Asaf Karagila ♦
    Commented May 17, 2018 at 23:45
  • $\begingroup$ Hi Asaf, thanks for your comment, "ordinal" should have been "well-orderable" to make the result match that of Felgner & Jech, I have now edited to correct that. $\endgroup$
    – Ali Enayat
    Commented May 18, 2018 at 5:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.