6
$\begingroup$

What is the definition of this symbol $\mathbb{N}^{<\mathbb{N}}$? How is it related to the infinite product $\mathbb{N}^{\mathbb{N}}$?

  • 0
    Yes, it is the same as the Kleene star operator.2012-02-24

2 Answers 2

5

We consider the set $X^n$ as the set of all sequences of length $n$ whose members are elements of $X$. For example, $\{0,1\}^n$ is the set of binary sequences of length $n$.

We often want to consider instead of a fixed length, a variable length. For example, all sequences shorter than $5$, that would be: $X^0\cup X^1\cup\ldots\cup X^4$, this can be abbreviated as $X^{<5}$.

In general, when $I$ has a nice [well-]ordering such that we can effectively know what lengths are shorter than $I$, we can write $X^{ as the set of all sequences of length shorter than $I$; and $X^I$ as the set of all sequences of length $I$. Indeed this is the set of all functions from $I$ into $X$, each of which defines a sequence.

The natural numbers have a very nice order. In fact we know that a sequence has a finite length if and only if it is strictly shorter than the sequence $\langle 0,1,2,3,\ldots\rangle$. This means that by writing $<\mathbb N$ we mean "as long as you want, but finite".

Therefore $X^{<\mathbb N}$ would mean all the finite sequences from $X$. If $X=\mathbb N$ as well this means all the finite sequences of natural numbers, whereas $\mathbb N^\mathbb N$ would be the set of all infinite sequences of natural numbers.

Note that if $X$ is nonempty we can choose some fixed element to be added infinitely many times to a sequence in order to make a finite sequence infinite. That is, we think of the sequence $\langle 4,1,3\rangle$ as $\langle 4,1,3,0,0,0,0,0,0,\ldots\rangle$. The former is in $\mathbb N^3$ and thus in $\mathbb N^{<\mathbb N}$ while the latter is in $\mathbb N^\mathbb N$.

If one wants an injection from $\mathbb N^{<\mathbb N}$ you need to remember that appending $0$ (for example) will not work, since $\langle 1\rangle$ and $\langle 1,0\rangle$ will both be sent to $\langle 1,0,0,0,\ldots\rangle$. This means that a slightly cleverer trick is in order.

10

$\mathbb{N}^{< \mathbb{N}}$, or sometimes $\mathbb{N}^{< \omega}$, is the set of all finite sequences of natural numbers. It admits an injection into $\mathbb{N}^\mathbb{N}$ but is strictly smaller.

Exercise. Show that $\mathbb{N}^{< \mathbb{N}}$ is countable: exhibit an injection $\mathbb{N}^{<\mathbb{N}} \to \mathbb{N}$. On the other hand, show that $\mathbb{N}^\mathbb{N}$ is uncountable, and show that there is a bijection $2^\mathbb{N} \to \mathbb{N}^\mathbb{N}$.

  • 0
    In fact I would like to have a more detailed set-theoretical definition for clarification, if anyone is willing to offer.2012-02-23