# Thread: Hartog's Theorem and the Axiom of Replacement

1. ## Hartog's Theorem and the Axiom of Replacement

I've been given a question asking me to re write our proof of Hartog's theorem highlighting where the Axiom of Replacement is used.

Our proof of Hartog's theorem goes thusly:

Let X be the set of ordinals of well-orderings of subsets of A. Let α be the least ordinal not in X.

Let h(A)={β:β < α}. Then α = ord (h(A)) ∉ X. Suppose we had an injection f:h(A)→ A. Then the image if f is a well ordered subset of A and so its ordinal (which is α) is in X, a contradiction.

Our definition of the Axiom of Replacement is: Let x be any set. Let H be a well-defined operation which assigns sets to members of x. Then there is a set whose members are exactly H(a) for all ax.

I can sort of see how the axiom is used in the second paragraph of Hartog's proof. We need to construct the function H like in the axiom, defining an operation between each (h(A), <) (< is a well order) to α. But it's difficult getting my head round these definitions, so could someone help me out a bit with this?

2. Hi

Let X be the set of ordinals of well-orderings of subsets of A

3. Originally Posted by clic-clac
Hi

Ok, so I guess you mean it's used to prove alpha is actually a set (right?). I'm still struggling to try and formulate the proof for this around the axiom. Sorry to not provide much of an attempt but I've been trying to wrap my brain around this for the last 2 hours or so without moving forward much.

4. Ok your proof is a bit different, I think, from the one I saw; $\displaystyle X$ is first a class of ordinals, which "elements" are the ordinals of a well-ordering of a subset of $\displaystyle A$ (a set). By the way I've seen you use the terminology "ordinal of a well-ordering", I never saw it before, I do as it refers to the only ordinal isomorphic to the well-order considered.

Now, your axioms (ZF) state that, if $\displaystyle A$ is a set, then $\displaystyle \mathcal{P}(A)\times\mathcal{P}(A\times A)$ is a set too. Now you can consider the operation that assigns to $\displaystyle (B,R),$ $\displaystyle B$ a subset of $\displaystyle A$ and $\displaystyle R$ a well-order on it, its ordinal (note that a subset $\displaystyle B$ can generally be well ordered in different ways, that is why $\displaystyle \mathcal{P}(A)$ alone does not work that well; but, well, there are various ways too proceed)

This operation is well-defined (I hope we have the same definition for this) because, given a well order, it has only one ordinal. Therefore the axiom or Replacement tells us that $\displaystyle X$ is a set of ordinals. And that gives also us that there exists a least element that is not in $\displaystyle X$. Can you tell me if you agree with that?

5. Between your post and a friend offering some other advice I've come to:

$\displaystyle h(A) = \{\beta | \beta < \alpha\}$. We have $\displaystyle B \subset A$. If we define an ordinal $\displaystyle \beta$ such that there is an injection from $\displaystyle \beta \rightarrow A$,we have $\displaystyle \beta$ is the image of A. f will be an order isomorphism between $\displaystyle \beta$ and $\displaystyle A$ if we define R as $\displaystyle b_{1}Rb_{2}$ iff $\displaystyle f^{-1}(b_{1}) = f^{-1}(b_{2})$

Now we set C as the subset of well ordering by R on A (C we know is a set like you said). We know from above that for $\displaystyle R \in C$ there is an order isomorphism $\displaystyle \beta$ to B. Now we can think of $\displaystyle H(R,\beta)$ as a function on C, where H iff $\displaystyle \beta$ is order isomorphic to B.

The image of H is $\displaystyle \alpha$ and the axiom of replacement states that the image of H will be a set. So alpha is a set.

It needs some polish but is the right sort of lines to follow?

6. I'm sorry, I don't understand... An $\displaystyle \alpha$ appears in your definition of $\displaystyle H(A).$ Is $\displaystyle \alpha$ the least ordinal not belonging to $\displaystyle X$? In such case, do you agree that $\displaystyle H(A)=\alpha$? Moreover, if alpha is an ordinal, it is also a set, so I don't understand the last sentence.

Assume $\displaystyle \alpha$ is the least ordinal not belonging to $\displaystyle X.$ Then, any ordinal $\displaystyle \beta<\alpha$ injects into $\displaystyle A,$ because it is, by definition of $\displaystyle \alpha,$ isomorphic to some well-ordered subset of $\displaystyle A.$ What we want now, is to prove that $\displaystyle \alpha$ ($\displaystyle =H(A)$) does not inject into $\displaystyle A;$ and you can use here what you wrote: if $\displaystyle \alpha$ injects into $\displaystyle A,$ then you can define a well ordering on the image of $\displaystyle \alpha$ by the injection, which is a subset of $\displaystyle A$ that can be well-ordered isomorphically to $\displaystyle \alpha,$ contradiction (in such case we would have $\displaystyle \alpha\in X$)
Hence $\displaystyle \alpha$ is the least ordinal that does not inject into $\displaystyle A.$

Isn't this what you wanted?