My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 19th, 2017, 10:29 PM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 316
Thanks: 22

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...)?
AplanisTophet is offline  
 
November 20th, 2017, 12:39 AM   #2
Senior Member
 
Joined: Aug 2012

Posts: 1,659
Thanks: 427

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:
Originally Posted by AplanisTophet View Post
Let $I = \{ x : x \text{ is an infinite binary string} \}$.
Ok, I is the set of infinite binary sequences. In the context of formal set theory we shouldn't write $\{x : \text{anything}\}$ because that's dangerously close to Russell's paradox. And it sounds awkward to me. Just say, "Consider the set of foobars," rather than, "Consider the set of all x where x is a foobar." The latter is redundant and the notation is imprecise.

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.

Quote:
Originally Posted by AplanisTophet View Post
Let $F = \{ x : x \text{ is a finite binary string} \}$.
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:
Originally Posted by AplanisTophet View Post
For each $a \in I$, $a = a_{1}a_{2}a_{3}\dots$ where each $a_i$ equals $0$ or $1$.
Yes.



Quote:
Originally Posted by AplanisTophet View Post
For each $a \in I$, let $f(a) = \{ a_{1}, a_{1}a_{2}, a_{1}a_{2}a_{3}, \dots \}$.
So $f$ inputs a bitstring and outputs the set of its initial segments. Ok.

Quote:
Originally Posted by AplanisTophet View Post
Let $\prec$ be a well ordering of $I$ (assumes the axiom of choice)
Yes, you may well-order $I$.

Quote:
Originally Posted by AplanisTophet View Post
: $a^1, a^2, a^3, \dots$.
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 2-element 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 well-order of an uncountable set!

So no, you may not assume that it is a list, which is defined as the particular countable well-order that we call the "usual order on the naturals," namely 1, 2, 3, 4, ...

That's only one particular well-order of a countable set, and it's the simplest one. There are many others and they are one of the most mind-boggling 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 well-order 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 well-order an arbitrary set. But we do not need Choice to show that there is some uncountable well-ordered 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 well-order 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 01:19 AM.
Maschke is offline  
November 20th, 2017, 12:25 PM   #3
Senior Member
 
Joined: Aug 2012

Posts: 1,659
Thanks: 427

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 well-order 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 well-order 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 well-order 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 12:38 PM.
Maschke is offline  
November 20th, 2017, 03:05 PM   #4
Senior Member
 
Joined: Aug 2012

Posts: 1,659
Thanks: 427

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 well-order 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 03:31 PM.
Maschke is offline  
November 20th, 2017, 03:36 PM   #5
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 316
Thanks: 22

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?
AplanisTophet is offline  
November 20th, 2017, 03:53 PM   #6
Senior Member
 
Joined: Aug 2012

Posts: 1,659
Thanks: 427

Quote:
Originally Posted by AplanisTophet View Post
We agree that if a true list of the elements of $I$ existed...
If you mean to sort of say the same thing as I said with my tree example, I think that's right but I'm not 100% certain because I convinced my self that there is no particular node could be left out. That's a problem I think.

However please don't call it a list. "List" is a technical term. It means a countable sequence order-equivalent 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 well-ordering. 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 set-theoretic 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 04:06 PM.
Maschke is offline  
November 20th, 2017, 04:11 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 1,659
Thanks: 427

Quote:
Originally Posted by AplanisTophet View Post
Yes, you are on the right track as to my logic.
Good.

Quote:
Originally Posted by AplanisTophet View Post
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:
Not sure about your example. But in my real number example earlier, the naturals have the property that the union of all their $q$-sets includes all the rationals. I think the key property is that the subset should be unbounded in the original set.

Quote:
Originally Posted by AplanisTophet View Post
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$.
I wonder if well-orderings aren't complicating all this. I think the question is which subsets of I can be unioned to cover all the substrings. Is there a reason you care about well-orderings?

Quote:
Originally Posted by AplanisTophet View Post
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...).
Yes you pick one and the remaining set is nonempty, so you can pick another one, and so forth. The trick is to formalize that idea. I think you use transfinite induction but I could be wrong about that. You should look up the proof to see how it's done.

But again, I suspect well-orderings 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 04:14 PM.
Maschke is offline  
November 20th, 2017, 04:14 PM   #8
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 316
Thanks: 22

Quote:
Originally Posted by Maschke View Post
If you mean to sort of say the same thing as I said with my tree example, I think that's right but I'm not 100% certain because I convinced my self that there is no particular node could be left out. That's a problem I think.

However please don't call it a list. "List" is a technical term. It means a countable sequence order-equivalent to the natural numbers.

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.
Yes, agreed. If you leave out a path, you must omit a substring. That is what I see. There is no way around that, as far as I can tell. But yet, it's standard math to say that the union of function $f$ across $T \subset I$ from my most recent post would equal $F$.

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.
AplanisTophet is offline  
November 20th, 2017, 04:16 PM   #9
Senior Member
 
Joined: Aug 2012

Posts: 1,659
Thanks: 427

Quote:
Originally Posted by AplanisTophet View Post
Yes, agreed. If you leave out a path, you must omit a substring. That is what I see. There is no way around that, as far as I can tell. But yet, it's standard math to say that the union of function $f$ across $T \subset I$ from my most recent post would equal $F$.

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.
Not philosophical. Just a matter of breaking through to clarity. I'm going to work on my tree problem. Can you tell me why you care about ordinals rather than subsets? It's the same problem either way but without ordinals it's much simpler to deal with IMO.

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 04:20 PM.
Maschke is offline  
November 20th, 2017, 04:26 PM   #10
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 316
Thanks: 22

Quote:
Originally Posted by Maschke View Post
Not philosophical. Just a matter of breaking through to clarity. I'm going to work on my tree problem. Can you tell me why you care about ordinals rather than subsets? It's the same problem either way but without ordinals it's much simpler to deal with IMO.

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.
I found ordinals potentially useful for trying to pinpoint where all subtrings of a path become covered despite the path itself being omitted. We need not use them.

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).
AplanisTophet is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 11:02 PM
show that M is uncountable 450081592 Real Analysis 2 November 23rd, 2011 07:34 PM
Uncountable whatlifeforme Number Theory 1 October 30th, 2011 05:53 AM
countable, uncountable wannabe1 Real Analysis 5 September 22nd, 2010 04:18 PM
Surjection, Uncountable Set vaevictis59 Applied Math 18 March 16th, 2010 10:14 AM





Copyright © 2017 My Math Forum. All rights reserved.