# If all sets were finite, how could the real numbers be defined?

An extreme form of constructivism is called finitisim. In this form, unlike the standard axiom system, infinite sets are not allowed. There are important mathematicians, such as Kronecker, who supported such a system. I can see that the natural numbers and rational numbers can easily defined in a finitist system, by easy adaptations of the standard definitions. But in order to do any significant mathematics, we need to have definitions for the irrational numbers that one is likely to encounter in practice, such as e or sqrt(2). In standard constructions, real numbers are defined as Dedekind cuts, or Cauchy sequences, which are actually sets of infinite cardinality, so they are of no use here. My question is, how would a real number like those be defined in a finitist axiom system. (Of course we have no hope to construct the entire set of real numbers, since that set is uncountably infinite.)

After doing a little research I found a constructivist definition in Wikipedia http://en.wikipedia.org/wiki/Constructivism_(mathematics)#Example_from_real_analysis , but we need a finitist definition of a function for this definition to work. (Because in the standard system, a function over the set of natural numbers is actually an infinite set.)

So my question boils down to this: How can we define a function f over the natural numbers in a finitist axiom system?

Original version of this question, which had been closed during private beta, is as follows:

If all sets were finite, how would mathematics be like?

If we replace the axiom that 'there exists an infinite set' with 'all sets are finite', how would mathematics be like? My guess is that, all the theory that has practical importance would still show up, but everything would be very very unreadable for humans. Is that true?

We would have the natural numbers, athough the class of all natural numbers would not be a set. In the same sense, we could have the rational numbers. But could we have the real numbers? Can the standard constructions be adapted to this setting?

-
Voting to close because I can't imagine there being a meaningful answer to this question –  BlueRaja - Danny Pflughoeft Jul 22 '10 at 16:13
Sure, you can only allow finite sets: just replace every real number $x$ defined by a Dedekind cut with the set $\{ x\}$. This is not very interesting though, since the entries of the finite sets can range over uncountably many things--but this is unavoidable, the reals being uncountable. –  Akhil Mathew Jul 22 '10 at 16:40
@Akhil: Dedekind cuts are infinite sets. I don't think this idea works. –  AgCl Jul 22 '10 at 23:24
@AgCl: you might be interested in reading terrytao.wordpress.com/2010/03/19/… . –  Qiaochu Yuan Jul 29 '10 at 22:02
@AgCl: in particular, you can define a constructible real number like the square root of 2 by defining an algorithm which takes as input a rational number and returns Yes if the rational number is less than the square root of 2 and No otherwise. This algorithm is "finite." –  Qiaochu Yuan Jul 29 '10 at 22:05
show 4 more comments

Set theory with all sets finite has been studied, is a familiar theory in disguise, and is enough for most/all concrete real analysis.

Specifically, Zermelo-Fraenkel set theory with the Axiom of Infinity replaced by its negation (informally, "there is no infinite set") is equivalent to first-order Peano Arithmetic. Call this system finite ZF, the theory of hereditarily finite sets. Then under the Goedel arithmetic encoding of finite sets, Peano Arithmetic can prove all the theorems of Finite ZF, and under any of the standard constructions of integers from finite sets, Finite ZF proves all the theorems of Peano Arithmetic.

The implication is that theorems unprovable in PA involve intrinsically infinitary reasoning. Notably, finite ZF was used as an equivalent of PA in the Paris-Harrington paper "A Mathematical Incompleteness in Peano Arithmetic" which proved that their modification of the finite Ramsey theorem can't be proved in PA.

Real numbers and infinite sequences are not directly objects of the finite ZF universe, but there is a clear sense in which real (and complex, and functional) analysis can be performed in finite ZF or in PA. One can make statements about $\pi$ or any other explicitly defined real number, as theorems about a specific sequence of rational approximations ($\forall n P(n)$) and these can be formulated and proved using a theory of finite sets. PA can perform very complicated induction proofs, i.e., transfinite induction below $\epsilon_0$. In practice this means any concrete real number calculation in ordinary mathematics. For the example of the prime number theorem, using complex analysis and the Riemann zeta function, see Gaisi Takeuti's Two Applications of Logic to Mathematics. More discussion of this in a MO thread and my posting there:

http://mathoverflow.net/questions/31846/is-the-riemann-hypothesis-equivalent-to-a-pi-1-sentence

http://mathoverflow.net/questions/31846/is-the-riemann-hypothesis-equivalent-to-a-pi-1-sentence/31942#31942

Proof theory in general and reverse mathematics in particular contain analyses of the logical strength of various theorems in mathematics (when made suitably concrete as statements about sequences of integers), and from this point of view PA, and its avatar finite set theory, are very powerful systems.

-

Disclaimer: I am not a finitist --- but as a theoretical computer scientist, I have a certain sympathy for finitism. The following is the result of me openly speculating what an "official" finitist response would be, based on grounds of computability.

The short version is this: (a) It depends on what you mean by a 'number', but there's a reasonable approach which makes it reasonable to talk about finitistic approaches to real numbers; (b) What you can do finitisitically with numbers, real, rational, or otherwise, depends on how you represent those numbers.

1. What is a number? Is −1 a number? Is sqrt(2) a number? Is i = sqrt(−1) a number? What about quaternions? --- I'm going to completely ignore this question and suggest a pragmatic, formalist approach: a "number" is an element of a "number system"; and a "number system" is a collection of expressions which you can transform or describe properties of in some given ways (i.e. certain given arithmetic operations) and test certain properties (e.g. tests for equality, ordering, etc.) These expressions don't have to have a meaningful interpretation in terms of quantities or magnitudes as far as I'm concerned; you get to choose which operations/tests you care about.

A finitist would demand that any operation or property be described by an algorithm which provably terminates. That is, it isn't sufficient to prove existence or universality a la classical logic; existence proofs must be finite constructions --- of a "number", that is a representation in some "number system" --- and univserality must be shown by a computable test.

2. Representation of numbers: How we represent the numbers matters. A finitist should have no qualms about rational numbers: ratios which ultimately boil down to ordered pairs. Despite this, the decimal expansions of these numbers may be infinitely long: 1/3 = 0.33333... what's going on here?

Well, the issue is that we have two representations for the same number, one of which is finite in length (and allows us to perform computations) and another which is not finite in length. However, the decimal expansion can be easily expressed as a function: for all k, the kth decimal place after the point is '3'; so you can still characterize it precisely in terms of a finite rule.

What's important is that there exists some finite way to express the number. But the way in which we choose to define the number (as a part of system or numbers, using some way of expressing numbers) will affect what we can do with it... there is now a question about what operations we can perform.

--- For rationals-as-ratios, we can add/subtract, multiply/divide, and test order/equality. So this representation is a very good one for rationals.

--- For rationals-as-decimal-expansions, we can still add/subtract and multiply/divide, by defining a new digit-function which describes how to compute the result from the decimal expansions; these will be messier than the representations as ratios. Order comparisons are still possible for distinct rationals; but you cannot test equality for arbitrary decimal-expansion representations, because you cannot necessarily verify that all decimal places of the difference |ab| are 0. The best you can do in general is testing "equality up to precision ε", wherein you show that |ab| < ε, for some desired precision ε. This is a number system which informally we may say has certain amount of "vagueness"; but it is in principle completely specified --- there's nothing wrong with this in principle. It's just a matter of how you wish to define your system of arithmetic.

3. What representation of reals? Obviously, because there are uncountably many real numbers, you cannot represent all real numbers even if you aren't a finitist. But we can still express some of them. The same is true if you're a finitist: you just don't have access to as many, and/or you're restricted in what you can do with them, according to what your representation can handle.

--- Algebraic irrational numbers such as sqrt(2) can be expressed simply like that: "sqrt(2)". There's nothing wrong with the expressions "sqrt(2) − 1" or "[1 + sqrt(5)]/2" --- they express quantities perfectly well. You can perform arithmetic operations on them perfectly well; and you can also perform ordering/equality tests by transforming them into a normal form of the type "[sum of integers and roots of integers]/[positive integer]"; if the difference of two quantities is zero, the normal form of the difference will just end up being '0'. For order comparisons, we can compute enough decimal places of each term in the sum to determine whether the result is positive or negative, a process which is guaranteed to terminate.

--- Numbers such as π and e can be represented by decimal expansions, and computed with in this form, as with the rational numbers. The decimal expansions can be gotten from classical equalities (e.g. "infinite" series, except computing only partial sums; a number such as e may be expressed by some finite representation of such an 'exact' formula, together with a computable function which describes how many terms of the series are required to get a correct evaluation of the first k decimal places.) Of course, what you can do finitistically with these representations is limited in the same way as described above with the rationals; specifically, you cannot always test equality.

-
Your decimal representations of rationals still allows for finite time exact algorithms, because you are guaranteed that only finitely many digits need to be handled before all operands have entered their 'repeat' stage. –  Larry Wang Aug 5 '10 at 2:39
And if you do not start from a rational representation, when do you know that the repitition has begun? –  Niel de Beaudrap Aug 14 '10 at 13:09

There is a fragment of mathematics that is given by a set of axioms known as the Peano axioms. Using these rules you can carry out a vast amount of mathematics relating to natural numbers. For example you can prove lots of theorems in number theory using these axioms. The Peano axioms make no reference to sets at all, whether finite or infinite. The only things that exist in this theory are naturals. You can't even form the set of all integers. You can only talk about the naturals themselves. So a vast amount of mathematics would work absolutely fine.

Even though Peano's axioms are about naturals, you can already use them to talk about finite sets. The idea is that any finite set could be encoded as a finite sequence of symbols which in turn could be represented as naturals using Godel numbering. So questions like "is this set a subset of that one?" could be turned into purely arithmetical statements about Godel numbers.

So I'm pretty sure that declaring that there is no infinite set would make little difference to people working within the system defined by Peano's axioms. We'd still have all of the natural numbers to work with, we just wouldn't be able to assemble them into a single entity, the set of all natural numbers.

On the other hand, there are theorems that make essential use of an infinite set. Like Goodstein's theorem. Without infinite sets (or a substitute of some sort) it would be impossible to prove this result.

So the overall result would be, I think, that you could still do lots of mathematics fine. The mathematics you could do wouldn't be all that weird. And you'd simply be depriving yourself of a useful proof technique.

By the way, you'd still be able to say many things about real numbers. A real number can be thought of as a Cauchy sequence. A Cauchy sequence is a certain type of sequence of rational numbers. So many statements about real numbers, when unpacked, are really statements about rational, and hence naturals, but in disguise.

Update: Uncovering precisely what parts of mathematics you need in order to prove things is a field known as reverse mathematics. Hilbert, and others mathematicians, were interested in trying to prove as much mathematics as possible using finite methods. Although it was ultimately shown that you can't carry out all mathematics using finite methods, it's surprising how much you can. Here's a paper that talks about a system called EA which has no infinite sets. Amazingly we can use results from analytic number theory in EA. This is because propositions about analytic functions can be interpreted as statements about natural numbers.

-
Not true. The real numbers would not even exist, it just wouldn't make sense for them to. –  Noldorin Jul 22 '10 at 16:31
@Noldorin You are confusing two things. There is the set of real numbers and the real numbers themselves. You could not construct the set of real numbers, but you can still reason about real numbers by not constructing sets of them. In Peano arithmetic you can make statements about all of the natural numbers despite there being no set of all natural numbers. The same goes for some statements about real numbers. –  Dan Piponi Jul 22 '10 at 16:37
How can you reason about them if they don't exist? Perhaps we're moving into the debate about constructivism versus intuitionism in mathematics now? –  Noldorin Jul 22 '10 at 16:52
@Noldorin Firstly, constructivism isn't normally opposed to intuitionism. Constructivism and intuitionism (which are closely related) are opposed to classical mathematics. And this is only tangentially related. You can reason about (some) real numbers, using the naturals, by interpreting statements about real numbers as being statements about natural numbers in disguise. You can even reason about (some) infinite sets this way using Peano arithmetic. This mentions the encoding of infinite ordinals up to $\epsilon_0$ as finite objects: en.wikipedia.org/wiki/Peano_axioms#Consistency –  Dan Piponi Jul 22 '10 at 18:04
I'm feeling it. –  Jonathan Fischoff Jul 23 '10 at 6:30

Finitism still allows you to use infinitary definitions of real numbers, because a finitist is content with finite proofs even if the concepts mentioned by those proofs would seem to require infinite sets. For example, a finitist would still recognize that "ZFC proves that every bounded nonempty set of reals has a least upper bound" even if the finitist does not accept that infinite sets exist.

Proofs in various infinitary systems are of interest to finitists because of conservation results. In this setting, a conservation result would show that if a sentence about the natural numbers of a certain form is provable in some infinitary system, the sentence is actually provable in a finitistic system. For example, there are finitistic proofs that if any $\Pi^0_2$ sentence about the natural numbers is provable in the infinitary system $\text{WKL}_0$ of second order arithmetic, that sentence is also provable in the finitistic system $\text{PRA}$ of primitive-recursive arithmetic.

Many consistency results are proven finitistically. For example, there is a finitistic proof that if ZF set theory without the axiom of choice is consistent, then ZFC set theory with the axiom of choice is also consistent. This proof studies infinitary systems of set theory, but the objects actually handled are finite formal proofs rather than infinite sets.

-

well: sqrt(2), e and \pi were defined before set theory was even conceived ;-)

I think that algebraic numbers could have been defined without resorting to the standard theory of real numbers, just looking at them as roots of polynomials; certain classes of transcendent numbers could also, but I wonder if there is "finitistic" way to define e. I am at loss with this.

-
I think the OP actually is asking what things would be like if mathematics itself were different in this way, not our knowledge of mathematics. –  Noldorin Jul 22 '10 at 16:16
I believe there should a way to define e in a finistic way, and I would like to learn how. –  AgCl Jul 22 '10 at 16:22
@Noldorin: if nobody could define e in a finitistic way, math would be different. I am just stating I am not be able to define e in such a way, but this really means nothing. I rephrased my answer. –  mau Jul 22 '10 at 16:24
There are algorithms that can output e to arbitrary precision. I wonder if that counts. –  Chao Xu Jul 22 '10 at 16:25
@Noldorin You are simply plain wrong. @Mgccl gives a perfectly good example of how you can reason about e using finite methods. You can prove things about e using finite machines running for a finite amount of time. You can reason about machines using finite mathematics. You don't need "the concept of infinity". –  Dan Piponi Jul 22 '10 at 20:48
show 2 more comments

You wouldn't even have the natural numbers (in totality), let alone the real numbers (or complex numbers) at all. The reals form an uncountably infinite set and it is the arbitrarily small spacing between them that really gives them their unique properties.

As a consequence, you certainly wouldn't have anything like calculus and thus no mathematical analysis whatsoever! Mathematics would not be mathematics in effect. It's almost an inherent contradiction to ask this question. Does that not say enough?

-
why no calculus? definition of limit with epsilons and deltas does not need an infinite set, and you should be able to define derivatives on functions over Q. –  mau Jul 22 '10 at 16:19
@Noldorin Statements about real numbers can be unpacked as statements about naturals. For example, stating that $\sqrt{2}$ is irrational can be unpacked as a statement that given a rational approximation to $\sqrt{2}$ (a notion that can be defined using just naturals) you can always find a better approximation, but never an exact solution to $a^2=2b^2$. –  Dan Piponi Jul 22 '10 at 16:32
@Noldorin if you use just rational numbers, there can be an arbitrarily small gap between two numbers. We developed calculus with real numbers just because we started with real numbers; Robinson developed non-standard analysis just avoiding the Archimedean property, but leaving all other things; why can't we develop calculus over Q or algebraic numbers? –  mau Jul 22 '10 at 17:10
@mau: The short answer is the rationals are not complete. –  Akhil Mathew Jul 23 '10 at 2:17
@Noldorin: I didn't downvote this, but you're confusing the matter of what sets are allowed with… something else you have in mind. With only finite sets allowed, you can still talk of natural and rational numbers, just not the set of naturals or the set of rational numbers. You can also talk of many real numbers, like √2 and π. You can still do some calculus (the epsilon-delta definition of a limit is still valid) but you can't take the supremum of an arbitrary set, etc. Look up constructivism, linked in the question. –  ShreevatsaR Aug 5 '10 at 17:05
show 6 more comments