Talk: First uncountable ordinal

Ikosarakt, please define order type of function. LittlePeng9 (talk) 20:10, July 9, 2013 (UTC)

I removed the sentence. \(\omega_1\) is the googologist's infinity. FB100Z • talk • contribs 20:22, July 9, 2013 (UTC)

Order type of f(n) is such \(\alpha\) so that \(f_\alpha(n)\) has growth rate comparable to f(n). But I can guess why you ask it. Ikosarakt1 (talk ^ contribs) 10:50, July 10, 2013 (UTC)

What is order type of arithmetic mean of f_a and f_a+1? LittlePeng9 (talk) 09:33, July 11, 2013 (UTC)

In FGH, we can compare only unary functions. If the function is binary, we get it unary taking all arguments to the one value. Arithmetic mean of n and n is n, and so we get that it grows slower than f_0(n). By the way, arithmetic mean of n and n is also H_0(n) in Hardy hierarchy, and we know that \(H_{\omega^\alpha}(n) \approx f_\alpha(n)\) for all alpha < e_0. We can take 0 = omega^(-infinity) and say that ar. mean has order type \(f_\infty(n)\). Ikosarakt1 (talk ^ contribs) 09:47, July 11, 2013 (UTC)

I meant that if we take any (fixed) \(\alpha\), for example \(\omega\), and we take \(f(n)={f_\omega+f_{\omega+1}\over 2}\), then what is order type of f(n)? LittlePeng9 (talk) 10:57, July 11, 2013 (UTC)

We get \(f(n) \approx f_{\omega+1}(n)\) (adding \(f_{\omega}(n)\) and dividing by 2 are too weak functions to affect the growth rate if we have \(f_{\omega+1}(n)\) in the expression), and thus f(n) has order type \(\omega+1\). As for stating it in general, I believe that from \(\alpha \geq 1\) it holds the same. Ikosarakt1 (talk ^ contribs) 11:06, July 11, 2013 (UTC)

By the way, put another way defining order type of function: we know that ordinal has set of ordinals lesser than it. If we get that f(n) outgrows \(f_{\alpha}(n)\) for each \(\alpha\) in this set, then f(n) has that order type. So, defining the function with order type \(\omega_1\) is equivalent to defining a function outgrowing all countable ordinals (as they are all in set of \(\omega_1\)). Ikosarakt1 (talk ^ contribs) 11:12, July 11, 2013 (UTC)

That definition would work if we can define a hierarchy of functions that assigns a function to every countable ordinal. Unfortunately there doesn't seem to be any way to explicitly define a nontrivial hierarchy of functions for all countable ordinals. (as any notation we devise can only refer to countably many ordinals) Deedlit11 (talk) 13:22, July 11, 2013 (UTC)

Does anyone know what ordinals beyond \(\omega_1\) have fundamental sequences? I have deduced a few rules:

• If \(\alpha > \beta\) and \(\beta\) has a fundamental sequence, then \(\alpha + \beta\) has a fundamental sequence.
• If \(\alpha > \beta\) and \(\beta\) has a fundamental sequence, then \(\alpha \times \beta\) has a fundamental sequence.
• If \(\alpha\) has a fundamental sequence, then \(\omega_\alpha\) has a fundamental sequence.

FB100Z • talk • contribs 20:25, July 9, 2013 (UTC)

\(\omega_\omega\) has fundamental sequence \(\omega_1,\omega_2,\omega_3,\cdots\). Ikosarakt1 (talk ^ contribs) 10:52, July 10, 2013 (UTC)

The list is much, much longer, for example \(\varepsilon_{\Omega+1}\), \(\Gamma_{\Omega+1}\). The thing I wanted also to point out is that fundamental sequence doesn't need to be countable. Every limit ordinal has fundamental sequence of size equal to its cofinality. But definitions may vary. LittlePeng9 (talk) 21:00, July 9, 2013 (UTC)

That is, and so \(\omega_1\) have the fundamental sequence, but it have the property \(\omega_1[\omega_1] = \omega_1\). Things like \(\omega_1[n]\) aren't meaningless, and this limits to \(\omega_1[\omega]\), which is still a countable ordinal. Thus, if we plug \(\omega_1\) into FGH we just get that \(f_{\omega_1}(n) = f_{\omega_1[\omega]}(n)\). It doesn't seems that function in the form f(n) (where n is a finite number) can outgrows any countable ordinal.

\(f_{\omega_1}(n)\) is just an useful shorthand, we can't use \(\omega_1\) literally here. It's just as if you said \(f_\omega(n)\) must be infinite because it is limit of \(f_0(n),f_1(n),...\) and latter functions have larger values than former. LittlePeng9 (talk) 15:09, August 13, 2013 (UTC)

But still, something seems amiss with \(\omega_1\) inside FGH. If \(\alpha\) is countable and \(\beta\) is uncountable, how can \(f_{\alpha}(n)\) be equivalent to \(f_{\beta}(n)\)? Recall \(\alpha = \omega_1\) and \(\beta = \omega_1[\omega]\).

Another interesting puzzle is defining finite terms of fundamental sequence to \(\omega_1\), i.e. \(\omega_1[n]\). Ikosarakt1 (talk ^ contribs) 18:19, August 13, 2013 (UTC)

The point with f_w_1 is that it isn't inside FGH, it is beyond it, as it is with any uncountable. \(\omega_1[\alpha]=\alpha\) for \(\alpha<\omega_1\) is consistent, so using ordinals literally we have \(f_{\omega_1}(n)=f_\omega(n)\). LittlePeng9 (talk) 18:29, August 13, 2013 (UTC)

\(\omega_1\) vs. \(\Omega\)

I wanted to ask you about last edit on this article (not mine). Do you think we should use \(\Omega\) in the article? In my opinion not, because \(\Omega\) is just useful shorthand for ordinal above any notation, which can be \(\omega_1\) as well as CK ordinal or any other uncountable regular ordinal. LittlePeng9 (talk) 06:34, August 11, 2013 (UTC)

For me, the better is think about \(\Omega\) just as diagonalizator, which is used in \(\theta_\alpha\) and \(\psi_\alpha\) functions. The red \(\Omega\) was also used as the symbol for the absolute infinity by Sbiis Saibian. Ikosarakt1 (talk ^ contribs) 10:13, August 11, 2013 (UTC)

Constructing function with order type \(\omega_1\) from irrational numbers

How about constructing the function for \(\omega_1\), assigning each countable ordinal to irrational number? If anyone would do it, he would prove whether continuum hypothesis true or not! Ikosarakt1 (talk ^ contribs) 15:18, August 30, 2013 (UTC)

Assuming axiom of choice there necessarily is injection from w_1 to irrationals: AC implies well-ordering theorem, which implies there is well-ordering of irrationals. It can't be countable, thus it has initial segment of length w_1, which we can inject countable ordinals to. If you ask for bijection, then it is equivalent to CH. but how does it relate to fast growing functions? LittlePeng9 (talk) 16:29, August 30, 2013 (UTC)

Also, without AC, note that continuum may be incomparible with w_1, so no injection in either way would be possible. LittlePeng9 (talk) 16:32, August 30, 2013 (UTC)

As there are uncountably many ordinals can be coded between 0 and 1 (if irrational numbers are allowed) probably there exists a definition of a hierarchy \(F_n(m)\) with 0 <= n <= 1 so that 0 is a notation for 0 and 1 is a notation for \(\omega_1\). Ikosarakt1 (talk ^ contribs) 16:40, August 30, 2013 (UTC)

Of course we can construct such hierarchy, but giving it any non-trivial property will be very hard, for example F_n(m)=1 for all n,m defines some hierarchy. Problem with this method is that giving every real an ordinal tells us nothing about fundamental sequences. LittlePeng9 (talk) 16:51, August 30, 2013 (UTC)

If you are trying to inject the countable ordinals into the irrationals in a way that preserves order, this is impossible. The reason is simple: Suppose that you have an order-preserving injection f from \(\omega_1\) to R. Then for every ordinal \(\alpha\), the open interval \((f(\alpha), f(\alpha+1))\) will contain a rational number; let \(g(\alpha)\) be any rational in that interval. Then g is an injection from \(\omega_1\) to the rationals, which is impossible since the rationals are countable. Q.E.D. Deedlit11 (talk) 18:33, August 31, 2013 (UTC)

How long FGH can be theoretically extended?

As far as I know, the cardinality of functions \(f : \mathbb{N} \mapsto \mathbb{N}\) is \(\mathfrak{c} = \mathbb{N}^\mathbb{N} = 2^\mathbb{N} \geq \aleph_1\). Since there might be more than \(\aleph_1\) functions, \(f_{\omega_1}(n)\) possibly can be defined (however, using infinitely long notation) supposing that CH is false. But is it also correct that \(\mathfrak{c} < \aleph_2\)? If it is true, then I can add to an article that extending FGH up to \(f_{\omega_2}(n)\) is not theoretically possible because there are not enough functions \(f_\alpha : \mathbb{N} \mapsto \mathbb{N}\). If it is false, then what is minimal \(\lambda\) for which we can be sure that \(\mathfrak{c} < \aleph_\lambda\)? Triakula (talk) 18:10, January 19, 2020 (UTC)

> Since there might be more than \(\aleph_1\) functions, \(f_{\omega_1}(n)\) possibly can be defined (however, using infinitely long notation) supposing that CH is false.

Which statement are you considering?

1. If CH is false, then for any system of fundamental sequences, there exists a function f_{ω_1}(n) which eventually dominates f_α(n) for any α<ω_1.
2. The statement "for any system of fundamental sequences, there exists a function f_{ω_1}(n) which eventually dominates f_α(n) for any α<ω_1" is consistent with ZFC+¬CH.

I think that the first statement is not provable under ZFC, although I do not have a counterexample. The second statement is perhaps true. I note that even if a partially ordered set of cardinality greater than ℵ_1 is not necessarily cofinality greater than ℵ_1. For example, the real line R is of cardinality ℵ_1, while it includes the unbounded countable subset Q of rational numbers, i.e. there is no real number which is greater than any rational number.

> But is it also correct that \(\mathfrak{c} < \aleph_2\)?

The statement is equivalent to CH.

> If it is true, then I can add to an article that extending FGH up to \(f_{\omega_2}(n)\) is not theoretically possible because there are not enough functions \(f_\alpha : \mathbb{N} \mapsto \mathbb{N}\).

The set (f_α(n))_{α<ω_2} with respect to a way to define f_α's is of cardinality bounded by ℵ_2, but it not necessarily of cardinality ℵ_2, because f_α = f_β can holds for distinct α,β<ω_2.

> If it is false, then what is minimal \(\lambda\) for which we can be sure that \(\mathfrak{c} < \aleph_\lambda\)?

It is a difficult problem in set theory. I have heard that even if we assume the existence of weakly inaccessible cardinal, ℵ < ℵ_I (= I) is not provable.

p-adic 01:06, January 20, 2020 (UTC)

> Which statement are you considering?

I was not referring to ZFC in the statement because it, as long as I know, cannot define all countable ordinals. I believe that the second statement is not correct by the same reason.

> The set (f_α(n))_{α<ω_2} with respect to a way to define f_α's is of cardinality bounded by ℵ_2, but it not necessarily of cardinality ℵ_2, because f_α = f_β can holds for distinct α,β<ω_2.

Okay, I shall add that to the article. Thank you. Triakula (talk) 05:43, January 20, 2020 (UTC)

> I was not referring to ZFC in the statement because it, as long as I know, cannot define all countable ordinals.

If you are talking about the meta theoretic "definability", then it is intuitively true, because there is only countably many formula in ZFC, while there are uncountably many countable ordinals. However, the meta theoretic "definability" is not a statement formalised in ZFC set theory itself. Therefore it does not contradict the statement 2. The situation is the same when we consider a stronger set theory. Therefore if you did not intend to specify axioms, then it is just an unformalised statement, which we cannot ask whether it is true or false in a theoretic way.

p-adic 06:00, January 20, 2020 (UTC)

The updated description includes errors.

> If continuum hypothesis is correct, then we can't extend FGH beyond \(\omega_1\).

It is wrong. If an f_{ω_1}(n) is defined for a specific choice of a system of fundamental sequences for all countable ordinal, then you can extend the hierarchy by setting f_{ω_1+1}(n) = f_{ω_1}^n(n). (Such an f_{ω_1}(n) does not necessarily exist for a specific choice, though.)

> In other words, if continuum hypothesis is false, then there exists an ordinal \(\lambda\) so that \(\omega_1 < \lambda < \omega_2\) up to which we can extend FGH.

It does not mean that. Maybe you need to specify what "we can extend FGH up to λ", because you are considering uncountable ordinal. Are you requiring that α<β implies f_β eventually dominates f_α? But it does not necessarily hold even if we are considering FGH below ω_1. You need to specify the precise assumptions which you are requiring to FGH beyond ω_1.

p-adic 07:35, January 20, 2020 (UTC)

> It is wrong. If an f_{ω_1}(n) is defined for a specific choice of a system of fundamental sequences for all countable ordinal, then you can extend the hierarchy by setting f_{ω_1+1}(n) = f_{ω_1}^n(n). (Such an f_{ω_1}(n) does not necessarily exist for a specific choice, though.)

By that I meant if continuum hypothesis is correct, then we can't extend FGH up to and beyond \(\omega_1\) since there are exactly \(\aleph_1\) functions. I'll improve that.

> It does not mean that. Maybe you need to specify what "we can extend FGH up to λ", because you are considering uncountable ordinal. Are you requiring that α<β implies f_β eventually dominates f_α? But it does not necessarily hold even if we are considering FGH below ω_1. You need to specify the precise assumptions which you are requiring to FGH beyond ω_1.

I'll warn users about that the article talks about linear hierarchy so that \(\alpha < \beta \rightarrow f_\alpha <^{*} f_\beta\). Triakula (talk) 07:45, January 20, 2020 (UTC)

> By that I meant if continuum hypothesis is correct, then we can't extend FGH up to and beyond \(\omega_1\) since there are exactly \(\aleph_1\) functions.

No, you just have at most ℵ_1 functions, because f_α = f_β can occur for distinct α,β<ω_1. Moreover, even if they are distinct ℵ_1 functions, it does not mean that there is no function eventually dominating them. Please remember that although R and [0,1] are of cardinality ℵ_1, there is an upperbound, e.g. 2, of [0,1] in R.

p-adic 07:58, January 20, 2020 (UTC)

I removed the false sentence. Triakula (talk) 08:09, January 20, 2020 (UTC)

I still do not understand the precise statements in the last paragraph. Are you fixing a single system of fundamental sequences below ω_2? Or are you considering all systems? Is the following your formulation of FGH beyond ω_1?

1. If α<ω_2 is of cofinality 0, then f_α(n) = n+1.
2. If α<ω_2 is of cofinality 1, then f_α(n) = f_β^n(n), where β is the predecessor of α.
3. If α<ω_2 is of cofinality ω, then f_α(n) = f_{α[n]}(n).
4. For any α<β<ω_2, f_β eventually dominates f_α.

At least, what is written looks still incorrect. (For example, why there is such a λ?) Although I am not certain about what you are trying to write, could I fix all errors and ambiguous statements?

p-adic 12:26, January 20, 2020 (UTC)

I didn't mean that there is a system of fundamental sequences below \(\omega_2\) which can be defined. I meant that there may be an increasing linear sequence of functions with length \(\lambda < \omega_2\) which may be treated not as FGH, but as an extension of FGH. If you think that it is ambiguous, you may fix my statements. Triakula (talk) 13:01, January 20, 2020 (UTC)

Then what does "an extendion of FGH" means? Since FGH is not a single hierarchy (because it depends on a choice of a system of fundamental sequences below a fixed ordinal), it is ambiguous. Also, why is there such a λ under the negation of CH?

p-adic 13:10, January 20, 2020 (UTC)

We are supposing that there is a single, fixed system of functions which are defined by a fixed system fundamental sequences below \(\omega_1\) and by some another artifical way beyond \(\omega_1\). That's what I called "an extension of FGH". However, I'm starting to believe from our discussion that this name is ambiguous. The reasoning why I thought that there exists \(\lambda > \omega_1\) under the negation of CH is that: if the number of functions is \(\aleph_1\), then there may be no function that grows faster than all \(\aleph_1\) functions if the hierarchy of functions is linear. Triakula (talk) 13:37, January 20, 2020 (UTC)

The negation implies that there are more than ℵ_1 functions. Are you assuming CH instead of the negation of CH? In any cases, "if the number of functions is \(\aleph_1\), then there may be no function that grows faster than all \(\aleph_1\) functions if the hierarchy of functions is linear" is wrong. As I wrote above, a partiall ordered set of cardinality ℵ_1 possibly has a subset of cardinality ℵ_1 which is bounded. For example, R and [0,1] have the same cardinality, while [0,1] admits an upperbound 2. If the set of all functions and a linear hierarchy have the same cardinality, it does not mean that the linear hierarchy does not have an upperbound, i.e. a function eventually dominating them.

p-adic 14:14, January 20, 2020 (UTC)

Sorry for my typo. I meant that there is such a function. Okay, it is more clear now. It would be nice if you replace my descriptions by the correct descriptions in the article. Triakula (talk) 14:21, January 20, 2020 (UTC)

At least, the paragraph looked completely wrong, and I could not find how to fix it. Therefore I deleted it.

p-adic 22:55, January 20, 2020 (UTC)

The removed paragraph is reproduced here:

If we want to extend FGH beyond \(\omega_1\), we need to specify that it is possible if the hierarchy is linear, i.e. \(\alpha < \beta\) implies that \(f_\alpha\) eventually dominates \(f_\beta\). If it would be possible to extend FGH up to \(\omega_1\) and somewhat beyond, we may not extend it up to \(\omega_2\), the second uncountable regular ordinal. The set of all functions \(f_\alpha(n)\) for ordinals \(\alpha < \omega_2\) with respect to a way to define \(f_\alpha\) is of cardinality bounded by \(\aleph_2\), but it not necessarily of cardinality \(\aleph_2\), because \(f_\alpha = f_\beta\) can hold for distinct \(\alpha,\beta < \omega_2\). In other words, if continuum hypothesis is false, then there exists an ordinal \(\lambda\) so that \(\omega_1 < \lambda < \omega_2\) up to which we can extend FGH, assuming that it is linearly ordered.

-- ☁ I want more clouds! ⛅ 17:44, January 21, 2020 (UTC)

Thank you.

p-adic 23:33, January 21, 2020 (UTC)

@Triakula

How do you show the existence of an f_{ω_1+ω_1}(n)? Also, "there is an ordinal beyond ω_1 which has a fundamental sequence" does not look notable because you have already written examples, i.e. ω_1+α for a countable limit ordinal α.

p-adic 23:40, January 24, 2020 (UTC)

The existence of \(f_{\omega_1+\omega_1}(n)\) is only an assumption like the existence of \(f_{\omega_1}(n)\). Of course, it is independent of formal logic like ZFC. As for FS's, I moved the paragraph. Triakula (talk) 06:20, January 25, 2020 (UTC)

It makes sense. Thank you.

p-adic 06:35, January 25, 2020 (UTC)

Number of systems of fundamental sequences

Are there at least \(\aleph_2\) systems of fundamental sequences for all countable ordinals? Triakula (talk) 17:50, February 4, 2020 (UTC)

No. The cardinality is ℵ×ℵ_1 = ℵ. It coincides with ℵ_1 if CH holds, and is greater than or equal to ℵ_2 if CH does not hold.

p-adic 22:39, February 4, 2020 (UTC)

Thanks, I'll know. Triakula (talk) 12:59, February 5, 2020 (UTC)

"First"

Is there a standard convention in math for enumerating a class using ordinal words such as "first", "second", etc. even though "zeroth" would be an ordinal word since \(0\in\textrm{Ord}\)? If this is the case, this page can be renamed to "least uncountable ordinal" C7X (talk) 02:23, 18 June 2021 (UTC)

I think that it is standard one, although I prefer to use "least" or "0-th".

p-adic 02:58, 18 June 2021 (UTC)