I can't understand how can there be languages of infinite size yet containing only words of finite length.

Question

My reasoning is:

• H1. A language $L$ such that $|L|=\infty$,
• H2. $\forall w \in L : |w| \neq \infty$.
• H3. A language such that every word has size at most $k$ will have less or equal than $(|\Sigma|+1)^k$ words. (The number of permutations with repetition of all symbols of the alphabet plus lambda, an upper bound, not a tight one).

Then, by H2, $\exists k$ finite such that $k = \max(\{|w|:w\in L\})$, and by H3, $|L| \le (|\Sigma|+1)^k$, therefore since the last expression was finite, $|L|$ is finite, which is in contradiction with H1.

In sum, why my reasoning is not correct and the infinity of the size of a language does not imply the infinity of the size of its words?

Edit:

Same problem with natural numbers, if $\infty \notin \mathbb{N}$ by definition, either $\mathbb{N}$ is finite or the definition is contradictory. Or so it seems.

Conclusion:

Seems that the problem is much more complex that what I first thought and it goes deep into the foundation of mathematics. One should just assume that the statement is true by convention.

The following source for instance disregards the whole idea of infinity altogether: https://en.wikipedia.org/wiki/Finitism

And here is a general description of set theories (yes, more than one): https://en.wikipedia.org/wiki/Set_theory#Axiomatic_set_theory

Finally I'd like to link an interesting discussion about this also found on Wikipedia: https://en.wikipedia.org/wiki/Actual_infinity

Answer 1

The simplest language of infinite (denumerable) size is $L=\{a^k\mid k\in\Bbb N_0\}= \{a^0=\epsilon,a,a^2,a^3,\ldots\}$ where the words are enumerated by the natural numbers.

Answer 2

This sentence from your comment is the core of your misunderstanding.

Can't you have a number with infinitely many digits? If you can not, then there has to be a number of finite amount of digits that has more digits than every other one (thus a finite set). If such number doesn't exist, that is, there is always a number with more digits, then there is no upper bound, hence you have number with infinitely many digits.

Just imagine the positive integers written as strings of digits in the usual way: $$ 1, 2, 3, \ldots, 10, 11, 12, \ldots, 100, 101, 102, \ldots $$

Clearly (I hope)

• There are infinitely many numbers.

• None of these numbers has infinitely many digits.

• There is no bound on the number of digits: no number greater than the number of digits in every number.

Answer 3

Your argument

Then, by H2, $\exists k$ finite such that $k = max(\{|w|:w\in L\})$

is plain wrong. To see this, take $L = a^*$, which clearly satisfies H1. Suppose that your conclusion holds, and let $w = a^{k+1}$. Then $|w| = k+1$. But since $k = max(\{|w|:w\in L\})$ and $w \in L$, $|w| \leqslant k$. Thus $k + 1 \leqslant k$, a contradiction.

Answer 4

Here the proof about $a^*$ you should understand through proof by contradiction. Assume $p$ holds. $$\big(\; (p \land q) \implies \bot \;\big) \implies \lnot q \lor \lnot p$$ You have $\lnot p \lor \lnot q \land p \equiv \lnot q$ . To argue that we do not have $p$ is the same (bijection) as arguing we don't have $\mathbb{N}$, which very few people happen to believe!

Update: I seriously didn't expect you to doubt that $\left|\mathbb{N}\right|= \infty$... If you stop at $n$, where do you put $n+1$?

Answer 5

Then, by H2, $\exists k$ finite such that $k = \max(\{|w|:w\in L\})$

This argument is wrong : while every word have finite length, there's no reason why the maximum of their length should exist. The point is that an infinite subset of the natural numbers $\mathbb{N}$ doesn't have a maximum.

Take a language $L$, finite or infinite, doesn't matter, and suppose $a\in L$, then consider $$X := \{w \in L^* \ \big| \ w=\underbrace{a\dots a}_{n \textrm{ times}}, n \in \mathbb{N}\}$$

Every word in $X$ is of finite length, yet the set $\{ |w| \ \big| \ w \in X \}$ is equal to $\mathbb{N}$, which has no maximum.