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

# Glossary

## Lemma

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, … .

### Integers

The integers include the negative whole numbers: … -3, -2, -1, 0, 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, …

or

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,**, …

*s*0,*ss*0,*sss*0,*ssss*0,*sssss*0

### 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 ** ^{1}⁄_{10}** (a tenth)

0.01 in decimal notation means ** ^{1}⁄_{100}** (a hundredth)

0.001 in decimal notation means ** ^{1}⁄_{1000}** (a thousandth)

Similarly,

0.1 in binary notation means a half, which in the binary system is written as ^{1}⁄_{10}

0.01 in binary notation means a quarter, which in the binary system is written as ^{1}⁄_{100}

0.001 in binary notation means an eighth, which in the binary system is written as ^{1}⁄_{1000}

## 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, or enumeration, is often used to refer to a one-to-one correspondence to natural numbers, so that to say that a set can be ‘listed’ or ‘enumerated’ 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.

### Denumerable

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. (Footnote:
Real numbers are said to constitute an ordered field.
) 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 a 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.

### Exponent

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 **5 ^{9}**. This is also called raising

**5**to the

*of*

**power****9**.

### Algebraic numbers

An algebraic number is a solution to what is called a polynomial equation. An example of a polynomial equation is **6 x^{3} + 7x^{2}y + 3y -2**. The numbers multiplying the variables (

**and**

*x***in the example) may only be integers. Algebraic numbers can be real numbers, or they can be complex numbers, see below.**

*y*

### Transcendental numbers

A transcendental number is an irrational number that is not algebraic. The common examples are ** π** (Pi), which has a value of approximately 3.1416, and

**(Euler’s number) which has a value of approximately 2.7183. A transcendental number cannot be expressed in terms of finitely many rational numbers, but can be expressed in terms of infinitely many rational numbers.**

*e*

## Complex numbers

A complex number is the sum of two parts, a real number part and an “imaginary” number part.

An imaginary number is a number that is a multiple of the imaginary unit, where the imaginary unit is the square root of minus 1. It is usually indicated by the small italic letter ** i**. So, for example,

**7**is an imaginary number. For more information see Wikipedia - imaginary numbers and Wikipedia - the imaginary unit.

*i*

So, for example, **57.9 + 8.3 i** is a complex number. For more information, see Wikipedia - Complex numbers.

The original reason the term “imaginary number” was used was because there does not appear to be any physical distance that corresponds to such a number. Despite that, imaginary numbers have numerous useful applications in science and engineering.

## Transfinite Numbers

Transfinite numbers are numbers that are limitlessly large, but with the catch that some limitlessly large transfinite numbers can be larger than other limitlessly large transfinite numbers. If you think that’s absurd, then you probably aren’t alone, see Why do people believe weird things? Georg Cantor invented transfinite numbers in the late 19^{th} century (see Cantor’s invented transfinite numbers and Cantor’s religious beliefs and his transfinite numbers) and since that time, no useful application of these numbers has ever been found. For further discombobulation see Wikipedia - Transfinite numbers which tries to explain transfinite numbers as “numbers that are infinite in the sense that they are larger than all finite numbers, yet not necessarily absolutely infinite.” But for elucidation, see Cardinal Numbers on this website.

## Syntax

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.

### Delimiters

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. Generally this is achieved by the rules of the language which only allows certain combinations of symbols. Special symbols can be used in the same way as the quotation marks were used above and which indicate that the enclosed symbol combination is an object. Such symbols (or sequences of symbols) are called delimiters. By using such delimiters, the same string of symbols can be either part of the syntax of the language when not enclosed by delimiters, or when it is enclosed by delimiters, it is an object. In this way 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.

### Use-Mention

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 as an object (so effectively referring to it by a meta-language), whereas when we *‘use’* a word, that means the word is part of the normal syntax of a language.

## The Halting Problem

The Halting problem is the question whether there is a general method that can be applied to any computer program and determine whether a computer that is run with that program will stop (halt) or keep running indefinitely on a given input.

It has been determined that there can be no such general method, first demonstrated by Alan Turing in his paper On Computable Numbers…. See also The Halting Problem at the Brilliant web-site.

## Consistent System

A consistent system is a system that can never result in a contradiction; no matter how many times the rules of the system are applied, a contradiction can never arise.

Footnotes:

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:

Frivolous, irrelevant comments.

Comments devoid of logical basis.

Derogatory comments.

Long-winded comments.

Comments with excessive number of different points.

Questions about matters that do not relate to the page they post on. Such posts are not comments.

Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.

Reasons for deleting comments of certain users:

Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous usernames for one person.

Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.

Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.

Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

Note: a password enables editing of comments, an email enables notification of replies