9
$\begingroup$

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.

  • 0
    Just to point out why this question is off-topic: what is the definition of a *mathematical truth*? Surely that definition would be needed to determine whether the set of them is countable. If every sentence of the elementary diagram of the field $\mathbb{R}$ is a mathematical truth then the question is trivial (see http://en.wikipedia.org/wiki/Elementary_diagram ).2011-11-28

5 Answers 5

21

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".

9

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).

  • 0
    @howdy: Yes it does, just scale down you computer at each step, just like you scale down your pen. There is no physical size involved in the zeros of the zeta function.2011-11-26
1

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.

  • 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.2011-11-25
0

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.

  • 0
    @Srivatsan I agree. I just meant x<4 as more simple to see than (x+y)=z.2011-12-02
-1

The set of all theorems is countable. The set of all mathematical truths isn't. You even could see this like a very basic proof of Gödel incompleteness: It's impossible to prove all mathematical proofs since there are less theorems than truths (which are different things). You can find this question and more interesting stuff on this topic in Geoffrey Hunter's book: Metalogic: An Introduction to the Metatheory of Standard First Order Logic.