2
$\begingroup$

I am having trouble seeing why the Axiom of Infinity is necessary to construct an infinite set. According to a professor of who's mine teaching a class on "infinity," the Peano axioms are only adequate to establish the existence of all of the natural numbers, but not also that there is an infinite set consisting of them. To do so, we must stipulate not only the Axiom of Induction, but that there also exists an inductive set (via the Axiom of Infinity).

So, why does the existence of an infinite set of the natural numbers not just follow from the existence of all of the natural numbers?

$\endgroup$
  • 7
    $\begingroup$ Just because every natural number exists doesn't necessarily imply that there's an infinite set. After all: Every ordinal exists, but there is no set of all ordinals. $\endgroup$ – T. Bongers Jan 31 '16 at 3:01
  • 8
    $\begingroup$ There's nothing that says given any collection of objects there exists a set containing them. In fact inconsistencies arise if you allow that. So you have to show that a given set exists using the axioms, and you need more axioms to prove that particular set exists. $\endgroup$ – Matt Samuel Jan 31 '16 at 3:01
  • 3
    $\begingroup$ You've probably already learned that the set of all sets doesn't exist. Just replace the word "natural number" with "set" and you'll see that that argument isn't valid. $\endgroup$ – David Jan 31 '16 at 3:06
  • $\begingroup$ @MattSamuel thanks for your response. For clarification, do you mean that having a certain property/satisfying a predicate is not enough to determine a set? For example, we also spoke of inconsistencies arising from "comprehension," i.e., for any property P, there is a set whose members are the objects with property P. So, for a collection of objects each having the property of being a natural number, this is not enough to determine the existence of a set containing them? $\endgroup$ – ata Jan 31 '16 at 3:12
  • 2
    $\begingroup$ It would seem, then, that no set-existence axioms at all are needed. If the elements that are supposed to go into the set $S$ exists, then the set exists ipso facto, right? How do you keep from getting the universal set, or the Russell set? $\endgroup$ – bof Jan 31 '16 at 3:25
10
$\begingroup$

BrianO's answer is spot-on, but it seems to me you may not be too familiar with models and consistency proofs, so I'll try to provide a more complete explanation. If anything it may better steer you towards what you need to study, as admittedly I'm about to gloss over a lot of material.

Why do we need the axiom of infinity? Because we know (and can prove) that the other axioms of ZFC cannot prove that any infinite set exists. The way this is done is roughly by the following steps:

  • Remember a set of axioms $\Sigma$ is inconsistent if for any sentence $A$ the axioms lead to a proof of $A \land \neg A$. This can be written as $\Sigma \vdash A \land \neg A \to \neg Con(\Sigma)$
  • If $Inf$ is the statement "an infinite set exists", then $\neg Inf$ is the statement "no infinite sets exist".
  • The axiom of infinity is essentially the assumption that $Inf$ is true and hence $\neg Inf$ is false.
  • If we don't need the axiom of infinity, then with the other axioms $ZFC^* = ZFC - Inf$, we should be able to prove $Inf$ as a theorem, in other words we'll posit that $ZFC^* \vdash Inf$
  • We assume that $ZFC$, and hence the subset $ZFC^*$, are consistent.
  • We then add $\neg Inf$ as an axiom to $ZFC^*$, which we'll call $ZFC^+$
  • By showing that $(ZFC - Inf) + \neg Inf$ has a model (a set in which all the axioms are true when quantifiers range only over the elements of the set), we can prove the relative consistency $Con(ZFC) \to Con(ZFC^+)$. In other words we're basically just proving $ZFC^+$ is consistent, but we need to be explicit that this proof assumes $ZFC$ is consistent.
  • The model we want is $HF$, the set of all hereditarily finite sets. I'll leave it you to verify all the axioms of $ZFC^+$ hold in this set. But the important point is $HF \models ZFC^+$, and our relative consistency is proven. (This follows from Godel's completeness theorem)
  • We are assuming that $ZFC^* \vdash Inf$, but because $ZFC^+$ is an extension of $ZFC^*$ it must also be the case that $ZFC^+ \vdash Inf$. But then we have $ZFC^+ \vdash Inf \land \neg Inf$ and is thus inconsistent, a contradiction.

Thus we must conclude that our hypothesis $ZFC^* \vdash Inf$ is false and there is no proof of $Inf$ from the other axioms of ZFC. $Inf$ must be taken as an axiom to be able to prove that any infinite set exists.

$\endgroup$
  • $\begingroup$ Hi @DanSimon, thanks for the response, this was certainly helpful as a more involved demonstration. $\endgroup$ – ata Jan 31 '16 at 15:33
  • $\begingroup$ Thanks for delving deeper. You spelled out many connections that my admittedly terse response takes for granted. +1! $\endgroup$ – BrianO Feb 6 '16 at 12:10
8
$\begingroup$

The existence of each natural number follows from the other axioms of set theory, but if you drop the Axiom of Infinity (AxInfinity), the resulting theory ZFC-AxInfinity has a (transitive) model consisting of the hereditarily finite sets, which contains no infinite sets. The axioms of ZFC-AxInfinity provide no way to gather all the natural numbers into a single set.

$\endgroup$
  • $\begingroup$ It would be worthwhile to add that PA and ZFC-AxInf+$\neg$AxInf are bi-interpretable. $\endgroup$ – Pedro Sánchez Terraf Jan 31 '16 at 4:42
  • $\begingroup$ Thanks for your response, I'll have to look a bit more into ZFC and some of those other terms. $\endgroup$ – ata Jan 31 '16 at 5:45
  • $\begingroup$ @PedroSánchezTerraf It would — and thanks for doing so in your comment ;) It would take a fair amount of talk (about coding) to spell that out to an acceptable extent, so I'm inclined to refrain from adding it to the answer. $\endgroup$ – BrianO Jan 31 '16 at 6:23
1
$\begingroup$

The point is once you collect all the natural numbers into a set, you can now treat that set as an atomic object like any other and you can do all the things you can do with a set to it. So, for example, you can make a set that has the set of natural numbers as an element, you can construct the powerset of natural numbers, you can make functionals (functions taking functions) of natural number functions.

The radical thing about Cantor's set theory was the combination of sets that can contain sets (with the usual operations from finite set theory) and infinite sets. Each idea alone isn't that big a deal. Finite set theory is a perfectly reasonable thing, powersets included. Having a "type" of natural numbers, is also a reasonable thing, it just states what operations you are allowed to do on things that have that type. In particular, in (simple) type theory, you can't make a function that returns a type itself, whereas in set theory it is a completely valid definition to say: $f(1) = \mathbb{N}; f(2) = \mathbb{Z}$.

So the crucial thing is, in the context of the overall theory of sets, the Axiom of Infinity states that not only do the natural numbers exist (effectively) but that you can hold it in your hands and manipulate the set as a whole like any other. This is what finitists rebel against. They don't have a problem with an "infinitude" of natural numbers (though they would say an "unbounded amount"), but with being able to manipulate that infinitude in the exact same way you would manipulate the finite set: $\{1, 2, 3\}$.

$\endgroup$
  • $\begingroup$ Thanks for your response. I see here why it's useful to have this set, but I still don't see from this how the axiom of infinity is necessary to obtain it/why it's not possible to construct the set without this axiom. $\endgroup$ – ata Jan 31 '16 at 5:45
  • $\begingroup$ Yeah, this doesn't answer that question. Your question then, is whether the Axiom of Infinity is derivable from the other axioms of ZFC and the easiest way to show it isn't is via the means BrianO discusses, i.e. providing a model where it is false. $\endgroup$ – Derek Elkins Jan 31 '16 at 5:52
  • 1
    $\begingroup$ @ata In the absence of AxInfinity, which axioms will you use to form the set of all integers? The only possible candidates are the replacement schema and comprehension schema. Comprehension only lets you isolate a subset of an already existing set; replacement only lets you form the range of a definable single-valued function applied to an existing set. It's not hard to see (prove, by induction on formulas) that neither of these can yield an infinite set if applied to finite sets, which is why the hereditarily finite sets provide a model of ZFC-AxInfinity. $\endgroup$ – BrianO Jan 31 '16 at 6:26
  • $\begingroup$ @BrianO Think I'm starting to understand it a little better now, thanks for your help. $\endgroup$ – ata Jan 31 '16 at 15:34
  • $\begingroup$ @ata You're welcome. $\endgroup$ – BrianO Jan 31 '16 at 15:37

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.