Code (set theory)

Template:Short description Template:Refimprove In set theory, a code for a hereditarily countable set

$x\in H_{{\mathrm{\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\}$.Template:R 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_{{\mathrm{\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_{{\mathrm{\aleph }}_1}$ can be converted into statements about the reals. Therefore, $H_{{\mathrm{\aleph }}_1}\subset L(R)$, where [[L(R)|Template:Math]] is the smallest transitive inner model of ZF containing all the ordinals and all the reals.

Codes are useful in constructing mice.

References

Template:Settheory-stub