28
$\begingroup$

Many students' first introduction to the difference between classes and sets is in category theory, where we learn that some categories (such as the category of all sets) are class-sized but not set-sized. After working with such structures, we discover that it is still worthwhile to sometimes treat them as if they were set-sized. But we can't always do so, without running into contradictions. A natural solution to this problem is the "Axiom of Grothendieck Universes". We then work not with the category of all sets, but the category of sets inside some given universe. This type of framework has been used by many notable mathematicians and seems very ubiquitous. For instance, it was an assumption in my universal algebra textbook. I would venture to say that most modern set theorists look at such an axiom as a very tame assumption.

My first question concerns the possible dangers of such an assumption, which are not often raised when first learning about this axiom. One obvious danger is that this axiom might lead to an inconsistency. In other words, ZFC might be consistent but ZFC+Universes might be inconsistent. I don't personally subscribe to this belief, but it is certainly a possibility (without further, even stronger, assumptions).

What really concerns me is the possibility of another danger: Could such a system proves false things about the natural numbers? In other words, even if we assume that ZFC+Universes is consistent, could it be the case that it proves false arithmetic statements?

The motivation for this question came from reading some of the work of Nik Weaver at this link, which argues for a conceptualist stance on mathematics. In particular, if we reject the axiom of power set, we are led to situations where all power sets of infinite sets are class-sized. Nik puts forth the idea that ZFC might prove false things about the natural numbers. Is this a real possibility? I suppose so, since it is possible that ZFC is inconsistent but the natural numbers aren't. But is it still possible even if ZFC is consistent? More generally:

Could treating the power set of the natural numbers as a set-sized object, rather than a class, force us to conclude false arithmetic statements (even if such a system is consistent)?

Even if the answer to this question is yes, I'm having a hard time seeing how we could recognize this fact, since according to the answers to this linked question it is difficult to state precisely what we mean by the natural numbers.

A second motivation for this question comes from what I've read about the multiverse view of set-theory. When creating a (transitive) model $M$ of ZFC, the set $P(\mathbb{N})$ can often be thought of as some "bigger" power set of the natural numbers intersected with the model. Moreover, via forcing, it seems that one can (always?) enlarge the power set of $\mathbb{N}$. This does seem to suggest that $P(\mathbb{N})$ is not completely captured in any model. Thus, in its entirety, perhaps $P(\mathbb{N})$ should be treated as a class-sized object.


Added: I believe that the current proof we have of Fermat's Last Theorem uses the existence of a(t least one) Grothendieck universe. However, my understanding is that this dependence can be completely removed due to the fact that Fermat's Last Theorem has small quantifier complexity. I imagine that proofs of statements with higher quantifier complexity that use Grothendieck universes, do not necessarily have a way of removing their dependence on said universes. How would we tell if such arithmetic statements are true of the natural numbers? [Some of this was incorrect, as pointed out by David Roberts and Timothy Chow.]


2nd addition: There are some theories that we believe prove false arithmetic statements. Assuming the natural numbers can consistently exist (which we do!), then both PA+Con(PA) and PA+$\neg$Con(PA) are consistent, but the second theory proves the false arithmetic sentence $\neg$Con(PA).

My question then might be rephrased as:

What principles lead us to believe that "Universes" is a safe assumption, whereas "$\neg$Con(PA)" is not safe, regarding what we believe is "true" arithmetic? (Next, repeat this question regarding the axiom of power set.) Is any theory that interprets PA "safe", as long as it is consistent with PA, and PA+Con(PA), and any such natural extension of these ideas?

Another way of putting this might be as follows:

Is the assumption Con(PA) a philosophical one, and not a mathematical one?

This ties into my previous question that I linked to, about describing the "real" natural numbers.

$\endgroup$
  • 2
    $\begingroup$ @jon The "category of all categories" runs into similar paradoxes as the "set of all sets", whereas the "category of all $U$-small categories" doesn't. We'd like to freely work with the standard categories (of groups, sets, monoids, etc...) as if they (together) can form a new collection which forms the object set of a category, and morphisms between them are functors. The standard way this is done is by working with the $U$-small categories instead. For this and other examples, look where textbooks make use of the axiom of universes. $\endgroup$ – Pace Nielsen Jun 19 at 18:49
  • 4
    $\begingroup$ I don't understand the question in the box -- in most of mathematics, $P(\mathbb N)$ is treated as a set and not a class. So it sounds like you're simply asking whether ordinary mathematics can prove false arithmetic statements. But I get the impression from the surrounding discussion that you're trying to ask something specific about Grothendieck universes... I don't know what you're asking though. $\endgroup$ – Tim Campion Jun 19 at 19:05
  • 7
    $\begingroup$ Ok. So there are two things going on in your question: 1.) You're asking whether "conceptualist mathematics" might prove different arithmetical statements then ZFC, say -- a mathematical question. 2.) You're asking whether there are reasons to think that the arithmetical consequences of one theory are more "true" than another--a philosophical question. To answer either question would require a much more precise specification of which theories, exactly we're discussing. FWIW I've never heard of "conceptualist mathematics" but generally restricting the powerset axiom is called "predicativism". $\endgroup$ – Tim Campion Jun 19 at 19:34
  • 3
    $\begingroup$ @HagenvonEitzen Consistency and truth are two different things. For instance, $PA + Con(PA)$ and $PA + \neg Con(PA)$ are both consistent, but at most one of them can be true -- after all, one of them asserts $Con(PA)$ while the other asserts $\neg Con(PA)$! Depending on your philosophy, you might deny that it is ultimately meaningingful to ask whether / assert that a mathematical theory is "true". But in this case, you can still "model" the situation as follows: when somebody makes such assertions, interpret them as being relative to some (unspecified) "ultimate metatheory". $\endgroup$ – Tim Campion Jun 20 at 13:31
  • 3
    $\begingroup$ Re: Fermat's last theorem, you're conflating the issue of universes (which can only be removed by actually looking at the proof - no general metatheorem applies) with choice (where we have a metatheorem, namely absoluteness, which automatically removes choice based purely on the syntactic complexity of the theorem itself). $\endgroup$ – Noah Schweber Jun 21 at 2:50
11
$\begingroup$

This answer repeats some of the material in other answers but I think it is not entirely redundant.

As you seem to have realized, the assertion that a theory is consistent is a much weaker statement than the assertion that the theory does not prove false arithmetical statements (or is "arithmetically sound", to use the standard terminology). So the answer to your question about whether it could be the case that ZFC + universes is consistent but not arithmetically sound is yes, but for perhaps a trivial reason: ZFC + universes could be consistent and yet ZFC itself could fail to be arithmetically sound. Probably what you really wanted to ask was, if ZFC is arithmetically sound, and ZFC + universes is consistent, does it follow that ZFC + universes is arithmetically sound? The answer is no. For example, it is conceivable that under these hypotheses, ZFC + universes could prove $\neg$Con(ZFC). (EDIT: This was a typo. I meant that ZFC+universes could prove $\neg$Con(ZFC+universes). Thanks to Noah Schweber for catching this—see the comments.)

Any feeling that universes are a "safe" assumption must come from a direct assessment of the universes axiom itself. The reasons are similar to the reasons that we have for believing that ZFC is arithmetically sound.

The ability to remove Grothendieck universes from the proof of Fermat's Last Theorem cannot be deduced from some simple abstract fact like "Fermat's Last Theorem has low quantifier complexity." No meta-theorem of this sort is known. Eliminability must come from careful examination of the nitty-gritty details of the proof.

Your question about whether Con(PA) is philosophical or mathematical needs clarification. Offhand, it sounds like a false dichotomy to me, predicated on dubious assumptions about the meaning of the words "philosophical" and "mathematical." Can you define precisely what you mean by a "mathematical" assumption? Are you implicitly assuming that "mathematical" assumptions are rock-solid while "philosophical" ones are not? If so, that in itself is a dubious assumption IMO.

$\endgroup$
  • $\begingroup$ "For example, it is conceivable that under these hypotheses, ZFC + universes could prove ¬Con(ZFC)." That's definitely false: ZFC + universes proves Con(ZFC), so if ZFC + universes is consistent it can't prove $\neg$Con(ZFC). $\endgroup$ – Noah Schweber Jun 21 at 2:43
  • $\begingroup$ Whoops! I mean that ZFC + universes could prove ¬Con(ZFC+universes). $\endgroup$ – Timothy Chow Jun 21 at 2:44
  • 4
    $\begingroup$ "No meta-theorem of this sort is known" Or, indeed, possible, since Con(ZFC) is a $\Pi^0_1$ statement already! $\endgroup$ – cody Jun 21 at 12:55
  • $\begingroup$ @TimothyChow Thank you for this answer. Would you have a good reference where I can learn more about (and the explicit definition of) arithmetical soundness and/or soundness in general? $\endgroup$ – Pace Nielsen Jun 21 at 15:54
  • 1
    $\begingroup$ @PaceNielsen : I would suggest Torkel Franzén's book Inexhaustibility: A Non-Exhaustive Treatment, especially Chapter 7, which gives a detailed explanation of arithmetical truth. $\endgroup$ – Timothy Chow Jun 21 at 17:17
20
$\begingroup$

For what it's worth, the reason I made that comment was because when I gave talks expressing skepticism about the philosophical basis of ZFC, I would often get the reaction "but as long as it's consistent, what's the problem?" Some version of this attitude is also quite prevalent in the philosophical literature on the subject. I wanted to make the point that just being consistent isn't good enough: ZFC might well be consistent yet still prove, for example, that some Turing machine halts when in fact it does not. If you're a skeptic about sets but not about numbers, this could be a concern.

As for the "safety" of assuming ZFC is arithmetically sound, it is clear that as long as ZFC is consistent, no weaker system could prove that it is unsound. So for predicativists like me, who generally work in much weaker systems than ZFC, it seems unlikely that we could ever establish unsoundness. In that sense I'd say it's pretty "safe" to assume it is sound.

However ... I regard the Peano axioms as expressing intuitively evident truths about the natural numbers, so I have no problem affirming Con(PA). Whereas I regard ZFC as what you get when you realize that full comprehension leads to inconsistencies, so you replace it with a hodgepodge of instances of comprehension which appears to be weak enough to block any paradoxes. (Edit. In case my meaning isn't clear: the axiom of pairing is an instance of full comprehension, the axiom of unions is an instance of full comprehension, the axiom of power sets is an instance of full comprehension ... Basically what you're doing is throwing in a bunch of unrelated instances of "for any property $P$ there is a set of all $x$ such that $P(x)$.") It seems to me quite ad hoc and unmotivated, so although we might (or might not) be confident that ZFC is consistent, there is little reason to expect it to be (or not to be) arithmetically sound.

(I should add that I regard the "iterative conception" which is supposed to justify ZFC as utterly unconvincing. Sets are said to be built up in stages, and then it is parenthetically added that they are, of course, timeless abstract objects so they aren't really "built", nor do they really "appear" in "stages" --- it's all just a "metaphor". Thus "any conviction that the iterative conception may carry is made to depend on metaphorical details that are dismissed as inessential to it." (I. Jane))

$\endgroup$
  • 4
    $\begingroup$ As you stated, we’d never be able to come across a reason that it’s unsound. So the only way we’d get “no reason” to believe in soundness is if we are radical and dismiss the intuition of the vast majority of mathematicians as having no import. I know that’s your whole schtick but I want to point out that it’s radical. $\endgroup$ – Monroe Eskew Jun 20 at 6:19
  • 2
    $\begingroup$ Your claim "as long as ZFC is consistent, no weaker system could prove that it is unsound" seems to be blatantly false. If someone does manage to construct a proof within ZFC of ( ZFC is inconsistent ), then we definitely can conclude that ZFC is unsound, even from the perspective of a very weak meta-system, because we can verify that ( ZFC proves ¬Con(ZFC) ) purely mechanically. In fact, we do not even need that much. It suffices if anyone constructs a ZFC proof of ( ZFC is Σ[n]-unsound ) for any fixed n. $\endgroup$ – user21820 Jun 20 at 13:24
  • 7
    $\begingroup$ @AsafKaragila I don't think your criticism is apropo. Nik has done lots of serious work with set theory, including writing a treatise on forcing for the regular mathematician, using diamond principle to solve problems in algebra, etc... $\endgroup$ – Pace Nielsen Jun 20 at 15:35
  • 16
    $\begingroup$ @AsafKaragila: Your point is fair, but in the converse direction, it’s easy to get Stockholm syndrome: Once you’re deeply familiar with the consequences of some definition, they shape your intuition, and so the definition feels natural because it matches this intuition so well. So even when some definition is terribly ad hoc, its adherents will find it natural. Most arguments about foundations come down in large part to these two effects: people overlook kludges in the systems they’re most familiar with, and are disproportionately conscious of them in other systems. $\endgroup$ – Peter LeFanu Lumsdaine Jun 20 at 16:30
  • 5
    $\begingroup$ @Pace: I'm not here to trash Nik or his knowledge of set theory, and I think he's well versed in what he's saying. But I think that people are the product of their views. I find it almost disparaging to call ZFC "hodgepodge", and double-down by saying that the iterative concept is "utterly unconvincing". I found it very convincing. I don't find statements like "true" and "false" convincing, though, I mean, who made you the king of everything that you can know what is true and what is false. So what? $\endgroup$ – Asaf Karagila Jun 21 at 7:40
6
$\begingroup$

There's a lot going on in this question; let's break it down:

Is the assumption Con(PA) a philosophical one, and not a mathematical one?

I suppose it depends on what you mean by "the assumption Con(PA)":

  • If you're writing a mathematical proof, then either the foundations you're assuming prove Con(PA) or they don't, and it's a mathematical question which is the case. You'll be mathematically justified in assuming Con(PA) in the former case. In the latter case, there are contexts where "assuming Con(PA)" is mathematically justified -- for example, if you're trying to prove a statement of the form $Con(PA) \Rightarrow P$ for some $P$, then you're allowed to argue by assuming Con(PA) and proving $P$. But probably that's not what you mean.

  • If you're just asserting "PA is consistent" in a non-mathematical context, then your statement requires some philosophical unpacking to make precise, and moreover to determine to what extent it is justified. In this sense, it's a philosophical statement.

What principles lead us to believe that "Universes" is a safe assumption, whereas "¬Con(PA)" is not safe, regarding what we believe is "true" arithmetic?

There is an extensive philosophical literature discussing justifications for large cardinal axioms. You might start here. I'm not an expert, but I'm not aware of arguments which specifically argue that one should accept the arithmetic consequences of large cardinal axioms without arguing that one should accept the axioms outright. I would be interested to see such an argument. I once asked this question with related motivations.

I think the relevant thing to say is that I've never heard of similar sorts of justifications for $\neg Con(PA)$, and I don't expect I will.

(Next, repeat this question regarding the axiom of power set.)

Restrictions on powersets are studied in predicative mathematics. For some discussion of predicativism, one might start here or here. For some arguments for impredicativism, one might start here.

Is any theory that interprets PA "safe", as long as it is consistent with PA, and PA+Con(PA), and any such natural extension of these ideas?

By "safe", I take it that you continue to mean that the theory's arithmetic consequences are "true". There is a large body of literature discussing truth in mathematics. You seem to be particularly interested in the hierarchy obtained by passing from $T$ to $T + Con(T)$ iteratively. This hierarchy appears to be discussed from a philosophical perspective here. I think most logicians would probably agree that ascending this hierarchy adds relatively little consistency strength. And I'm not aware of serious attacks on the common-sense idea that if one believes $T$ is true, then one should also believe that $T + Con(T)$ is true.


Again, I'm not an expert, but it seems to me that most of the time when trying to justify stronger axioms from weaker assumptions, one appeals to some sort of reflection principle. This concept seems to be relevant to several of the questions you're asking.

You might also be interested in Reverse mathematics, where the "strength" of a mathematical theorem is calibrated by finding just how weak of a foundational theory can prove the theorem. One can interpret this as finding how "safe" a theorem is -- if you can prove it in a weaker theory, then it will continue to be true even if stronger theories are inconsistent, or simply "false".

$\endgroup$
  • $\begingroup$ Regarding your second-to-last paragraph, on "truth" in mathematics, how would you interpret the wikipedia article on Goodstein's Theorem, as it asserts that this is "a true statement that is unprovable in Peano arithmetic". What do they mean by "true" in this context? I think my comment about "safe" means "consistent with anything that we naturally would take to be true"---but I'm also a little confused at what things we take to be true! $\endgroup$ – Pace Nielsen Jun 20 at 0:37
  • 4
    $\begingroup$ That statement makes sense if you don't read too much into it: if a statement is provable in ZFC, then it's standard mathematical practice to regard it as true. So the statement isn't that different from saying "Goodstein's theorem is a theorem of ZFC but not of PA". (Of course, Goodstein's theorem can presumably be proven using less than the full strength of ZFC, but that's beside the point.) $\endgroup$ – Tim Campion Jun 20 at 3:41
  • 2
    $\begingroup$ @TimCampion : I've met people who are comfortable accepting the 1-consistency of a large cardinal axiom but not the large cardinal axiom itself. Roughly speaking, they're suspicious of set theory and so don't want to endorse an actual set-theoretic axiom, but they're comfortable with arithmetic and are willing to accept "inductive evidence" that a set-theoretic axiom is 1-consistent. I don't know that anyone has tried to make this argument formally, though. $\endgroup$ – Timothy Chow Jun 21 at 20:17
  • $\begingroup$ @TimothyChow I'm not sure what you mean by "1-consistent" -- do you mean that the theory doesn't prove all arithmetic sentences? But then it follows that the theory is consistent, so 1-consistency comes out the same as consistency! I can see how there would be space to believe that large cardinals are consistent without believing that they're true. What I would find exotic would be the view that the arithmetic consequences of large cardinals are true, but the large cardinals themselves are not. $\endgroup$ – Tim Campion Jun 21 at 20:27
  • 2
    $\begingroup$ @TimCampion : 1-consistency is a standard technical term meaning that all $\Sigma_1^0$ consequences are true, or if you like, that every Turing machine that it claims halts really does halt. So it's a weak form of your "arithmetic consequences are true." Most of if not all of Harvey Friedman's "necessary uses of large cardinals" are combinatorial statements that are equivalent to the 1-consistency of a large cardinal axiom (and are provable by a slightly stronger large cardinal axiom). I know people who are willing to accept the combinatorial statement but not the large cardinal axiom itself. $\endgroup$ – Timothy Chow Jun 22 at 0:39
6
$\begingroup$

Let us abbreviate ZFCU = ZFC + "Every set is contained in a Grothendieck universe." Here is why ZFCU is a "safe" assumption. Suppose it actually is consistent. Then it cannot possibly prove any arithmetical statement that contradicts an arithmetical theorem of, for example, $n^{th}$-order PA for any $n$. This is because it proves that $n^{th}$-order PA has an "internally standard" interpretation, and so everything that it proves about the naturals is true of the "standard" model (i.e. within the theory ZFCU), and thus agrees with everything "true" (true according to ZFCU).

If we further assume that ZFCU has an actually standard model, then this means that all its arithmetical theorems are actually true. But this kind of begs the question, I think. We would like to know about some kind of coherency between various theories at a syntactical level, that they don't prove contradictory arithmetical statements (or other statements about "standard objects").

The idea, I believe, is that if we can organize them linearly in a "standard interpretation hierarchy," then we are fine as long as we believe in the consistency of the strongest theory under consideration. To be more precise, we look at theories $T$ which have a "natural numbers object" $\mathbb N^T$, which should at least satisfy PA. If $S$ is another such theory, and $T$ proves that $S$ has a model $\frak A$ such that $\mathbb N^{\frak A} = \mathbb N^T$, then $T$ and $S$ cannot disagree about what their respective natural numbers object satisfies.

I don't at present have an all-encompassing definition of "standard model," but here are some examples to illustrate the idea.

Example: ZFC proves that for all $n<\omega$, $\mathbb N$ satisfies $n^{th}$-order PA.

Example: ZFCU proves that for each $n<\omega$, there is a standard model of $I_n = $ ZFC + "There are exactly $n$ inaccessible cardinals." This should be the least rank $V_\alpha$ satisfying this theory, so that it is definable. Although the $I_n$ are mutually inconsistent and inconsistent with ZFCU, whatever $I_n$ proves, ZFCU proves it holds in $I_n$'s standard model. $I_n$ has a standard model of $I_m$ for $m<n$. Iterating the operation of taking standard models "commutes" in some sense.

Non-example: ZFCU proves the consistency of $I_1$ + $\neg Con(I_2)$. However, it proves that this does not hold in the standard model.

$\endgroup$
  • $\begingroup$ I think by "safe" I mean not just consistent with PA, but consistent with all arithmetic true we would naturally accept. This would include Con(PA) as well as Con(PA+Con(PA)), etc... It might also include deeper things like Goodstein's theorem. $\endgroup$ – Pace Nielsen Jun 20 at 0:39
  • 1
    $\begingroup$ @PaceNielsen well it proves all of the statements you mention... $\endgroup$ – Monroe Eskew Jun 20 at 6:06
  • 2
    $\begingroup$ There is a standard way to say that! "ZFC + Universes is conservative over ZFC for arithmetical statements." $\endgroup$ – Matt F. Jun 20 at 21:35
  • 1
    $\begingroup$ @MattF. But it’s not. The former proves Con(ZFC). $\endgroup$ – Monroe Eskew Jun 21 at 4:51
  • 1
    $\begingroup$ Indeed. So it would help to clarify the answer. $\endgroup$ – Matt F. Jun 21 at 10:49

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.