What is the definition of this symbol $\mathbb{N}^{<\mathbb{N}}$? How is it related to the infinite product $\mathbb{N}^{\mathbb{N}}$?
What is $\mathbb{N}^{<\mathbb{N}}$?
-
0I ask because I fail to search this symbol. – 2012-02-23
-
0For your information, the question in mind is somehow related to: http://en.wikipedia.org/wiki/Kleene_star – 2012-02-23
-
0Yes, it is the same as the Kleene star operator. – 2012-02-24
2 Answers
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.
$\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}$.
-
1Do you mean $\mathbb{N}^{<\mathbb{N}} = \bigcup_{n=0}^\infty \mathbb{N}^n$? Is it a valid way to write this set? – 2012-02-23
-
2Yes. ${}{}{}\;$ – 2012-02-23
-
0@MichaelNgelo Essentially, though one might not interpret the right hand side as sequences *per se*. – 2012-02-23
-
1@MichaelNgelo: Yes, assuming the sets are disjoint. (They are for any reasonable implementation.) – 2012-02-23
-
0In fact I would like to have a more detailed set-theoretical definition for clarification, if anyone is willing to offer. – 2012-02-23