Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is the set of all theorems countable or uncountable?

Maybe its a stupid question. I just wanted to know. I am led to think that since, we use a finite set of symbols and English letters, the set of theorems is countable.

EDIT: The set of theorems is not just a set of linguistic combinations, but a set of mathematical truths.

share|improve this question
3  
What about the set of theorems {$x$ is a limit of a sequence of rational numbers: $x\in \mathbb{R}$? It's obviously uncountable... However, most real numbers can't be named, as you can't name all elements in an uncountable set. From the other hand, you can make up a name on the fly for every conceivable number... My point is that vaguely stated questions usually have vague answers :) –  Shai Deshe Nov 25 '11 at 13:17
2  
@Arjang "Of course there are many mathematical truths that can be stated only by infinite means." Are you sure? Can you give an example? ;) –  Roupam Ghosh Nov 25 '11 at 13:21
4  
It seems to depend on what you think of a theorem as. Now, a theorem as "mathematical truth" will lead you quickly to there being proper-class-many theorems. (For any $x$ the statement "$x \in \{ x \}$ is clearly a mathematical truth -- though uninteresting -- and we can vary $x$ through the class of all sets.) Of course, we could not actually write down all of these mathematical truths. –  Arthur Fischer Nov 25 '11 at 13:25
4  
The OP's nonstandard usage of the term theorem has set the stage for needless argumentation. (In standard usage, a theorem is a syntactic expression, rather than a "truth" it expresses.) In my opinion, the question should be edited so as to not use the term "theorem" at all. –  r.e.s. Nov 25 '11 at 16:07
6  
Voting to reopen. The previous question asks for the cardinality of finite strings of symbols; but this question asks the question whether finite strings of symbols is the right thing to count in the first place. Those are different questions. (@Carl, if you agree with r.e.s. that this question is not - or should not be - about syntactic objects, why did you vote to close as a duplicate of a question that's explicitly about syntactic objects?) –  Henning Makholm Nov 25 '11 at 21:58

4 Answers 4

up vote 20 down vote accepted

A theorem is, by definition, a finite string of symbols that can be derived by some specified proof system. Because there are countably many finite strings of symbols, there are at most countably many theorems in any given theory.

Speaking of "a set of mathematical truths", where the elements of that set is supposed to be something different from symbolic representations, is not well defined. What kind of object is "a mathematical truth" to you such that you can put them into a set and count them? There is no definition of such a thing in general use, except for the formulas of symbolic logic.

In model theory one can speak of theories where the set of possible symbols are uncountable, such as a symbol for each real number. Such a theory, of course, has uncountably many theorems of the form $c=c$. However, these theories are generally considered artificial objects of study. Studying them can be useful as a stepping stone in proving things about ordinary countable theories, but their formulas are not considered to directly represent "mathematical truth".

share|improve this answer
    
I am accepting your answer for now as it is the best possible explanation. :) –  Roupam Ghosh Nov 29 '11 at 1:39

If you have countable many theorems $T_1,T_2,T_3...$, you can construct an uncountable set of new theorems by stating that every subset of {$T_1,T_2,T_3...$} is a theorem.

Additionally there are true finite statements which in a given formal system is only provable by a countable infinite number of theorems. (eg. Goodstein's theorem in PA).

share|improve this answer
1  
@howdy: the problem is "says". In order to say that, you need a finite description of the set in question, and for most subsets of an infinite set, this is not possible. One does not call "theorem" a hypothetical truth that cannot be expressed. For instance there is no theorem saying "the numbers 5,11,17,47,93,... are all prime", unless I can specify exactly how that sequence continues. And saying abstractly that it could continue in uncountably many ways does not make it uncountably many theorems. See Henning Makholms answer. –  Marc van Leeuwen Nov 25 '11 at 14:24
2  
@MarcvanLeeuwen He specifically said, "The set of theorems is not just a set of linguistic combinations, but a set of mathematical truths. " And you can specify how that sequence continues, you just need a countably infinite time and space –  user1708 Nov 25 '11 at 14:30
1  
Human abilities isnt relevant for mathematical truth. –  user1708 Nov 25 '11 at 14:37
1  
@howdy +1 Wonderful! this gives me something to think about. –  Roupam Ghosh Nov 25 '11 at 16:40
2  
That's incorrect according to standard usage of the term theorem. For almost every subset $S$ of a countably infinite collection of theorems, a finite string cannot specify $S$ and hence cannot specify the logical conjunction of just those theorems in $S$ — i.e., the "truth" of the logical conjunction is expressed by no theorem. –  r.e.s. Nov 25 '11 at 17:22

Do you think mathematic is finite? I think the number of mathematical theorem is infinite but countable. Did you mean that we count the number of letters in the theorems, we do not count the number of the theorems? For me, it does not make sense.

Ps. Somebody voted down for this answer, may be there is a misunderstanding here. I did not understand the question clearly, so I asked the author again for sure and I gave my thinking on it. Sorry for my poor English.

share|improve this answer
3  
Somebody flagged this as not an answer. I don't think it's a very good answer, but "I think the number of mathematical theorem is infinite but countable" certainly counts as an attempt to answer the question. –  Henning Makholm Nov 25 '11 at 14:56
1  
Thank Henning, in fact, I try to say that the number of theorems are countable, but may be my poor English led to misunderstanding. –  Knumber10 Nov 25 '11 at 18:06

If by "theorem" you just mean any mathematical truth, it doesn't seem too hard to figure out that the number of mathematical truths is uncountable. For the real numbers, in addition to c=c as Henning points out, you can consider (x+y)=z (or any other binary operation on the reals). There exist uncountably many triples (x, y, z) for which "(x+y)=z" is true, where x, y, and z all belong to the set of all real numbers. Perhaps more simply, consider x<4. There exist uncountably many real numbers we can put in for "x" which makes x<4 into a true statement, so there exist uncountably many mathematical truths of the form x<4. This all takes for granted that say 2.9<4 qualifies as a mathematical truth, which at the very least I would believe it hard for anyone to seriously deny as a mathematical truth, no matter what you mean by that term exactly.

share|improve this answer
    
I don't get how to see $x < 4$ "more simply" than $c=c$... –  Srivatsan Dec 1 '11 at 3:41
    
@Srivatsan I agree. I just meant x<4 as more simple to see than (x+y)=z. –  Doug Spoonwood Dec 2 '11 at 2:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.