Encode/decode

There’s a very neat way of encoding any set as a set of ordinals, which has the somewhat peculiar feature of it being hard (which here meaning that it requires the axiom of choice) to encode sets, but easy to decode them. Like some kind of a very ineffective crypto-system.

encode_decode

Let’s start out with the encoding process. If we’re given a set X and want to encode it as a set of ordinals, we first “unpack” our set, meaning that we pass to its transitive closure \text{tc}(\{X\}), which is defined recursively as \text{tc}_0(\{X\}):=\{X\},

\text{tc}_{n+1}(\{X\}):=\text{tc}_n(\{X\})\cup\{y\mid\exists x\in\text{tc}_n(\{X\}): y\in x\}

and finally \text{tc}(\{X\}):=\bigcup_{n<\omega}\text{tc}_n(\{X\}). Now, our next step is to use the axiom of choice to find a well-ordering \prec of \text{tc}(\{X\}), because then there exists a unique ordinal \alpha such that

(\text{tc}(\{X\}),\prec)\cong(\alpha,\in).

Let \varphi:\text{tc}(\{X\})\to\alpha be the underlying bijection. We can then take the point-wise image under \varphi\times\varphi of the membership relation \in\upharpoonright\text{tc}(\{X\}) to achieve a binary relation E\subseteq\alpha\times\alpha, giving us a new isomorphism

(\text{tc}(\{X\}),\in)\cong(\alpha,E).

Letting \kappa be the cardinality of \alpha we also have a bijection \psi:\alpha\to\kappa (without using choice since \alpha is an ordinal), so by now taking the point-wise image of E under \psi\times\psi, we end up with a binary relation F\subseteq\kappa\times\kappa.

Next up, we have the canonical Gödel pairing function, a bijective function G:\kappa\times\kappa\to\kappa — here we’re using that \kappa, being a cardinal, is closed under this function. By taking that point-wise image of F under G, we wind up with a set of ordinals A\subseteq\kappaThis, is our encoding of X. The thing that made this encoding hard was that we had to rely on the axiom of choice to pull out the well-ordering \prec along the way.

Now, let’s start out with the encoded set A\subseteq\alpha and begin the decoding procedure. First of all, since the Gödel pairing function works the same way in every universe, we can extract the binary relation F\subseteq\kappa\times\kappa from A, by taking the point-wise image of A under G^{-1}. Now we consider (\kappa,F), which satisfies the requirements for taking the Mostowski collapse, so we retrieve the isomorphism

(\text{tc}(\{X\}),\in)\cong(\kappa,F)

by uniqueness of the collapse, using that \text{tc}(\{X\}) is in fact transitive. But now that we have extracted \text{tc}(\{X\}), we can from this also extract X, since X is the unique element of \text{tc}(\{X\}) which isn’t an element of any Y\in\text{tc}(\{X\}). This encoding procedure doesn’t refer to the well-ordering \prec at all!

A consequence of this encoding-decoding procedure is that, given any set X, we can find a set of ordinals A such that X\in L[A]: by simply letting A encode X, we get that A=A\cap L[A]\in L[A] as L[A] contains all the ordinals, so we can perform the above decoding process inside L[A] to extract X.