Skip to main content

A word cannot be described within the same language

Here's a proof that any word in a language cannot be described within the same language.

Proof by Induction #

Assume that each word takes at least one other word to define. Also assume that circular definition is not allowed. And finally, assume that a language can be constructed by adding word one by one.

Basis: Suppose a language consists of one word. Then trivially, this word cannot be described in terms of other words in the language. Thus the word cannot be described.

Inductive step: Suppose the statement is true for k1. Then add one more word T to this language, constructing a language with k + 1 words. Now suppose the statement is false; i.e. suppose that T can be described in terms of other words. But then T must be described in terms of at least one word in the original k words. Let us call such a word S. But S must be described in order to define T. However, by our inductive hypothesis, S cannot be described. Then T that cannot be described and we've reached a contradiction. Thus any word in a language consisting of k + 1 words cannot be described.

Hence basis and inductive steps have been proven. By mathematical induction, the statement is true. Q.E.D.