## How many theorems are there?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Robert'); DROP TABLE *;
Posts: 730
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

### How many theorems are there?

I know that there are an uncountably infinite amount of irrational numbers, and so an uncountably infinite number of theorems along the lines of proving every irrational number to be irrational. However, there are only a countably infinite number of strings of potentially infinite length. Are there some theorems that cannot be written down, or have I missed something?
...And that is how we know the Earth to be banana-shaped.

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

### Re: How many theorems are there?

Robert'); DROP TABLE *; wrote:Are there some theorems that cannot be written down

Yes. Or possibly no, depending on what you mean by theorem.

If a theorem is a true fact about mathematics that can be written in a formal language, then no, clearly there aren't theorems that can't be written down (tautologically) and the number of theorems is at countable (since there are only countably many things we can write down total).

If a theorem is just a true fact about mathematics, then there are definitely theorems that you cannot write down. For instance, there are uncountably many theorems of the form 'x is an irrational number'. However, almost all irrational numbers are undefinable (in the sense that there is no way to write down even an algorithm for generating them), so we can't write down theorems that 'specifically mention' (whatever the hell that means) those numbers.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: How many theorems are there?

It depends on whether or not you permit infinite length mathematical statements.

Obviously, for any list of statements of any length, we can diagonalize across that list and create a new statement not in that list, so no list is ever truly complete.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: How many theorems are there?

Robert'); DROP TABLE *; wrote:I know that there are an uncountably infinite amount of irrational numbers, and so an uncountably infinite number of theorems along the lines of proving every irrational number to be irrational. However, there are only a countably infinite number of strings of potentially infinite length. Are there some theorems that cannot be written down, or have I missed something?

I've always had a trouble with statements like "there are numbers that can't be written down". As far as I'm concerned, if I were going to work with such things, I would say something like:

"Suppose the set T of number which cannot be written down is nonempty. Choose some t in T. As t is a written form an element of T, it has been written down, and so cannot be in T. Contradiction."

I would, however, agree with the statement "There are numbers whose binary expansion's digits cannot be written down." because I can't even write down all of the binary digits of 1/3, and those are all the same. I guess I've just always seen such questions as a bit silly, given nobody I know thinks twice about a nonconstructive proof if it gets the job done. Of course, constructive ones are preferable since they can often tell you more, but...
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: How many theorems are there?

There are countably many statements in a countable language, and hence countably many theorems in any theory in a countable language. Logicians are quite happy to talk about uncountable languages; for instance, you might have a constant symbol for each real number. In a theory in such a language, there could well be uncountably many theorems. However, mathematicians only ever work in countable languages in practice, so there are only countably many theorems that mathematicians will ever be able to prove (and of course, only finitely many that we ever will prove). For instance, there are countably many theorems of ZFC.

z4lis, you can make the statement "there are numbers that can't be written down" rigorous by making rigorous what we mean by "written down". If the sentence you just wrote down allegedly naming some number doesn't actually count as a name, then there is no contradiction. For instance, you might require that the sentence you write down picks out a single number, in that it holds of that number but no other number. If this definition is adopted, there are certainly real numbers which can't be named.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

gmalivuk
GNU Terry Pratchett
Posts: 26132
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: How many theorems are there?

And then there are the ones you can name, but that you shouldn't because it gets the Death Eaters on your case.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: How many theorems are there?

"Suppose the set T of number which cannot be written down is nonempty. Choose some t in T. As t is a written form an element of T, it has been written down, and so cannot be in T. Contradiction."
In math, you have to specify how you are writing things down - what language. If the language you are using is consistent, then there are, by necessity, true things which cannot be written in that language. For every two consistent languages, there is another language that can say by itself everything that either of the two says on their own. No matter how sophisticated you make your system, there will always be things you cannot say, or else you will be struck by inconsistencies.

Whether an inconsistent language like English can say anything that can be said (admitting ridiculous things like infinite length descriptions) or not, I have no idea.

If we allow infinite length statements, then for every true thing, there is a language of some sort which can note it - simply construct a language with the truth of the thing as one of its axioms. Then it can most certainly state it. In this sense, there is no set of true things (such as the existence of a number satisfying a property) that cannot be said by any possible language.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Yakk
Poster with most posts but no title.
Posts: 11077
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: How many theorems are there?

Multiple choice:
1) There are only a countable number of numbers that can be picked out and distinguished from other numbers.

2) There are only a countable number of numbers that can be distinctly described.

3) Not all sets you can describe in English exist.

4) The Axiom of Choice is not true.

5) Zorn's Lemma is true.

6) S(5)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: How many theorems are there?

Yakk wrote:Multiple choice quote goes here!

Obviously, 4 and 5 are both the correct answer.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: How many theorems are there?

Yakk wrote:Multiple choice:
1) There are only a countable number of numbers that can be picked out and distinguished from other numbers.

2) There are only a countable number of numbers that can be distinctly described.

3) Not all sets you can describe in English exist.

4) The Axiom of Choice is not true.

5) Zorn's Lemma is true.

6) S(5)

What on earth are you talking about? From my perspective, 3 depends on what you mean by "exist", and whether you are a Platonist, formalist, or ascribe to some other school of philosophy of mathematics. I don't even know what 6 means. For the others, 1 and 2 are obviously true (and synonymous), 4 is obviously false, and who can say about Zorn's lemma?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Yakk
Poster with most posts but no title.
Posts: 11077
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: How many theorems are there?

Sorry. S is the successor function.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: How many theorems are there?

I think 3 is necessarily true, so the rest of them must obviously be false.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.