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

There are two questions here that need to be distinguished: (1) Does the decimal expansion of pi contain a large but finite string of consecutive 7's--say, 1000 consecutive 7's? (2) Does it contain an infinite string of consecutive 7's? The second question is the easier one. The only way that pi could contain a string of infinitely many consecutive 7's is if all the digits are 7's from some point on. And, as William has pointed out, that can't happen because pi is irrational. But the first question is harder. The digits of pi "look random." Imagine a number whose digits are generated by some random process--for example, we might roll a 10-sided die repeatedly to generate the digits. One could compute the probability that a string of 1000 consecutive 7's appears in the first n digits of this number. For n =1000, this number would be extremely small--you'd have to roll 1000 consecutive 7's on your first 1000 rolls, and that's very unlikely. But as n increases, the probability increases, and...

To answer this question, it may be helpful to say something about the mathematical formalism usually used in probability theory. The first step in applying probability theory to study some random process is to identify the set of all possible outcomes of the process, which is called the sample space . For example, in the case of an infinite sequence of coin flips, the sample space is the set of all infinite sequences of H's and T's (representing heads and tails). Probabilities are assigned to events , which are represented by subsets of the sample space. For example, in the case of an infinite sequence of coin flips, the set of all HT-sequences that start with H represents the event that the first coin flip was a heads, and (assuming the coin is fair) this event would have probability 1/2. The set of sequences that start with HT is a subset of the first one, and it represents the event that the first flip was heads and the second tails; it has probability 1/4. Now, consider some infinite HT...

I'd like to add a little bit to what Thomas has said. Probability problems can be tricky because the answers sometimes depend on small details about exactly what procedure was followed. For example, the problem says that "you are given one envelope." Who gave you the envelope? Did the person who gave you the envelope know which envelope was which? Was he a very stingy person, who might have been more likely to give you the envelope with the smaller amount of money? If so, then the probability that you have the smaller amount might not be 1/2. But that is clearly not the intent of the problem, so let us assume that the person who gave you the envelope flipped a coin to decide which envelope to give you. Then, as Thomas says, the probability is 1/2 that you have the small amount and 1/2 that you have the large amount. Suppose that you open your envelope and find $100 in it. You now know that the other envelope contains either $50 or $200. Do these two outcomes still have probability 1/2 each? ...

You are right that the first thing you do when you make a model for set theory is to specify a domain. You also have to specify an interpretation for the "is an element of" symbol. For example, you might specify that the domain is to be the set of natural numbers, and the symbol for "is an element of" is to be interpreted to mean "is less than". Of course, under this interpretation most of the axioms of set theory would come out false, so although this is a possible interpretation for the language of set theory, it is not a model of ZFC. But if ZFC is consistent, then it has a model whose domain is the set of natural numbers. In this model, the "is an element of" symbol would be interpreted as some relation on the natural numbers. (The existence of such a model follows from the Lowenheim-Skolem theorem, which says that if ZFC is consistent, then it has a countable model.) Now, you might object that this model is not the intended model, because our intention is that the variables...

Philosophers of mathematics don't have to be mathematicians, but it would be helpful to know a fair amount of math. Here are some more specific suggestions: 1. You need to study enough math to appreciate the role of proofs in mathematics. Usually students don't see this until they get beyond calculus. Courses on analysis and abstract algebra would show you this side of mathematics. (Abstract algebra would also allow you to see the role of abstraction in math.) 2. There are ideas from logic, such as Godel's incompleteness theorems, that are important in philosophy of math, so you should study logic. 3. You should know about how some of the fundamental objects studied in mathematics are defined. For example, how are the real numbers defined? Usually mathematicians trace the ideas behind the definitions of these fundamental mathematical objects back to set theory, so it would be good to learn some set theory.

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