First, what is the cardinality of the set of all syntactically valid sentences in, say, the first-order predicate calculus? (Is this something anyone has bothered thinking about?) My guess is that, if you can use it to formalize the reals, it must have the same cardinality as the reals, because you have to be able to use it to do things like prove a certain number is irrational, which requires you to specify that number in a sentence, and there you go.
Second, what set has the same cardinality as the power set of the reals? Again, my sleep-deprived mind guesses the set of all functions on the reals: A function is a map, or a set of ordered pairs (domain value, codomain value), so you can create a set of all such maps, try to index them with your own ordered pairs (set of all ordered pairs of reals has the same cardinality as the reals, of course: They’re just the complex numbers!), and then apply Cantor’s theorem (greedy/non-greedy) to the result. (No total ordering on the complex numbers. Never understood why. Does this bother us?)
(Also, I imagine Kurt Gödel as Eraserhead. In Cantor’s heaven, everything is fine…)
You gues correctly the set of all functions from R->R is called R[sup]R[/sup] and |R[sup]R[/sup]| = |P(R)|.
The set R[sup]R[/sup] under the normal rules for addition of real functions and multiplication of a real function by a real number also is a simple example of an unocuntably infinite dimensional vector space.
The reason that the complex numbers aren’t ordered is that the real numbers is ‘the (Cauchy) complete ordered field’, there is no other Cauchy complete complete ordered field. If you desire the Cauchy completeness and the additional algebraic closure of the complex numbers in your fields, then the only thing that can give is the ordered part.
It’s a set of finite strings, so can be Gödel-numbered, i.e. brought into one-to-one correspondence with the natural numbers – hence, aleph-nought, like the naturals.
By “syntactically valid” do you mean the same as a well-formed formula?
If so, the cardinality is the same as the integers. Each possible symbol can be assigned a number, then a unique number computed from each possible string by assigning each symbol in the string a number equal to two raised to the power assigned to that symbol previously, then adding up the resulting powers of two for the entire string. Since each string can be assigned a unique number, and since the well-formed strings are a subset of all strings, the cardinality of well-formed strings is less than or equal to that of the integers. I take it that it’s obvious that it’s not less than. So it’s equal. (ETA: Basically what HMHW said.)
As for your question about formalizing the reals, I’m not sure what to say about that. As far as I can remember, first order logic can’t formalize the reals, but I may be remembering wrong. (Wikipedia also says this, though.)
There are two problems with this claim. First the “real” reason the complex numbers cannot be ordered is that in any ordered field -1 < 0 (for if -1 > 0, then 1 = (-1)(-1) is also > 0 and then so is 1 + (-1).
Now there are plenty of other complete ordered fields. The correct statement is that the reals is the unique Archimedean ordered field. An ordered field is Archimedean if for all x > 0, there is an (ordinary) positive integer n with nx > 1. Here is an example. Form the ring of rational functions p(t)/q(t) where p and q are polynomials with real coefficients and q not the 0 polynomial. You add, subtract, multiply and divide in the usual way with rational functions. Order it by saying that x > 0 but x < r for any real number r. This leads to a consistent order and now complete this by adding a limit for every Cauchy sequence. The resultant field can be described as the field of all formal Laurent series \sum_{i=n}^\infty a_i t^i, where n can be positive, negative or 0. The crucial point is that every such sum, unless 0, has an inverse of the same form. If the degree (the index of the first non-zero coefficient) is n, the degree of the inverse is -n. This gives a complete ordered field that is non-Archimedean.
Even had the theorem been quoted correctly, it would still by shooting peas with an AK-47 to invoke to prove that the complex numbers cannot be a complete ordered field. And not really relevant to the question.
As to the question, a finite vocabulary permits at most countably many first or statements, in fact at most countably many strings of letters from the vocabulary. What about the fact that there are uncountably many reals? Well, only countably many of them have any description in first order logic. You could think of decimals with recursively generated strings of digits. Only countably many of them.
If calculus sentences include numbers, then wouldn’t it have the same cardinality of those numbers? If your sentences contain real numbers, then there necessarily can’t be less of them then the number of reals.
I’m not sure if I’m making myself clear. Take, for example, the statement “This object and that object are ___ inches apart.” I can replace ___ with any of the positive reals (or 0). So that necessarily means there are the same number of variations of that sentence as their are positive reals.
Also, I don’t believe there is a finite number of constructed sentences, as there is no upper limit for the number of words in a sentence.
Almost all of these sentences would not be expressible with a finite number of symbols, as all well-formed formulas of predicate logic must be, though. (Most real numbers are of infinite length, so to speak.)
However, if you’re generally admitting symbol strings of infinite length, you’d indeed get a set of the cardinality of the reals.
In fact, what I said earlier was incomplete. Let me start over. If -1 > 0, then so is (-1)(-1) = 1 and then so is 0 = 1 + (-1). (The definition of ordered field explicitly says that the sum and product of positive things is positive). Now suppose that x < 0. Then adding -x to both sides of that inequality, we see that x + (-x) < -x, which means that -x > 0. Then since x^2 = (-x)^2 is the product of two positive things, this shows that all squares are positive. But i^2 = -1 so this is impossible.
The proof that I’ve seen of this starts with three axioms for P, the set of positive numbers:
[ol]
[li]For every a [/li]eq 0, either a \in P or -a \in P.
[li]a, b \in P implies that a + b \in P.[/li][li]a, b \in P implies ab \in P.[/li][/ol]
By axiom 1, either i or -i is positive, and two applications of axiom 3 will get you a contradiction.
You could put a total ordering on the complex numbers*. You can put random orderings on lots of things. But what nice properties would you want that ordering to have? It’s hard to put an ordering on the complex numbers that is useful or even nice, for reasons such as those pointed out by Hari Seldon and ultrafilter. But if you had a convoluted enough account of what a “nice ordering” was, you could conceivably devise one.
[*: For example, you might say A > B if A - B either is a positive real or has a positive imaginary component. That gives you a fairly simple total ordering, playing nicely with the additive, but not the multiplicative, structure of the complex numbers. When would this be useful? Er… I don’t know. That’s the catch.]
Hari Seldon, ultrafilter: Oh, yes, all that seems perfectly obvious now.
Indistinguishable: OK, I can see that. Mentally, I can also see that partitioning the plane so such an ordering makes sense visually doesn’t seem very reasonable; I just came up with two schemes based on comparing them in polar form and neither made any sense.