How many theorems are there?

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

How many theorems are there?

Postby Robert'); DROP TABLE *; » Thu Feb 03, 2011 10:19 pm UTC

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.
User avatar
Robert'); DROP TABLE *;
 
Posts: 672
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: How many theorems are there?

Postby letterX » Thu Feb 03, 2011 10:37 pm UTC

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.
letterX
 
Posts: 526
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: How many theorems are there?

Postby WarDaft » Thu Feb 03, 2011 11:40 pm UTC

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.
User avatar
WarDaft
 
Posts: 1561
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: How many theorems are there?

Postby z4lis » Fri Feb 04, 2011 3:12 am UTC

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.
User avatar
z4lis
 
Posts: 732
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: How many theorems are there?

Postby skeptical scientist » Fri Feb 04, 2011 3:20 am UTC

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
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6148
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: How many theorems are there?

Postby gmalivuk » Fri Feb 04, 2011 3:50 am UTC

And then there are the ones you can name, but that you shouldn't because it gets the Death Eaters on your case.
Treatid basically wrote:widdout elephants deh be no starting points. deh be no ZFC.


(If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome)
User avatar
gmalivuk
A debonaire peeing style
 
Posts: 21971
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

Re: How many theorems are there?

Postby WarDaft » Fri Feb 04, 2011 5:45 am UTC

"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.
User avatar
WarDaft
 
Posts: 1561
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: How many theorems are there?

Postby Yakk » Fri Feb 04, 2011 3:31 pm UTC

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.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10369
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: How many theorems are there?

Postby z4lis » Fri Feb 04, 2011 3:41 pm UTC

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.
User avatar
z4lis
 
Posts: 732
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: How many theorems are there?

Postby skeptical scientist » Fri Feb 04, 2011 7:53 pm UTC

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
User avatar
skeptical scientist
closed-minded spiritualist
 
Posts: 6148
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: How many theorems are there?

Postby Yakk » Fri Feb 04, 2011 8:29 pm UTC

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.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10369
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: How many theorems are there?

Postby WarDaft » Fri Feb 04, 2011 10:30 pm UTC

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.
User avatar
WarDaft
 
Posts: 1561
Joined: Thu Jul 30, 2009 3:16 pm UTC


Return to Mathematics

Who is online

Users browsing this forum: Derek and 7 guests