4
$\begingroup$

Does there exist a function $f$ that satisfies all of the following three properties?

  1. The function converts an arbitrarily large (empty, finite, countably/uncountably infinite) set of ordinals to a single ordinal;
  2. If two sets $S$ and $T$ of ordinals are not equal, then two ordinals $f(S)$ and $f(T)$ are not equal; if two ordinals $\alpha$ and $\beta$ are not equal, then two sets $f^{-1}(\alpha)$ and $f^{-1}(\beta)$ are not equal;
  3. The function and its inverse are computable by Ordinal Turing Machines, i.e. there exists an Ordinal Turing Machine $m$ that (i) given an arbitrary set $T$ of ordinals as the input, outputs a single ordinal $f(T)$; (ii) given a single ordinal $\alpha$ as the input, outputs a set $f^{-1}(\alpha)$ of ordinals.
$\endgroup$
1
  • 1
    $\begingroup$ This is kind of self-evident in the case of $V=L$ (unless I am misreading the question), because it would follow from equivalence of SO (sets of ordinals) in $L$ and those that are ordinal computable by (some suitable) ordinal parameters . But for the general scenario, it is unclear to me. $\endgroup$
    – SSequence
    Jun 28, 2022 at 9:44

1 Answer 1

7
$\begingroup$

The existence of a function $f$ as specified in the question cannot be proved in ZFC. This follows from the following theorem and the well-known independence of $\mathrm{V = OD}$ (equivalently: $\mathrm{V = HOD}$) from $\mathrm{ZFC}$. Recall that $\mathrm{OD}$ is the class of ordinal-definable sets.

Theorem. (ZFC) There is a (parameter-free) definable injective function $f$ from the class of subsets of ordinals to the class of ordinals (i.e., a definable function $f$ satisfying properties (1) and (2) of the question) if and only if $\mathrm{V = OD}$.

Proof. The right-to-left direction readily follows from the well-known fact that there is a (parameter-free) global well-ordering of the class of all sets $\mathrm{V}$ of order-type $\mathrm{Ord}$ (class of ordinals) in the presence of $\mathrm{ZF + V = OD}$.

For the other direction, recall that it is a theorem of $\mathrm{ZFC}$ that every set can be canonically coded by a subset of ordinals (more precisely, for every set $x$ there is a subset $y$ of ordinals such that $x \in \mathrm{L}(y)$). This makes it clear that if there is a definable injection $f$ of the class of subsets of ordinal into the class $\mathrm{Ord}$ of ordinals, then there is an injection $F$ of the class of all sets $\mathrm{V}$ to $\mathrm{Ord}$. More specifically, given a set $x$, let $F(x)$ be $f(y_0)$, where $f(y_0)$ is the minimum element of the set of all ordinals of the form $f(y)$, where $y$ canonically codes $x$. Since $\mathrm{V=OD}$ is equivalent to the existence of a parameter-free definable injection of $\mathrm{V}$ into $\mathrm{Ord}$, this completes the proof.

$\endgroup$

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.