Talk:Cofinality

Incoherent sentence

There is this statement: "Moreover, any cofinal subset of B whose cardinality is equal to the cofinality of B is well-ordered and order isomorphic to its own cardinality." Is this correct? I don't think so... The last part "order isomorphic to its own cardinality." would imply that B is a cardinal?! Anyone? 82.157.131.133 21:21, 30 Mar 2005 (UTC)

Yup, that sentence didn't make sense. I think I have it stated correctly now.--Luke Gustafson 11:05, 22 December 2005 (UTC)

Countable choice needed?

Countable union of countable sets is countable - this requires at least the Countable Axiom of Choice, as far as I know. Correct?

Correct, I added a mention of that.--Luke Gustafson 10:36, 22 December 2005 (UTC)

Why is cf(card(R)) uncountable?

How does the countable union of countable sets help in establishing that cf(card(R)) is uncountable? Without CH we don't know that sets smaller than R are countable - so maybe we can get R with a countable union of uncountable sets which still are smaller than R. --SirJective (84.151.224.202) 23:03, 2 January 2006 (UTC)

It follows from König's Theorem that k < cf(2^k) for any infinite cardinal k, so in particular the cardinality of the continuum has uncountable cofinality. I don't see how the countable union of countable sets is relevant here, and I suspect this is a mistake based on assuming CH (as I've seen mistakes of this nature on Wikipedia before). --Zundark 14:26, 3 January 2006 (UTC)

Thanks for pointing out the proof to me, I agree with your suspicion - assuming CH clearly rules out card(R) = aleph_omega, which was the question I had when I found this page ;). I edited the article accordingly. --SirJective (129.187.111.179) 13:47, 11 January 2006 (UTC)

For any infinite well-orderable cardinal number κ?

Isn't every cardinal well-ordered? In particular, isn't 0 a least element of every cardinal? -lethe ^{talk +} 12:49, 31 January 2006 (UTC)

Hmm... maybe what is meant is not that cardinals need not be well-founded, but rather that they need not be totally ordered. If we don't assume AC, that is. -lethe ^{talk +} 12:51, 31 January 2006 (UTC)

By a "well-orderable cardinal", it means a cardinal k such that any set of cardinality k can be well-ordered. This is true of all cardinals, of course, but the proof requires AC. (As with many articles, this one is a mess as regards AC - sometimes mentioning when it is needed, and at other times silently assuming it.) --Zundark

Yeah, I was thinking of cardinals as some least ordinal, and well ordering of ordinals is built into their definitions. But of course, that definition of cardinals relies on AC. And the proof of well ordering in the general case also requires AC. I knew that stuff, but the reason I was momentarily confused was because well-ordering really means two things: least element, and totalness of ordering. I somehow thought that sentence meant that you need AC to prove every cardinal has a least element, which is certainly not true. But I was just being dumb. Anyway, thanks for the clarification. -lethe ^{talk +} 14:30, 31 January 2006 (UTC)

every limit cardinal is singular

The article says: "one can prove that for a limit ordinal δ $\mathrm {cf} (\aleph _{\delta })=\mathrm {cf} (\delta )$". But I have a problem: ℵ_δ is a limit cardinal iff δ is a limit ordinal. And I think ℵ_δ is always greater than δ, while cf(δ) ≤ δ. Therefore, this statement implies that no inaccessible cardinal exists. Somethings not right. Or am I mucking it up? -lethe ^{talk +} 08:51, 1 February 2006 (UTC)

Hmm.. let's go through that a little more carefully. Let δ be a limit ordinal. Then ℵ_δ is a limit cardinal. Then, according to the article, cf(ℵ_δ) = cf(δ). cf(δ) ≤ δ, so cf(ℵ_δ) ≤ δ. If ℵ_δ is regular, then we have ℵ_δ ≤ δ. But I claim that ℵ_λ is strictly greater than λ, for all λ.

For a successor ordinal λ+1, ℵ_λ+1 = union {all ords of cardinality ℵ_λ} ≥ ℵ_λ > λ (this last by inductive assumption). Since ℵ_λ+1 ≥ λ, it must also be greater than λ+1, since ℵ_λ+1 is a limit ordinal, ℵ_λ+1 > λ ==> ℵ_λ+1 > λ+1.

Now if λ is a limit ordinal, ℵ_λ = union {ℵ_κ: κ<λ} > union {κ: κ<λ} = λ.

OK, I think that might be a problem. I use the fact that if ℵ_κ > κ for all κ<λ (inductive hypothesis), then I can take the union of both sides and have union {ℵ_κ: κ<λ} > union {κ: κ<λ}. But that operation probably isn't valid. For instance, n+1 > n for all finite n, but if you take the union, you get ω > ω.

So maybe it's possible to have ℵ_λ = λ if λ is a limit ordinal? Maybe this equality will hold for the inaccessible cardinals? -lethe ^{talk +} 09:38, 1 February 2006 (UTC)

There are many ordinals $\delta$ for which $\delta =\aleph _{\delta }$. For example, let $\kappa _{0}$ be any cardinal number, and for each positive integer $n$ let $\kappa _{n}=\aleph _{\kappa _{n-1}}$, then let $\delta$ be the supremum of all the $\kappa _{n}$. --Zundark 09:42, 1 February 2006 (UTC)

Wow. Easy enough to see, but still surprising. I added a section about aleph fixed points to aleph number. Since I'm a newbie to the topic, maybe you can just glance it over? Thanks again for your help. -lethe ^{talk +} 10:54, 1 February 2006 (UTC)

decipherability of unicode aleph symbol

You-all are using a character (in "think ℵ_δ") which just looks like a square-box to me. And I do not think that my browser is defective. Why? If it is supposed to be an $\aleph$, then you should use <math>\aleph</math> to create it. JRSpriggs 12:25, 19 March 2006 (UTC)

It's not that your browser is defective, but rather that your system doesn't have a unicode enabled font with that symbol. As far as using math tags, I never use math tags for inline math text. I'm fighting hard not to revert your changes, I've seen others do the same revert. But I try to remind myself that not everyone has a capable computer. Please do consider getting some unicode fonts though. -lethe ^{talk +} 14:06, 19 March 2006 (UTC)

Even if I can find a better unicode font than I have or get a Hebrew language package, that would only solve the problem for ME. Surely there are many other readers out there who only see square boxes when you-all use those characters. JRSpriggs 07:18, 21 March 2006 (UTC)

It has a codepoint of x2135, part of the block of "letterlike symbols". This is a different glyph from the Hebrew letter. But anyway, if you don't have it, you don't have it. I didn't revert you, but I don't agree with your argument. If we insist on everything being readable in every single browser, we'll never be able to move forward. -lethe ^{talk +} 08:18, 21 March 2006 (UTC)

For what it's worth, I use IE 6 SP 2, and Firefox 1.5.0.1, and I see the "you don't have this character" box in IE, but I see the aleph-lookalike glyph in Firefox. I hypothesize that it's so much a font thing, since both programs surely access the same pool of fonts, as a browser thing.151.200.185.98 02:32, 22 March 2006 (UTC)

Like the user at 151.200.whatever (who is probably my nephew Edward), I could not read the small alephs in Internet Explorer, but now that I am using Firefox (without any change in fonts), they are clear. JRSpriggs 09:02, 25 March 2006 (UTC)

I guess I was wrong about this being a unicode font issue. I guess the real issue is that Internet Explorer is broken. I don't like making Wikipedia (or the web in general) cater to the bugs of Microsoft, but it's unrealistic to expect to be able to not support IE when it constitutes 90% of the market or whatever. It's unreasonable to tell everyone who wants to view wikipedia to get a different web browser, right? -lethe ^{talk +} 09:22, 25 March 2006 (UTC)

Yes, I feel that we must support IE by avoiding the use of those small alephs. Now that I have down-loaded Firefox, I checked that the characters which I replaced were in fact alephs, which they were as I had inferred from the context. JRSpriggs 10:33, 26 March 2006 (UTC)

I've reorganized the article a bit

I've reorganized the article a bit. I moved the definition of regular and singular into the lead. I added some content to the "Examples" section (please double check my additions), and moved that section to follow immediately after the lead (I think it helps to have examples as soon as possible). And I titled the remaining content "Properties". Comments? Paul August ☎ 16:51, 21 February 2006 (UTC)

New section on cofinality of well-ordered sets

This section was copied with minor changes from the Wikipedia article on ordinal numbers. JRSpriggs 07:48, 18 March 2006 (UTC)

Error in Properties?

The second sentence, "Moreover, any cofinal subset of B whose cardinality is equal to the cofinality of B is well-ordered, and these sets are all order isomorphic.", in the section "Properties" seems (to me) to be incorrect. Let us take B to be the Integers with the usual order. Their cardinality is aleph-null. And so is the cardinality of the obvious co-final subset which is the natural numbers (which are well-ordered). But one could also choose the cofinal subset to be the integers themselves (after all, B is cofinal in itself, right?), since they also have cardinality aleph-null which is the cofinality. And the integers are not well-ordered, contrary to the sentence. Also the integers are not order-isomorhpic to the natural numbers, again contrary to the sentence. JRSpriggs 12:16, 19 March 2006 (UTC)

OK. I see that I was failing to read the second sentence in the context of the first sentence, "If A admits a totally ordered cofinal subset, then we can find a subset B which is well-ordered and cofinal in A.", which says that that B is well-ordered. So the integers would not be a counter-example, since they are not well-ordered. Still, the second sentence is hard to understand. Could it be expanded to make it clearer? JRSpriggs 07:13, 21 March 2006 (UTC)

Merge "cofinal" with "cofinality"?

about merging cofinality with cofinal (mathematics), I say absolutely. support. -lethe ^{talk +} 20:30, 6 July 2006 (UTC)

I have removed the overlap between cofinality and cofinal (mathematics). Now I am not sure about the merge anymore. I think that enough could be said about the properties of cofinal subsets to justify separate articles. --Tobias Bergemann 20:48, 6 July 2006 (UTC)

I'm a bit of a mergist by heart. So whether or not we could fit them logically into separate articles is not as relevant to me as whether a single merged article would be too long. I think the answer to the latter question is "no", and hence I support the merger. I also note that having separate articles for the noun and the adjective is a bad policy. But your point is taken, when we use the word "cofinality" we are usually talking about only a least cardinality (and only apropos a cardinal number), where as with the word "cofinal" we may talk about any set inside any poset. The latter usage is different. I still say merge though. But let's hear what others think as well. -lethe ^{talk +} 21:24, 6 July 2006 (UTC)

If we do not merge, then I think that "Cofinal (mathematics)" should be renamed "Cofinal subset". JRSpriggs 06:47, 7 July 2006 (UTC)

I agree. — Tobias Bergemann 07:45, 7 July 2006 (UTC)

I'm not necessarily against a merge, but if they're merged I feel strongly that the article should be at cofinality, which is the more used concept. --Trovatore 14:57, 7 July 2006 (UTC)

Merge "regular cardinal" into "cofinality"?

Right now there is a certain asymmetry between the content on regular cardinals and regular ordinals: regular ordinal redirects to cofinality while regular cardinal has its own (very short) article. Maybe regular cardinal should be merged into cofinality. — Tobias Bergemann 11:49, 7 July 2006 (UTC)

No, I think regular cardinal should be expanded, and regular ordinal should redirect there. There's a lot to be said about regular cardinals that goes far beyond their cofinality. --Trovatore 14:58, 7 July 2006 (UTC)

Is this right?

"This definition of cofinality relies on the axiom of choice, as it uses the fact that every non-empty set of cardinal numbers has a least member." - This is a way to avoid the axiom of choice.

From Axiom of choice:

For certain infinite sets X, it is also possible to avoid the axiom of choice. For example, suppose that the elements of X are sets of natural numbers. Every nonempty set of natural numbers has a least element, so to specify our choice function we can simply say that it takes each set to the least element of that set. This gives us a definite choice of an element from each set and we can write down an explicit expression that tells us what value our choice function takes. Any time it is possible to specify such an explicit choice, the axiom of choice is unnecessary.

—Preceding unsigned comment added by Drysh (talk • contribs)

What is your method of making an "explicit choice" and so avoiding the axiom of choice? JRSpriggs 02:45, 17 August 2006 (UTC)

IMHO it should be changed to: "This definition of cofinality avoids using the axiom of choice, as it relies on the fact that every non-empty set of cardinal numbers has a least number." - The first emplies it uses the axiom of choice, but actualy it avoids using it because you are making an explicit choice. - Drysh 19:00, 17 August 2006 (UTC)

No, it relies on the Axiom of Choice. The explicit choice is the choice of the least member of a non-empty set of cardinals. You are right that we don't need the Axiom of Choice to pick this least member if it exists. The trouble is that without the Axiom of Choice it may not exist. --Zundark 20:09, 17 August 2006 (UTC)

As a matter of fact, quoting axiom of choice again, "Trichotomy: If two sets are given, then they either have the same cardinality, or one has a smaller cardinality than the other." is one of the theorems which are equivalent to the axiom. In other words, without the axiom there are pairs of cardinal numbers which are incomparable -- neither is smaller than the other nor are they the same. JRSpriggs 03:48, 18 August 2006 (UTC)

This depends on your definition of a cardinal. You can define cardinals such that cardinals are well-ordered independent of choice, but the drawback is that it is then possible to have sets with undefined cardinality. —Preceding unsigned comment added by 24.196.91.135 (talk) 00:11, 13 July 2010 (UTC)

Arithmetics of cofinality

Are there any rules to compute the cofinality of the sum, product or power of ordinals? For example, what is the cofinality of $\omega ^{\omega +42}+\omega ^{2}+\omega \cdot 3\,$? Albmont (talk) 20:25, 3 April 2009 (UTC)

Yes. One uses the fact that the binary operations of ordinal arithmetic are continuous and strictly increasing in the right argument. Thus the cofinality of $\omega ^{\omega +42}+\omega ^{2}+\omega \cdot 3\,$ is the same as the cofinality of $\omega \cdot 3=\omega +\omega +\omega \,$ which is the same as the cofinality of $\omega \,$ which is just $\omega \,$ itself.

However, if the right argument is zero or a successor (such as the "3" in your example), then this does not work because continuous functions are λ-continuous for any infinite regular ordinal λ, but neither 0-continuous nor 1-continuous in general. (But multiplication is 0-continuous; and addition is 1-continuous.) JRSpriggs (talk) 05:40, 4 April 2009 (UTC)

Relying on axiom of choice

It is written : "This definition of cofinality relies on the axiom of choice, as it uses the fact that every non-empty set of cardinal numbers has a least member" Isn't it always true by the well ordering of the ordinals that every set of ordinals has a minimum ? Why do one need the axiom of choice for that ? — Preceding unsigned comment added by 79.182.240.117 (talk) 16:30, 30 June 2012 (UTC)

Without the axiom of choice there are non-wellorderable sets. Their cardinal numbers do not have initial ordinals. So you cannot sort them that way, JRSpriggs (talk) 20:00, 30 June 2012 (UTC)

Wording

Does this have excess words>

cf(κ) = the cardinality of the smallest collection of sets of strictly smaller cardinals such that their sum is κ

Why do we need 'sets of' in there?

173.25.54.191 (talk) 22:03, 13 March 2014 (UTC)

• Agreed, "sets of" seems superfluous. Also, the '=' should be replaced by 'is'.

Least vs. infimum

In the section "Cofinality of cardinals", the text says "cf(κ) = the cardinality of the smallest collection of sets of strictly smaller cardinals whose sum is κ". But the equation directly following it defines it as the infimum, i.e. a greatest lower bound rather than the least element from the set. Which is true? If they are always the same due to properties of cardinalities, it is better to use "min" than "inf", since "inf" implies that a limit must be taken whereas "min" just picks the smallest element, which is then assumed to exist. If they are not the same, then I believe the textual definition should be corrected to use the infimum.212.242.115.68 (talk) 15:02, 12 November 2014 (UTC)

The second paragraph of the lead includes "... the axiom of choice is assumed ... in the rest of this article ...". Consequently, the cardinal numbers are a subclass of the ordinal numbers and thus well-ordered. The infimum of any nonempty subclass of a well-ordered class exists and is a member of the subclass. So "infimum" and "minimum" mean the same thing in this case. JRSpriggs (talk) 09:01, 13 November 2014 (UTC)

Thank you for clarifying that! Suggest, then, to change "inf" to "min", since "inf" implies a more complicated operation (which in this case ends up just yielding the minimum). 130.225.98.243 (talk) 14:11, 13 November 2014 (UTC)