Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Cofinality
open-in-new
<h2 id="examples">Examples</h2> <ul><li>The cofinality of a partially ordered set with <a href="/facts/Greatest_element/JVn2B3mo">greatest element</a> is 1 as the set consisting only of the greatest element is cofinal (and must be contained in every other cofinal subset). <ul><li>In particular, the cofinality of any nonzero finite ordinal, or indeed any finite directed set, is 1, since such sets have a greatest element.</li></ul></li> <li>Every cofinal subset of a partially ordered set must contain all <a href="/facts/Maximal_element/7FCC9qAW">maximal elements</a> of that set. Thus the cofinality of a finite partially ordered set is equal to the number of its maximal elements. <ul><li>In particular, let A {\displaystyle A} be a set of size n , {\displaystyle n,} and consider the set of subsets of A {\displaystyle A} containing no more than m {\displaystyle m} elements. This is partially ordered under inclusion and the subsets with m {\displaystyle m} elements are maximal. Thus the cofinality of this poset is n {\displaystyle n} <a href="/facts/Binomial_coefficient/Tsx7eY5h">choose</a> m . {\displaystyle m.} </li></ul></li> <li>A subset of the <a href="/facts/Natural_number/u65og8JE">natural numbers</a> N {\displaystyle \mathbb {N} } is cofinal in N {\displaystyle \mathbb {N} } if and only if it is infinite, and therefore the cofinality of ℵ 0 {\displaystyle \aleph _{0}} is ℵ 0 . {\displaystyle \aleph _{0}.} Thus ℵ 0 {\displaystyle \aleph _{0}} is a <a href="/facts/Regular_cardinal/wrGvPz2c">regular cardinal</a>.</li> <li>The cofinality of the <a href="/facts/Real_number/R02gw5Pb">real numbers</a> with their usual ordering is ℵ 0 , {\displaystyle \aleph _{0},} since N {\displaystyle \mathbb {N} } is cofinal in R . {\displaystyle \mathbb {R} .} The usual ordering of R {\displaystyle \mathbb {R} } is not <a href="/facts/Order_isomorphic/PwpVTjW5">order isomorphic</a> to c , {\displaystyle c,} the <a href="/facts/Cardinality_of_the_continuum/ob578Q9l">cardinality of the real numbers</a>, which has cofinality strictly greater than ℵ 0 . {\displaystyle \aleph _{0}.} This demonstrates that the cofinality depends on the order; different orders on the same set may have different cofinality.</li></ul> <h2 id="properties">Properties</h2> <p>If A {\displaystyle A} admits a <a href="/facts/Total_order/xnTtmuYJ">totally ordered</a> cofinal subset, then we can find a subset B {\displaystyle B} that is well-ordered and cofinal in A . {\displaystyle A.} Any subset of B {\displaystyle B} is also well-ordered. Two cofinal subsets of B {\displaystyle B} with minimal cardinality (that is, their cardinality is the cofinality of B {\displaystyle B} ) need not be order isomorphic (for example if B = ω + ω , {\displaystyle B=\omega +\omega ,} then both ω + ω {\displaystyle \omega +\omega } and { ω + n : n < ω } {\displaystyle \{\omega +n:n<\omega \}} viewed as subsets of B {\displaystyle B} have the countable cardinality of the cofinality of B {\displaystyle B} but are not order isomorphic). But cofinal subsets of B {\displaystyle B} with minimal order type will be order isomorphic. </p> <h2 id="cofinality-of-ordinals-and-other-well-ordered-sets">Cofinality of ordinals and other well-ordered sets</h2> <p>The cofinality of an ordinal α {\displaystyle \alpha } is the smallest ordinal δ {\displaystyle \delta } that is the <a href="/facts/Order_type/koXjnax6">order type</a> of a <a href="/facts/Cofinal_subset/l5Hoqx3o">cofinal subset</a> of α . {\displaystyle \alpha .} The cofinality of a set of ordinals or any other <a href="/facts/Well-ordered_set/GrWEBWlW">well-ordered set</a> is the cofinality of the order type of that set. </p><p>Thus for a <a href="/facts/Limit_ordinal/jPCCoPuP">limit ordinal</a> α , {\displaystyle \alpha ,} there exists a δ {\displaystyle \delta } -indexed strictly increasing sequence with limit α . {\displaystyle \alpha .} For example, the cofinality of ω 2 {\displaystyle \omega ^{2}} is ω , {\displaystyle \omega ,} because the sequence ω ⋅ m {\displaystyle \omega \cdot m} (where m {\displaystyle m} ranges over the natural numbers) tends to ω 2 ; {\displaystyle \omega ^{2};} but, more generally, any countable limit ordinal has cofinality ω . {\displaystyle \omega .} An uncountable limit ordinal may have either cofinality ω {\displaystyle \omega } as does ω ω {\displaystyle \omega _{\omega }} or an uncountable cofinality. </p><p>The cofinality of 0 is 0. The cofinality of any <a href="/facts/Successor_ordinal/k2acCuUG">successor ordinal</a> is 1. The cofinality of any nonzero limit ordinal is an infinite regular cardinal. </p> <h2 id="regular-and-singular-ordinals">Regular and singular ordinals</h2> <p class="note">Main article: <a href="/facts/Regular_cardinal/wrGvPz2c">Regular cardinal</a></p> <p>A regular ordinal is an ordinal that is equal to its cofinality. A singular ordinal is any ordinal that is not regular. </p><p>Every regular ordinal is the <a href="/facts/Initial_ordinal/EHFlKG96">initial ordinal</a> of a cardinal. Any limit of regular ordinals is a limit of initial ordinals and thus is also initial but need not be regular. Assuming the axiom of choice, ω α + 1 {\displaystyle \omega _{\alpha +1}} is regular for each α . {\displaystyle \alpha .} In this case, the ordinals 0 , 1 , ω , ω 1 , {\displaystyle 0,1,\omega ,\omega _{1},} and ω 2 {\displaystyle \omega _{2}} are regular, whereas 2 , 3 , ω ω , {\displaystyle 2,3,\omega _{\omega },} and ω ω ⋅ 2 {\displaystyle \omega _{\omega \cdot 2}} are initial ordinals that are not regular. </p><p>The cofinality of any ordinal α {\displaystyle \alpha } is a regular ordinal, that is, the cofinality of the cofinality of α {\displaystyle \alpha } is the same as the cofinality of α . {\displaystyle \alpha .} So the cofinality operation is <a href="/facts/Idempotent/khbSpexv">idempotent</a>. </p> <h2 id="cofinality-of-cardinals">Cofinality of cardinals</h2> <p>If κ {\displaystyle \kappa } is an infinite cardinal number, then cf ( κ ) {\displaystyle \operatorname {cf} (\kappa )} is the least cardinal such that there is an <a href="/facts/Bounded_(set_theory)/TJVtvQAT">unbounded</a> function from cf ( κ ) {\displaystyle \operatorname {cf} (\kappa )} to κ ; {\displaystyle \kappa ;} cf ( κ ) {\displaystyle \operatorname {cf} (\kappa )} is also the cardinality of the smallest set of strictly smaller cardinals whose sum is κ ; {\displaystyle \kappa ;} more precisely cf ( κ ) = min { | I | : κ = ∑ i ∈ I λ i ∧ ∀ i ∈ I : λ i < κ } . {\displaystyle \operatorname {cf} (\kappa )=\min \left\{|I|\ :\ \kappa =\sum _{i\in I}\lambda _{i}\ \land \forall i\in I\colon \lambda _{i}<\kappa \right\}.} </p><p>That the set above is nonempty comes from the fact that κ = ⋃ i ∈ κ { i } {\displaystyle \kappa =\bigcup _{i\in \kappa }\{i\}} that is, the <a href="/facts/Disjoint_union/x9QSfkr5">disjoint union</a> of κ {\displaystyle \kappa } singleton sets. This implies immediately that cf ( κ ) ≤ κ . {\displaystyle \operatorname {cf} (\kappa )\leq \kappa .} The cofinality of any totally ordered set is regular, so cf ( κ ) = cf ( cf ( κ ) ) . {\displaystyle \operatorname {cf} (\kappa )=\operatorname {cf} (\operatorname {cf} (\kappa )).} </p><p>Using <a href="/facts/K%25C3%25B6nig%2527s_theorem_(set_theory)/fUaNe2PK">König's theorem</a>, one can prove κ < κ cf ( κ ) {\displaystyle \kappa <\kappa ^{\operatorname {cf} (\kappa )}} and κ < cf ( 2 κ ) {\displaystyle \kappa <\operatorname {cf} \left(2^{\kappa }\right)} for any infinite cardinal κ . {\displaystyle \kappa .} </p><p>The last inequality implies that the cofinality of the cardinality of the continuum must be uncountable. On the other hand, ℵ ω = ⋃ n < ω ℵ n , {\displaystyle \aleph _{\omega }=\bigcup _{n<\omega }\aleph _{n},} the ordinal number ω being the first infinite ordinal, so that the cofinality of ℵ ω {\displaystyle \aleph _{\omega }} is card(ω) = ℵ 0 . {\displaystyle \aleph _{0}.} (In particular, ℵ ω {\displaystyle \aleph _{\omega }} is singular.) Therefore, 2 ℵ 0 ≠ ℵ ω . {\displaystyle 2^{\aleph _{0}}\neq \aleph _{\omega }.} </p><p>(Compare to the <a href="/facts/Continuum_hypothesis/R0yGqHND">continuum hypothesis</a>, which states 2 ℵ 0 = ℵ 1 . {\displaystyle 2^{\aleph _{0}}=\aleph _{1}.} ) </p><p>Generalizing this argument, one can prove that for a limit ordinal δ {\displaystyle \delta } cf ( ℵ δ ) = cf ( δ ) . {\displaystyle \operatorname {cf} (\aleph _{\delta })=\operatorname {cf} (\delta ).} </p><p>On the other hand, if the <a href="/facts/Axiom_of_choice/1Ura2HTh">axiom of choice</a> holds, then for a successor or zero ordinal δ {\displaystyle \delta } cf ( ℵ δ ) = ℵ δ . {\displaystyle \operatorname {cf} (\aleph _{\delta })=\aleph _{\delta }.} </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Club_set/TJVtvQAT">Club set</a> – Set theory concept</li> <li><a href="/facts/Initial_ordinal/EHFlKG96">Initial ordinal</a> – Mathematical conceptPages displaying short descriptions of redirect targets</li></ul> <ul><li><a href="/facts/Thomas_Jech/E4JQu4Mk">Jech, Thomas</a>, 2003. <i>Set Theory: The Third Millennium Edition, Revised and Expanded</i>. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-44085-2.</li> <li><a href="/facts/Kenneth_Kunen/jbJNPJKV">Kunen, Kenneth</a>, 1980. <i>Set Theory: An Introduction to Independence Proofs</i>. Elsevier. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-86839-9.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Shelah, Saharon (26 November 2002). "Logical Dreams". arXiv:math/0211398. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>