Code (set theory)

In set theory, a code for a hereditarily countable set

$x\in H_{\aleph _{1}}\,$

is a set

$E\subset \omega \times \omega$

such that there is an isomorphism between $(\omega ,E)$ and $(X,\in )$ where $X$ is the transitive closure of $\{x\}$. If $X$ is finite (with cardinality $n$), then use $n\times n$ instead of $\omega \times \omega$ and $(n,E)$ instead of $(\omega ,E)$.

According to the axiom of extensionality, the identity of a set is determined by its elements. And since those elements are also sets, their identities are determined by their elements, etc.. So if one knows the element relation restricted to $X$, then one knows what $x$ is. (We use the transitive closure of $\{x\}$ rather than of $x$ itself to avoid confusing the elements of $x$ with elements of its elements or whatever.) A code includes that information identifying $x$ and also information about the particular injection from $X$ into $\omega$ which was used to create $E$. The extra information about the injection is non-essential, so there are many codes for the same set which are equally useful.

So codes are a way of mapping $H_{\aleph _{1}}$ into the powerset of $\omega \times \omega$. Using a pairing function on $\omega$ such as $(n,k)\mapsto (n^{2}+2nk+k^{2}+n+3k)/2$, we can map the powerset of $\omega \times \omega$ into the powerset of $\omega$. And we can map the powerset of $\omega$ into the Cantor set, a subset of the real numbers. So statements about $H_{\aleph _{1}}$ can be converted into statements about the reals. Therefore, $H_{\aleph _{1}}\subset L(R)$, where L(R) is the smallest transitive inner model of ZF containing all the ordinals and all the reals.

Codes are useful in constructing mice.