1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Noah Schweber Dec 3 '18 at 23:06
  • $\begingroup$ @NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity. $\endgroup$ – Gödel Dec 4 '18 at 1:09
  • $\begingroup$ My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $\cong$ is $\endgroup$ – DanielWainfleet Dec 4 '18 at 2:45
  • $\begingroup$ Another name for Regularity is Foundation $\endgroup$ – DanielWainfleet Dec 4 '18 at 2:46
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Not Mike Dec 4 '18 at 2:08
  • $\begingroup$ 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? $\endgroup$ – Gödel Dec 4 '18 at 22:49
  • 3
    $\begingroup$ @Gödel: Given two well-orders, one is isomorphic to an initial segment of the other. $\endgroup$ – Asaf Karagila Dec 5 '18 at 0:27

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.