# What is $\mathbb{N}^{<\mathbb{N}}$?

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

-
I ask because I fail to search this symbol. – MichaelNgelo Feb 23 '12 at 23:22
For your information, the question in mind is somehow related to: en.wikipedia.org/wiki/Kleene_star – MichaelNgelo Feb 23 '12 at 23:53
Yes, it is the same as the Kleene star operator. – Zhen Lin Feb 24 '12 at 7:22

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^{<I}$ 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.

-

$\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}$.

-
Do you mean $\mathbb{N}^{<\mathbb{N}} = \bigcup_{n=0}^\infty \mathbb{N}^n$? Is it a valid way to write this set? – MichaelNgelo Feb 23 '12 at 23:32
Yes. ${}{}{}\;$ – Ricky Demer Feb 23 '12 at 23:36
@MichaelNgelo Essentially, though one might not interpret the right hand side as sequences per se. – Alex Becker Feb 23 '12 at 23:37
@MichaelNgelo: Yes, assuming the sets are disjoint. (They are for any reasonable implementation.) – Zhen Lin Feb 23 '12 at 23:44
In fact I would like to have a more detailed set-theoretical definition for clarification, if anyone is willing to offer. – MichaelNgelo Feb 23 '12 at 23:53