My Math Forum  

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

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
September 2nd, 2019, 09:51 PM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 644
Thanks: 55

Another Opus Here

This thread deals with ordinal numbers:

Ordinal Number -- from Wolfram MathWorld

The standard less-than ordinal comparison, $<$, implies that $\alpha < \beta$ if and only if $\alpha$ is order isomorphic to an initial segment of $\beta$. The class of ordinal numbers are well ordered by the relation.

Define the relation $\prec$ such that, for any two sets of ordinal numbers $A$ and $B$, we have:
$$A \prec B \iff \forall b \in B(\forall a \in A( a < b))$$

Define $\phi$ as a boolean function where $\phi(\gamma)$ is true if and only if $\gamma$ is an ordinal number that can be partitioned into at least one arbitrary sequence of sets, $S$, such that three requirements are met:

1) $S = s_1, s_2, s_3, \dots$ (that is, $S$ is an infinite sequence),

2) $\{ s_i : s_i \in S \}$ is a partition of $\gamma$, and,

3) given $s_i, s_j \in S$, the following relation holds true: $s_i \prec s_j \iff i < j$.

For example, $\phi(\omega)$ is true because the first limit ordinal, $\omega$, can be partitioned into the sequence of finite ordinals meeting the above criteria:

$$S = \{1\}, \{2\}, \{3\}, \dots$$

Other possible sequences exist as well that suffice to prove $\phi(\omega)$ true. E.g., the following two sequences $S’$ and $S’’$ also suffice (and there are infinitely many more as well):
$$S’ = \{1,2,3\}, \{4, 5, 6\}, \{7,8,9\}, \dots, \text{ and}$$
$$S’’ = \{1 \}, \{2,3\}, \{4,5.6\}, \dots$$

Let it be emphasized that there are no restrictions on the cardinality of any of the elements of an arbitrary sequence $S$ that suffices to prove $\phi(\gamma)$ true for a given ordinal $\gamma$. As a result, even though $S$ is restricted to being a standard (countably infinite) sequence, the cardinality of $\bigcup S$ could potentially be uncountable.

Let it also be emphasized that $\phi(\gamma)$ will not hold true for any ordinal $\gamma$ that is not a limit ordinal. This is because $\gamma$ will have a greatest element that must also be in one and only one element of $S$ due requirement #2. That one element of $S$ containing the greatest element of $\gamma$ would also have to be the last element of $S$ due requirement #3 and in contradiction of requirement #1.

Conjecture #1: $\phi(\gamma)$ will hold true for any limit ordinal.

By definition, the smallest uncountable ordinal, $\omega_1$, is a limit ordinal that is the set of all countable ordinals.

Given that $\omega_1$ is a limit ordinal, we know that it has no immediate predecessor under the standard ordering. That is, if $y < \omega_1$, we know there also exists some ordinal $x$ where $y < x < \omega_1$ holds true.

What happens if we assume the existence of a set $S$ that suffices to prove $\phi(\omega_1)$ true?

In that case, one of two statements must be true and the other false:

1) There exists an element $s_j \in S$ such that $|s_j| = |\omega_1|$ or

2) There does not exist an element $s_j \in S$ such that $|s_j| = |\omega_1|$.

Assume statement #1 is true. Then the least upper bound of $s_j$ is both uncountable and less than $\omega_1$, resulting in a contradiction:
$$(\text{sup }s_j < \omega_1 \text{ and } |\text{sup }s_j| = |\omega_1|) \implies \omega_1 \text{ is not the smallest uncountable ordinal.}$$

Assume statement #2 is true. Then we have an uncountable set, $\omega_1$, being equal to a countable union of countable sets. Such a theorem would be consistent with the negation of the axiom of choice (at least one model exists where the real numbers are a countable union of countable sets given the negation of the axiom choice), noting the axiom of (countable) choice is required to show that a countable union of countable sets is itself countable. See https://en.wikipedia.org/wiki/Axiom_of_choice

If my conjecture is true, then either statement #1 or statement #2 must be true if my logic is correct. Also, if the axiom of choice is adopted, $\omega_1$ would be countable by statement #2, contradicting the definition of $\omega_1$.

Maybe uncountable ordinals simply don’t exist as sets and instead need to be characterized as proper classes? See Burali-Forti Paradox -- from Wolfram MathWorld, showing that the class of ordinals is a proper class.

If no uncountable ordinals exist as sets, then the Continuum Hypothesis is resolved.

I wonder what implications this has for Gödel’s constructible universe, which is built on the hierarchy of the ordinals?

Ok. I assume I didn’t break math or anything. Any help?

Last edited by AplanisTophet; September 2nd, 2019 at 10:13 PM. Reason: To add reason for editing. Fixed statement #1, least upper bound
AplanisTophet is offline  
 
September 2nd, 2019, 10:28 PM   #2
Senior Member
 
Joined: Aug 2012

Posts: 2,424
Thanks: 759

Quote:
Originally Posted by AplanisTophet View Post
If no uncountable ordinals exist as sets, then the Continuum Hypothesis is resolved.
I skimmed till this. $\omega_1$ can be proven to exist in ZF. So your antecedent is false.

The proof sketch (missing many details) is:

* The collection of all countable ordinals is a set.

* The collection of all countable ordinals is an ordinal.

* It can't be a countable ordinal since that would violate Foundation.

* Therefore it's an uncountable ordinal.

The definition of ordinal I'm using is a transitive set well-ordered by $\in$.

If you convinced yourself otherwise, you have an error.

ps -- See Asaf Karagila's answer here.

https://math.stackexchange.com/quest...-exists-at-all

pps -- "It is hard not to become awestruck by the staggering immensity of $\omega_1$".

https://ncatlab.org/nlab/show/first+uncountable+ordinal

By the way the Wiki page on the first uncountable ordinal is absolutely wretched, providing neither an existence proof nor insight.

And finally, here is another nice page with several existence proofs and a discussion of the issues involved.

https://math.stackexchange.com/quest...ntable-ordinal

Last edited by Maschke; September 2nd, 2019 at 11:03 PM.
Maschke is offline  
September 3rd, 2019, 12:07 AM   #3
Senior Member
 
Joined: Aug 2012

Posts: 2,424
Thanks: 759

ps -- Didn't you just convince yourself that conjecture 1 is false, with $\omega_1$ being the counterexample? You can't reach $\omega_1$ with a countable sequence. I haven't thought this all the way through but that's what seems to be going on. No countable sequence of ordinals can cover $\omega_1$.

For example you could accomplish your partition by allowing "long sequences," functions whose domain is some initial segment of the class of ordinals. Then $\{0\}, \{1\}, \{2\}, \dots, \{\omega \}, \{\omega + 1\}, \dots$ where you go through all the countable ordinals, is a valid partition of $\omega_1$. It just happens to be uncountably long.

Last edited by Maschke; September 3rd, 2019 at 12:37 AM.
Maschke is offline  
September 3rd, 2019, 12:58 AM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 644
Thanks: 55

Quote:
Originally Posted by Maschke View Post
I skimmed till this. $\omega_1$ can be proven to exist in ZF. So your antecedent is false.
So, assuming ZF is consistent, we must negate the axiom of choice because then I don't derive any contradiction?

Well, that or we can't form a sequence $S$ that suffices to show $\phi(\omega_1)$ is true, correct?

Which is it?

Given the basic construction of the ordinals, if $\omega_1$ exists as a limit ordinal, we should also have an arbitrary sequence $S$ that suffices for $\phi(\omega_1)$ to be true was my speculation. I suppose I don't see why we are not guaranteed an arbitrary ordinal $\tau$ that is less than $\omega_1$ but also large enough so that:

$$S = \{x \in \omega_1 : x \leq \tau \}, \{\tau + 1\}, \{\tau + 2\}, \dots$$
and
$$\omega_1 = \bigcup S$$

Are you able to prove that no arbitrary sequence $S$ exists meeting the criteria for $\phi(\omega_1)$ to be true?

Last edited by AplanisTophet; September 3rd, 2019 at 01:07 AM.
AplanisTophet is offline  
September 3rd, 2019, 01:02 AM   #5
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 644
Thanks: 55

Quote:
Originally Posted by Maschke View Post
ps -- Didn't you just convince yourself that conjecture 1 is false, with $\omega_1$ being the counterexample? You can't reach $\omega_1$ with a countable sequence. I haven't thought this all the way through but that's what seems to be going on. No countable sequence of ordinals can cover $\omega_1$.

For example you could accomplish your partition by allowing "long sequences," functions whose domain is some initial segment of the class of ordinals. Then $\{0\}, \{1\}, \{2\}, \dots, \{\omega \}, \{\omega + 1\}, \dots$ where you go through all the countable ordinals, is a valid partition of $\omega_1$. It just happens to be uncountably long.
Please see my immediately preceding post and also this part of the OP:

"Let it be emphasized that there are no restrictions on the cardinality of any of the elements of an arbitrary sequence $S$..."

In other words, that countable sequence can contain uncountable elements (as far as the definition of $S$ is concerned), so it doesn't matter that the sequence itself is only countably infinite. A sequence of only a finite number of elements could meet the criteria absent requirement #1.
AplanisTophet is offline  
September 3rd, 2019, 04:55 AM   #6
Senior Member
 
Joined: Aug 2012

Posts: 2,424
Thanks: 759

See the first paragraph of Asaf Karagila's answer here, which says that $\omega_1$ has uncountable cofinality. That means (in this context) that there is no countable subset of $\omega_1$ that is unbounded in $\omega_1$. I believe this is the fact needed to show that your construction can't work. On the other hand I'm only quoting Asaf's remark and not supplying a proof that $\omega_1$ has uncountable cofinality, so that fact needs proof. In fact I think your construction amounts to claiming $\omega_1$ has countable cofinality, which is known to be false. I haven't thought all the way through this line of argument in detail but you should probably look into it.

https://math.stackexchange.com/quest...ble-cofinality

Secondly, you are dealing with sets of ordinals so you don't need Choice to pick the smallest one in each set to prove that the union of countable sets is countable in this instance. For example the snaking diagonals proof that the rationals are countable is valid even in ZF. You only need Choice for arbitrary countable collections of countable sets.


Quote:
Originally Posted by AplanisTophet View Post
"Let it be emphasized that there are no restrictions on the cardinality of any of the elements of an arbitrary sequence $S$..."

In other words, that countable sequence can contain uncountable elements (as far as the definition of $S$ is concerned), so it doesn't matter that the sequence itself is only countably infinite. A sequence of only a finite number of elements could meet the criteria absent requirement #1.
Irrelevant. Take the smallest element of each of your countably many sets of ordinals. No Choice needed. Such a set would be countable and unbounded in $\omega_1$. No such set exists. That's the cofinality argument. [Disclaimer: This argument might be shaky as-is but can probably be fixed up].

Quote:
Originally Posted by AplanisTophet View Post
So, assuming ZF is consistent, we must negate the axiom of choice because then I don't derive any contradiction?

Well, that or we can't form a sequence $S$ that suffices to show $\phi(\omega_1)$ is true, correct?

Which is it?
Neither, actually. You don't need choice to pick the least element from a collection of sets of ordinals. And you can't have a countable sequence unbounded in $\omega_1$.

You have a logic error re Choice. The negation of Choice doesn't say no countable union of countable sets is countable, it says SOME such union fails to be uncountable.

If you don't know about cofinality you might have to google around a bit because the Wki article on the subject leaves much to be desired.

Quote:
Originally Posted by AplanisTophet View Post


Assume statement #2 is true. Then we have an uncountable set, $\omega_1$, being equal to a countable union of countable sets. Such a theorem would be consistent with the negation of the axiom of choice (at least one model exists where the real numbers are a countable union of countable sets given the negation of the axiom choice),
I shouldn't have let this go earlier. First, in the absence of Choice, SOME countable union of countable sets fails to be countable, but not any particular one. And in the case where all the sets are ordinals, you can just pick the least element of each.

Re your referencing the obscure fact about the reals possibly being a countable union of countable sets, please note that EVEN SO, the reals are uncountable. That's provable in ZF. See Noah Schweber's comment to the question at https://mathoverflow.net/questions/1...ets-consistent

Finally I'll disclaim my cofinality argument to the extent that I haven't thought it all the way through and don't know much about the subject. I wrote all this down before working out all the details. But you should think it through and read up on cofinality, I think that's the essence of the matter. If you knew there is no countable, unbounded subset of $\omega_1$, would that resolve the matter?

Last edited by Maschke; September 3rd, 2019 at 05:35 AM.
Maschke is offline  
September 3rd, 2019, 06:01 AM   #7
Senior Member
 
Joined: Aug 2012

Posts: 2,424
Thanks: 759

ps -- I found in Kunen, Set Theory, first edition, page 33, that without AC it's consistent that the cofinality of $\omega_1$ is $\omega$. So without AC your construction is perhaps possible. Deep waters. Looks like you're right about the relevance of the consistency of the reals as a countable union of countable sets. In that model your construction probably works.

pps -- In the link I gave earlier in which Asaf Karagila said that $\omega_1$ has uncountable cofinality, he made the same point.

"... it requires some choice to prove there exists an ordinal with an uncountable cofinality, since it is consistent with ZF that there are none."

https://math.stackexchange.com/quest...ble-cofinality

Last edited by Maschke; September 3rd, 2019 at 06:26 AM.
Maschke is offline  
September 3rd, 2019, 04:23 PM   #8
Senior Member
 
Joined: Aug 2012

Posts: 2,424
Thanks: 759

Where'd you go? Is this thing on? It's König's theorem.

https://en.wikipedia.org/wiki/K%C3%B...m_(set_theory)

König's theorem is equivalent to the axiom of choice, and it basically disallows your partition. In its absence, your partition is allowed. You have a nice insight. It's about partitioning a set into a smaller number of smaller sets. Like a countable union of countable sets possibly being uncountable or not. It's the generalization of all that. And it always depends on the axiom of choice.

It's also about cofinality. If $\omega_1$ is a countable union of countable sets, as it might be in the absence of Choice, you can take one element from each set to get a countable set that's unbounded in $\omega_1$. So the cofinality of $\omega_1$ might be $\omega$.

Note that since these are sets of ordinals, we don't need Choice to obtain the choice set! That seems to be a key point.

I still don't see my way through the proof that with Choice, the cofinality of $\omega_1$ is $\omega_1$, but it shouldn't be too hard. Your visualization is, why can't one of those sets gulp up uncountably many elements and make a countable partition work? Good question.

Last edited by Maschke; September 3rd, 2019 at 04:32 PM.
Maschke is offline  
September 4th, 2019, 09:56 AM   #9
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 644
Thanks: 55

Thank you, will reply again, just had a baby girl
AplanisTophet is offline  
September 4th, 2019, 09:59 AM   #10
Senior Member
 
Joined: Aug 2012

Posts: 2,424
Thanks: 759

Quote:
Originally Posted by AplanisTophet View Post
Thank you, will reply again, just had a baby girl
A little taxpayer! Congratulations!
Maschke is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
opus



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
My Opus AplanisTophet Number Theory 12 October 12th, 2018 04:42 AM





Copyright © 2019 My Math Forum. All rights reserved.