10
$\begingroup$

This is a followup question to Does foundation/regularity have any categorical/structural consequences, in ZF?

As shown in answers to that question, the axiom of foundation (AF, aka regularity) has consequences over ZF–AF that can be formulated purely in structural terms (i.e. using sets only in ways that respect isomorphism).

In particular, it implies the statement “Every set can be embedded into a set equipped with a well-founded extensional relation”, which Mike Shulman has called the axiom of well-founded materialisation; and (by the arguments in that question) this axiom should have the same structural consequences as foundation.

This statement is a very mathematically reasonable one. However, I don’t think I have ever seen this or anything similar appearing in practice in ordinary mathematics — only in logical investigations like this one, where it occurs specifically because of its relation to AF. So my question here is: Does the axiom of foundation have any consequences (over ZF–AF) that have appeared in ordinary mathematics?

Slightly more precisely:

  • By “consequence of foundation over ZF–AF”, I of course mean principally a statement that’s provable in ZF, but not in ZF–AF. But I’d also be interested in e.g. a proof in ZF that doesn’t go through in ZF–AF and can’t be trivially modified to do so.

  • By “ordinary mathematics”, I mean… this of course is subjective, and mostly I think “we know it when we see it”, and hope that most of us will find our judgement on it mostly agrees. But to articulate my own intent here a little: a sufficient (but not necessary) condition to would be that the statement has been considered in a field of mathematics other than logic; necessary conditions would be that it’s purely structural, and that it’s been considered outside work specifically investigating foundation (or related axioms) or modelling set theories that include foundation. To illustrate the non-necessity of the “outside logic” criterion — I would certainly be happy to consider consequences in e.g. general classical model theory.

See e.g. Where in ordinary math do we need unbounded separation and replacement? for a similar question, about different axioms, and relevant discussion of what should be considered “ordinary mathematics”.

$\endgroup$
  • 3
    $\begingroup$ How would one give evidence that the answer is "there are no such consequences"? I suppose we could try to prove a meta-theorem. $\endgroup$ – Andrej Bauer May 30 '18 at 16:56
  • 2
    $\begingroup$ Would this be sufficiently "ordinary": That existence of a tree without a branch implies the existence of such a tree with a linear order on each rank? $\endgroup$ – Elliot Glazer May 30 '18 at 19:10
  • 1
    $\begingroup$ @Andrej: agreed, a negative answer would be much harder to justify than a positive. The best I can imagine is some knowledgeable person saying “I thought about this a while ago, and did a large literature search, but didn't find anything.” The next best thing would be if this question gets a lot of views but no satisfactory answer… $\endgroup$ – Peter LeFanu Lumsdaine May 30 '18 at 20:41
  • 1
    $\begingroup$ What about the theory of scattered linear orders? @AsafKaragila: Are there choiceless models that have counterexamples to Hausdorff's theorem on these? $\endgroup$ – Monroe Eskew May 31 '18 at 10:08
  • 2
    $\begingroup$ @Asaf, If you assume choice then everything that happens outside the well-founded part has a copy inside WF. So I guess that this means in the choice context, foundation can't affect "ordinary math." The theorem of Hausdorff is a classification of scattered linear orders. He defines an inductive hierarchy starting from singletons and shows that every linear order which does not contain a copy of $\mathbb Q$ appears in this list. $\endgroup$ – Monroe Eskew May 31 '18 at 11:03
5
$\begingroup$

What about Scott's trick?

In more detail: here, I claim, is a proof-schema in ZF that belongs to "ordinary mathematics" but cannot be trivially modified to go through in ZF–AF.

Let $C$ be a locally-large category, by which I mean a proper class of objects, a proper class of morphisms, class-functions for domain, codomain, composition, and identities, satisfying the axioms of a category. (Since a proper class in ZF is specified by a logical formula, this is why the proof is a schema rather than a single one.) Let $W$ be a subclass of the morphisms of $C$. Then we can construct the localization $C[W^{-1}]$ as another locally-large category, as described here: we consider the (large) directed graph whose edges are the morphisms of $C$ and the morphisms of $W^{\rm op}$, generate the free (large) category on it, and then quotient by an appropriate equivalence relation.

The free large category on a large directed graph is unproblematic even in ZF–AF: its morphisms are finite lists of composable edges, and we can define a formula that specifies the proper class of finite sequences of elements of some other proper class. But there is no obvious way to form the quotient of a generic proper class by a proper-class equivalence relation in ZF–AF: the usual construction of the quotient of a set by an equivalence relation takes the elements of the quotient to be equivalence classes, but if the "equivalence classes" are proper classes then they cannot be elements of some other class. Scott's trick is to instead define the elements of the quotient to be the sub-sets of the equivalence proper-classes consisting of all their elements of minimal rank, which are sets since each $V_\kappa$ is a set. But without the axiom of foundation, this doesn't work since we can't assert that each equivalence proper-class contains any well-founded elements.

$\endgroup$
  • $\begingroup$ Of course! Yes, this I agree this definitely hits the “ordinary mathematics” criterion, and while it’s not obvious whether the statement can fail in ZF–AF, it at least seems unlikely that any proof along these lines can work. For anyone who hasn’t seen it, I recommend the original source of Scott’s trick as a beautiful piece of mathematical writing — a 2-paragraph abstract, clearly setting out a powerful statement and its non-trivial proof. (Dana Scott, Definitions by abstraction in axiomatic set theory, Bulletin Amer. Math. Soc. 61 (1955), 442.) $\endgroup$ – Peter LeFanu Lumsdaine Jul 27 '18 at 7:58
  • $\begingroup$ Do you have a simple example of a locally large category? Googling that term only brought me to locally small categories... $\endgroup$ – Asaf Karagila Jul 28 '18 at 4:43
  • $\begingroup$ @AsafKaragila Well, every locally small category is also locally large... $\endgroup$ – Mike Shulman Jul 28 '18 at 17:16
  • $\begingroup$ Yes, but something less trivial? $\endgroup$ – Asaf Karagila Jul 28 '18 at 17:19
  • 1
    $\begingroup$ Right, local largeness is not the real point, I only talked about that because it's the natural context for localization; in general localization doesn't preserve local smallness, although in many cases arising in practice there are other tricks that imply that it does. The point is that, as Peter says, even if the localization is locally small, its equivalence classes are proper classes, so constructing it requires some trick. $\endgroup$ – Mike Shulman Jul 29 '18 at 0:46
6
$\begingroup$

It has long been the informal view of set theorists that the Axiom of Foundation does not have consequences for "ordinary mathematics". For example, in Chapter III of his Set Theory: An Introduction to Independence Proofs (1980), K. Kunen tells us that we introduce the axiom to limit set theory to the sets that are actually employed to do mathematics. Similarly, in their mathematico-philosophical classic Foundations of Set Theory (1973, p. 87)), A. A. Fraenkel, Y. Bar-Hillel and A. Levy maintain "its omission will not incapacitate any field of mathematics". Of course mathematics has changed since these works were written, but I suspect the opinions expressed therein have not changed among contemporary set theorists with respect to what you informally call "ordinary mathematics".

$\endgroup$
  • $\begingroup$ Thankyou for giving these relevant quotes! However, I have always understood these as having in mind the mainstream setting of ordinary mathematics, where choice is used without too many qualms; and as discussed in the linked previous question and its answers, the consequences of regularity in the presence of choice are quite restricted, in a way that makes them unlikely to affect ordinary mathematics. If you have seen similar quotes from people working in choiceless settings, especially if they suggest serious thought on this issue, then that would seem a stronger negative answer. $\endgroup$ – Peter LeFanu Lumsdaine May 31 '18 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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