Explicitly constructing an infinite set with particular size - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:44:38Z http://mathoverflow.net/feeds/question/19729 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19729/explicitly-constructing-an-infinite-set-with-particular-size Explicitly constructing an infinite set with particular size Gabriel Benamy 2010-03-29T14:53:43Z 2010-03-29T22:36:28Z <p>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.</p> <p>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.<p></p> <p>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 <em>algebraic</em> numbers were countable, which proved the stronger statement that for any finite <em>n</em>, $\aleph_0^n = \aleph_0$. But yet, the cardinality of the real numbers is still strictly greater.<p></p> <p>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 <em>exponential</em>, whereas the cardinality of the countable numbers is strictly <em>polynomial</em>.<p></p> <p>This is where my confusion arises. If I construct a set whose size after an infinite number of steps is bounded by <em>any</em> polynomial, it is countable, whereas a set whose size is greater than <em>every</em> polynomial would <em>not</em> be countable.<p></p> <p>The <a href="http://en.wikipedia.org/wiki/Adleman%25E2%2580%2593Pomerance%25E2%2580%2593Rumely_primality_test" rel="nofollow">Adleman–Pomerance–Rumely_primality_test</a> has running time, for a given <em>n</em>, 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 <em>less</em> than it, either. Therefore, it exists between the polynomials and exponentials.<p></p> <p>Using this, I can construct a set of numbers whose size after <em>n</em> 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.<p></p> <p>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.<p></p> <p>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 <em>n</em><sup>th</sup> item in my set, and if you give me any item in my set, I can tell you exactly where it lies.<p></p> <p><b>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.</b><p></p> <p>Any help would be appreciated, thanks!</p> <p>--Gabriel Benamy</p> http://mathoverflow.net/questions/19729/explicitly-constructing-an-infinite-set-with-particular-size/19731#19731 Answer by Jamie Weigandt for Explicitly constructing an infinite set with particular size Jamie Weigandt 2010-03-29T15:07:17Z 2010-03-29T15:07:17Z <p>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.</p> <p>Let $A$ be the cardinality of a set. e.g. $A = 2$ or $A=\aleph_0.$</p> <p>$A^n$ is the cardinality of the n-fold cartesian product of a set with cardinality $A.$</p> <p>$2^{A}$ is the cardinality of the power set, i.e. the set of all subsets, of a set with cardinality $A.$</p> <p>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.$</p> http://mathoverflow.net/questions/19729/explicitly-constructing-an-infinite-set-with-particular-size/19738#19738 Answer by Neel Krishnaswami for Explicitly constructing an infinite set with particular size Neel Krishnaswami 2010-03-29T16:10:38Z 2010-03-29T16:10:38Z <p>As others have already noted, the notion of size these algorithms appeal to is not the cardinality of a set. </p> <p>However, there is a useful sense in which your intuition can be formalized: via the <a href="http://en.wikipedia.org/wiki/Ordinal_number" rel="nofollow">ordinal numbers</a>. 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?" </p> <p>(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.) </p> http://mathoverflow.net/questions/19729/explicitly-constructing-an-infinite-set-with-particular-size/19778#19778 Answer by gowers for Explicitly constructing an infinite set with particular size gowers 2010-03-29T21:53:12Z 2010-03-29T21:53:12Z <p>If you're looking for mathematics rather than idle speculation then do not bother reading any further in this comment.</p> <p>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?</p> <p>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. </p> <p>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 <em>smaller</em> 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.</p> <p>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.</p>