This page is keyboard accessible:
• Use Tab, Shift + Tab keys to traverse the main menu. To enter a sub-menu use the Right Arrow key. To leave a sub-menu use the Left Arrow or the Escape key.
• The Enter or the Space key opens the active menu item.
• To skip the menu and move to the main content, press Tab after the page loads to reveal a skip button.
• To get back to the top of the page anytime, press the Home key.
• For more information, click here: Accessibility   Close this tip.

Note: Full functionality of this web page requires JavaScript to be enabled in your browser.



A lemma is a theorem that is usually not considered a primary result in itself, but which is useful as a step towards proving another theorem.


Natural numbers

The term “natural numbers” is usually used to refer to the non-negative whole numbers, 0, 1, 2, 3, …, but it is also sometimes used to mean only the positive whole numbers 1, 2, 3, … .


Number Systems

There are many different ways of denoting numbers. The system we use today for almost everything is the decimal system, which uses the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. However, there is no particular reason to use the decimal system other than it is the system that has become universally accepted today. Most historians believe that the decimal system arose because we have ten fingers, and long ago, fingers were used as a handy portable counting tool. As a matter of historical interest, 5000 years ago the Sumerians of ancient Mesopotamia also used a system in which they counted by 60s (the sexagesimal system). The Babylonians developed this into a fairly sophisticated system, from which we get our 60 seconds in a minute, and sixty minutes in an hour, and 360 degrees in a circle (360 = 6 x 60, and degrees are divided into 60 minutes, and each minute of arc is divided into 60 seconds).


Unary System

The most basic number system is the Unary number system. This system uses only the digit 1 and no other digits. To represent a number in the unary system, you simply write down as many 1s as the number you want. For example: 1111111 represents 7, 111 represents 3, and 111111111 represents 9. Note that in the unary system the position of any digit is immaterial. In other systems, the positions of the digits are of fundamental importance. Also note that in the unary system, there is no representation of the number zero. Unary systems were the first number system used by man. It was a simple way to make a record of a count and is still used today, called tallying.


The modified Unary system with the number zero is the same as the Unary system, except that there is a symbol for zero. There are two types of such systems, representing numbers as:

0, 1, 11, 111, 1111, 11111, …


0, 10, 110, 1110, 11110, 111110, …

Note that the latter method is commonly used in formal systems, except that a symbol such as s is usually used instead of 1, so that you might have 0, s0, ss0, sss0, ssss0, sssss0,


Decimal system

In the standard decimal system we use the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 to write down numbers. In the binary system we only use the digits 0 and 1 to write down numbers. In the decimal system, you can think of a number as being organized into columns, so that 2973 gives:


The leftmost column is for ones, the next column is for tens, the next for ten times ten, the next ten times ten times ten, and so on. So the positions tell us that 2973 means 2 thousands plus 9 hundreds plus 7 tens plus 3 ones. So the number 9372 is quite different to the number 2973, although the symbols used are the same.

In unary notation the number 2973 would be a sequence of 2973 1’s following each other, 11111111111111111111…

which is quite a handful, so you can see why we use a system such as the decimal system to deal with numbers in a manageable way. The decimal system is also called the base 10 number system.


Binary system

The binary system is also called the base 2 number system. It works under exactly the same principles as the decimal system, only the positions of the digits represent multiples of 2s rather than multiples of 10s. And instead of having 10 distinct digit symbols, it has only two digit symbols, 0 and 1.

As for the decimal system, you can think of a number as being organized into columns, so that the binary number 1011011 gives:


The leftmost column is for ones, the next column is for twos, the next for two times two, the next two times two times two, and so on. So the positions tell us that 1011011 means:

Sixty-four plus sixteen plus eight plus two plus one, which is 91 in decimal notation. Binary notation seems difficult only because we aren’t used to it.


Binary expansion

A representation in the binary system of a real number between 0 and 1 (see also Binary system). Whereas a decimal number uses all of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a binary expansion only uses the digits 0 and 1.

A binary expansion or a decimal expansion is simply a convenient way of writing fractions:

0.1 in decimal notation means 110 (a tenth)


0.01 in decimal notation means 1100 (a hundredth)


0.001 in decimal notation means 11000 (a thousandth)


0.1 in binary notation means a half, which in the binary system is written as 110


0.01 in binary notation means a quarter, which in the binary system is written as 1100


0.001 in binary notation means an eighth, which in the binary system is written as 11000


One-to-one Correspondence

If one set of things can be matched up with another set of things, so that everything in the first set is paired up uniquely with one and only one thing in the second set, then that is often called a one-to-one correspondence, or a bijection, or for some cases, a list or a sequence. When this is the case, then there is no thing in the first set that is not matched to some thing in the second set, and there is no thing in the second set that is not matched to a thing in the first set – and every thing is matched up to one and only one thing from the other set.


As a simple example, for a set of numbers, {1, 2, 3, 4, 5, 6} and a set of letters {A, B, C, D, E, F}, then if we match 1 to A, 2 to B, etc, to give a list of pairings, {1, A}, {2, B}, {3, C}, {4, D}, {5, E}, {6, F}, then we have a one-to-one correspondence of the two sets. For sets of a finite size, a one-to-one correspondence always gives a finite list of pairings.


We can also have a one-to-one correspondence between limitlessly large sets. For example, if we have the set of all natural numbers, {0, 1, 2, 3, …} and the set of all even numbers {2, 4, 6, …}, and we define the pairing to be such that an element of the second set is given by adding one to the value of an element of the first set, and then multiplying by two, and that defines a one-to-one correspondence of the two sets as (0, 2), (1, 4), (2, 6), (3, 8), …


The term ‘list’ (or sequence) is often used to refer to a one-to-one correspondence to natural numbers, so that to say that a set can be ‘listed’ means that there can be a one-to-one correspondence between that set and the set of natural numbers. Obviously, for a one-to-one correspondence such as the one above, for the natural numbers and the even numbers, we can never actually write out such a list in its entirety; the list must be defined rather than written as an actual written down list.



For a given set of things, if a one-to-one correspondence can be defined between the elements of the set and the natural numbers, then the set is said to be denumerable, otherwise it is a non-denumerable set. Note that the term countable is often used instead of denumerable, and uncountable instead of non-denumerable - I prefer not to use the terms countable and uncountable, since in ordinary language uncountable is often used to mean finite, whereas the intended mathematical meaning is that the set is infinite but a one-to-one correspondence cannot be defined between the set and the natural numbers.


Other terms used to denote the same meaning as denumerable are listable and enumerable.


Primitive Recursive Relations

This section is not intended to be a comprehensive explanation of primitive recursion, since the information is readily available elsewhere. Instead we will try to give the fundamental essentials of what primitive recursion entails.


When the free variables of a relation are substituted by specific numbers, the result of the substitution is a proposition that may be correct or incorrect. For a primitive recursive relation, when its free variables are substituted by specific numbers, the result of the substitution is a proposition - and this proposition, or else its negation, can always be proved to follow from the axioms of number theory by a method that always has a finite number of steps.


Similarly, when the free variables of a function are substituted by specific numbers, the result of the substitution is an expression that has a numerical value. For a primitive recursive function, when its free variables are substituted by specific numbers, the resulting numerical value can always be evaluated (according to the axioms of number theory) by a method that always has a finite number of steps.


Note: There are functions and relations that can be calculated by a finite number of steps, but which are not primitive recursive - this is not explained by the simplified description above.


Use of Primitive Recursion in Incompleteness Proofs

Gödel used primitive recursive relations in his proof of incompleteness for two reasons:

  • Because every (substituted) primitive recursive relation, or its negation, is provable from the axioms of number theory, and
  • Because every primitive recursive relation can be expressed in the formal system.


When it is said that every primitive recursive relation can be expressed in the formal system, what this means is that:

For any primitive recursive relation with a free variables, there is a corresponding formula in the formal system which also has a free variable (and this also applies for relations with more than one free variable).


If the free variables of a primitive recursive relation are substituted by number values, then it can be proved by a finite number of steps if the relation is a correct or an incorrect proposition. Since there is a precise correspondence between the relation and a formula of the formal system, then if the relation is proven to be a correct proposition, the corresponding formula is also a correct proposition - and if the relation is proven to be an incorrect proposition, the corresponding formula is also an incorrect proposition.



Real numbers

Real numbers can be divided into rational numbers and irrational numbers. A fundamental property of any real number is that it can be set in order against any other real number. It either has to be bigger, or smaller, or than any other real number. The name ‘real’ was used because at that time, mathematics was considered to be a science that dealt principally with quantity, so that mathematics was the means by which quantities might be measured, and the real number system was the foundation for all such measurement.


Rational numbers

Rational numbers are numbers that can be represented as fractions. The name ‘rational’ comes from the fact that all such numbers represent a ratio. Given any two rational numbers, there is always at least another rational number between those two numbers – in fact, there is no limit to how many rational numbers there can be between any two rational numbers.


However, despite this fact, there are real numbers other than the rational numbers - numbers for which there is no way they can be represented as a fraction - these are the irrational numbers.


Irrational numbers

An irrational number is the solution of an numerical equation where the solution cannot be represented as a rational number, but the value of the solution can be set in order against any other real number. An example of an irrational number is the square root of two - that is, the value which, when multiplied by itself, gives the value 2.


When a number is multiplied by itself, the number of times that it is multiplied by itself is called the exponent. For example, if 5 is multiplied by itself 9 times, then 9 is the exponent, and this is denoted by a superscript, as 59. This is also called raising 5 to the power of 9.



Essentially, when we refer to the syntax of a language, we are referring to valid expressions of the language, as opposed to strings of symbols simply being objects that the expressions of the language refer to. In a valid syntactical expression some, but not all, of the symbols of the expression may be objects. (Footnote: In computer languages, objects of the language are usually called data.) Note that, for any object of the language, there can be a variable that has a domain that includes that object as a value. Variables of a logical language should never also be objects of that language.


As an example of the distinction of syntax and object, in English, the expression ‘The cat sat on the mat’ is valid syntax, where ‘cat’ and ‘mat’ are objects. The inherent ambiguity of natural languages such as English, means that there can be sentences where it is not clear whether a certain string of symbols is intended to be read as a valid syntactical expression or as an object. We might use quotation marks; for example, we might write, ‘The expression “The cat is black” has thirteen letters.’, and we use the quotation marks to indicate that the string of symbols within the quotation marks is intended to be an object to be referred to, rather than as part of the syntax of the overall sentence. We could equally well write , ‘The expression “kab ic aaT chest” has thirteen letters.’ which is also syntactically correct, but in this case it is obvious that the string of symbols within the quotation marks is not valid syntax of the language - and nor does it need to be for the overall sentence to be valid syntax. However, in English, there are no rules to prevent certain strings of symbols appearing at the same time to be valid syntactical expressions and also as objects. This ambiguity is the root source of many paradoxes of natural language.


For a language to be suitable for logical analysis, we would want to ensure that strings of symbols cannot at the same time be objects and valid syntactical expressions of that language.



For formal languages where no such ambiguity is allowed, there must always be a clear distinction between valid syntax and objects of the language, and so, in clearly defined formal languages, there will always be some method of distinguishing syntax and object, and special symbols are often used in the same way as the quotation marks were used above. Such symbols (or sequences of symbols) are called delimiters. By using delimiters, the same string of symbols can be either part of the syntax of the language, or, when enclosed by delimiters, an object. The delimiters maintain the distinction between the string as part of the normal syntax and as an object. Computer languages are examples of formal languages that use delimiters.


In terms of a meta-language and a sub-language, within the meta-language, every combination of symbols of the sub-language is an object - they are not part of the syntax of the meta-language. When delimiters are used, the symbol strings within the delimiters are effectively symbol strings of a sub-language, since as far as the meta-language is concerned, everything within the delimiters is an object.



Many philosophers like to use the terms ‘use’ and ‘mention’, where to ‘use’ a word or phrase is to use it as part of the syntax of the language, whereas to ‘mention’ a word or phrase is to refer to it as an object. In other words, when we ‘mention’ a word, we are referencing it by a meta-language, whereas when we ‘use’ a word, that means the word is part of the normal syntax of a language.






Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked (comments will be checked before appearing on this site). Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - this will only be used to notify you of replies to your comments - it will never be used for any other purpose, will never be displayed and does not require verification. Comments are common to the entire website, so please indicate what section of the site you are commenting on.


If you cannot see any comments below, it may be that a plug-in on your browser is blocking Disqus comments from loading. Avast anti-virus in particular is known to do this, especially with Internet Explorer and Safari. See Disqus Browser plug-in/extension conflicts or Why isn’t the comment box loading?.



Please wait for comments to load …  


The Lighter Side



There’s something about Gödel by Francesco Berto

There is a new addition to the page Yet another flawed incompleteness proof, where Berto’s proof of incompleteness in his book There’s something about Gödel comes under scrutiny.



Easy Footnotes

I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).



O’Connor’s “computer checked” proof

I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.



New page on Chaitin’s Constant

There is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.



Updated: Diagonal Lemma

Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.

Previous Blog Posts  


16th Mar 2015 Bishops Dancing with Pixies?


23rd Feb 2015 Artificial Intelligence


31 Mar 2015 Cranks and Crackpots


30 Apr 2015 The Chinese Room




For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem


– a page with general links:

Gödel Links


– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines


Printer Friendly


All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.

Note: for some browsers JavaScript must be enabled for this to operate correctly.




Comments on this site are welcome, please see the comment section.


Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.


If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.


Feedback about site design would also be appreciated so that I can improve the site.


Copyright © James R Meyer 2012 - 2016