There are things that are discovered, and things that are invented. The boundary is put at different places by different people. I put myself on the list and I believe that my position is objectively justifiable, and others are not.
Definitely discovered: finite stuff
By probabilistic considerations, I am sure that nobody in the history of the Earth has ever done the following multiplication:
9306781264114085423 x 39204667242145673 = ?
Then if I compute it, am I inventing its value, or discovering the value? The meaning of the word "invent" and "discover" are a little unclear, but usually one says discover when there are certain properties: does the value have independent unique qualities that we know ahead of time (like being odd)? Is it possible to get two different answers and consider both correct? etc.
In this case, everyone would agree the value is discovered, since we actually can do the computation--- and not a single (sane) person thinks that the answer is made up nonsense, or that it wouldn't be the number of boxes in the rectangle with appropriate sides, etc.
There are many unsolved problems in this finite category, so it isn't trivial:
- Is chess won for white, won for black, or a draw, in perfect play?
- What are the longest possible Piraha sentences with no proper names?
- What is the length of the shortest proof in ZF of the Prime Number Theorem? Approximately?
- What is the list of 50 crossing knots?
You can go on forever, as most interesting mathematical problems are interesting in the finite domain too.
Discovered: asymptotic computation
Consider now an arbitrary computer program, and whether it halts or does not halt. This is the problem of what are called "Pi-0-1 arithmetic sentences" in first order logic, but I prefer the entirely equivalent formulation in terms of halting computer programs, as logic jargon is less accessible than programming jargon.
Given a definite computer program P written in C (or some other Turing complete language) suitably modified to allow arbitrarily large memory. Does this program return an answer in finite time, or run forever? This includes a hefty chunk of the most famous mathematical conjectures, I list a few:
- The Riemann hypothesis (in suitable formulation)
- The Goldbach conjecture.
- The Odd perfect number conjecture
- Diophantine equations (like Fermat's last theorem)
- consistency of ZF (or any other first order set of axioms)
- Kneser-Poulsen conjecture on sphere-rearrangement
You can believe one of the two
- "Does P halt" is absolutely meaningful, so that one can know that it is true or false without knowing which.
- "Does P halt" only becomes meaningful upon the halting of P, or a proof that it doesn't halt in a suitable formal system, so that it is useful to introduce a category of "unknown" for this question, and the "unknown" category might not eventually become empty, as it does in the finite problem case.
Here is where the intuitionists stop. The famous name here is
Intuitionistic logic is developed to deal with cases where there are questions whose answer is not determined as true or false, so that one cannot decide the law of excluded middle. This position leaves open the possibility that some computer programs that don't halt are just too hard to prove halt, and there is no mechanism for doing so.
While intuitionism is useful for situations of imperfect knowledge (like us, always), this is not the place where most mathematicians stop. There is a firm belief that the questions at this level are either true or false, we just don't know which. I agree with this position, but I don't think it is trivial to argue against the intuitionist perspective.
Most believe discovered: Arithmetic hierarchy
There are questions in mathematics which cannot be phrased as the non-halting of a computer program, at least not without modification of the concept of "program". These include
- The twin prime conjecture
- The transcendence of e+pi.
To check these questions, you need to run through cases, where at each point you have to check where a computer program halts. This means you need to know infinitely many programs halt. For example, to know there are infinitely many twin primes, you need to show that the program that looks for twin primes starting at each found pair will halt on the next found pair. For the transcendence question, you have to run through all polynomials, calculate the roots, and show that eventually they are different from e+pi.
These questions are at the next level of the arithmetic hierarchy. Their computational formulation is again more intuitive--- they correspond to the halting problem for a computer which has access to the solution of the ordinary halting problem.
You can go up the arithmetic hierarchy, and the sentences which express the conjectures on the arithmetic hierarchy at any finite level are those of Peano Arithmetic.
There are those who believe that Peano Arithmetic is the proper foundation, and these arithmetically minded people will stop at the end of the arithmetic hierarchy. I suppose one could place Kronecker here:
- Leopold Kronecker: "God created the natural numbers, all else is the work of man."
To assume that the sentences on the arithmetic hierarchy are absolute, but no others, is a possible position. If you include axioms of induction on these statements, you get the theory of Peano Arithmetic, which has an ordinal complexity which is completely understood since Gentzen, and it is described by the ordinal epsilon-naught. Epsilon-naught is very concrete, but I have seen recent arguments that it might not be well founded! This is completely ridiculous to anyone who knows epsilon-naught, and the idea might strike future generations as equally silly as the idea that the number of sand grains in a sphere the size of Earth's orbit is infinite--- an idea explicitly refuted in "The Sand Reckoner" by Archimedes.
Most believe discovered: Hyperarithmetic hierarchy
The hyperarithmetic hierarchy is often phrased in terms of second order arithmetic, but I prefer to state it computationally.
Suppose I give you all the solution to the halting problem at all levels of the arithmetic hierarchy, and you concatenate them into one infinite CD-ROM which contains the solution to all of these simultaneously. Then the halting problem with this CD-ROM (the complete arithmetic-hierarchy halting oracle) defines a new halting problem--- the omega-th jump of 0 in recursion theory jargon, or just the omega-oracle.
You can iterate the oracles up the ordinal list, and produce ever more complex halting problems. You might believe this is meaningful for any ordinals which produce a tape.
There are various stopping points along the hyperarithmetic hierarchy, which are usually labelled by their second-order arithmetic version (which I don't know how to translate). These positions are not natural stopping points for anybody.
Church Kleene ordinal
I am here. Everything less than this, I accept, everything beyond this, I consider objectively invented. The reason is that the Church-Kleene ordinal is the limit of all countable computable ordinals. This is the position of the computational foundations, and it was essentially the position of the Soviet school. People I would put here include
In the case of Paul Cohen, I am not sure. The ordinals below Church Kleene are all those that we can definitely represent on a computer, and work with, and any higher conception is suspect.
First uncountable ordinal
If you make an axiomatic set theory with power set, you can define the union of all countable ordinals, and this is the first uncountable ordinal. Some people stop here, rejecting uncountable sets, like the set of real numbers, as inventions.
This is a very similar position to mine, held by people at the turn of the 20th century, who accepted countable infinity, but not uncountable infinity. Those who were here include many famous mathematicians
Skolem's theorem was an attempt to convince mathematicians that mathematics was countable.
I should point out that the Church Kleene ordinal was not defined until the 1940s, so this was the closest position to the computational one available in the early half of the 20th century.
Continuum
Most practically minded mathematicians stop here. They become wary of constructions like the set of all functions on the real line, since these spaces are too large for intuition to comfortably handle. There is no formal foundation school that stops at the continuum, it is just a place where people stop being comfortable in the absoluteness of mathematical truth.
The continuum has questions which are known to be undecidable by methods which are persuasive that it is a vagueness in the set concept at this point, not in the axiom system.
First Inaccessible Cardinal
This place is where most Platonists stop. Everything below this is described by ZFC. I think the most famous person here is:
I assume this is his platonic universe, since he says so explicitly in an intro to one of his more famous early papers. He might have changed his mind since.
Infinitely many Woodin Cardinals
This is the place where people who like projective determinacy stop.
It is likely that determinacy advocates believe in the consistency of determinacy, and this gives them evidence for the consistency of Woodin Cardinals (although their argument is somewhat theological sounding without the proper computational justification in terms of an impossibly sophisticated countable computable ordinal which serves as the proof theory for this)
This includes
Possibly invented: Rank-into-Rank axioms
I copied this from the Wikipedia page, these are the largest large cardinals mathematicians have considered to date. This is probably where most logicians stop, but they are wary of possible contradiction.
These axioms are reflection axioms, they make the set-theoretic model self-similar in complicated ways at large places. The structure of the models is enormously rich, and I have no intuition at all, as I barely know the definition (I just read it on Wiki).
Invented: Reinhard Cardinal
This is the limit of nearly all practicing mathematicians, since these have been shown to be inconsistent, at least using the axiom of choice. Since most of the structure of set theory is made very elegant with choice, and the anti-choice arguments are not usually related to the Godel-style large-cardinal assumptions, people assume Reinhardt Cardinals are inconsistent.
I assume that nearly all working mathematicians consider Reinhardt Cardinals as imaginary entities, that they are inventions, and inconsistent at that.
Definitely invented: Set of all sets
This level is the highest of all, in the traditional ordering, and this is where people started at the end of the 19th century. The intuitive set
- The set of all sets
- The ordinal limit of all ordinals
These ideas were shown to be inconsistent by Cantor, using a simple argument (consider the ordinal limit plus one, or the power set of the set of all sets). The paradoxes were popularized and sharpened by Russell, then resolved by Whitehead and Russell, Hilbert, Godel, and Zermelo, using axiomatic approaches that denied this object.
Everyone agrees this stuff is invented.