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
    Your answer is correct. Now try to think how you can show it is so.2011-11-25
  • 0
    I have seen that post. The problem is maybe all mathematical truths may not be expressed by our current set of language and symbols. So, thats why my question. The set of theorems is not just a set of linguistic combinations, but a set of mathematical truths.2011-11-25
  • 0
    @RoupamGhosh : You need to separate the set of all mathematical truths from the set of all mathematical truths that can be stated. Of course there are many mathematical truths that can be stated only by infinite means.2011-11-25
  • 4
    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 :)2011-11-25
  • 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? ;)2011-11-25
  • 0
    @ShaiDeshe Yes, I have been thinking the same way. I was thinking of the set of theorems {$x$ is irrational}. But I wouldn't jump up to conclude that its "obviously" uncountable.2011-11-25
  • 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.2011-11-25
  • 0
    @ArthurFischer Yes, that is what is confusing me. I cannot think of a way to define theorems, let alone count them. Thats why I wrote the term mathematical truth. But there again I stepped on another trap. :) Thanks!2011-11-25
  • 0
    @RoupamGhosh. The set, as you described it, is uncountable, as there's a very obvious bijection between it and the irrationals...2011-11-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.2011-11-25
  • 0
    @r.e.s.: I agree, and I cast the final vote to close for this reason.2011-11-25
  • 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?)2011-11-25
  • 2
    In case the question is being reopened, can we at least __edit the title__ to something else? I feel the OP has changed the question from the cardinality to «something I don't quite understand». The present title is (a) too similar to the "original" question, and (b) not very appropriate.2011-11-25
  • 0
    Perhaps [tag:philosophy] tag would be suitable?2011-11-25
  • 2
    @Henning: I voted to close as "not constructive", which I view as the replacement for the old "subjective and argumentative" option. "Duplicate" was just the majority reason. I view the question as both subjective and off topic if it asks us to discuss how many mathematical truths there are.2011-11-26
  • 2
    @Carl: Sorry, the possibility that the close reason was not unanimous completely slipped my mind. Mea culpa.2011-11-26
  • 0
    @RoupamGhosh : Look up the book $\Omega$ by Chaitin , this is good starting point to limits of mathematical knowledge http://en.wikipedia.org/wiki/Chaitin's_constant2011-11-26
  • 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
    No: The subsets, even the singleton subsets, of your set are not theorems. Perhaps you mean logical conjunctions of the base theorems. But there are only countably many of those.2011-11-25
  • 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.2011-11-25
  • 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 space2011-11-25
  • 1
    Human abilities isnt relevant for mathematical truth.2011-11-25
  • 0
    @howdy. Ah yes, if only I had countably infinite many lives. (Actually I would settle just for a couple...). And if OP had meant truths that cannot possibly be expressed, why should he have bothered to mention the finiteness of symbols? By the way my example gives 0 theorems regardless, because 93 is not a prime... (this was not on purpose, but I can no longer edit the comment, so my foolishness will haunt me all my countably infinite many lives ;-).2011-11-25
  • 1
    @howdy +1 Wonderful! this gives me something to think about.2011-11-25
  • 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.2011-11-25
  • 1
    You cam make only one new theorem by stating "every subset of $\mathcal{T}$ is a theorem".2011-11-25
  • 0
    I agree that the word theorem in the first sentence is wrong, and truth is more fit. Still, the argument that we need infinite time and space to write one of them down is wrong, we could for instance write one symbol at time 1/2^t sec, and use 1/2^t cm per symbol, for integers t. Then we are done in 1 sec using 1 cm paper.2011-11-26
  • 0
    @howdy: Go ahead and try. Oh, and please don't forget to as well test a zero of the Riemann zeta function for every symbol you write down (not skipping any one of them), so that we can finally settle that matter as well.2011-11-26
  • 0
    @MarcvanLeeuwen That isnt possible Marc, because the time needed to check a zero does not scale like the time needed to write a character with smaller and smaller letters.2011-11-26
  • 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.

  • 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.2011-11-25
  • 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
    I don't get how to see $x < 4$ "more simply" than $c=c$...2011-12-01
  • 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.