Skip to main content
Became Hot Network Question
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 285

What's the Bijectionbijection between Realsreals and infinite sequences of integers?

added 8 characters in body
Source Link
Neil Strickland
  • 56.9k
  • 7
  • 142
  • 262

In Descriptive Set Theory we often see the notion of encoding a real as a sequence of integers or natural numbers -- i.e. there obviously is a bijection according to ZF axioms. But how does it look like concretely? Anybody has seen a simple construction?

My own approach is by chain-fractions:

Let $q\in\R$$q\in\mathbb{R}$ be the given real and now define the sequence $(z_i,q_i)$ by $$z_{i+1}=\begin{cases}[q_i]&\text{if } \{q_i\}\leq\frac{1}{2}\\ [q_{i}]+1&\text{else} \end{cases}$$ $$q_{i+1}=(q_i-z_{i+1})^{-1}$$ where $[q]$ is the next lower integer and $\{q\}=q-[q]$. (Hence $(q_i-z_{i+1})\in(-\frac12,\frac12]$ thereby absolute value of $q_{i+1}$, its reciprocal, is bigger than 2.) Now my bijection is mapping $q$ to the sequence: $$m_i=\begin{cases}z_i-2&z_i>0, i>1\\ z_i&i=1\\ z_i+2&z_i<0, i>1\end{cases}$$ with $i$ starting at 1 and above $q_0$ becomes the initial $q$. And the inverse of my bijection just calculates the chain-fraction:$q_{i-1}\in(z_i-\frac12,z_i+\frac12]$ with $q_{i-1}=z_i+q_i^{-1}$ step-wise narrowing down the real by a sequence of intervals each containing the next.

is there a paper or book covering my example? any other simple constructions?

In Descriptive Set Theory we often see the notion of encoding a real as a sequence of integers or natural numbers -- i.e. there obviously is a bijection according to ZF axioms. But how does it look like concretely? Anybody has seen a simple construction?

My own approach is by chain-fractions:

Let $q\in\R$ be the given real and now define the sequence $(z_i,q_i)$ by $$z_{i+1}=\begin{cases}[q_i]&\text{if } \{q_i\}\leq\frac{1}{2}\\ [q_{i}]+1&\text{else} \end{cases}$$ $$q_{i+1}=(q_i-z_{i+1})^{-1}$$ where $[q]$ is the next lower integer and $\{q\}=q-[q]$. (Hence $(q_i-z_{i+1})\in(-\frac12,\frac12]$ thereby absolute value of $q_{i+1}$, its reciprocal, is bigger than 2.) Now my bijection is mapping $q$ to the sequence: $$m_i=\begin{cases}z_i-2&z_i>0, i>1\\ z_i&i=1\\ z_i+2&z_i<0, i>1\end{cases}$$ with $i$ starting at 1 and above $q_0$ becomes the initial $q$. And the inverse of my bijection just calculates the chain-fraction:$q_{i-1}\in(z_i-\frac12,z_i+\frac12]$ with $q_{i-1}=z_i+q_i^{-1}$ step-wise narrowing down the real by a sequence of intervals each containing the next.

is there a paper or book covering my example? any other simple constructions?

In Descriptive Set Theory we often see the notion of encoding a real as a sequence of integers or natural numbers -- i.e. there obviously is a bijection according to ZF axioms. But how does it look like concretely? Anybody has seen a simple construction?

My own approach is by chain-fractions:

Let $q\in\mathbb{R}$ be the given real and now define the sequence $(z_i,q_i)$ by $$z_{i+1}=\begin{cases}[q_i]&\text{if } \{q_i\}\leq\frac{1}{2}\\ [q_{i}]+1&\text{else} \end{cases}$$ $$q_{i+1}=(q_i-z_{i+1})^{-1}$$ where $[q]$ is the next lower integer and $\{q\}=q-[q]$. (Hence $(q_i-z_{i+1})\in(-\frac12,\frac12]$ thereby absolute value of $q_{i+1}$, its reciprocal, is bigger than 2.) Now my bijection is mapping $q$ to the sequence: $$m_i=\begin{cases}z_i-2&z_i>0, i>1\\ z_i&i=1\\ z_i+2&z_i<0, i>1\end{cases}$$ with $i$ starting at 1 and above $q_0$ becomes the initial $q$. And the inverse of my bijection just calculates the chain-fraction:$q_{i-1}\in(z_i-\frac12,z_i+\frac12]$ with $q_{i-1}=z_i+q_i^{-1}$ step-wise narrowing down the real by a sequence of intervals each containing the next.

is there a paper or book covering my example? any other simple constructions?

Source Link

What's the Bijection between Reals and infinite sequences of integers?

In Descriptive Set Theory we often see the notion of encoding a real as a sequence of integers or natural numbers -- i.e. there obviously is a bijection according to ZF axioms. But how does it look like concretely? Anybody has seen a simple construction?

My own approach is by chain-fractions:

Let $q\in\R$ be the given real and now define the sequence $(z_i,q_i)$ by $$z_{i+1}=\begin{cases}[q_i]&\text{if } \{q_i\}\leq\frac{1}{2}\\ [q_{i}]+1&\text{else} \end{cases}$$ $$q_{i+1}=(q_i-z_{i+1})^{-1}$$ where $[q]$ is the next lower integer and $\{q\}=q-[q]$. (Hence $(q_i-z_{i+1})\in(-\frac12,\frac12]$ thereby absolute value of $q_{i+1}$, its reciprocal, is bigger than 2.) Now my bijection is mapping $q$ to the sequence: $$m_i=\begin{cases}z_i-2&z_i>0, i>1\\ z_i&i=1\\ z_i+2&z_i<0, i>1\end{cases}$$ with $i$ starting at 1 and above $q_0$ becomes the initial $q$. And the inverse of my bijection just calculates the chain-fraction:$q_{i-1}\in(z_i-\frac12,z_i+\frac12]$ with $q_{i-1}=z_i+q_i^{-1}$ step-wise narrowing down the real by a sequence of intervals each containing the next.

is there a paper or book covering my example? any other simple constructions?