Recently in chat, we investigated the explicit construction of $\omega_1$. Regardless on whether we use ZFC or hartogs number, we seemed to hit a roadblock.

Using either ZFC or hartogs number, we managed to came up a set of countable ordinals $S$ that corresponds to well orderings on $\omega$. However, other than its existence, there seemed to be no algorithmic way to describe that well ordering in more detail

(for example, some explicit but not necessary computable predicate P(x,y) such that given any pair (x,y) it unambiguously give either true or false to the question x < y, that is, $P(x,y)$ is not of the form "There exists a well ordering...")

therefore cannot show that $S$ is well ordered and hence $\omega_1$ cannot be shown to exist by construction.

  1. Is there exists a predicative well ordering of an uncountable set $S$ which the injection $\omega \to S$ can be constructed without first assuming $S$ can be well ordered without the axiom of choice (and possibly without excluded middle)?
  2. If there is, what is $P$, that is, the criteria on how exactly any given countable well orderings are well ordered within $S$?
  • 1
    $\begingroup$ We can't. But some elements of it can be well-ordered, and at least one of those is order isomorphic to $\omega_1$. $\endgroup$ – Arthur Oct 6 '17 at 16:16
  • 1
    $\begingroup$ @user21820 I use the rationals because the construction is more human readable and uses the standard total ordering on the rationals for all its worth. One could use any countably infinite set, but it wouldn't be as transparent. $\endgroup$ – Arthur Oct 6 '17 at 16:19
  • 1
    $\begingroup$ Oh, and I made a mistake. There is a subset of $P(P(\Bbb Q))$ which is well-orderable and order isomorphic to $\omega_1$. $\endgroup$ – Arthur Oct 6 '17 at 16:22
  • 1
    $\begingroup$ If you can prove that any predicative function applied to a countable ordinal generates a countable ordinal, then the answer is obviously not. Since $\omega_1$ is regular (at least assuming some bits of choice), any countable-to-countable function on ordinals would require $\omega_1$ iterations to reach $\omega_1$, which is exactly what being impredicative is all about. $\endgroup$ – Asaf Karagila Oct 25 '17 at 9:44
  • 1
    $\begingroup$ $\aleph_1$ and $\omega_1$ are the same object. The former is used to hint "we are talking about cardinals and cardinal arithmetic" and the latter denotes "we are talking about ordinals and order types". So $\aleph_1+\aleph_0=\aleph_1$, but $\omega_1+\omega\neq\omega_1$. Now. It is indeed consistent with ZF that $\omega_1$ is singular and thus the countable union of countable sets. But again, as far as predicativity, you would need to somehow argue that you can find a countable cofinal sequence which is obtained by iterating some predicative construction in a predicative way. [...] $\endgroup$ – Asaf Karagila Oct 25 '17 at 11:10

Your Answer

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

Browse other questions tagged or ask your own question.