(ZF) For every set A we denote with h*(A) the smallest ordinal α for which there is no surjective function from A to α (α is nonzero):

h∗(A) = µα[¬(α ≤∗ A)]. Prove that for every set A it is true that:

  1. h∗(A) ≤ α ⇒ ¬(α ≤∗ A);
  2. h∗(A) is a cardinal number;
  3. h(A) ≤ h∗(A);
  4. If A can be well ordered set, then it follows that h(A) = h∗(A).

Before I start, I have to say that I am a liitle bit confused of the problem itself. The reason is in the notation of h(A). In previous cases, we have named h as a function of choice for A,but here the meaning is different, so I stick to what is written above,since we are in ZF. However,

My ideas are: To use the following

Lemma: .For every set A there exists an ordinal α such that there is no surjective function from A to α: (∀A)(∃α)[¬(α ≤∗ A). /1/ Since we have picked up the smallest such ordinal, I will try to use Transfinite recursion to prove the statement. Namely, Let P(h∗(A),α) be a property defined over all ordinals α in A,satisfying the condition we want. Then:(∃ h∗(A))P(h∗(A),α,u)->(∃ h(A))(P(h(A),α,u) and for every β(β<h(A)->¬(P(h(A),β,u)). This directly proves 1). /2/ Since for every β(β<h*(A)->¬(P(h*(A),β,u)), a.k.a ¬(Limit(β)) and ord(h*(A)) => Nat(h*(A)). But this means card(h*(A)).

To prove (3) I will use the fact that h*(A) is the min cardinal for which there is no surjection. Hence for an arbitrary cardinal number h(A)<h*(A) there is an image with Dom in h(A) and Rng in A.

For (4) I think that the direct application of the Definition for well ordered set which states that : if for every subset A' of A there is a smallest element (<), then A is well ordered. But then since we have assumed that h*(A) is the min cardinal satisfying this and h(A)<h*(A), they should be equal.

I will be extremely thankful if someone help to verify the correctness of my sttempts to solve it. Thank you.


I dislike being so blunt, but so far as I can tell, you are completely lost. Your argument for (1) makes no sense: (1) is not a statement about ordinals in the set $A$. And even if it were, it is not at all clear what $P(h^*(A),\alpha)$ is intended to be. Your argument for (2) is completely incomprehensible. In your argument for (3) you seem to be trying to prove something about ordinals that are known to be less than $h^*(A)$, when in fact you are supposed to be proving that a certain ordinal is less than $h^*(A)$. And your argument for (4) is simply incoherent.

I’m going to do the first three and let you take another crack at the fourth one; spaceisdarkgreen’s comment should at least point you in the right general direction.

(1) Suppose that $h^*(A)\le\alpha$; then the function

$$f:\alpha\to h^*(A):\xi\mapsto\begin{cases} \xi,&\text{if }\xi<h^*(A)\\ 0,&\text{otherwise} \end{cases}$$

is a surjection. If $g:A\to\alpha$ is a surjection, $f\circ g$ is a surjection from $A$ onto $h^*(A)$, contradicting the definition of $h^*(A)$, so there is no surjection of $A$ onto $\alpha$, and therefore $\alpha\not\le^* A$.

(2) Since $h^*(A)$ is an ordinal, there is a cardinal $\kappa\le h^*(A)$ such that there is a bijection $f:\kappa\to h^*(A)$. If $g:A\to\kappa$ is a surjection, then $f\circ g$ is a surjection of $A$ onto $h^*(A)$, which is impossible. Thus, there is no surjection from $A$ onto $\kappa$. By definition $h^*(A)$ is the smallest ordinal that is not a surjective image of $A$, so $h^*(A)\le\kappa$, and hence $h^*(A)=\kappa$ is a cardinal.

(3) Suppose that $h(A)>h^*(A)$; $h(A)$ is the smallest ordinal $\alpha$ such that there is no injection from $\alpha$ into $A$, so there is an injection $f:h^*(A)\to A$. Let $R=\operatorname{ran}f$, so that $f^{-1}$ is a bijection from $R$ to $h^*(A)$. Then the function

$$g:A\to h^*(A):\xi\mapsto\begin{cases} f^{-1}(\xi),&\text{if }\xi\in R\\ 0,&\text{otherwise} \end{cases}$$

is a surjection from $A$ onto $h^*(A)$, which is impossible, and therefore $h(A)\le h^*(A)$. (I am assuming here that $h$ is the Hartogs function; it certainly isn’t a choice function.)

  • $\begingroup$ There is no reason to feel bad saying the true. I am completely aware of my limited knowledge in set theory, but I am quite interested in it. I want to thank you for your time and help, because without it I wold have barely taken the idea of the problem!For the 4th part i came up with: Since WO(A) <=> (h(A)∈A & h*(A) ∈ A -> h(A) ∈ h*(A) || h*(A) ∈ h(A) || h(A) = h*(A) ) & for every subset u of A ( u is not the empty set & u ⊂ A & h(A) ∈ u and h(A) ∩ u= ∅.) But then {h(A)} ⊂ A & h*(A) which is non empty. Absurd. $\endgroup$ – Tiki Jan 8 at 6:40
  • $\begingroup$ @Tiki That is also incomprehensible. Some general advice: 1) write the logical flow of the argument in words rather than chains of logic notation. In general, use symbols sparingly. 2) When you do use symbols, write them in mathjax so it is more readable. 3) If you are lost, try to clarify the underlying concepts, don't just try to force an argument through. Based on what you've written it's clear that you don't understand a lot of things that are required to even begin tackling this problem. For instance even writing down "$h(A)\in A$" in this context is a red flag that something is wrong. $\endgroup$ – spaceisdarkgreen Jan 8 at 18:31
  • $\begingroup$ Thank you so much for the feedback and advice. I will try to go through the theory before working on problems. $\endgroup$ – Tiki Jan 8 at 18:35
  • $\begingroup$ @Tiki No problem. Just to clarify my last comment (and hopefully help more generally), the reason I say $h(A)\in A$ doesn't "make sense" is that what the particular elements of $A$ are don't matter in this setup. The only properties of $A$ that we care about (e.g. what ordinals map injectively into it or surjectively from it) are ones that are preserved when we replace $A$ with any other set that is in one to one correspondence with it. So $A$'s elements don't matter, only its cardinality. $\endgroup$ – spaceisdarkgreen Jan 8 at 19:32
  • $\begingroup$ @Tiki And a good thing to make sure you understand is the structure of the well-ordered cardinals. Any well-ordered set is order-isomorphic to some ordinal, so in one-to-one correspondence with some ordinal $\alpha$. Ten there is some least ordinal $|\alpha|$ that is in one-to-one correspondence with $\alpha$ ($A$'s cardinal number), and some least ordinal $|\alpha|^+>\alpha$ that is not in one-to-one correspondence with it (the successor to $A$'s cardinal number). $h(A)$ and $h^*(A)$ are sort of generalizations of the successor for when $A$ is not necessarily well-ordered. $\endgroup$ – spaceisdarkgreen Jan 8 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.