10
$\begingroup$

According to my readings, Russell showed that a principle Frege used to reduce Peano arithmetic to logic lead to a contradiction. So, Russell tried to reduce mathematics to logic a different way but realized that he needed things such as an infinity axiom to get his reduction off the ground. But of course, that there are infinite collections is not just a matter of logic. So it seems that Russell just had to stipulate an infinity axiom. (This is just background.)

So, in modern set theory, is the axiom of infinity just stipulated? Or is there an argument for its truth?


Some directions:

G. Boolos derived the ZFC axioms from the iterative conception of set, and thus gave a motivation or argument in favor of the axiom of infinity.

Or, someone might think, as Cantor did, that all consistent mathematical results have (material?) instantiations in nature. Much of mathematics is dependent on the natural numbers, the real numbers, etc., and thus there is reason to accept axioms of infinity.

There are some similar threads to mine:

  1. Math without infinity?
  2. Do infinity and zero really exist?
  • 5
    Do you want induction? Do you want to be able to speak about the set of natural numbers in order to _state_ induction? (This isn't a completely rhetorical question. Some people reject the full strength of induction precisely because they don't believe the natural numbers ought to exist as a "completed infinity.")2012-06-07
  • 9
    I'm a little confused, because all axioms are, by definition, stipulated.2012-06-07
  • 21
    I don't think the existence of anything follows from logic alone.2012-06-07
  • 0
    @QiaochuYuan Do you really need need infinite sets for induction. There is first order arithmetics, where you have induction, even though $\omega$ itself is not formally an object of first order arithmetics. However, I believe you need the axiom of infinite to have something called an inductive set.2012-06-07
  • 0
    @William: Yes, in ZFC it is just so. In fact the axiom of infinity says that there exists an inductive set.2012-06-07
  • 1
    @William: well, a model of PA is an infinite set even if PA doesn't talk directly about infinite sets. So if you want set theory to be capable of constructing models of PA...2012-06-07
  • 0
    @QiaochuYuan I don't know about the desirability of being to actually produce a model of PA as strong reason to include the axiom. Is being able to formally prove the consistency of PA that important. ZF - INF has the Heriditarily Finite Sets as a model. Maybe there is a subclass (not set) of this model that can serve as a model of PA.2012-06-08
  • 0
    @William: you wrote "I don't know about the desirability of being to actually produce a model of PA _as strong reason to include the axiom_." All I'm asking for is such a reason. What is a strong reason for including it?2012-06-08
  • 0
    @pichael: What is different about your question than the one you linked, so that the answers to the other question don't answer yours?2012-06-08
  • 3
    @pichael The axiom of infinity is great because it allows you to consider more interesting aspect of ordinals and cardinals. However, plenty of math can be done in first order arithmetics or ZF - Inf which has model the hereditarily finite sets. Here you just have to take the finitist view that HF or $\mathbb{N}$ is just a abbreviation and not a real object within the system.2012-06-08
  • 0
    @Hurkyl: I guess nothing. I saw those other questions after I posted this one. Should I just delete it?2012-06-08
  • 0
    possible duplicate of [Math without infinity](http://math.stackexchange.com/questions/50629/math-without-infinity)2012-06-08
  • 0
    @pichael: Deleting it is probably wrong: other threads I've seen have simply been closed as a duplicate. I've made a vote to close as duplicate (My first one since getting the power), but since nobody else has, I suppose the topic is interesting enough that people want another thread on it.2012-06-09

6 Answers 6

2

The Axiom of Infinity in ZFC, gives you a successor function $S(x)=x\cup \{ x \} $ from which you can construct the equivalent of the infinite set of natural numbers.

If you find that a bit strange, as I do, another approach is to simply define the natural numbers by means of some equivalent of Peano's Axioms which describe the required properties of a successor function on the set of natural numbers in set-theoretic terms, as you would, say, for the group or ring axioms.

Still another approach is to construct the set of natural numbers starting from the axioms for a complete ordered field (the real numbers).

  • 1
    You ought to be able to create the naturals without the reals. Most (all) constructions of the reals rely on the naturals. The flow is in the other direction.2012-06-13
  • 0
    It's much easier starting with the reals. See my formal derivation at http://www.dcproof.com/DerivingPA.htm2012-06-13
  • 1
    BTW, the Axiom of Infinity has nothing to do with resolving Russell's Paradox. To get around RP, ZFC has the Axiom of Regularity and the Axiom Schema of Separation.2012-06-13
  • 4
    The successor function has nothing to do with the axiom of infinity. It is well definable without it. With or without this axiom the function $x\mapsto S(x)$ is a proper class as it can be applied to *all* sets in the universe. The axiom of infinity says that there is a **set** which contains $\varnothing$ and is closed under $S$. Without the axiom of infinity this would simply amount to a class, which may be a set or a proper class depending on the universe.2012-06-13
  • 0
    The axiom of infiting simply says there an infinite set, nothing more, no direct relation to successor or natural numbers.2012-06-13
  • 1
    The Wiki article on ZFC makes clear mention of a successor function S under the heading "Axiom of Infinity" http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory#7._Axiom_of_infinity2012-06-13
11

If you believe in the set of natural numbers you already accept the axiom of infinity. For most mathematician existence of the set of natural numbers is an intuitively clear fact that doesn't need an argument so mathematicians are typically not bothered with the axiom. In addition lots of classical mathematics depends on such infinite concepts.

The question of accepting or rejecting such an axiom is mainly interesting for philosophers not mathematicians. One can reject the axiom of infinity (such people are often called finitists) but most mathematicians do not. They believe in the existence of the set of natural numbers and therefore see the axiom of infinity as a trivially true fact.

  • 1
    Historically, most mathematicians rejected that we can construct a complete set with all natural numbers. The reasons most mathematicians believe in it, probably had more to do that any textbook they ever read assumed such a set exists. I believe that we can construct any natural number which we would be practically interested in, but I have never seen anyone being able to construct the complete set of all natural numbers.2018-06-02
  • 0
    1. To accept the existence of the set of natural numbers doesn't mean accepting it as a completed construction, e.g. intuitionist accept existence of the set of natural numbers but not as a completed construction. 2. The concept of set is rather new, any referral to history before that and saying mathematicians didn't accept it is misleading, they didn't know about it. Since Cantor almost all mathematicians have accepted the existence of set of natural numbers, you would have hard time finding those who have rejected its existence. There are not that many finitists.2018-06-02
  • 0
    3. Note also that even finitists accept quantifying over natural numbers, one has to be very careful to allow quantifying over natural numbers but not allow treating the set of natural numbers as an object, without getting into trouble (essentially I think they have to be a logician).2018-06-02
  • 0
    1. What does it mean for an object to exists if it can not be constructed? This seems just logical impossible to me. I guess it is seen as an object that already magically was there at the beginning of the (mathematical) universe, but can not be reconstructed again. It sounds like some kind of divine object. It may be interesting to think about, but because of the vague and inprecise nature of this topic it seems to belong more to philosophy or religion than to mathematics.2018-06-04
  • 0
    2. The formalization of set theory is new, but the discussion about infinite mathematical objects is not. The greek believed that there is a potential infinity (for example, the sequence of natural numbers) but not an actual infinity (for example, the set of natural numbers). You can also observe this in the fact that Euclid didnt say that the set of prime numbers is infinite, he said something like: “No matter how many prime numbers you are able to describe, there exist more prime numbers than those.” In more recent history, Gauss refuted the idea of an “actual” infinity.2018-06-04
  • 0
    3. Yes, I dont see a logical problem with this. That is also how historically this is done. “Given n be a natural number. It follows ...” Instead of: “For all n in the set of natural numbers, ...” You dont really need the axiom of infinite sets to study natural numbers. The reasons mathematicians wanted it it (and wishfully started believing in it) had probably much more to do that infinite sets are used for modelling irrational numbers.2018-06-04
  • 1
    Sorry, but we are not discussing your beliefs here (which seem to be some restricted flavor of constructive mathematics, which is again different from finitism), not discussing which philosophy of mathematics is the right one (assuming there is one). Classical mathematicians, which historically make very large majority of mathematicians, believe in existence of N as an object. Many constructists also accept axiom of infinity, e.g. look up the intuitionistic set theory IZF.2018-06-04
9

It is possible and interesting to have as our axiom system the usual ZF, but with the Axiom of Infinity replaced by its negation. The resulting theory, which one might call the theory of (hereditarily) finite sets, turns out to be bi-interpretable with first-order Peano arithmetic.

9

A finitist, who rejects the axiom of infinity, will be denied both the Dedekind and Cauchy constructions of real numbers. The problem? The reals are uncountable (Cantor showed this), and in a finitist's universe, the universe itself is countable.

$V_0=\varnothing$

$V_{n+1}= \mathscr P (V_n)$ where $\mathscr P$ denotes the powerset.

The universe if we accept the negation of the axiom of infinity is $V_\omega=\bigcup_{x\in\omega} V_x$, a countable union of at most countable sets.

  • 1
    Note that the problem with the Cauchy and Dedekind Cut construction in finitistic mathematics come well before Cantors uncountability argument. Finistist have $\omega$, as an abbreviation, but $\omega$ is not a real object. However in the Cauchy Construction, your objects are equivalent class of sequence. Sequences are function on $\omega$. So you need $\omega$ to exists for this construction. Similary, Dedekind Cut construction are pairs of infinite sets of rational numbers, which again do not exists in finite math.2012-06-08
  • 1
    I am not sure if a finitist would even believe in the Cantor Diagonalization argument since it require you to assume the existence of a bijection from $\omega \rightarrow \mathbb{R}$ and they do not believe that either exists as a formal object.2012-06-08
  • 0
    @William: It doesn’t assume the existence of such a bijection; it’s a machine that when given a function from $\omega$ to $\Bbb R$ constructs a real number not in the range of the function. (This may be just as objectionable to a finitist, of course.)2012-06-08
  • 0
    @BrianM.Scott What is a machine? Finistic certainly believe in Turing Machines. However, how will you represent a real number. Finistic believe in anything that can be encoded as a natural number. But if you encode a real number as decimal expansion, binary expansion, equivalence class of Cauchy Sequence, Dedekind cut, you will formally require the existence of at least $\omega$. Functions on $\omega$ are also infinite objects.2012-06-08
  • 0
    @BrianM.Scott Also there is a subtle distinction. Finistic do believe in the formal proof Cantor Argument of the uncountability of $\mathbb{R}$ (or any other theorem of ZFC) in the formal language of ZFC. This is because proofs are essentially finite objects. So finitist will agree that Cantor proof is correct as purely logical finite manipulation of symbols. But they probably won't believe that your manipulation or your axiom describe anything real and interesting.2012-06-08
  • 0
    @William: I think that you missed my point. I’m not arguing about the beliefs of finitists; I frankly don’t care, since I’m not interested in doing mathematics with one hand tied behind my back. I’m merely pointing out that the diagonal argument does **not** require the assumption that there is a bijection between $\omega$ and $\Bbb R$. As for the machine, it’s as nice as the class of functions you allow.2012-06-08
  • 0
    @BrianM.Scott How do you prove the uncountability of $\R$? Usually for simplicity, we will prove binary sequence $\omega \rightarrow \{0,1\}$ are uncountable? Before even going on, a finitistic would be believe such function exists, but lets return to Cantor Argument, if you like you can think this as the Cantor Set insider $\mathbb{R}$. Usually you assume there is a bijection $f$ from $\omega$ into the set of all binary sequences. Then you go along diagonal and produce a binary sequence that is unequal to $f(n)$ for all $n$. Contradiction.2012-06-08
  • 0
    @BrianM.Scott (sorry too long; continuing) This usually the spirt of the diagonalization argument. Note that the assumption that the set binary sequence is countable is essential. How does your argument go?2012-06-08
  • 0
    @BrianM.Scott Be nicer to finitist! For all we know, the axiom of infinity could lead to inconsistencies of set theory.2012-06-08
  • 3
    @William: There is absolutely no need to assume a bijection. The diagonal argument shows directly, without any appeal to contradiction, that no function from $\omega$ to $\Bbb R$ is surjective.2012-06-08
  • 0
    One can work with recursive reals which are countable. ps: one doesn't need to be a finitist to reject the classical reals à la Dedekind/Cauchy.2012-06-09
4

As a formalist, I echo the comment of Neal that says "axioms are, by definition, stipulated". The real question is whether the structure so axiomatized is interesting, or worth study.

As many mathematicians make arguments that involve a set of natural numbers, it follows that a good universe of sets should include a set of natural numbers. Whether its existence is an axiom or a theorem is not really important; that's merely matter of exposition. Exposition is important of course, but I wanted to emphasize that's all it is.

Now, I also like to observe the close analogy between logic and set theory. IMO, that's really the main reason why set theory has attained the importance it has: it's really just a systematization of the things we like to do with logic.

For example, if I decide to play at being a finitist and consider finite set theory, I can still meaningfully say the word "natural number", and consider predicates like "$x$ is a natural number". This lets me say things about the class of natural numbers, consider class functions on the natural numbers like $f(x) = x+1$, consider predicates on the class of natural numbers like "E(x) := $x$ is even", quantify predicates over the natural numbers such as $\forall x \in \mathbb{N} : E(x) \leftrightarrow \neg E(x+1)$, and so forth.

And because I can consider predicates like E(x), this means I can also talk about the class of even natural numbers.

If I can consider one variable denoting a natural number, I can consider two variables denoting natural numbers: I can talk about the class $\mathbb{N} \times \mathbb{N}$.

If one is of the sort to focus on such things, one can talk about mechanically translating all such statements into equivalent statements in an untyped language of finite set theory, and keep thinking in the back of one's mind that one is actually working with these untyped statements rather than the more suggestive ones the notation indicates.

While such a translation is possible, and it's a good thing to know, I think the way of thinking is unjustified -- the fact that translation is possible means that you should have no qualms about thinking in terms of the new and suggestive ideas rather than handicapping yourself with a restrictive thought process.

So really, when I'm playing at being a finitist, I still have access to a limited amount of set theory that includes a set of natural numbers. NBG set theory codifies this into having "sets" and "classes". NBG with anti-infinity has two sorts of objects: sets, and classes. The natural numbers would be a (proper) class. I assume that in the presence of anti-infinity, NBG is still 'equivalent' to ZFC.

If I further allow myself to consider second-order logic, I can do more. My objects now include first-order predicates. I can consider the second order predicate "$\varphi(P) := \forall x: P(x) \implies x \in \mathbb{N}$". In other words, I can now talk about subsets of the natural numbers.

If I don't stop there and go all the way up to higher order logic, then I can do this for every type. In the logic-set theory analogy, I now consider power sets. I assert that this means that all of the types I can talk about are organized into a Boolean topos with natural number object -- in other words, that the higher order logic of finite set theory is an instance of the first-order logic of bounded Zermelo set theory (with infinity). Bounded means that I'm never allowed to just say $\forall x: \cdots$ instead, $x$ must be bound to some set/type, as in $\forall x \in T: \cdots$.

Because of all of these things, I am thoroughly unpersuaded when a finitist rejects the notion of a set of natural numbers. I could understand being restrictive in what sorts of things you can do with said set, but rejecting it outright is, IMO, a silly notion which I ascribe more to simply having a contrary attitude than substantive content.

  • 0
    I've been asking a lot of question about Skolem's Paradox here. You're post interested me for the following reason. You post mentioned the usefulness of higher-order logics. Now, I've heard (1) that countability is relative in first order logic whereas in second order logic it is not and (2) that people (mathematicians/philosophers) don't reject the relativity of countability on the grounds that second order logic is "better," but for other reasons. Do you know what these "other" (probably more philosophical) reasons are? Do you yourself have a view? Thanks for the great post.2012-06-10
  • 0
    Just as side note, without enough assumptions about natural numbers one cannot manipulate symbols, so formalist already assume syntax manipulations which is similar to manipulation of natural numbers. Also using unbounded quantifiers is typically not considered finitism.2012-06-10
  • 1
    @pichael: I have no problem with relativity of countability myself. I do not maintain an external, absolute notion of countability but instead accept that each suitable sort of structure -- e.g. a universe of sets -- can define its own meaning, and various different structures simply may or may not agree in situations where they can both speak about an object. There's also another point of view (I'm not sure what I think about it) that cardinality is more about complexity than counting. So the countable model in Skolem's paradox really just lacks the *complexity* to construct a bijection.2012-06-11
  • 0
    @Kaveh: For the record, throughout the construction, I'm thinking things like 'Cartesian category' or 'topos' in the back of my mind, and the internal logic of such things is indeed bounded. I'm correct in assuming a finitist is allowed to quantify over the natural numbers?2012-06-11
  • 0
    @Hurkyl, the problem is that finitism is not just one specific philosophy. What I remember is that unbounded quantification is not considered finitistic because it is expressing a non-finite statement, there is not much difference between the set of natural numbers satisfying the formula and the formula itself, one doesn't need to consider the extension a set, simply assuming that the formula has a truth value for each particular assignment (of natural numbers to its free variables) would go over what a finitist is ready to accept. Take for example Hilbert's work in logic and proof theory2012-06-11
  • 0
    , the use of epsilon notation in place of existential quantifiers in his and his students work is not just a matter of taste. Some experts consider quantifier-free PRA as an upperbound for finitism (e.g. Bill Tait?). IIRC, for a finitist a quantified formula always comes with a bound. (Unfortunately I cannot think of a reference right now, I might have read these in Kleene's "Metamathematics"). What you are describing seems more in line with constructive schools like intuitionism. Finitists accept way less than what intuitionists accept.2012-06-11
2

Frege's set theory leads to contradictions and we aim to move away from it by using Zermelo set theory or NBG set theory, however to move into these more developed (or more constricted) types, we need to define the universe very well in how our classes and sets behave.

Recall that a class is a basic universe if it follows 6 specific axioms, for the class to be transitive, swelled, to include the empty set and the power set of any x in the class, to include any union of any x in the class and to include {x,y} for any x and y in the class.

We cannot move onto Zermelo set theory or NBG by the definition of the universe I have just given; we add in a new axiom, we accept that the set of natural numbers can be included in our universe, which is now no longer basic and thus a Zermelo universe.

I would argue that the axiom of infinity guarantees the existence of infinite sets, however arguments such as a large amount of work being placed on the natural and real numbers are poor ones for the support and supposed truth of the axiom of infinity, say we find out that this axiom causes trouble to some framework; our arguments for placing huge emphasis on the real and natural numbers do us no favour at this point, rather we use the axiom to construct set theory further.