Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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

share|improve this answer
1  
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
2  
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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