Sets of integers, binary sequences and real numbers
This page is a ChatGPT draft. Please, feel free to expand it.
In computability theory, there is a well-established tradition of identifying three distinct mathematical objects: sets of integers, infinite binary sequences, and real numbers. This identification is often useful, but it is important to recognize that the corresponding topological spaces are different and lead to distinct mathematical properties.
Identification in computability theory
From a computational perspective, these objects are often treated interchangeably:
A set of integers \( A \subseteq \mathbb{N} \) can be represented by its characteristic function, an infinite binary sequence where the \( n \)-th bit is 1 if \( n \in A \) and 0 otherwise.
An infinite binary sequence \( X \in 2^{\mathbb{N}} \) can be interpreted as the binary expansion of a real number in \( [0,1] \) via the standard encoding: \[ X = 0.X_0X_1X_2 \dots \] where \( X_i \) are the bits of \( X \).
This correspondence allows many notions from computability theory, such as recursive enumerability, Turing reducibility, and randomness, to be transferred between these objects.
Differences in topological structure
Despite their computational similarities, these objects belong to distinct topological spaces:
The Cantor Space \( 2^{\mathbb{N}} \): The space of infinite binary sequences, equipped with the product topology where basic open sets correspond to finite initial segments. This space is totally disconnected, compact, and perfect.
The Baire Space \( \mathbb{N}^{\mathbb{N}} \): The space of functions from \( \mathbb{N} \) to \( \mathbb{N} \), which is often used to represent sets of integers in computability theory. Unlike the Cantor space, it is not compact but remains completely metrizable.
The Real Numbers \( \mathbb{R} \): When infinite binary sequences are interpreted as real numbers, they are placed in the standard topology of \( \mathbb{R} \). However, not all real numbers have unique binary expansions, and the topology of \( \mathbb{R} \) is significantly different from that of \( 2^{\mathbb{N}} \).
Implications in Computability and Logic
These distinctions become important in various areas:
The study of computable analysis treats real numbers in a way that respects the topology of \( \mathbb{R} \), rather than simply encoding them as binary sequences.
The difference between measure and category in \( 2^{\mathbb{N}} \) versus \( \mathbb{R} \) leads to different notions of randomness and genericity.
In reverse mathematics, the choice of representation affects the strength of formal systems needed to prove certain theorems.
While the computational tradition of identifying these objects is often convenient, it is essential to be aware of their underlying topological distinctions to avoid incorrect generalizations.