Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: Hartogs number

Bottom of Page

1 to 34 of 34

  1.  
    • CommentRowNumber1.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 26th 2016

    Added a bit to Hartogs number. Including the curiosity that GCH implies AC. :-)

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeJan 26th 2016

    How are you phrasing the GCH in the absence of AC to make that true? I usually see GCH phrased as something lke 2 ℵ n=ℵ n+12^{\aleph_n} = \aleph_{n+1}, and in the absence of AC usually the ℵ\alephs are only the well-orderable cardinalities; so that doesn’t seem sufficient for your argument which applies GCH to P(P(P(X)))P(P(P(X))) when XX is not known to be well-orderable. Unless I’m missing something?

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 26th 2016
    • (edited Jan 26th 2016)

    Can’t we say ∀ X,Y¬(|X|<|Y|<|PX|)\forall_{X, Y} \neg (|X| \lt |Y| \lt |P X|)? Which is probably more or less what Cantor would have said.

    • CommentRowNumber4.
    • CommentAuthorMike Shulman
    • CommentTimeJan 26th 2016

    How do you get from that to ℵ(X)\aleph(X) being bijective to P(X)P(X), P 2(X)P^2(X), or P 3(X)P^3(X)?

    • CommentRowNumber5.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 26th 2016

    Hm, maybe I unwittingly let trichotomy sneak into my thinking. (The result ZF + GCH implies AC happens to be true, but maybe this route through Hartogs is not really the way to do it.) Let me think on it more (and thanks).

    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 26th 2016
    • (edited Jan 26th 2016)

    Well, here is a more responsible demonstration, which does in fact use the Hartogs numbers. The key result seems to be lemma 3 (page 552).

    • CommentRowNumber7.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 27th 2016
    • (edited Jan 27th 2016)

    Okay, I’ve written up what I think is a tight proof of GCH implies AC at Hartogs number. It’s a rendition of the Gillman article cited in my last comment (I did spot a little oversight in his proof).

    I learned of this fact last night while I was idly leafing through Eric Wofsey’s old blog Ultrawaffle (or whatever he calls it); it’s one of his series “Fun Little Math Problem of the Day”; see here. I think the “little” made me underestimate the amount of argumentation that is actually required, but the proof does wind up being fun (and the statement a little surprising at first, as Gillman says: what could GCH possibly have to do with AC?).

    • CommentRowNumber8.
    • CommentAuthorMike Shulman
    • CommentTimeJan 27th 2016

    Nice, thanks!

    Maybe it’s too late at night, but I need help with the easy exercise that |P|=|2P|{|P|} = {|2P|} if PP is an infinite power set. I can see how to do it if P=P(Y)P=P(Y) where YY is Dedekind-infinite, but in the general case I’m stuck.

    • CommentRowNumber9.
    • CommentAuthorMike Shulman
    • CommentTimeJan 27th 2016

    I do feel like the “recall the GCH” comment merits some more discussion, since it appears to be only this particular way of phrasing GCH that implies AC, right? If we state GCH as 2 ℵ n=ℵ n+12^{\aleph_n} = \aleph_{n+1}, which is equivalent in the presence of AC (and is how the article continuum hypothesis states it), then it doesn’t imply AC.

    • CommentRowNumber10.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 27th 2016

    I can see how to do it if P=P(Y)P=P(Y) where YY is Dedekind-infinite, but in the general case I’m stuck.

    Oh! I may have elided over this point.

    So in ZF with classical logic, there is a distinction between infinite and Dedekind-infinite? I just assumed that in that context, XX infinite is the same as existence of a bijection 1+X≅X1+X \cong X, which is what I had in mind.

    • CommentRowNumber11.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 27th 2016

    As for #9: I don’t know the history, but maybe someone should check on Sierpinski’s article. You again raise an interesting point.

    • CommentRowNumber12.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 27th 2016

    Okay, I just consulted Wikipedia, and yes you’re right that Dedekind-infinite and infinite are distinct in ZF in classical logic. (Live and learn.) However, the patch is easy: just embed YY into a Dedekind-infinite set like ℕ+Y\mathbb{N} + Y, and take the power set XX of that. The proof then goes through. I’ll put the patch in now.

    • CommentRowNumber13.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 27th 2016

    And finally (Mike), I added some remarks to continuum hypothesis to cover the point you brought up in #9. Sierpinski of course uses the stronger form of GCH.

    • CommentRowNumber14.
    • CommentAuthorMike Shulman
    • CommentTimeJan 27th 2016

    Thanks!! Dedekind-infiniteness is definitely an unexpected gotcha: you expect that constructive mathematics may have trouble defining “infinite”, but it’s surprising (to me) that even in ZF there’s some ambiguity left in what you mean by “infinite”.

    Morally, I feel like 2 ℵ n=ℵ n+12^{\aleph_n}=\aleph_{n+1} and ∀X∀Y(|X|≤|Y|≤|P(X)|→|Y|=|X|∨|Y|=|P(X)|\forall X \forall Y ({|X|}\le {|Y|}\le {|P(X)|} \to {|Y|}={|X|}\vee {|Y|}={|P(X)|} ought to have two different names, like “weak GCH” and “strong GCH”. Then the theorem would be that strong GCH is equivalent to the conjunction of weak GCH and AC.

    • CommentRowNumber15.
    • CommentAuthorDavidRoberts
    • CommentTimeJan 27th 2016

    The latter should be ’global CH’, since it applies to all sets, and the traditional ’G(eneralised )CH’ can be saved for the version with only alephs.

    • CommentRowNumber16.
    • CommentAuthorDavidRoberts
    • CommentTimeJan 27th 2016

    Also: is the full strength of ZF even used? The argument looks like it could be done in BZ.

    • CommentRowNumber17.
    • CommentAuthorTodd_Trimble
    • CommentTimeJan 27th 2016
    • (edited Jan 28th 2016)

    As for the nomenclature, I have no strong opinions. I’m fine with implementing the proposed theorem in #14 if agreement is reached.

    I’m pretty sure BZ suffices. Each subset of XX equipped with a well-ordering is uniquely specified by its set of principal ideals or downsets, i.e., an element of PP(X)P P(X). An equivalence class of well-orderings is then a subset of PP(X)P P(X) or an element of PPP(X)P P P(X), so the set of equivalence classes ℵ(X)\aleph(X) is a subset of PPP(X)P P P(X) as advertised. There is no funny business with unbounded quantifiers or replacement that I can see anywhere; everything is locally definable. This is probably worth a remark at Hartogs number.

    • CommentRowNumber18.
    • CommentAuthorMike Shulman
    • CommentTimeJan 31st 2016

    “global” to me implies that the other one would be “local” in some way, which doesn’t seem to be the case.

    • CommentRowNumber19.
    • CommentAuthorDavidRoberts
    • CommentTimeJan 31st 2016

    Localised to alephs? Of course, ’local’ has a fairly established meaning in set theory as well, which is better suited to specific instances of CH at a given set/cardinal.

    • CommentRowNumber20.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 21st 2016

    I added a few more examples (equivalent forms of AC) to Hartogs number, to illustrate the kinds of things you can do with it.

    • CommentRowNumber21.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 10th 2018

    Added the proof that the Hartogs of SS doesn’t inject into SS.

    diff, v19, current

    • CommentRowNumber22.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 24th 2019

    I’ve been looking around and can’t find the following. Given a set XX, a “least” set YY such that XX does not surject onto YY. The Hartogs number Y=ℵ(X)Y=\aleph(X) doesn’t quite work, because it’s a least set such that YY does not inject into XX. With AC, given a surjection X→ℵ(X)X\to \aleph(X), take a section, hence an injection ℵ(X)→X\aleph(X)\to X, which can’t exist. But without AC it’s not clear, let alone without EM.

    The library lost its copy of Practical Foundation of Mathematics, and I suspect something like it could be in there (it is buying another copy).

    • CommentRowNumber23.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 24th 2019
    • (edited Apr 24th 2019)

    Hmm, this MO question tells me that one can have XX surjecting onto ℵ(X)\aleph(X) in the absence of AC. So it would have to be some other type of construction. I was thinking about X=ℕX=\mathbb{N} and ℵ 1\aleph_1, and how constructive the proof is that ℵ 1\aleph_1 has the properties it has, from different points of view. Certainly ℵ 1≰ℵ 0\aleph_1 \nleq \aleph_0 seems ok, but was thinking about the ≤ *\leq^* ordering, which is the one that the diagonal argument uses to show XX is smaller than P(X)P(X).

    • CommentRowNumber24.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 24th 2019

    And this MO question discusses the dual notion

    h *(A)h^*(A) is defined as the least ordinal aa such that there exists no surjection f:B→af \colon B \to a with BB a subset of AA.

    however this uses the well-ordering of ORDORD and seems rather impredicative. For the case of ℕ\mathbb{N} there’s no problem, as the question indicates that h *h^* returns the usual Hartogs number given a well-ordered set, but conceptually it’s messy.

    Maybe something like taking the supremum of all well-orderings of subquotients of my given set? This seems better.

    • CommentRowNumber25.
    • CommentAuthorMike Shulman
    • CommentTimeApr 24th 2019

    How constructive/predicative are you trying to be? LEM (no AC) suffices for ORDORD to be classically well-ordered.

    Taking the supremum of all well-ordered quotients or subquotients does seem an obvious dual of the Hartogs construction, but I haven’t thought about whether it works.

    • CommentRowNumber26.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 24th 2019

    Actually, I found one reference that defines a “surjective Hartogs number” ℵ *(X)\aleph^*(X) of a set xx as being the set of ordinals admitting a surjection from xx. With LEM this would be the same as the set of ordinals that are subquotients, so it’s reasonable. And ℵ(x)≤ℵ *(x)≤ℵ(P(x))\aleph(x)\leq\aleph^*(x)\leq\aleph(P(x)) for all sets, with ℵ(x)=ℵ *(x)\aleph(x)=\aleph^*(x) for well-orderable xx.

    • CommentRowNumber27.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 24th 2019

    To answer your question, Mike, I think I’m after something that would work at least in any topos with nno. Defining the thing shouldn’t be a problem, it’s proving it has the desired properties that makes me pause.

    And something that is more predicative would be good. I mean, what sort of ’cardinals’ can one construct in an arithmetic universe, for instance? Or less ambitiously, in a Π\Pi-pretopos with nno?

    • CommentRowNumber28.
    • CommentAuthorMike Shulman
    • CommentTimeApr 24th 2019

    I expect that that ℵ *(x)\aleph^*(x) gives an ordinal definable in any topos with the property that xx doesn’t surject onto it. However, it’s not clear to me that one will be able to do very much with it beyond that; even the ordinary Hartogs number doesn’t seem to be very useful without LEM, since its defining property is purely negative.

    • CommentRowNumber29.
    • CommentAuthorDavidRoberts
    • CommentTimeApr 24th 2019

    Yes, I was trying to think if we can parallel the diagonal argument a bit more closely, in that given a function ℕ→ℵ *(ℕ)\mathbb{N}\to \aleph^*(\mathbb{N}) we can construct an element not in its image (and analogously for other cases). But the proofs all work by assuming surjectivity, then arriving at a contradiction. The case for the ordinary Hartogs number really does require Choice as well, since it’s possible for a set to surject onto its Hartogs number under the negation of AC.

    • CommentRowNumber30.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 24th 2022

    Clarified the proof of non-existence of an injection from the Hartogs of a set into that set.

    diff, v24, current

    • CommentRowNumber31.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 24th 2022

    Added a proof for a claim in the Properties section.

    diff, v25, current

    • CommentRowNumber32.
    • CommentAuthorDavidRoberts
    • CommentTimeDec 25th 2022

    Assuming the axiom of choice (countable choice and excluded middle are enough), we have ℵ 0 +=ℵ 1\aleph_0^+ = \aleph_1 as a cardinal.

    What’s the definition of ℵ 1\aleph_1 in this context? And presumably ℵ 0 +\aleph_0^+ is the Hartogs number of the natural numbers?

    • CommentRowNumber33.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 25th 2022
    I suspect Toby wrote that, and I can't say what he had in mind with certainty. In particular, I don't know why we would need countable choice here.
    • CommentRowNumber34.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 31st 2023
    • (edited Aug 31st 2023)

    Does anybody know what is meant by the statement that X↦ℵ(X)X \mapsto \aleph(X) is “functorial” on sets? (I suppose you could take the core groupoid on SetSet, and consider ordinals and their isomorphisms as forming an essentially discrete category, but in that case there is not much content to the statement.)

    I suppose the sentiment is that the operation is “structural” (an operation on sets, not numbers) in some sense…

1 to 34 of 34

  1.