Is it possible to prove within ZF(C) that the set of all proper infinite subsets of set N has cardinality that is strictly greater than |N|?

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

Is it true that anything can be concluded from a contradiction? Can you explain? It's seems like its a tautology if taken figuratively because we can indeed conclude anything if we suspend the rules of reasoning, but there is nothing especially interesting in that fact in my humble opinion.

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

Is it impossible that there be two recursive sets T and T* of axioms (in the same language) such that their closures under the same recursive set of recursive rules is identical and yet there is no recursive proof of this fact? It seems impossible but a simple proof of this fact would help elucidate matters!

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

Are there as many true propositions as false ones? More of one than the other?

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

Can sentences refer to themselves? Take the "Liar" paradox: (1) This sentence is false. Does "This" really refer to the sentence I've labeled as (1)? Can sentences predicate properties to themselves in this way?

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

In a critical thinking textbook I’m trying to study from, there is an exercise which gives groups of three different independent reasons from which I must select the one which supports a stated conclusion. For example: Conclusion: Blood donors should be paid for giving blood. (a) The blood donor service is expensive to administer. (b) People who give blood usually do so because they want to help others. (c) There is a shortage of blood donors, and payment would encourage more people to become donors. (Anne Thomson, Critical Reasoning - a practical introduction .) For each question I must pick the answer which could be a reason for a conclusion, say why it is the right answer, and why the other options are wrong. I’ve had absolutely no problems selecting the correct answer, but I can’t seem to say why. It would seem that I could easily say THAT a particular reason gives or doesn’t give support to a conclusion, but I can’t seem to put into words HOW or WHY. So my question is, why and how do...

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

Hello philosophers. I was just wondering about Gödel's Incompleteness Theorem. What exactly is it and does it limit what we are capable of knowing? I have no training in mathematics or formal logic so if you could reply in lay terms, I would appreciate that. Thanks, Tim.

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

Is the Liar paradox, stated as "this sentence is false" false? The Liar surely means, "The proposition expressed by this sentence is false", but this implies that there is one and only one proposition contained within the sentence. If this is not the case then the whole statement is false because "The proposition" must pick out exactly one object. The direct proposition expressed is "This sentence is false", yet surely since the predicate "is false" applies to the sentence in question, "This sentence is false" is false is a proposition that is also logically entwined with the sentence. Since the sentence expresses two propositions, and not one, there is no object which corresponds to "The proposition expressed" and so the whole sentence becomes false.

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 am reading a logic book which discussed the differences between Aristotelian Logic and Boole-Russell (modern) Logic. If the Boole-Russell logic leaves 5 valid moods out, which Aristotelian Logic covers, why do we continue to use Boole-Russell logic if it is "incomplete" per se?

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.

Are there logic systems that are internally consistent that have a different makeup to the logic system that we use?

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

Pages