Is this property of infinite language correct?

37 Views Asked by At

Let $L$ be an infinite language.
Is it true to say that for all $k∈\Bbb N$, we can find $w∈L$ so that $|w|>k$?

I think it's part of an infinite language definition, but I didn't find it formally anywhere, so I also tried to prove it:
Let $k∈N$. Proof by contradiction: we will assume that we don't have $w∈L$ so that $|w|>k$. so the maximum length of a word in $L$ can be $p$ ($p$ is at most $k$).
We know that $Σ^p$ is a finite language, and therefore $Σ^m$ is finite for all $m<p$.
So we get that $Σ^0∪Σ^1∪\dots∪Σ^p$ is a finite language, and we also know that $|L|≤|Σ^0+Σ^1+\dots+Σ^p|$. so we got that L is finite- contradiction.

1

There are 1 best solutions below

2
On BEST ANSWER

The theorem is true iff $\Sigma$ is finite, and your proof works correctly in this case. If $\Sigma$ is infinite, then the set $\{w\in\Sigma^*\mid|w|=1\}$, which is equinumerous to $\Sigma$, is an infinite language with no words of length $>1$.

It is, however, not correct to say that it is true by definition. The definition of "$L$ is an infinite language" is that $L$ contains infinitely many distinct words, or equivalently (if that sounds like restating the definition) for any finite sequence $S$ of words there is a word in $L\setminus S$.