0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Aloizio Macedo Oct 9 '19 at 18:17
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "None if those numbers has infinitely many digits". $1,2,3,...,10,11,12,...,100,101,102,...,n$. $n$ has. "..." can be infinite. $\endgroup$ – elmeunick Oct 9 '19 at 13:06
  • 3
    $\begingroup$ @elmeunick No. "$n$" is not a number, it's just a letter you are using to represent a particular number. Which particular infinitely long number do you have in mind? There is no $n$ at the (nonexistent) "end" of that list. The $\ldots$ is a way to say that the list goes on forever, $\endgroup$ – Ethan Bolker Oct 9 '19 at 13:11
  • $\begingroup$ I had in mind an infinite amount of numbers, $\{0,1,2,3,4,5,6,7,8,9\}^k$ for $k = \infty$ to be precise. In no particular order, that is true, so I probably should have written $1,2,3,...,n,...$ where for, instance, $n=10...$. $\endgroup$ – elmeunick Oct 9 '19 at 13:19
  • 1
    $\begingroup$ Any actual $n$ is at some particular place in the sequence and has some finite number of digits. If you can't see that then I have not explained it clearly enough, but I have done the best I can, so there's no point in continuing the interchange. $\endgroup$ – Ethan Bolker Oct 9 '19 at 13:23
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Precisely the conclusion is "this is a contradiction". Here we agree. But why is it a contradiction? You conclude it is because there is no max(...) in a set where all elements are finite yet the set is infinite, but you can also instead conclude (my point) that there is simply no such set. By this, $a^*$ contains words of infinite length. Intuitively, if all elements are finite, such max should exist because there must be a limited number of them, there is no way to have infinitely sequences of a finite amount of combinations unless some of these sequences have infinite length. $\endgroup$ – elmeunick Oct 16 '19 at 15:22
  • 1
    $\begingroup$ I can only subscribe to Ethan Bolker's comment: If you can't see that then I have not explained it clearly enough, but I have done the best I can, so there's no point in continuing the interchange. $\endgroup$ – J.-E. Pin Oct 16 '19 at 15:30
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Same argument for the natural numbers, as it is also a set of infinite elements whose elements are all of finite size. I don't get it. $\endgroup$ – elmeunick Oct 9 '19 at 12:52
  • $\begingroup$ But the OPs view is that the word are of finite length. $\endgroup$ – Wuestenfux Oct 9 '19 at 12:53
  • $\begingroup$ Isn't that the same as $a^*$, a regular language (of words with finite length)? $\endgroup$ – elmeunick Oct 9 '19 at 12:56
  • $\begingroup$ True, its the same. $\endgroup$ – Wuestenfux Oct 9 '19 at 13:12
0
$\begingroup$

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$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ About the proof: I'm not saying that necessarily $|L|=\infty$ is false, I'm saying that it is false if every element in $L$ is finite. To bring it to $\mathbb{N}$, what I'm saying is $|\mathbb{N}|=\infty \implies \infty \in \mathbb{N}$. This however needs some extra consideration. In $L$ you have words, which are sequences of characters. If numbers are sequences of digits this holds true, otherwise it doesn't. Your first order logic proof is missing something, I don't understand it. What are you trying to prove about $a^*$? How does that translate to the logic formula? $\endgroup$ – elmeunick Oct 17 '19 at 20:05
  • $\begingroup$ About finitism: There is one, only one, $n \in \mathbb{N}$ such that there is no $n+1$ operation defined for it, therefore there is one $n$ such that $n=max(\mathbb{N})$. This can be any number, but not infinity. Using smaller numbers will however have weird behavior, for instance if $n=2$, then $2+2$ is an invalid operation. This said, finitism is only one of the many ways to understand infinity, you could also say that $|\mathbb{N}|=\infty$ and that is fine. The important thing when going by convention is to agree, because it is by convention there is no truth behind it. $\endgroup$ – elmeunick Oct 17 '19 at 20:07
  • $\begingroup$ By the way, finitism may at first look absurd, but when you consider that $n$ may be very large numbers it makes a lot of sense. Consider for instance $n=g_{googolplex}$, where g is a Graham's number. Even this number may produce behaviors like the one showed, but never on the real word or on any manageable size problem. $\endgroup$ – elmeunick Oct 17 '19 at 20:25
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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