Differences

This shows you the differences between two versions of the page.

--- topic:sets_sequences_reals [2025/02/12 10:14] – lpatey
+++ topic:sets_sequences_reals [2025/02/12 10:18] (current) – lpatey
@@ Line 1: / Line 1: @@
-====== Sets, binary sequences and real numbers ======
+====== Sets of integers, binary sequences and real numbers ======
-<note>Explain that in computability theory, the tradition is to work up to coding, and therefore to identify sets of integers, infinite binary strings, real numbers. Explain that there is a topological difference, but that from a computational viewpoint, it does not matter.</note>
+<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.