Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I would like to preface by saying that I have no significant experience working with set theory, so I'm probably making an intuitive mistake. I have figured out where the mistake probably is, but I can't figure out why it IS a mistake. I figured that this was the best outlet to ask my question.

I was reading about the Continuum Hypothesis on Wikipedia recently, particularly about the fact that it's undecidable in ZFC -- which means that it is undecidable whether or not there is an infinite set whose size is strictly between that of the natural numbers and that of the real numbers. Now, intuitively, a proof that it cannot be disproved would immediately give way to the fact that no counterexample could be constructed (for such a counterexample would disprove it, which is impossible), and thus it must therefore be true. But that's not where I'm going with this.

Cantor proved that the rational numbers are countable -- that there exists a counting method such that, given any integer, you could determine the unique rational number which corresponds to it, and given any rational number, you could determine the unique integer which corresponds to it. The proof is fairly cool, but that's not where I'm going, either. Essentially, this demonstrated that $\aleph_0^2 = \aleph_0$. Then, he went on to prove that all algebraic numbers were countable, which proved the stronger statement that for any finite n, $\aleph_0^n = \aleph_0$. But yet, the cardinality of the real numbers is still strictly greater.

He explicitly determined the cardinality of the real numbers as $2^{\aleph_0}$, or, strictly speaking, for any $\alpha > 1, \mathfrak c = \alpha^{\aleph_0}$, because, no matter which base you're in, the number of real numbers doesn't change. This means that the cardinality of the real numbers is strictly exponential, whereas the cardinality of the countable numbers is strictly polynomial.

This is where my confusion arises. If I construct a set whose size after an infinite number of steps is bounded by any polynomial, it is countable, whereas a set whose size is greater than every polynomial would not be countable.

The Adleman–Pomerance–Rumely_primality_test has running time, for a given n, of $n^{O\log(\log(n))}$, which is of super-polynomial running time -- there exists no polynomial that is strictly greater than that function. However, it is also sub-exponential -- there exists no exponential function that is strictly less than it, either. Therefore, it exists between the polynomials and exponentials.

Using this, I can construct a set of numbers whose size after n steps is equal to $f(n) = n^{O\log(\log(n))}$ by appending approximately f'(n) unique values to the end of the set. I have now explicitly constructed an infinite set whose size is $\aleph_0^{\log(\log(\aleph_0))}$, have I not? And, as I said before, it is, eventually, larger than any set whose size grows polynomially. But it is also smaller than every set whose size grows exponentially.

Of course, it also turns out that this set is countable -- I can give you the numbers in the set, if you so wish. But that's only part of the problem.

Using the same method, I can also construct a set whose size grows exponentially, if I only change my function to $f(n) = 2^n$. I then append f'(n) unique values to the end of my set and, voila, as I take a countably infinite number of steps, namely $\aleph_0$, the size of my set becomes $2^{\aleph_0}$, the cardinality of the continuum -- but, as before, I can tell the nth item in my set, and if you give me any item in my set, I can tell you exactly where it lies.

Thus is my question: What did I do wrong? Either I have shown that $2^{\aleph_0} = \aleph_0$, which is exceedingly unlikely, or my assumption that my new set's size is equal to $2^{\aleph_0}$ is incorrect, and I cannot understand why.

Any help would be appreciated, thanks!

--Gabriel Benamy

share|improve this question
3  
Seems that you were led astray by notation. The exponential notation for cardinal numbers has nothing to do with asymptotics of the exponential function, or with exponentiation as a series of multiplications, or anything else in arithmetics. –  Sergei Ivanov Mar 29 '10 at 15:04

3 Answers 3

up vote 6 down vote accepted

The problem lies with your interpretation of the notation $2^{\aleph_0}$ and $\aleph_0^n.$ These do not mean that your set is constructed from finite sets with a specified rate of growth.

Let $A$ be the cardinality of a set. e.g. $A = 2$ or $A=\aleph_0.$

$A^n$ is the cardinality of the n-fold cartesian product of a set with cardinality $A.$

$2^{A}$ is the cardinality of the power set, i.e. the set of all subsets, of a set with cardinality $A.$

Your interpretation in terms of rates of growth does not work. The reason for this notation is that when $A$ is finite, the arithmetic interpretation works. That is, if $S$ is a set with $k$ elements, then $S^n$ has $k^n$ elements, and there are $2^k$ subsets of $S.$

share|improve this answer
1  
Thanks. So because of the countable nature of the way I constructed my set, it still has cardinality $\aleph_0$, right? –  Gabriel Benamy Mar 29 '10 at 15:15
3  
Your set is a countable union of finite sets, so your set is countable. Regardless of how fast the (finite) sizes of the sets grow. –  Gerald Edgar Mar 29 '10 at 15:29

As others have already noted, the notion of size these algorithms appeal to is not the cardinality of a set.

However, there is a useful sense in which your intuition can be formalized: via the ordinal numbers. These are the order types of well-ordered sets (ie, isomorphism classes of well-ordered sets). These give a finer notion of the size of set than set cardinality does, and in particular can give you a sense in which a function which takes $n^{(\log\log(n))}$ time to run is bigger than a polynomial-bounded function like $n^2$, yet smaller than an exponential $2^n$. Intuitively, what they do is answer the question, "What is the weakest induction principle which can prove a particular algorithm is total?"

(Be careful to note, however, that algorithms are specific definitions of functions, and not their graphs. E.g., merge sort is $O(n \log n)$, whereas a pessimal sort which generates all permutations and looks for the sorted one is $O(n!)$ -- even though they compute the same extension.)

share|improve this answer

If you're looking for mathematics rather than idle speculation then do not bother reading any further in this comment.

It is amusing to try to pursue your basic thought and see where it leads. I would interpret your thought as follows: we can think of polynomial and exponential functions set theoretically (the cardinality of $A\times A$ is $|A|^2$ and the cardinality of the set of functions from {0,1} to $A$ is $2^{|A|}$) and in that way transfer these operations from natural numbers to cardinals. So why not produce a counterexample to CH by interpreting some intermediate function set-theoretically?

What would the most natural intermediate function be? Well, we'd like a function that takes natural numbers to natural numbers. The set-theoretic operations we know that are likely to be useful are unions, Cartesian products and the set of functions from a fixed set to a given set. The third is too big, unless the "given set" is some quite small subset of the set you start with. On the other hand, Cartesian products are too small unless the number of sets you multiply together is unbounded. But we don't want to multiply n sets together, so whichever way we try to do it we seem to need a function of n that grows more slowly than n itself. But if we had such a function then the infinite analogue should surely be some set that is infinite in size but smaller than the set of natural numbers.

But unless you are going to work in some quite strange system, there are no such sets. However, the proof that the natural numbers embed into any infinite set does need the axiom of countable choice, so perhaps in a choice-free world one could do something. But to get an infinite set that is smaller than the natural numbers doesn't seem possible because if you inject it into the natural numbers then you can inductively turn that injection into a bijection. I'm not a set theorist, but I'm beginning to think that the natural numbers will be the smallest infinite set even if you choose very restrictive axioms.

So, not surprisingly, it doesn't seem to be possible to cook up a counterexample to CH in the way you want. That failure seems to be bound up with the fact that a "lower-level CH" (that there aren't any sets with cardinality intermediate between finite and countably infinite) is true.

share|improve this answer
    
Actually, there are combinatorially-defined sequences with growth intermediate between polynomial and exponential; I just can't remember what any of them are right now... –  Qiaochu Yuan Mar 29 '10 at 21:58
    
Without the axiom of choice you can have infinite sets that are "small" in the sense that they contain no countably infinite set. ("Dedekind finite" sets.) Among the models constructed by Cohen there is one with a Dedekind finite set of reals. –  John Stillwell Mar 29 '10 at 22:37
    
In bounded arithmetic, the hypothesis that $\Omega(n) = n^{|n|}$ ($|n| = \lceil\log_2(n+1)\rceil$) is total is strictly weaker than the totality of $2^n$. This fascinating fact has no extension into the infinite (that I know of). –  François G. Dorais Mar 29 '10 at 22:46
    
To get smaller sets, you need to tweak the logical rules -- induction and the logical rule of contraction conspire to allow fast-growing functions on the naturals. If you eliminate that rule (and take a host of knock-on effects into account), then you can get "light set theory", in which the provably total functions on the natural numbers are the polytime functions. I prefer to think of it as decomposing the naturals into subcomponents, rather than changing the function space, though. (See jstor.org/pss/20016605) –  Neel Krishnaswami Mar 29 '10 at 22:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.