# Uncountable well ordered set in $Z^-$ theory.

I want to build an uncountable well-ordered set within the theory $$Z^\textbf-$$. So, I take $$A=\omega$$ (exists by infinity axiom) and define $$W:=\{(X,R)\in\mathcal{P}(A)\times\mathcal{P}(A\times A):\langle X,R\rangle\ \text{is a well-ordered set}\}$$

With this I consider the set $$T:=W/\cong$$ (where $$\cong$$ is isomorphism relation). Note that $$W$$ and $$T$$ are sets by power set axiom. So I define for each equivalence class $$[x],[y]\in T$$ the order

$$[x]\leq_T[y]\Leftrightarrow \text{type}(x, R_x)\leq \text{type}(y,R_y)$$

Here, $$R_x$$ means the order of $$x$$ that make it belongs to $$[x]$$.

So, $$T$$ is well ordered by $$\leq_T$$ and it is uncountable.

Question: I don't pretty sure if I can build $$\leq_ T$$ without replacement axiom. Another doubt is, Can I take the $$R_x$$ without AC?

• What is Z$^-$? (ZF without replacement is just "Z.") Also, "$\le_T$" is the standard symbol for Turing reducibility, so it might be better to use a different symbol here. – Noah Schweber Dec 3 '18 at 23:06
• @NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity. – Gödel Dec 4 '18 at 1:09
• My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $\cong$ is – DanielWainfleet Dec 4 '18 at 2:45
• Another name for Regularity is Foundation – DanielWainfleet Dec 4 '18 at 2:46

## 1 Answer

Hartogs' theorem is provable without Replacement. The trick is to note that the isomorphism with ordinals is really unnecessary.

Instead you want to just look at well-orders modulo order isomorphisms. In fact, one can look at $$\{X\subseteq\mathcal P(A)\mid (X,\subsetneq)\text{ is well-ordered}\}/\cong$$, or in other words, look at the set of chains of subsets of $$A$$ which are well-ordered by $$\subseteq$$, modulo the order-isomorphism relation.

It is not hard to show that this set is both well-ordered, and does not embed into $$A$$. So if $$A=\omega$$, the resulting order type is uncountable by definition.

Note that Replacement was never used here. We never mapped each well-order to its order type as a von Neumann ordinal. We just looked at sets of sets of chains of subsets, with a bunch of Separation.

• It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 \le E_1$, iff, for every $a\in E_0$, there is some $b\in E_1$, with $a\subset b$. – Not Mike Dec 4 '18 at 2:08
• It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint? – Gödel Dec 4 '18 at 22:49
• @Gödel: Given two well-orders, one is isomorphic to an initial segment of the other. – Asaf Karagila Dec 5 '18 at 0:27