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

Question

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 the 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?

Answer 1

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:

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

https://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.

Answer 2

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 k^th 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 |a−b| are 0. The best you can do in general is testing "equality up to precision ε", wherein you show that |a−b| < ε, 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.

Answer 3

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.

Answer 4

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.