Paradoxical Proof?

[BAndrew]

My friend challenged me to solve the following problem*. I seriously haven't found the solution yet, but I would like to hear your ideas (and no I don't want to steal your ideas and go to play the smart guy or something. That would be pointless.). In my opinion it is a great puzzle which can astonish even experienced solvers. Please, if you think you have an answer put it into spoilers.

---

Below we will prove that every natural number can be described in fourteen words or less. Natural numbers are called integers that are greater than 0. By words we mean any English (or other language) words contained in any dictionary and which must form a phrase with a meaning. For example, the phrase "the natural number between three and five" specifies the number 4.
The proposal is obviously incorrect for the following reason: The English (or any other language you choose) has a finite number of words. The combinations resulting from fourteen selected words of a finite set is also finite. The natural numbers are infinite and therefore they cannot be assigned to all the combinations of 14 or fewer words , even if all these combinations had some meaning.

The following proof is by the method of reductio ad absurdum that works as follows: We want to prove that a proposition A is true. We assume initially that it is false and then with logical reasoning we try to reach a contradiction. Then the assumption we made that proposal A is false is not correct and therefore the sentence A must be true .
Try to discover why the proof is incorrect.

PROOF

1. Assume that there are natural numbers that cannot be described with fourteen words or less.
2. One of these numbers is the smallest. Let's call it N.
3. Then the number N can be defined as "the smallest natural number that cannot be described with fourteen words or less".
4. This proposal describes the number N with fourteen words or less and thus contradicts the hypothesis that the N is a number that cannot be described with fourteen words or less.
5. The initial assumption we made in Step 1 resulted with logical steps in contradiction so it must be false.
6. So all natural numbers can be determined with fourteen words or less!



*I have already failed to solve the challenge if that interests you.

[Apjjm]

There are a few ways to solve this problem. First an assumption which was unstated (this doesn't actually help pin down the fallacy, it just removes a little weasel out):
A word is a finite sequence of characters, drawn from a finite alaphabet..

The fallacy

Spoiler below!

The problem is that the number referred to by the sequence "the smallest natural number that cannot be described with fourteen words or less" (this sequence will be referred to as Y from now on) actually refers to more than one number. Lets assume for the moment we use every other sequence of words to represent a number, and the smallest remaining number we have not represented is X. Then sequence Y must represent X, as it cannot be defined by our other sequences. However, as Y now can represent X, X is no longer unrepresentable in 14 or fewer words, and as such X+1 (or some number >x) is the smallest number and Y must refer to it. This means that interpreting Y in this manner makes Y inconsistent, and hence this interpretation of Y is incorrect.

tldr version: The phrase is self referential, hence inconsistent. The confusing behavior comes from the fact that the phrase represents multiple numbers when it should only represent one.
See also: Russells paradox

Refutation without pointing out the fallacy

Spoiler below!

If we start off with a finite set of finite words, where each word is comprised of a finite alphabet. Given this, we can construct a finite dictionary D, of length #D (a finite integer) that holds every word.

It follows, that by replacing each word with it's index into D we can obtain a sequence of integers, up to 14 integers in length, where each integer is smaller than #D and greater than 0.

Therefore, the number of possible permutations of words is #D^14 + #D^13 + ... + #D^2 + #D which is finite, as each term in that expression is finite. This is important, as this number represents the maximum total number of integers we can represent using a 1-to-1 mapping (we actually might be able to represent less if we include restrictions on sentence structure!). This number is finite, hence there is not enough informational content to represent the countable infinity of the natural numbers without ambiguity.

Edit hint: So, here by stripping all the meaning from the words and just directly mapping them to integers we do not have any surprising results. This gives you a clue: using the english interpretation of the statements allows you to seemingly refer to a set of numbers larger than it should - you must therefore be somehow referring to more than one number with certain statements, violating the implicit constraint that the mapping must be bijective. The question then becomes which step of the process is worded such that this inconsistency can slip through, and how does this wording cause the problem.

[Froge]

To say that the statement "a number N cannot be described with 14 words or less" is a description of that number N is self-contradictory. It's like


the sentence below is true
the above sentence is false

[BAndrew]

There are a few ways to solve this problem. First an assumption which was unstated (this doesn't actually help pin down the fallacy, it just removes a little weasel out):
A word is a finite sequence of characters, drawn from a finite alaphabet..


Refutation without pointing out the fallacy

Spoiler below!

If we start off with a finite set of finite words, where each word is comprised of a finite alphabet. Given this, we can construct a finite dictionary D, of length #D (a finite integer) that holds every word.

It follows, that by replacing each word with it's index into D we can obtain a sequence of integers, up to 14 integers in length, where each integer is smaller than #D and greater than 0.

Therefore, the number of possible permutations of words is #D^14 + #D^13 + ... + #D^2 + #D which is finite, as each term in that expression is finite. This is important, as this number represents the maximum total number of integers we can represent using a 1-to-1 mapping (we actually might be able to represent less if we include restrictions on sentence structure!). This number is finite, hence there is not enough informational content to represent the countable infinity of the natural numbers without ambiguity.

I only saw your second part (Refutation without pointing out the fallacy) which was in a way stated in my post (or at least that's what I meant):

The proposal is obviously incorrect for the following reason: The English (or any other language you choose) has a finite number of words. The combinations resulting from fourteen selected words of a finite set is also finite. The natural numbers are infinite and therefore they cannot be assigned to all the combinations of 14 or fewer words , even if all these combinations had some meaning.

Thanks though for the response. I'll wait to hear more opinions (if any) and then I'll read your answer.

---

To say that the statement "a number N cannot be described with 14 words or less" is a description of that number N is self-contradictory.(1) It's like


the sentence below is true
the above sentence is false
(2)

I didn't understand why (1) is similar to (2)

[Apjjm]

I would advise you to look at Russell's paradox, which is rather similar in its self-referential manner. Though clicking that might give you the answer easily.

Edit: Also worth reading up on: Komolgorov complexity, Berry paradox, Richard paradox.

[Bridge]

Technically there is no "smallest number" so if one number equals one word it is possible to go on infinitely long, right?

[Apjjm]

Edit: nvm misinterpreted above post.

[BAndrew]

Technically there is no "smallest number" so if one number equals one word it is possible to go on infinitely long, right?

Actually there has to be a smallest natural number N (which we of course don't know).

---

I read Berry paradox after reading the Russel's Paradox.

Here's the solution it proposes(from wikipedia)

The Berry paradox as formulated above arises because of systematic ambiguity in the word "definable". In other formulations of the Berry paradox, such as one that instead reads: "...not nameable in less..." the term "nameable" is also one that has this systematic ambiguity. Terms of this kind give rise to vicious circle fallacies. Other terms with this type of ambiguity are: satisfiable, true, false, function, property, class, relation, cardinal, and ordinal. To resolve one of these paradoxes means to pinpoint exactly where our use of language went wrong and to provide restrictions on the use of language which may avoid them.

This family of paradoxes can be resolved by incorporating stratifications of meaning in language. Terms with systematic ambiguity may be written with subscripts denoting that one level of meaning is considered a higher priority than another in their interpretation. "The number not nameable0 in less than eleven words" may be nameable1 in less than eleven words under this scheme.

Perhaps I am not smart enough, but I didn't understand the solution.

[Bridge]

Actually there has to be a smallest natural number N (which we of course don't know).

I do not see how it is even remotely possible to describe something indefinable.

EDIT: There's a reason why abstracts such as infinity exist in the first place.

[BAndrew]

Actually there has to be a smallest natural number N (which we of course don't know).

I do not see how it is even remotely possible to describe something indefinable.

Wait, what? All I meant was that there has to be a smallest natural number N which can be described with fourteen words or fewer.

EDIT: I think I misunderstood what you meant.