Talk:Large countable ordinal

Untitled

I created this article by extracting a section from the article on "ordinal number". See the discussion for that article on the creation of this one. JRSpriggs 08:23, 13 March 2006 (UTC)

Title of article

The article looks great (not that I've looked at the details). But the title's gotta go. The ordinals in question might be large from a proof theorist's point of view, but not from that of a set theorist—all the ones mentioned except for in one brief sentence are below ω₁.

If the article is to be primarily about proof-theoretic ordinals, then that might be the title (except it should be singular: "Proof-theoretic ordinal"). Another possibility might be List of named ordinals, except it's not in list format currently and I'm not sure it would be an improvement to put it in that format. Specific countable ordinals? Named countable ordinals? Maybe just Countable ordinal; that would give a rationale for this text to be separate from ordinal and give space for all this discussion. At the moment I think I like the last suggestion best, but others are solicited. --Trovatore 17:16, 13 March 2006 (UTC)

Whether an ordinal is large or not depends on one's point of view. To someone used to thinking in terms of large cardinals, these are small. But to someone who is only thinking about ordinals with constructive notations, these are large. Tell me, are there any ordinals which are large in your sense and are discussed in the literature other than the initial ordinals of large cardinals? I think not. JRSpriggs 08:08, 14 March 2006 (UTC)

I agree with JRSpriggs's comment above. Perhaps the title is not the best possible, but I can't think of better, and the argument that large ordinals should be large cardinals doesn't strike me as convincing at all. --Gro-Tsen 09:06, 14 March 2006 (UTC)

Well, of course it depends on point of view. That's part of what makes "large ordinals" a bad title. I didn't say large ordinals should be large cardinals; I'm not suggesting a different subject matter under the title "large ordinals" (which as far as I know is not a standard term, so we shouldn't have an article called that, no matter the subject matter) but rather a different title for this article.

I don't claim I have a really good title for this article, but I have mentioned several better ones. Please discuss your objections to these. --Trovatore 14:56, 14 March 2006 (UTC)

Well, it's obvious, isn't it? Now suppose I wish to also say a few things about large ordinals which aren't necessarily countable. E.g., the smallest α such that $V_{\alpha }$ is a model of ZFC: should I create another article, or what? The way I defined admissible ordinals, they don't have to be countable: so discussing them in full generality os now off-topic. You could at least have waited for some sort of consensus here, or at least for the discussion to settle down, before moving the article! --Gro-Tsen 18:17, 15 March 2006 (UTC)

Granted, it might not have been the most politic move. But no one was responding, and the title was horrible. The α you mention above is countable, of course (that's not provable in ZFC, but then neither is its existence). Admissible ordinals should have an article of their own, and I suspect anything you'd want to say about uncountable ordinals would be sufficiently different in character from this article that it wouldn't be naturally included here. --Trovatore 20:39, 15 March 2006 (UTC)

No, the smallest α such that "$V_{\alpha }$ is a model of ZFC" is not countable (indeed, "being countable" is absolute for all $V_{\alpha }$ with α>ω limit (or some such thing) because whenever X is a countable set of rank less than α any bijection with ω will also have rank less than α; so the existence of ω₁ being a theorem of ZF precludes any $V_{\alpha }$ with countable α from being a model of ZFC). It has countable cofinality, however (by Skolem closure), and it is less than the first inaccessible. All of this might have been worth mentioning in the article (since passing note is made of the first α such that "$L_{\alpha }$ is a model of ZFC" — which is countable), except that it doesn't fit the title. As for the "no one was responding", couldn't you have waited even one week? --Gro-Tsen 23:11, 16 March 2006 (UTC)

Yeah, you're right on points 1 and 3. On point 2, including that α in this article, well, this is probably not the best final title. What the ordinals discussed have in common is not so much being "large" but rather having "names" or, if you like, sufficiently absolute definitions. "Large" should probably not be a part of the name the article winds up under. While I doubt it's particularly interesting to mention that particular α, we can probably choose a name that accommodates it if you have your heart set on including it. --Trovatore 23:35, 16 March 2006 (UTC)

Applying large ordinals to large natural numbers

We have seen that large uncountable ordinals can help one to describe large countable ordinals. Similarly, large countable ordinals can help one to describe large finite ordinals (natural numbers).

For example, one can extend the Ackermann function to the transfinite as follows:

A (0, n) = n+1.

A (α+1, 0) = A (α, 1).

A (α+1, n+1) = A (α, A (α+1, n)).

If λ is a limit ordinal with the fundamental sequence which takes k to λ_k, we let:

A (λ, n) = A (λ_n+1, n+1).

Then A (ε₀, 9!!!) would be a large finite number.

by JRSpriggs 07:37, 15 March 2006 (UTC)

Introduction

Per WP:LEAD and Wikipedia:Guide to writing better articles#Introductory material, it is not correct to have the article start with a section called "Introduction" and no text before the first section header. It's also not great style to talk about "this article" (think about articles in a print encyclopedia; when have you ever seen that there?). Moreover there is no reason to tell people not to look here for information about large cardinals, as there is no reason to think anyone would do so, and the line

The ordinals described here are large only in relationship to ordinals which have contructive notations (descriptions).

is misleading, given that a large fraction of the article is devoted to ordinals that do have constructive notations. The "Introduction" header should be removed, along with the self-referential text about "this article". --Trovatore 23:44, 16 March 2006 (UTC)

I hope that these problems have been adequately fixed now. JRSpriggs 06:35, 20 March 2006 (UTC)

To be honest I still don't like the first two sentences, referring to "the reader" and to the content of another article. This sort of "metalanguage" is, in my opinion, poor style except in things like disambiguation links, though there are times it's hard to get around. But I don't think it's hard to get around here, as neither sentence is really necessary: the reader can find what he needs through prominent links in the article, and the thing about large cardinals was always a red herring. You were the one who brought that up, and I never understood why.

Part of the problem is that it's still not a good article title. We should find one without the word "large", which is not really what distinguishes these ordinals. What distinguishes them is that they fall into certain naming schemes, or perhaps that they have sufficiently "absolute" definitions (under forcing, say). --Trovatore 15:23, 20 March 2006 (UTC)

Although I understand your dislike of "metalanguage", I feel that the reference to "ordinal arithmetic" is necessary. Ordinal arithmetic is used in this article, especially in the two subsections on the Veblen hierarchy. But there is no obvious place to work a reference to "ordinal arithmetic" into the language which would give the reader a sufficient nudge to get him to look at the other article. If you can figure out how to do it, please try. My reference to "large cardinals" was an attempt to cope with the confusion (which you pointed out) which a reader might be led into by the title "LARGE countable ordinals"; and the remainder of that sentence is an attempt to justify why I used the word "large" inspite of the fact that these ordinals are only countable. These ordinals ARE large compared to the other ordinals discussed in "ordinal number" and "ordinal arithmetic" which are generally less than or equal to epsilon-zero. The final sentence of that paragraph, "Larger and larger ordinals can be defined, but they become more and more difficult to describe.", summarizes the main point of this article. JRSpriggs 06:47, 21 March 2006 (UTC)

It just isn't standard practice. There are lots and lots of articles that can't really be understood by someone without prior knowledge (probably almost all the articles in the math project, really) and we don't try to do this sort of pointing (though there have been proposals, such as using templates; that would be ugly in my opinion but would not raise the "metalanguage" problem). I don't really agree with the last claim starting "these ordinals ARE large", because while it's true with respect to the ordinals discussed "retail" in those articles, the articles are really more about ordinals "wholesale", named or not. And the ordinals discussed in this article are not large compared to most of those.

So really, it's still not a good name for the article. Once we get it to a better title, many of the problems you raise will cease to be problems. --Trovatore 07:07, 21 March 2006 (UTC)

Title again

Since Trovatore is still not happy with the title, I was thinking that something more along the line of "Constructive ordinal notations" might be good, provided that we add more material on Kleene's O and Takeuti's ordinal diagrams, etc.. JRSpriggs 10:33, 22 March 2006 (UTC)

I, for my part, would be even less happy: that would make the whole section "Beyond recursive ordinals" off-topic, and I'm waiting for someone more knowledgeable than I am to say interesting things about the hyperjump, recursively inaccessibles, recursively mahlos and so on (and there's another word I forget: "uncompressible" or something?). --Gro-Tsen 16:59, 22 March 2006 (UTC)

I agree; that's not the right title either. Something like "named ordinals", maybe. Although I think the stuff Gro-Tsen mentions should perhaps be a different article altogether—it seems to be about large-cardinal-like properties that can be reflected into the countable hierarchy; that's quite different in character from the subject matter of the current article. --Trovatore 17:09, 22 March 2006 (UTC)

I don't want to step on any toes regarding the title —I have no answers to the problems y'all have been discussing in that regard— but I do want to make the title conform to Wikipedia:Naming conventions (plurals). So I'm going to move it to Large countable ordinal and fix the double redirects, but please don't interpret that as my support (or opposition) to that title (over Large ordinal, Proof-theoretic ordinal, etc). —Toby Bartels 01:36, 9 September 2006 (UTC)

An ordinal collapsing function

I wrote this description of an ordinal collapsing function which provides a system of notations up to the Bachmann-Howard ordinal (with a note of how to go further). It turned out to be longer than I expected, in fact (but the main reason for writing it was to clarify my own thoughts as to how ordinal collapsing functions work, and to provide a simpler vision of the Bachmann-Howard ordinal than the transcountable Veblen scheme of two variables). Anyway, comments are welcome, especially concerning the question of which articles this could be merged into (if any) and how (and which parts are actually useful for Wikipedia). One might accuse me of bordering on original research (horresco referens!) because the function in question is not exactly one which has been published already, but I think it is close enough to the ψ functions of Buchholz to ward me from that reproach (the reason for any changes is purely pedagogical). Any thoughts? --Gro-Tsen (talk) 16:26, 16 March 2008 (UTC)

Suggestions for merging

Since nobody is responding to the above call for suggestions on where/how to insert my text on constructing an ordinal collapsing function, I'll make my own suggestion. I propose having

• one article for "predicatively defined ordinals" (title is debatable, though, and probably disagreeable to those who insist the Feferman-Schütte ordinal is the largest predicative one), which would merge the Veblen functions (extended to finitely many, then transfinitely many variables — this is perhaps Schütte's Klammersymbol but I'm not sure), the (not very notable) Ackermann ordinal, and the small and large Veblen ordinals, and of course the Feferman-Schütte ordinal;
• another article for "ordinal collapsing" (or something), which would merge in my above-mentioned description, thus describing the Bachmann-Howard ordinal in detail, and then go on to mention some even larger proof-theoretic ordinals such as Rathjen's collapsing of a weakly compact cardinal.

How does this sound? The idea of having one page for each remarkable named ordinal seemed nice at first but now I think merging them in two broad families would be better. Of course, the large countable ordinal article would be slightly reorganized accordingly. --Gro-Tsen (talk) 10:15, 12 April 2008 (UTC)

Well, given the deafening silence, I started doing something of the sort: now there is a new article on ordinal collapsing functions (most of which is copied from my initial draft, but with additions on collapsing large cardinals). Now the articles on large countable ordinals (this one, that is) and ordinal analysis should probably be updated to refer to it. --Gro-Tsen (talk) 23:49, 16 April 2008 (UTC)

WP:BOLD Zero sharp (talk) 03:13, 17 April 2008 (UTC)

Literature pointer

I am interested in the quoted result that the ordinal strength of a system is equal to the first countable ordinal which is not proven to be a countable ordinal in the system. I could not figure out whether the strength of ZF would be this ordinal, or the possibly larger ordinal given by the limit of the images of some collapsing functions operating on the uncountable ordinals as well. I did not see any obvious reason that the two ordinals must be the same, even if the collapsing function is shown to be a function in ZF, but perhaps it is obvious. The claim here is that the "useless" definition of the ZF ordinal can prove the arithmetical consequences of ZF, but what is the statement of this theorem, and the literature source?Likebox (talk) 23:50, 28 October 2009 (UTC)

Define the ordinal strength of a (true) theory as the least least ordinal which is not the order type of some definable binary relation on a subset of ω which can be proven to be a well-ordering in the given theory. See Ordinal analysis. JRSpriggs (talk) 10:11, 29 October 2009 (UTC)

Where is this result in the literature? I just wanted to learn more about it.Likebox (talk) 15:22, 29 October 2009 (UTC)

Since you are giving a definition, by result I mean the following: if you know the ordinal strength of the theory, you can know which recursive function growth-rate is not provably recursive, and further that for theories with faster growth rates the ordinal is bigger.Likebox (talk) 15:27, 29 October 2009 (UTC)

Also, given a theory T with ordinal a, what is the ordinal of T+consis(T)?Likebox (talk) 15:36, 29 October 2009 (UTC)

(For posterity, since this is an old discussion) If T is a consistent, primitive recursive, Σ₁¹-sound theory that extends PA, T+Con(T) has the same proof theoretic ordinal as T. In general, adding any true Σ₁¹ sentence to T does not change its proof theoretic ordinal, since we assumed T is consistent, Con(T) is such a sentence. (Proposition 2.24 in Rathjen's The Realm of Ordinal Analysis.) C7XWiki (talk) 08:32, 4 December 2022 (UTC)

Platonist nonsense

There is a blurb at the beginning of this article which says that these large countable ordinals have no relation to large cardinals, which are much bigger, which reflects the usual ZF-Platonist bias of the contributors on these pages.

What is missing from this is the clear statement that all this "large uncountable ordinal" business is just a take-it-or-leave-it religion. The countable ordinals are all you ever see on a computer, since you can pass to a countable model for any set theory. The larger the large-cardinals in the theory, the larger the large countable ordinal that you need to describe the theory, so that the construction of these ordinals are precise computational counterparts of large cardinal axioms (and in this sense, pure ZF is a "large cardinal" for arithmetic). Although to a ZF-Platonist, these ordinals seem silly and small, if your mathematical universe includes computations, but not infinite uncountable sets, this heirarchy is the truly meaningful one.Likebox (talk) 15:48, 29 October 2009 (UTC)

The article does not say that "large countable ordinals have no relation to large cardinals". Indeed, there is a sense in which they are related. The article merely makes it clear that as ordinals the large countable ordinals are smaller than the large cardinals. A fact which is obvious to any experienced set theorist. JRSpriggs (talk) 00:51, 31 October 2009 (UTC)

This fact is only obvious to the Platonist, it's false in other philosophies of mathematics. The effective size of a large cardinal depends on how you philosophically view an uncountable ordinal. Is it an objective construction like the Platonist would have you believe, or is it a model dependent construction, as a formalist would believe. An uncountable ordinal in a model of ZFC+Large cardinals can be smaller than a large countable cardinal defined by some process.Likebox (talk) 21:08, 31 October 2009 (UTC)

Ron, whatever your philosophy, it is standard in mathematics to make assertions that make sense when translated into object language. Clearly the formalization of, say, "every inaccessible cardinal is larger than every countable ordinal" is provably true. --Trovatore (talk) 21:17, 31 October 2009 (UTC)

Likebox, I often disagree with Trovatore, but I totally agree with him on this. I am very far from being a Platonist, but I use this kind of language because everybody uses it. And everybody uses it because it's efficient. I am assuming that we are talking about this: "The ordinals described here are not as large as the ones described in large cardinals [...]". This statement has a precise technical meaning:

Let O be the class of ordinals described in large ordinals and C the class of cardinals described in large cardinals. (Let's ignore that these articles don't define O and C precisely; it could be done, although it would be hard to get a consensus for any one definition. But the following holds for any reasonable definitions.) Recall that every cardinal is also represented by an ordinal (the smallest ordinal of the same cardinality.) Then every element α of O is strictly smaller than every element of κ of C, in the standard sense of smallness. In other words, there is an injective map from α to κ but there is no injective map from κ to α.

It's easy to translate this statement into a sentence of first-order logic, in the language of set theory. According to the standard conventions of language use in mathematics, by stating this as fact we really mean that this first-order sentence follows from the axioms of ZFC. This has nothing to do with Platonism. In fact, it's almost impossible to identify a mathematician as a Platonist or otherwise by reading their technical works. Hans Adler 23:54, 31 October 2009 (UTC)

To Likebox: Suppose we have a transitive set which (together with the restriction of the true element relation) is a model of ZFC. Suppose that there is (as the downward Löwenheim–Skolem theorem requires) a countable elementary submodel of the given model. Assume that the submodel is collapsed to a transitive set. If one has a Π₁ predicate which defines a countable ordinal in the given model, then the ordinal which represents it in the submodel will be the same countable ordinal. Any definable uncountable cardinal of the given model will be represented in the submodel by a countable ordinal which is larger than all of those. So your "large countable cardinal defined by some process" must either be smaller than the "uncountable cardinals" of the submodel or not be representable in the submodel at all. JRSpriggs (talk) 19:28, 1 November 2009 (UTC)

(deindent) To JRSpriggs: such a countable ordinal doesn't have to be unrepresentable, it just has to be too large for the axioms of the theory to show that it is countable.

The "precise technical meaning" of the statement I don't like is this: countable ordinals are smaller than uncountable ones. Hans Adler has taken care to repeat this obvious statement in the language of ZF, and to correctly point out that it is a theorem of ZF. That's absolutely true. but this statement also has a precise philosophical meaning, a Platonist one, that the size of uncountable ordinals is well-defined, that it makes sense as a statement outside of a given axiomatic set theory and model for this set theory.

The Platonist position is that the first uncountable ordinal "omega-1" is an objective, precise object, living in a Platonic realm of pure existence. Stronger and stronger axiom systems define it more precisely, by proving larger and larger ordinals are countable, proving that the size of omega-1 is ever bigger. Since y'all believe that omega-1 is objective, often you do not mention that it is consistent to take other points of view. Any time someone mentions "omega-1" without specifically mentioning which axiom system and model for set theory, this person is committing a (very minor) act of Platonism.

One position, the one that I personally hold, is that the countable ordinals are objective, while uncountable ordinals are model-dependent fictions. The uncountable ordinals are only proved to exist in ZF by well-ordering powersets of infinite sets, which gives model-dependent results. Depending on the model, the powerset of Z, considered as an ordinal, is as humongous as you like. Following Paul Cohen, I believe that the size of the powerset of Z is not objective, that it is strongly model-dependent, and that the model-dependency can never be fixed, even in principle, because the powerset of Z is just too big to comfortably shoehorn into an ordinal. If you believe this, you don't care too much for uncountable ordinals, because the intuition that produced them--- namely that powerset of Z is well-orderable--- is wrong.

So the question becomes: what is omega-1, really? Using Powerset and uncountable-choice, omega-1 is proved to exist within ZF, but we don't know exactly how big it is. Since no theory is ever strong enough to exhaust the large countable ordinals, what happens in a minimal model of ZF is that omega-1 just becomes equal to the first countable ordinal that ZF is too weak to show is countable. It isn't uncountable in this model, just really big.

Powerset repeated ordinally many times constructs ever larger uncountable ordinals, and perhaps you add an axiom for inaccessible cardinals, and you get an ordinal tower of those too. These ordinals in a minimal model are just even bigger countable ordinals, and put together, you get some really enormous countable ordinal that is the universe in ZF or ZF+large-cardinals or whatever.

Since these universe always fit inside a large countable ordinal, it is consistent philosophically to reject the uncountable ordinals, keeping set theory pretty much unchanged. You just replace the axioms which produce uncountable ordinals with axioms of equivalent strength which produce larger countable ordinals. It's up to you. If you like a universe with well-ordered infinite powersets, you can pretend to have that. If you want a system with equivalent theorem proving power and no uncountable ordinals, you can have that too. This is the paradise that Cohen constructed.

The important thing to understand is that ordinals have computational consequences: they give you theorem-proving power. Extra strength ordinals have more theorem-proving power than regular ordinals. The uncountable ordinals of ZF, and the large-cardinals of extensions, only give you marginally more theorem proving power than countable ordinals, and they only do that by giving an extra "push" on top of the countable ordinals, to make a bigger countable model.Likebox (talk) 03:20, 2 November 2009 (UTC)

To Likebox: I get the feeling that you would be happier with a different kind of set theory rather than ZFC — a set theory without Platonic concepts. Perhaps Constructive set theory? Or Kripke–Platek set theory? JRSpriggs (talk) 06:01, 4 November 2009 (UTC)

The Kripke-Platek stuff looks very interesting. I didn't know it existed until recently. It seems to be some sort of ultra-constructive set theory, where the analog of Gentzen's method can be applied with some medium-sized ordinals. But ZFC is no different in principle, except that the ordinals are bigger. So we don't have a good handle on the exact values of the largest countable ordinals in the minimal model, or the proof theoretic ordinal (which I was recently told is defined as the smallest unrepresentable primitive recursive countable ordinal).

ZFC is not a philosophy, it's a formal theory: it doesn't necessarily involve Platonic concepts. Platonic concepts come in when you interpret the symbols of ZFC. You can interpret the sybols in many different ways.

One way is to take ZFC at face value, to interpret it as giving you accurate statements about the Platonic truth about uncountable sets. That means that the powerset of Z is well ordered, and can be matched to some ordinal. This point of view contradicts the everyday intuition that you can pick a real number between 0 and 1 at random, and it leaves the question of "how big is the smallest ordinal which can be matched to the powerset of Z?" forever unanswerable. But this point of view is still popular.

Another point of view is to take ZFC with a grain of salt. Then you think like this: "ZFC says that these ordinals are uncountable. Ok ZFC. You can think that. But I know that in the model I have in mind for you, that this ordinal is really countable, except you don't know that. I also know that the ordinal that you think matches up one-to-one with the real numbers doesn't really match up one-to-one with all of them, just with a countable subset. So you can continue to have your delusions of grandeur, and I will just interpret your delusions as statements about what you can prove about your minimal countable model."

This point of view is the formalist view, and it is also a reasonable way to view ZFC. Importantly, it doesn't leave out any arithmetic theorems, because the arithmetic theorems are all produced by countable ordinals.Likebox (talk) 23:48, 4 November 2009 (UTC)

This is an interesting point of view, and I've thought similar things myself. I would suggest that you write a paper about it and submit it to a journal specializing in the philosophy of science. However, I fail to see, or perhaps I disagree, with the idea that your point of view is any less "Platonic" than the ZFC-centric one (I'm not even sure it's really less ZFC-centric).

Let me see if I understand correctly: I believe you're suggesting that somewhat like the (generally agreed-upon) idea that the class of all ordinals should be treated as just one particular large ordinal which just so happens to be the smallest not included in whatever we think is the universe (the class of all ordinals in one model of ZFC² is just one inaccessible cardinal in a larger model of ZFC²), the same thing should hold for ω₁ in (first-order) ZFC, which should be regarded as an ever unfinished process; in fact, (you suggest,) any ordinal whatsoever should become countable in some sufficiently large universe of set theory. Am I not distorting too much? If not, I think it's still a very Platonic view of things (not to criticize): the idea that the ordinals somehow really "exist", even though one may wrongfully view them as uncountable. You don't seem to believe in any fewer ordinals than ZFC-platonists do, merely to regard them as smaller. :-) (It's not like if you had said that no ordinals exist beyond the Church–Kleene ordinal.)

Note that there may be technical difficulties lurking about, though. It's certainly true that if L_α is the smallest transitive model of ZFC and L_β the first one after that, then the ω₁ of L_α is countable in L_β. However, nothing says that the ordinals which act as ω₁ in transitive models of ZFC don't in some sense "stabilize" in the end. I'm being vague here, because I'm not sure what exactly should be meant by that. But here's at least one thought in this direction: when viewed in ZFC+(0# exists), models of ZFC+(V=L) seem very small, yet the values of ω₁ in such models eventually stabilize to some ω₁^L which is the smallest ordinal which is not allowed to be uncountable in a way compatible with V=L: of course, the latter is still countable in ZFC+0#, so you might say this goes your way, but my point is that to make ω₁ any larger than ω₁^L you have to actually break something in the structure of the universe (viz., V=L), not just pass to a larger model. In ZFC, this does not seem to happen, because we can always use forcing to collapse any cardinal to a countable ordinal; but this could be regarded as cheating, because what forcing really does is tinker with truth values: philosophically, I'm not sure it's really telling us anything useful that we can take any cardinal no matter how large and fiddle with truth values to say "oh, look, I can force a bijection with ω to make it countable if I want". So with models of ZFC, "more" is not necessarily "better" (or "truer"), and I'm not convinced, philosophically speaking, that ω₁ can be made as large as you want it to be.

As far as this Wikipedia article is concerned, I think it's best to stick to ZFC. You may wish to reformulate some statements to avoid any debatable philosophical implications (though I think the term "nonsense" is needlessly aggressive), and I'd agree with that as long as the reformulation doesn't make them sound too clumsy or artificial. For the truly philosophical questions, I think this is an interesting debate in the philosophy of mathematics, but it should probably go in research articles. --Gro-Tsen (talk) 10:06, 5 November 2009 (UTC)

(deindent) That's more or less what I was saying, except said slightly differently.

Why am I bringing this up here?: The reason is to protect this page from deletion or weakening. "Large countable ordinals" are the central object of study in proof theory, the source of new arithmetical theorems. It is important for editors to avoid making the claim that these ordinals are somehow small, or easy to understand, since understanding the structure of all of these ordinals is probably as difficult as solving the halting problem. Further, large countable ordinals are sufficient to model any universe, including that of ZFC and the hugest large cardinals anyone has ever imagined, so it is philosophically consistent to consider these objects as the biggest mathematical objects there are.

The lead already says that large countable ordinals are smaller than uncountable ordinals, and smaller than large cardinals, and pretends that this is an objective statement, not just a theorem of ZFC. That should be changed to something like "A Platonist would say that large countable ordinals are smaller than omega-1, and much smaller than large cardinals, although within countable models of set theory, this statement is clearly not objectively true". This will avoid giving readers the impression that these ordinals are somehow unimportant, or that adding uncountable ordinals is in some way a generalization.

Why should some philsophical comments be made?: The main reason is that there is a Platonist dogma in mathematics which is imposed on everybody, even though many working professionals have a more nuanced view. This makes it very difficult for some people to take mathematicians seriously, since they often make statements like: R can be well ordered, function spaces have a finite-additivity basis, non-measurable sets exist, etc. These theorems are false in that it is completely consistent (and more intuitive) to believe their negation. But many mathematicians insist to students that you have to believe in these absurd lies in order to pass to systems which are sufficiently strong.

But these old hoary issues were completely sorted out in the 1960s, but set theorists have lousy PR, and they haven't bothered to tell the rest of the world. The main insight is that Hilbert's program works exactly as planned, except that the finitistic discrete objects you need to establish consistency of infinite set theory are not just the integers as described by PA, but the "large countable ordinals". Since Hilbert's program (probably) works, you don't have to drink the Platonist kool-aid to accept the consistency of ZFC, or of any large cardinals.

Philosophical comments: An "uncountable ordinal" is already an unfinished process (as you say), because the ordinals we can actually work with and give bounds on are all countable. So that omega-1 should be thought of as collapsed onto some large countable ordinal in whatever countable transitive model you have in mind for ZFC. In this way, the class of ordinals which ZFC claims to reveal is actually much larger than the class of ordinals that you need in order to get all the computationally verifiable results of ZFC. This formalist position is not new, I think that many working logicians or set-theorists hold it implicitly. Paul Cohen held a similar, although not identical, view.

This position moots many questions, like "how big is R as an ordinal?". That question is obviously undecidable if all ordinals are secretly countable. The answer obviously depends on exactly what countable process you use to produce the real numbers while generating a model for ZFC. All of the questions which are shown undecidable by forcing methods are similarly moot.

Mathematical comments: do the uncountable ordinals "stabilize" with large cardinal axioms? If by stabilize you mean "all questions which can be asked in the language of ZFC become answerable", the answer is obviously no, because even the most elementary question "is omega-1 equal cardinality with the powerset of Z" never stabilizes. But I think that you meant that all questions which relate the ordinals to each other stabilize, meaning that any question that you ask about the relationship of omega-1 with, say, omega-(omega-1) will stabilize. I think that the answer to this question is also no

Why not the Church-Kleene ordinal? The honest reason is that CK ordinal is about a different question--- that of strict constructiveness. I am trying to make clear a much simpler question, namely "Do I have to take the enormous sets in ZFC like powerset of powerset of powerset of Z seriously?".

You are right that the more constructive place to put the cut-off for absoluteness is not at omega-1, but at Church-Kleene. But there's an issue: is CK still the uppermost ordinal when a computer has a genuine random number generator? Whatever the random computation ordinal, I agree that it is natural to place the cut off for absoluteness there. It might be the CK ordinal again.Likebox (talk) 06:09, 6 November 2009 (UTC)

"A Platonist would say that large countable ordinals are smaller than omega-1, and much smaller than large cardinals, although within countable models of set theory, this statement is clearly not objectively true"

If the set theory is strong enough to prove that countable sets are smaller than uncountable sets, then even within its countable models, the statement is still objectively true.

"since they often make statements like: R can be well ordered, function spaces have a finite-additivity basis, non-measurable sets exist, etc"

Go ZF+AD !

76.94.202.208 (talk) 20:14, 8 September 2010 (UTC)

Brief couple of comments.

"there is a Platonist dogma in mathematics which is imposed on everybody"

I think you are reading a Platonist interpretation into formal statements where no interpretation is being provided, much less 'imposed on everybody'.

"Do I have to take the enormous sets in ZFC like powerset of powerset of powerset of Z seriously?"

What does 'take seriously' mean? Should we be unable to discuss the idea of "all possible functions taking sequences of integers to integers", or perhaps, each time we discuss the concept we should be required to add a disclaimer stating, "please note this thing we're about to discuss might not 'exist'"? I think there is an irony here: it feels to me like an attempt to phrase things so carefully as to avoid suggesting any Platonist interpretation may in fact be adding Platonist connotations where there were none to begin with.TricksterWolf (talk) 15:07, 4 June 2021 (UTC)

All ordinals are definable

Consider that there is some undefinable ordinal less than ω₁. Then, obviously, there exists non-empty set of undefinable ordinals less than ω₁. As every set in class of ordinals is well ordered (here we consider ordinals up to ω₁), there exists least element of set of undefinable ordinals. Recall that this set is definable. But now we can define least element of this set. Because we considered that it contains only undefinable ordinals, we got contradiction. Then there is no smallest undefinable ordinal and (from well order properties) no undefinable ordinals at all. On the other hand, there is uncountably many ordinals smaller than ω₁, and only countably many definitions, so there is more ordinals than definitions. So there must be some undefinable ordinal. But this statement was just disproved. What is wrong with all these statements? Which of them are wrong? Wojowu (talk) 17:27, 5 May 2012 (UTC)

Whether an ordinal is definable (in the true universe V) is not describable by any formula of ZFC set theory. So one cannot form the set of undefinable subsets of ω₁ using the axiom of separation. Thus one cannot define the smallest such ordinal as the least element of that set.

In other words, what you called "obvious" is not so. JRSpriggs (talk) 21:08, 6 May 2012 (UTC)

Questionable assertion about Predicativity

The article contains a questionable assertion, "Likewise, the least-fixed-point operator used in the Veblen hierarchy is not predicative.", which it cites to Nik Weaver's paper "Predicativity beyond Gamma_0". Weaver is a skeptic of the Feferman-Schutte analysis of predicative second-order arithmetic, which places the Feferman-Schutte ordinal Gamma_0 as the upper bound of the predicative ordinals, and his paper instead argues that the bound for predicativity should be placed much lower, because he thinks that the Veblen hierarchy involves impredicative definitions. This viewpoint has pretty much no mainstream acceptance, so I think this sentence may need to be removed, and perhaps even the previous sentence "This definition is impredicative, because it uses the uncountable ordinal Ω, which, in some sense, already uses all the countable ordinals we are trying to construct in its construction.". (I don't know whether this assertion has mainstream acceptability or not, but in any case it would be better to source it to someone other than Weaver.) 69.248.132.69 (talk) 02:55, 8 December 2013 (UTC)

As far as I'm concerned, the word "predicative" is at best a vague convention (ordinals whose definition somehow does not refer to larger ordinals: which, obviously, depends very much on what we mean by "definition") or an ad hoc definition (defined to be exactly ordinals less than Γ₀), and at worse philosophical mumbo-jumbo. I don't even understand what the debate is about (you say Weaver argues that the predicativity bound should be placed lower than Γ₀ whereas his paper is called "predicativity beyond Γ₀"? is that right?), nor do I understand what's magical about Γ₀. So anyway, as far as I'm concerned, you can edit this as you like, and if you can somehow explain to me that predicativity is not a useless or ill-defined notion, all for the better! --Gro-Tsen (talk) 21:42, 8 December 2013 (UTC)

Gro-Tsen, I'd be happy to explain it to you. I don't know your background knowledge, but I assume you're familiar with second-order arithmetic. (If not, you can look at the Wikipedia article). Well, second-order arithmetic has a axiom schema of comprehension which goes as follows: if phi(x) is a formula in the language of second-order arithmetic with one free variable, then there exists a set of all natural numbers x which satisfies phi(x). But the thing is, phi may contain second-order quantifiers, i.e. quantifiers of the form "for all sets" or "there exists a set". So it may quantify over all sets of natural numbers, including the set defined by phi! So the comprehension schema is impredicative. The standard way to fix this impredicativity is through the ramified hierarchy, which splits the comprehension schema into levels, so that we never allow a formula that quantifies over the set defined by itself. The comprehension schema for level 0 sets does not allow any formulas that have second-order quantifiers. The comprehension schema for level 1 sets only allows formulas with quantification over level 0 sets. For any natural number n, the comprehension schema for level n+1 sets only allows formulas with quantification over sets of level n and below. And we don't need to stop at finite levels. For instance, the schema for level omega sets allows quantification over sets of any finite level. And so on, for higher and higher transfinite ordinals.

The question is what ordinals to use. Feferman and Schutte noted that some ordinals are so high that a predicativist might not acknowledge their existence, so we adopt the following procedure: we only make a comprehension schema for level alpha sets if alpha is an ordinal whose existence can be proved using the comprehension schemes for levels less than alpha. (Where proving the existence of an ordinal alpha using second-order arithmetic means that you use Godel numbering to code ordinals using natural numbers, and then you prove that there is no infinite descending chain of ordinals starting from alpha.) So we start with the fact, proven by Gentzen, that first-order Peano arithmetic can prove the existence of every ordinal less than epsilon_0. So we're allowed to make a comprehension schema for every level up to epsilon_0. And then using the comprehension schemes for those levels, we can prove the existence of a bigger ordinals than epsilon_0, and then we construct comprehension schemes corresponding to those bigger ordinals, and then we use that to prove the existence of even bigger ordinals, etc. And if we keep continuing that process, Feferman and Schutte showed that the ordinals we'd ultimately end up with are all the ordinals less than Gamma_0.

Now Nik Weaver argues that some of the principles that Feferman and Schutte used in their reasoning to get up to Gamma_0 are actually impredicative. And he argues that if you allowed the use of those principles, you could actually get ordinals much greater than Gamma_0, which is why he calls his paper "Predicativity beyond Gamma_0". But since he views them as impredicative, he thinks that if you actually did things in a predicative manner, you would get to an ordinal less than Gamma_0. (Note that Weaver says that he doesn't have a different notion of predicativity than Feferman and Schutte, he just thinks they made an error in their analysis.) But the mathematical community rejects Weaver's claims; they don't think that Feferman and Schutte used anything impredicative in their reasoning. Anyway, I removed the two sentences I mentioned. I hope this explanation was helpful. Feel free to ask questions! 69.248.132.69 (talk) 02:45, 17 December 2013 (UTC)

"Countable ordinals larger than this may still be defined, but do not have notations."

This statement is in the lede, but ω₁^CK+1 looks like a notation to me. Perhaps the use of the word 'notation' here should be clarified.

Later on, it is phrased, "there is no hope of precisely “describing” any ordinals from this point on—we can only define them" instead, but even here it is not clear to a layperson. If ω₁^CK+1 is not 'precisely described', then neither is ω₁^CK, so mentioning why ω₁^CK is impossible to 'precisely describe' is kind of important. I'm concerned this concept may not be well-defined (not ω₁^CK, of course, just the description of how it differs notationally).TricksterWolf (talk) 15:13, 4 June 2021 (UTC)

In the first case, "notation" is being used in a specific way here, to mean a particular system of "ordinal notations" — see Kleene's O for our article on it. That probably needs to be clarified.

Your second quote sounds problematic as well but I don't have time at the moment to look into it; maybe later if someone else doesn't get to it. --Trovatore (talk) 16:40, 4 June 2021 (UTC)

See Ordinal notation. To have a notation for an ordinal means, not just to have some arbitrary symbol for it, but to have a system of symbols for an initial segment of the ordinals which includes it as a member. Thus if an ordinal has a notation (in this sense), it must have a recursive (and thus countable) well-ordering on the smaller ordinals. JRSpriggs (talk) 01:14, 5 June 2021 (UTC)

Your third sentence doesn't follow from the second. You could have a "system of symbols" that includes the Kleene ordinal notations, plus ω₁^CK and ω₁^CK+1. It isn't computable, because Kleene's O isn't computable, but your second sentence doesn't mention computability. --Trovatore (talk) 18:45, 6 June 2021 (UTC)

I meant "system" to imply something effective (computable, recursive). JRSpriggs (talk) 23:03, 6 June 2021 (UTC)

Resolve disputes by references to textbooks?

This looks like an article that is much better than many many others and I am grateful for experts in developing it. (Additional material should probably not sit around in talk pages where few will find it if it can be put into the main article, even if its perfect place is not yet known.) It seems the issue should not be as much in coming up with the best title or discussing the writing style, but rather making sure that we are not using wikipedia to invent new terminology if we can reuse terminology from existing published literature, such as refereed articles and textbooks by established experts in proof theory and set theory. Moreover, I believe that it would be useful to insert historical references indicating which results make use of some of particular ordinals and sets of orginals, so that we don't just talk about the fact that an ordinal *can* be defined, but that defining it helps in some other constructions or results (in proof theory or elsewhere). — Preceding unsigned comment added by 80.218.94.164 (talk • contribs) 12:21, 5 June 2021 (UTC)

I think this is in the right direction, but the underlying problem is that this article doesn't have a clear subject matter, or at least not one standardly identified as a separate object of study in sources I'm familiar with. That makes it a little bit original-researchy or original-synthesis-y, even if all the individual facts are sourced.

This I think is the reason that it's hard to find a good name for the article. It's not clear that there should be a Wikipedia article on this exact combination of topics. Possibly the content should be distributed among other articles. --Trovatore (talk) 18:41, 6 June 2021 (UTC)

Maksudov's functions

Even though the functions are described (and perhaps proven by others) to be sophisticated, since the research is self-published it may not be eligible for Wikipedia C7XWiki (talk) 20:08, 11 September 2021 (UTC)

Taranovsky's C probably doesn't reach PTO(Z2)

According to https://apeirology.com/wiki/Taranovsky%27s_ordinal_notations, "the system may not even reach the subsystem of Pi^1_2-comprehension", whatever that means

The page implies it does reach PTO(Z2) TariosGD1618 (talk) 23:29, 13 September 2024 (UTC)

Extension of admissible, recursively inaccessible, recursively hyperinaccessible, ...

"An ordinal that is both admissible and a limit of admissibles is called recursively inaccessible. An ordinal that is both recursively inaccessible and a limit of recursively inaccessibles is called recursively hyperinaccessible." So can we continue to extend this?

$\omega _{\alpha }^{E_{0}}=\omega _{\alpha }^{CK}$ is the $\alpha$-th admissible ordinal if $\alpha$ is a successor ordinal, and a limit of $\alpha$ is a limit ordinal.

$\omega _{\alpha }^{E_{\beta +1}}$ is the $\alpha$-th fixed point of $\alpha \mapsto \omega _{\alpha }^{E_{\beta }}$ if $\alpha$ is a successor ordinal, and a limit of $\alpha$ is a limit ordinal.

$\omega _{\alpha }^{E_{\beta }}$ is the limit of $\omega _{\alpha }^{E_{\gamma }}$ for $\gamma <\beta$ if $\beta$ is a limit ordinal.

By definition, the mapping $\alpha \mapsto \omega _{\alpha }^{E_{\beta }}$ is continuous for all $\beta$, so $\omega _{\alpha }^{E_{\beta +1}}$ is also a fixed point even when $\alpha$ is a limit ordinal. 129.104.241.231 (talk) 22:30, 24 September 2024 (UTC)