The Baire-Space is the set of all infinite sequences of integers, i.e. $$ \mathcal N = \omega^{\omega}. $$ On this space usually the following metric is given $$ d(\alpha, \beta) = \left\{ \begin{array}{ll} 0 & \textrm{if } \alpha = \beta \\ \frac{1}{\min\{ n : \alpha(n) \ne \beta(n)\} + 1} & \textrm{if } \alpha \ne \beta \end{array}\right. $$ which means two infinite sequences are close if they share a long common intial segment/prefix. This metric (in fact it is an ultrametric) induces a topology which is equivalent to the product topology if we take on the natural numbers the discrete topology.

I want to generalize this "common-prefix-metric" to infixes, i.e. sequences in between. Intuitively what I want is a metric which gives a small distance between two sequences if all their infixes up to a specific length coincide.

Before I gave the formal definition I define some sets, let $\xi \in \mathcal N$. Then by $\operatorname{infix}(\xi)$ I denote the set of infixes of $\xi$ (which could be formalized as finite subwords if thinking of $\xi$ as an infinite word or sequence, or as a function $f : \{i,\ldots,i+n\} \to \mathbb N$ if thinking of the elements of $\mathcal N$ as functions). If $w$ is such an finite infix, I denote by $|w|$ it's length. The expression $\operatorname{infix}_n(\xi)$ denotes all infixes of $\xi$ up to and including a length of $n$, i.e. $\operatorname{infix}_n(\xi) = \{ w \in \operatorname{infix}(\xi) : |w| \le n \}$. Finally by $\operatorname{pref}(\xi)$ I denote all prefixes of $\xi$, i.e. finite initial segments, surely $\operatorname{pref}(\xi) \subseteq \operatorname{infix}(\xi)$. I also denote by $\xi[0\ldots n]$ the prefix of $\xi$ of length $n$.

Now the metric could be defined as $$ d'(\alpha, \beta) = \left\{ \begin{array}{ll} 0 & \textrm{if } \alpha = \beta \\ \frac{1}{\max\{ n : \operatorname{infix}_n(\alpha) = \operatorname{infix}_n(\beta) \land \alpha[0\ldots n] = \beta[0\ldots n] \}} & \textrm{if } \alpha \ne \beta \end{array}\right. $$ We have $d(\alpha, \beta) \le 1/n$ iff the first $n$ values are the same and all infixes of length up to and including $n$ are equal.

Now I collect some facts I already know:

1) The metric could equivalently be defined by $$ d'(\alpha, \beta) = \sup\left\{ \frac{1}{|w|} : w \in \operatorname{pref}(\alpha) \bigtriangleup \operatorname{pref}(\beta) \lor w \in \operatorname{infix}(\alpha) \bigtriangleup \operatorname{infix}(\beta) \right\} $$ by setting $\sup \emptyset = 0$ (if $\alpha = \beta$).

2) It is an ultrametric.

Let $d'(\alpha, \beta) = 1/n$ and $d'(\beta, \gamma) = 1/m$ and $n \ge m$ without any loss of generality. Then $$ \alpha[0\ldots n] = \beta[0\ldots n] \land \operatorname{infix}_n(\alpha) = \operatorname{infix}_n(\beta) $$ and $$ \beta[0\ldots m] = \gamma[0\ldots m] \land \operatorname{infix}_m(\beta) = \operatorname{infix}_m(\gamma). $$ Then surely $\alpha[0\ldots m] = \gamma[0\ldots m]$ and because if $\operatorname{infix}_n(\alpha) = \operatorname{infix}_n(\beta)$ then for $m \le n$ also $\operatorname{infix}_m(\alpha) = \operatorname{infix}_m(\beta)$. So $\operatorname{infix}_m(\alpha) = \operatorname{infix}_m(\gamma)$. All in all $d'(\alpha, \gamma) \le 1/m$.$\mathbf{QED}$

3) The metric is not complete on $\mathcal N$ (due to Joseph Van Name)

Let $f_n : \mathbb N \to \mathbb N$ denote the function $$ f_n(m) = \left\{ \begin{array}{ll} 1 & \textrm{if } n = m \\ 0 & \textrm{if } n \ne m \end{array} \right. $$ then $\{ f_n \}$ is a Cauchy sequence that does not converge.

To see that it is Cauchy, note that for all $N$ if $n, m > N$ then $f_n, f_m$ both have the same prefixes of length $N$ and the same infixes of length at most $N$, so $d'(f_n, f_m) \le \frac{1}{N}$. Therefore the sequence $\{ f_n \}$ is Cauchy.

On the other hand, the sequence $(f_{n})_{n}$ does not converge to any point in $\mathbb{N}^{\mathbb{N}}$ with respect to $d'$. If $f_{n}\rightarrow f$ with respect to $d'$, then for all $r\in\mathbb{N}$, we have $f_{n}(r)\rightarrow f(r)$. This shows that $f(r)=0$ for all $r$. However, $f_{n}$ does not converge to $f$ with respect to $d'$ since $f_{n}$ contains the infix $1$ where $f$ does not. $\mathbf{QED}$

I am interesed in the topology induced by this metric, and in what relations does it stand to the "standard topology" mentioned above. Do you know any references where such alternative metrics or even topologies for the Baire Space are studied? Or even know further properties satisfied by this metric?

  • I think the metric is not well defined. There may be $\alpha\neq\beta$ with common infixes of arbitrary length so that the maximum does not exist. – jonathanverner Sep 6 '13 at 12:14
  • thx for pointing out, I corrected the metric, see my edit. – StefanH Sep 6 '13 at 12:43
  • 1
    So ... we can have two sequences that agree from positions 10 to 20, from positions 100 to 200, from positions 1000 to 2000, and so on. But disagree elswhere. Their $d'$ distance is zero? – Gerald Edgar Sep 6 '13 at 13:07
  • 1
    Pn the other hand: if $\alpha$ and $\beta$ have long common infixes and $\beta$ and $\gamma$ have long common infixes, it need not follow that $\alpha$ and $\gamma$ have long common infixes. You would need that for the triangle inequality. – Gerald Edgar Sep 6 '13 at 13:10
  • 1
    Could you please post a single version of your question (without any extras, which you may redirect to comments, if it were necessary)? – Włodzimierz Holsztyński Sep 6 '13 at 18:07
up vote 3 down vote accepted

I am going to answer the question that you all ask whenever you see a metric space "is it complete?"

$\mathbf{Proposition}$ The metric $d'$ on $\mathbb{N}^{\mathbb{N}}$ is not a complete metric.

$\mathbf{Proof}$ Let $f_{n}:\mathbb{N} \rightarrow \mathbb{N}$ denote the function where $f_{n}(n)=1$ and $f_{n}(m)=0$ whenever $m \neq n$. I claim that the sequence $(f_{n})_{n}$ is a Cauchy sequence that does not converge.

To see that the sequence $(f_{n})_{n}$ is Cauchy, we take note that for all $N$, if $n,m>N$, then the functions $f_{n},f_{m}$ both have the same prefixes of length $n$ and the same infixes of length at most $n$, so $d'(f_{n},f_{m}) \leq \frac{1}{N}$. We therefore conclude that the sequence $(f_{n})_{n}$ is Cauchy.

On the other hand, the sequence $(f_{n})_{n}$ does not converge to any point in $\mathbb{N}^{\mathbb{N}}$ with respect to $d'$. If $f_{n}\rightarrow f$ with respect to $d'$, then for all $r\in\mathbb{N}$, we have $f_{n}(r)\rightarrow f(r)$. This shows that $f(r)=0$ for all $r$. However, $f_{n}$ does not converge to $f$ with respect to $d'$ since $f_{n}$ contains the infix $1$ where $f$ does not. $\mathbf{QED}$

Since $d'$ is not a complete metric, it would probably be a good idea to look at the completion of $(\mathbb{N}^{\mathbb{N}},d')$ and not simply $(\mathbb{N}^{\mathbb{N}},d')$.

  • guess you mean $f_n(n) = 1$ and $f_n(m) = 0$ for $m \ne n$. – StefanH Sep 7 '13 at 23:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.