
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
November 19th, 2017, 09:29 PM  #1 
Senior Member Joined: Jun 2014 From: USA Posts: 617 Thanks: 50  Well Ordering of an Uncountable Set Question
Let $I = \{ x : x \text{ is an infinite binary string} \}$. Let $F = \{ x : x \text{ is a finite binary string} \}$. For each $a \in I$, $a = a_{1}a_{2}a_{3}\dots$ where each $a_i$ equals $0$ or $1$. For each $a \in I$, let $f(a) = \{ a_{1}, a_{1}a_{2}, a_{1}a_{2}a_{3}, \dots \}$. Let $\prec$ be a well ordering of $I$ (assumes the axiom of choice): $a^1, a^2, a^3, \dots$. Is there a least ordinal number $\alpha$ such that: $$\bigcup_{n = 1}^{\alpha} f( \,a^n) \, = F$$ If there is no least ordinal number $\alpha$ with the above property, but we nevertheless assert that the union of all $f(a)$ such that $a \in I$ is equal to $F$, then wouldn't $I$ be countable (not possible due Cantor's Theorem, so I know this assertion is wrong, just having trouble seeing why)? At the same time, if there is a least ordinal number $\alpha$ with the above property, then proceeding to union $f( \,a^{\alpha + 1}) \,$ could not add anything (ie, $F \cup f( \,a^{\alpha + 1}) \, = F$), so wouldn't there have to be an $a^{i}$ such that $i$ is the least $i \leq \alpha$ where: $$f( \,a^{\alpha + 1}) \, \subset \bigcup_{n = 1}^{i} f( \,a^n) \,$$ Just trying to understand where my logic is going off here... Maybe we cannot have an uncountable union in this fashion, maybe there is no $a^{\alpha}$ but this doesn't imply $I$ is countable (well, ok, obviously not, but that's how I interpret it with the well order), or maybe I'm just misunderstanding something about ordinals (they're murky...)? 
November 19th, 2017, 11:39 PM  #2  
Senior Member Joined: Aug 2012 Posts: 2,409 Thanks: 753 
It's late and I only read the first few lines. Just some quick comments before I take a look at the rest of this tomorrow. Quote:
Let's take a moment to reflect on $I$. A binary sequence or bitstring is a function $b : \mathbb N \to 2$, where $2$ is the symbol that stands for the set $\{0, 1\}$. The set of all such functions is called $2^\mathbb N$ and it has cardinality $2^{\aleph_0}$. We usually notate the sequence $b_1, b_2, b_3, \dots$ as $b_1 b_2 b_3 \dots$. We can map bitstrings $b$ to the real interval $[0, 1)$ via the formula $b = \sum \frac{b_i}{10^i}$ and when we do that we notate $b$ by putting a decimal point in front of the string. The map is bijective if we wave our hands at the pesky trailing $9$'s, of which there are only countably many. We can always patch this up. Likewise I'd just say, "Let $F$ be the set of finite bitstrings." We know that this is a countable set, since there are finitely many strings of length 1, finitely many of length 2, dot dot dot, and a countable union of finite sets is countable. Quote:
Quote:
Quote:
Aha. No. No. Not so simple. Well orders can be very wild. Consider a few well orders on the naturals: * 2, 3, 4, 5, ..., 1 That has a first and last element. * 2, 4, 6, ..., 1, 3, 5, ... Odds before evens. That's $\omega + \omega = \omega \cdot 2$. Note that this is not the same as $2 \cdot \omega$, which is $\omega$ copies of a 2element set, an entirely different order type. Ordinals are very weird. * $2 \omega, 3 \omega, \dots, \omega \omega = \omega^2$. * $\omega, \omega^2, \omega^3, \dots, \omega^\omega$. * $\omega, \omega^\omega, \omega^{\omega^\omega}, \dots$. The ordinal number at the end of this process, a countably infinite exponential tower of $\omega$'s, is a magic ordinal named $\epsilon_0$. https://en.wikipedia.org/wiki/Epsilo...s_(mathematics) * After that the $\epsilon$ numbers keep going. I'm only mentioning all this to show you how absolutely wild the ordinals are. And every ordinal I mentioned so far is a countable ordinal. They're all just different ways of rearranging the natural numbers. Now imagine how incomprehensible must be a wellorder of an uncountable set! So no, you may not assume that it is a list, which is defined as the particular countable wellorder that we call the "usual order on the naturals," namely 1, 2, 3, 4, ... That's only one particular wellorder of a countable set, and it's the simplest one. There are many others and they are one of the most mindboggling objects in mathematics that I know. The contemplation of the countable ordinals makes me dizzy. And now you are attempting to contemplate an uncountable ordinal. I'm not saying we can't do that. It will be fun to work with this. But let's be aware of the pitfalls and complications. The first uncountable ordinal is $\aleph_1$. In ordinal notation it's $\omega_1$, and $\aleph_1$ refers to the same number as a cardinal. The best (probably the only) way to visualize $\omega_1$ is that it's the set of countable ordinals. In other words say you continue developing the countable ordinals as I did earlier, and you consider every possible way that you could wellorder the naturals. Any set of ordinals is well ordered, in fact every ordinal is an initial segment of all the ones above it. So one, the set of all countable ordinals is in fact a set [needs proof]; and two, it's an ordinal [ditto]. It can't be a countable ordinal, because a set can't be a member of itself. So the set of all countable ordinals must be the first uncountable ordinal. I've just sketched a proof of the existence of an uncountable ordinal that did not depend on the axiom of choice. In fact the existence of $\omega_1$ is a theorem of ZF. Isn't that interesting? We need Choice to wellorder an arbitrary set. But we do not need Choice to show that there is some uncountable wellordered set. But now here is a problem you might have. We just described the uncountable ordinal $\omega_1$. But when you well order $2^{\aleph_0}$, you have no conceivable idea what that ordinal looks like. As wild as the countable ordinals are, how wild must the uncountable ordinals be? And what if the Continuum hypothesis is false and the $2^{\aleph_0} = \aleph_{47}$ or worse. How wild might your wellorder of $I$ be? I will end for tonight and take up the rest of this tomorrow. I hope this review of ordinals has been helpful. When you write $a^n$ are you thinking of wild uncountable ordinals but just writing them like the usual order on the naturals? Or are you intuitively thinking of the usual order and possibly confusing yourself? I couldn't tell from your exposition but I didn't read it closely yet. ps  When you ask if there's a least ordinal such that such and so, the answer is always yes. That's the thing about ordinals. If there's ANY ordinal such that X, there's a least one such that X, where X is any property. Last edited by Maschke; November 20th, 2017 at 12:19 AM.  
November 20th, 2017, 11:25 AM  #3 
Senior Member Joined: Aug 2012 Posts: 2,409 Thanks: 753 
Been thinking about your question. Here is what I think you are asking, in a different format. For each real number $x$, let $q(x) = \{q \in \mathbb Q : q < x\}$. In other words we associate with each real the countable set of rationals smaller than it. Now we wellorder the reals, and we ask if there is some particular real such that the union of the $q$sets of all reals less than it in the wellorder is all of the rationals. This is a pretty good puzzler because intuitively the answer must be yes, because there are only countably many rationals so at some uncountable point in the wellorder you must have gotten all of them. But on the other hand, for any given real, its $q$set excludes all of the rationals greater than or equal to that real (in the usual order). So no union of $q$sets that isn't all of the $q$sets can cover all the rationals. Good question. Let me percolate for a while. Not sure what the answer is. Have I understood your question? Last edited by Maschke; November 20th, 2017 at 11:38 AM. 
November 20th, 2017, 02:05 PM  #4 
Senior Member Joined: Aug 2012 Posts: 2,409 Thanks: 753 
I have another little visualization that might be helpful. Consider the infinite binary tree. If you fill out this picture, there are countably infinite many nodes. Each node represents one of the possible finite bitstrings. The set of paths through the nodes is uncountable, representing the set of all infinite bitstrings. Now I think this is a visualization that will be helpful for your problem. It is clear that if you take any proper subset of the set of all paths, the union of all those paths might be missing some finite sequences. Specifically, for any path not included in the subset, all its initial segments (that is, all its nodes) are possibly missing from the union of the given subset. I say possibly because for all we know, those nodes are already present in one of the paths that are in the subset. It seems that it's likely that for some subsets of the paths we've already got all the finite paths, and for others we don't. Or maybe it has to go one way or the other. I think this is close to what your question is about. It's not so much about how we wellorder the paths; rather the question is, what subsets of the paths "cover" all of the finite paths. ps  I have a proof that if you omit even one path, you'll necessarily miss some finite string. If not, call the missing path $P = (b_i)_{i \in \mathbb N}$. If any finite substring $P_n = (b_i)_{i = 1, 2, 3, \dots, n}$ is missing from the union of the nodes in all the other paths, then we're done. We've shown that no proper subset of the paths can cover all the nodes. Assume then that every one of the $P_n$'s is contained in the union of all the other paths besides $P$. So $P_1$ is in the union, and so is $P_2$ under it, and $P_3$ under that ... in fact the entire path $P$ is in the set of paths, contrary to our assumption that $P$ wasn't there. In other words the limit of the sequence $P_1, P_2, P_3, \dots$ is $P$, and we can formalize the idea of limit by saying that the limit of a sequence of nodes is their union. So if the union of everything but $P$ contains all of $P$'s substrings, then the union must include $P$ after all. Contradiction! Now we know that some finite substring of $P$ must be missing from the union ... but it's hard to see which one that could be! If it's $P_{47}$, say, then at level 48 we have both the finite paths $P_{47} 0$ and $P_{47} 1$. [I hope that notation is clear, those are the two child nodes]. So $P_{47}$ must be in the union, since $P$ was one of those paths and the other one isn't $P$; and the one that isn't $P$ has all its nodes in the union. [I hope it's clear that "node", "substring," and "finite substring" are all synonymous]. There must be some missing node; but it can't be any particular node! This is a real puzzler. Am I getting the proper spirit of your question? Because this is really interesting. ps  There must be something wrong with my logic because I've proven that some node is missing but no particular node can be missing. I have an error somewhere, I haven't broken math. Last edited by Maschke; November 20th, 2017 at 02:31 PM. 
November 20th, 2017, 02:36 PM  #5 
Senior Member Joined: Jun 2014 From: USA Posts: 617 Thanks: 50 
Yes, you are on the right track as to my logic. I think I made a little progress with the help of your explanation of the ordinals. It's clear there is a countable subset of $I$ such that the union of the range of function $f$ across it would produce $F$. This subset might consist of each element of $I$ that simply has a trailing string of 0's: {finite string}{trailing string of 0's} < as though concatenating So let $T$ equal this particular subset of $I$. In a well ordering of $I$, we might assume that the elements of $T$ are the first $\omega$ elements of the well ordering. In that case, we have $\alpha$ from my OP being equal to $\omega$. Consider an element of $I$ with a trailing string of 1's as opposed to 0's and let it be $\omega + 1$ in the ordering. There would be no specific ordinal $i$ as mentioned in the OP where we have it becoming a subset, only $\omega$ itself. The same goes for all elements of $I$ not in $T$. I've been trying think through the proof that the axiom of choice implies the well ordering theorem. It seems to have a pick one, pick another, and just keep picking sort of method in order to produce the well ordering. I know it's not a list as you say, but "messy" or "wild" despite the ordering being a "well ordering" (if that isn't counterintuitive, I don't know what is...). We agree that if a true list of the elements of $I$ existed, we could never have the union of function $f$ across the list being equal to $F$ unless all elements of $I$ were in the list, yes? 
November 20th, 2017, 02:53 PM  #6  
Senior Member Joined: Aug 2012 Posts: 2,409 Thanks: 753  Quote:
However please don't call it a list. "List" is a technical term. It means a countable sequence orderequivalent to the natural numbers. I think that absolute clarity in this area is essential. There is no list of $I$. I don't know what you mean by "true" list. I think clarity on this point will be helpful. Since $I$ is uncountable, so is any wellordering. It may be some crazy ordinal but you are hoping it's not too crazy. But even "sensible" ordinals are pretty complicated. The ordinal $\omega_1$ is the entire set of countable ordinals, lined up in order. Any set of ordinals is always lined up in order, even though they are individually quite wild. So the use of the word "list" is bad, because it induces intuitions that are far from reality. Also I should mention that there are limit ordinals. For example to get from the finite ordinals 1, 2, 3, 4, ... to the first infinite ordinal $\omega$, there is a jump where we take the limit (defined as the settheoretic union) of all the finite ordinals. An ordinal is a limit ordinal if it has no immediate predecessor. Just mentioning that as further problems for the idea that anything we're dealing with could be called a "list." So I did convince myself that if you leave out a path, you must necessarily leave out one of its substrings. But I also proved that you can't have left out any particular substring. I have to sort that out. Last edited by Maschke; November 20th, 2017 at 03:06 PM.  
November 20th, 2017, 03:11 PM  #7  
Senior Member Joined: Aug 2012 Posts: 2,409 Thanks: 753  Good. Quote:
Quote:
Quote:
But again, I suspect wellorderings are a red herring in your original problem. The question is, which proper subsets of $I$ "cover" the substrings. It doesn't matter how you order them, only that there's a subset. If you forget about ordinals this problem might be easier to think about. Last edited by Maschke; November 20th, 2017 at 03:14 PM.  
November 20th, 2017, 03:14 PM  #8  
Senior Member Joined: Jun 2014 From: USA Posts: 617 Thanks: 50  Quote:
I find this confusing. I'm not sure how to go past it, like we're walking on the far edge of $\omega$ looking for where the elements of $T$ and those not in $T$ 'thread together.' It starts to turn philosophical, which is where the conversation would break down as I believe neither one of us care to delve into philosophy. Hmmm... frustrating too.  
November 20th, 2017, 03:16 PM  #9  
Senior Member Joined: Aug 2012 Posts: 2,409 Thanks: 753  Quote:
I apologize, my eyes glazed around your $T$ discussion earlier so I don't know what $T$ is. ps  Oh ok $T$ is the set of finite strings padded with zeros? Still not sure what you were doing with that. Last edited by Maschke; November 20th, 2017 at 03:20 PM.  
November 20th, 2017, 03:26 PM  #10  
Senior Member Joined: Jun 2014 From: USA Posts: 617 Thanks: 50  Quote:
Because all finite strings appear in the initial segments of elements of $T$ (all substrings to mirror your node example), we can have a subset of $I$ that covers all of $F$ (all the substrings) despite omitting the vast majority of the elements of $I$ (omitting the vast majority of the paths).  

Tags 
ordering, question, set, uncountable 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to prove P(N) is uncountable ?  mcquintrix  Computer Science  3  January 19th, 2015 10:02 PM 
show that M is uncountable  450081592  Real Analysis  2  November 23rd, 2011 06:34 PM 
Uncountable  whatlifeforme  Number Theory  1  October 30th, 2011 04:53 AM 
countable, uncountable  wannabe1  Real Analysis  5  September 22nd, 2010 03:18 PM 
Surjection, Uncountable Set  vaevictis59  Applied Math  18  March 16th, 2010 09:14 AM 