I assume that N here denotes the set of natural numbers: N = {0, 1, 2, 3, ...}. Yes, it is possible to prove this. And the axiom of choice isn't needed, so you can prove it in ZF. Here's one way to do it: Let E = {2, 4, 6, ...} and O = {1, 3, 5, ...}. Thus, E and O are the sets of even and odd positive integers. (Notice that I have left out 0). Now consider the collection of all sets of the form E U X, where X is a subset of O. Every set in this collection is infinite, since it includes all even integers. And every set is a proper subset of N, since it doesn't include 0. There is one such set for each subset X of O, so the cardinality of this collection of sets is the same as the cardinality of the set of all subsets of O (the power set of O). And since O can be put into one-to-one correspondence with N, the cardinality of the power set of O is the same as the cardinality of the power set of N, which, as Cantor showed, is strictly greater than |N|. Note: When I say that the cardinality of a...

Stephen Maitzen has given a syntactic response, showing how formal rules of logic can be used to derive any conclusion Q from a contradiction P & not-P. It might be worthwhile to point out that one can also give a semantic explanation of why Q follows from P & not-P--that is, an explanation based on the truth or falsity of the premise and conclusion, rather than on rules for manipulating logical symbols. The semantic definition of logical consequence is this: We say that a conclusion follows from a collection of premises if, in every situation in which the premises are all true, the conclusion is also true. To put it another way: the conclusion fails to follow from the premises if (and only if) there is some situation in which all the premises are true, but the conclusion is false. For example, the conclusion "It is snowing" does not follow from the premise "It is either raining or snowing," because there is a situation in which the premise is true but the conclusion is false-...

I find the original question a little unclear, because I'm not sure what a "recursive proof" is. Peter and Richard have interpreted the question as asking whether or not there is an algorithm to tell, in general, whether or not any given recursive sets of axioms T and T* have the same theorems. This is one possible interpretation, and Richard has given a very nice proof that the answer is no. But the original question does not seem to be asking about a general solution for all recursive sets of axioms T and T*. Rather, it seems to be asking whether there can be a single pair of recursive sets of axioms T and T* such that T and T* have the same theorems, but this fact is, in some sense, not provable. Let me give an example that might respond to this interpretation. For each natural number n, let P(n) be the statement "n is not the Godel number of a proof of a contradiction in Zermelo Frankel (ZF) set theory." This is expressible in the language of number theory. Let T be the set of Peano axioms...

Yes, I agree, under the alternative interpretation I proposed the word "recursive" in "recursive proof" is doing no work. So my interpretation is not entirely satisfactory either. I don't know which interpretation was meant, but both seem to be interesting questions. As for the generalization to any extension U of PA: Presumably we're talking about recursive extensions of PA. (Well, we do have that occurrence of the word "recursive" floating around that isn't doing any work; perhaps we can use it here.) But there's one other issue. In my argument, I made use of the fact that the consistency of PA is provable in ZF. But the consistency of PA is not provable in PA, so I don't think it's going to be true in general that you can prove in PA that PA and PA(U) have the same theorems iff U is consistent. But I think you can prove it in the theory PA + Con(PA) (that is, the theory PA with an additional axiom asserting that PA is consistent). So as long as U is strong enough to prove...

A few comments on the answers from Professors George and Pogge: 1. If two statements are logically equivalent, do we think of them as expressing the same proposition or two different propositions? If we think of logically equivalent statements as expressing the same proposition, and we use classical logic, in which "it is not the case that it is not the case that P" is logically equivalent to P (and if we ignore, for the moment, Prof. Pogge's worries about meaningless statements), then there's no problem with Prof. George's original pairing. In the example given by Prof. Pogge, "Bush is married" and "it is not the case that it is not the case that Bush is married" express the same proposition, and that proposition is paired with the proposition expressed by "it is not the case that Bush is married". 2. If we do not group together logically equivalent statements as suggested in 1 above, then as Prof. Pogge points out, Prof. George has paired each true statement with a false one, but some false...

Your sentence (1) is often given as an example of a paradoxical sentence. The paradox arises from interpreting the phrase "this sentence" as referring to sentence (1) itself. If the sentence is true, then what it says is incorrect, so it is false. But if it is false, then what it says is correct, so it is true. It is tempting to think that the problem is caused by the interpretation of the phrase "this sentence". I suspect that this is the motivation for your question. Can we avoid the problem by saying that the phrase "this sentence" can't be interpreted in this way? The answer is no: the paradox can be created without using this phrase. To see how to do it, first note that it is possible for a sentence to talk about a linguistic expression. The usual way to accomplish this is to use quotation marks. For example, here is a sentence that talks about sentence (1): (2) "This sentence is false" is a paradoxical sentence. Of course, there's nothing paradoxical about sentence (2). ...

One way of further spelling out Alex's standard for deductive inference ("if the reasons are true then the conclusion must be as well") is to use the idea of "possible worlds"--different ways that the world might be. To say that if the reasons are true then the conclusion must also be true means that in all possible worlds in which the reasons are true, the conclusion is true. The idea of possible worlds can be helpful in thinking about many kinds of reasoning. For example, consider the problem you presented about blood donors. One way to think about the problem is to consider different possible worlds. What would the world be like if blood donors were paid? What would the world be like if they weren't? Choice (c) says that in a world in which blood donors are paid there would be less of a shortage of blood donors than in a world in which they aren't, so it supports the conclusion. The other two choices don't give any sense in which a world in which blood donors are paid would be better than one...

Godel's Incompleteness Theorem is a theorem about formal axiomatic theories: theories in which there is a collection of axioms from which all of the theorems are deduced, and in which the theorems are deduced from these axioms by the application of rules of logic. It applies to a wide range of theories, but to start off it might be helpful to focus on one such theory, so let's consider Peano Arithmetic, often abbreviated PA. This is an axiomatic theory of the properties of addition and multiplication of the natural numbers 0, 1, 2, ... (Peano Arithmetic is named after Giuseppe Peano.) Godel's Incompleteness Theorem says that if PA is consistent--that is, if the axioms don't contradict each other--then there are statements about the arithmetic of the natural numbers that are neither provable nor disprovable from the PA axioms. Thus, the axioms are not powerful enough to settle every question of number theory. Now, you might think that all this shows is that Peano must have forgotten an axiom...

There are two aspects of your argument that worry me: 1. If I understand your argument correctly, you are saying that the liar sentence expresses two different propositions, namely: (a) This sentence is false. (b) "This sentence is false" is false. But don't (a) and (b) mean the same thing? Isn't that, in fact, what your argument shows? So is this really two different propositions? 2. You say that you think the liar sentence is false. But aren't you worried that that would make it true, since it asserts--correctly, in your view--that it is false? By the way, a common first reaction to the liar paradox is to think that the problem is caused by the phrase "this sentence". There is a wonderful example, due to Quine, of a sentence that achieves the same effect as the sentence "this sentence is false" without using the phrase "this sentence". (The example makes use of the same mechanism for achieving self-reference that Godel used in his proof of the Incompleteness Theorem.) ...

I'm not sure what you (or your book) are referring to when you say that modern logic "leaves 5 valid moods out". But modern logic is complete. To explain what this means, the following terminology is helpful: We say that a conclusion is a semantic consequence of a collection of premises if, in every situation in which the premises are true, the conclusion is also true. Then it is possible to prove the following statement: Whenever a conclusion is a semantic consequence of a collection of premises, it is possible to derive the conclusion from the premises using the rules of modern logic. To put it another way: If you cannot derive a conclusion from a collection of premises using the rules of modern logic, then there must be some possible situation in which all the premises would be true and the conclusion false. This is the completeness theorem of logic, proven by Godel in his doctoral dissertation in 1929.

I have a minor quibble with one of Richard's statements. He says that an intuitionist "can prove that not every number is either positive, negative, or equal to zero." I don't think an intuitionist would claim to be able to prove that. Rather, an intuitionist would say that he is unable to prove that every number is either positive, negative, or equal to zero. It's a small point, but there is a difference between being unable to prove that something is true and being able to prove that it is false. For more on this, see the entry in the Stanford Encyclopedia of Philosophy on Weak Counterexamples . Notice that conclusion 2 in that entry is "we cannot now assert that every real number is either positive, negative, or equal to zero," which is different from saying "we can now assert that not every real number is either positive, negative, or equal to zero."