Sets of integers, binary sequences and real numbers [Computability theory]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Sets of integers, binary sequences and real numbers ======

<note>This page is a ChatGPT draft. Please, feel free to expand it.</note>

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.