In maths the term is used in two related but distinguishable senses: "logical axioms" and "non-logical axioms". In both senses, an axiom is any mathematical statement that serves as a starting point from which other statements are logically derived. Unlike theorems, axioms (unless redundant) cannot be derived by principles of deduction, nor are they provable since they do not follow from any other axiom or theorem derived from an axiom.

Logical axioms are usually statements that are taken to be universally true (e.g., A and B implies A), while non-logical axioms (e.g.,) are defining properties of a group of mathematical objects. In general, a non-logical axiom is not a self-evident truth, but rather a property used build a mathematical theory. To axiomatize a system of knowledge is to show that its claims can be derived from a complete, self consistent set of sentences (the axioms).

There are typically multiple ways to axiomatize a given system. In arithmetic, one set of axioms are the Peano axioms. These are the most widely used axiomatization of first-order arithmetic. They are a set of axioms strong enough to prove many important facts about number theory and logic and they allowed Gödel to establish his famous second incompleteness theorem.

We have a language1where 0 is a constant symbol,is a unary function and the following axioms:

- or anyformulawith one free variable.

The standard structure iswhereis the set of natural numbers, is the successor function and 0 is naturally interpreted as the number 0.

]]>One way Church's Thesis can be formally stated is by the schema:A number-theoretic function is computable if there is an algorithm, or mechanical procedure, that computes it. The procedure should specify what is to be done at each step, as a function of the input only, without involving any creativity on the part of the agent. Computability is an informal, or pre-formal, notion in that it has meaning independently of, and prior to, its formal development.

A function is recursive, for example, if its values can be derived from a fixed set of equations in a certain form. It is reasonably clear that every recursive function is computable, since an algorithm can be ‘read off’ a recursive derivation or a Turing machine. Church's thesis is the assertion that a function is computable if and only if it is recursive, Turing-computable, etc.

Formally we may write

Where the variablesrange over the natural numbers, andis any predicate. This schema asserts that, if for everythere is asatisfying some predicate, then there is in fact anwhich is the Gödel number of a general recursive function which will, for everyproduce such a y satisfying that predicate. (T is some universal predicate which decodes the Gödel-numbering used.)

The thesis is incompatible with classical logic. For instance, it is a classical tautology that every Turing machine either halts or does not halt on a given input; but if that were true, then from Church's Thesis one would conclude that there is a general recursive function which solves the halting problem. This is impossible.

]]>"The moon is round" is a declarative sentence.

Other sentences can be

interrogative, asking a question: “Is the moon a balloon?”

exclamatory: “There goes that green girl!”

or imperative, expressing the need to do something: “Drop the bomb on Washington”.

Logic is full of declarative sentences that must be either proved or disproved if possible. Not all declarative sentences can be proved or disproved. “It is right” cannot be proved or disproved since it is not clear what is being referred to. “Isosceles triangles have two equal sides” can be proved. If a declarative sentence can be proved or disproved it is called a declarative statement. “It is right” is not a declarative statement but “Isosceles triangles have two equal sides” is a declarative statement.

Every declarative statement has a truth value (1 or T if it is true and 0 or F if it is false). Sentences can be combined into arguments and truth values manipulated using Boolean Logic or truth tables to prove or disprove entire arguments on a rigorous manner.

]]>If John committed the murder, then he was in the victim's apartment and did not leave before 11. John was in the victim's apartment. If he left before 11, then the doorman saw him but it is not the case either that the doorman saw him or that he committed the murder.

Define the statements:p: John committed the murder.

q: John was in the victim’s apartment.

r: John left before 11.

s: The doorman saw him.

The first sentence becomes(1)

The second sentence becomes q (2)

The third sentence becomes(3)

We construct two truth tables – one for each of (1) and (3)

The first is

1 |
0 |
1 |
0 |
0 |
1 |

1 |
1 |
1 |
1 |
1 |
0 |

1 |
0 |
0 |
0 |
0 |
1 |

1 |
0 |
0 |
0 |
1 |
0 |

0 |
1 |
1 |
0 |
0 |
1 |

0 |
1 |
1 |
1 |
1 |
0 |

0 |
1 |
0 |
0 |
0 |
1 |

0 |
1 |
0 |
0 |
1 |
0 |

The second is

1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |

0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |

1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |

0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |

1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |

0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |

1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |

0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |

Examination of the tables gives that the statements are consistent ifand

]]>Some sets which are 'obviously' not enumerable turn out to be, and also surprisingly, sets whih are larger or smaller than setn , containing setn as a proper subset, or a proper subset of setn , turn out to be capable of being put into a one to one correspondence with elements of setn , so are in a very real sense, the same size as setn .

The set of even numbers E can be put into a one to one correspondence with elements of setn .

Ifthen there existsand there is one such element offor each and every element ofand vice versa so the mapping

with

is a one to one mapping fromto

Much more surprisingly, the set of rational numbers (fractions) is enumerable. There are many more rational numbers that natural numbers since every natural number can be written as a fraction, but not vice versa. To demonstrate enumerability, construct the table shown below.

With natural numbers in the margins, start in the upper left hand corner and work diagonally. The first rational number isthe second isthe third isthe fourth isand so on. Every rational number appears somewhere is the table (the rational numberappears at positionin the table) so the rational numbers are enumerable.

]]>A sentence in first-order logic is written in the form P(x), where P is the predicate and x is the subject, represented as a variable. Complete sentences are logically combined and manipulated according to the same rules as those used in Boolean algebra.

In first-order logic, a sentence can be structured using the universal quantifier (symbolized) or the existential quantifier (). Consider a subject that is a variable represented byLet A be the predicate "is an pear," F be the predicate "is a fruit," S be the predicate "is soft"', and M be the predicate "is green." Then we can say

which translates to "Every x that is a pear is a fruit is a pear."

We can also say such things as

which says that “there exists a fruit x that is also a pear.

which says that “there exists a pear x that is soft.”

which says that “there exists a pear that is green.”

First order logic gives rise to statements that in general can be proved to be always true (tautologies), true in certain circumstances or never true. For example(meaning for all eitheror notimplies)is always true and)meaning for alland notimplyis never true

First-order logic can be useful in the creation of computer programs. It is also of interest to researchers in artificial intelligence (AI). There are more powerful forms of logic, but first-order logic is adequate for most everyday reasoning. The Incompleteness Theorem , proven in 1930, demonstrates that first-order logic is in general undecidable. That means there exist statements in this logic form that, under certain conditions, cannot be proven either true or false.

]]>Example:

Bothandare bound variables in this statement. We could changeforandfor throughout to obtain the statementThe meaning of the stament does not change – the statement says that addition is commutative.

Example:

Ifis a natural number thenis even.is a bound variable here andis a free variable.

Example:

Nothing can be substituted fororso both variables are bound.

A variable can be both bound and free in the same expression.

The first and fifth occurrences ofare free and the others are bound.

]]>The first states:

In any consistent axiomatic system (formal system of mathematics) sufficiently strong to allow one to do basic arithmetic, one can construct a statement about natural numbers that can be neither proved nor disproved within that system.

An axiomatic system is one with a recursive set of axioms; equivalently, the theorems of the system can be generated by a Turing machine. The statement which cannot be proved nor disproved within the system is furthermore true in the sense that what it asserts about the natural numbers in fact holds. Because the system fails to prove a true statement, it is said to be incomplete. In other words, Godel's first incompleteness theorem says that any sufficiently strong formal system of mathematics is either inconsistent or incomplete.

Godel's second incompleteness theorem, which is proved by formalizing part of the proof of the first within the system itself, states:

Any sufficiently strong consistent system cannot prove its own consistency.

In essence, the proof of the first theorem consists of constructing the statement

- p = "This statement cannot be proven"

within a formal axiomatic system. As such, it can be seen as a modern variant of the Liar paradox.

If the axiomatic system is consistent, Godel's proof shows that p (and its negation) cannot be proven in the system. Therefore p is true (p claims not to be provable, and it isn't) yet it cannot be formally proved in the system.

For the second theorem, let p stand for the undecidable sentence constructed above, and assume that the consistency of the system can be proven from within the system itself. We have seen above that if the system is consistent, then p is not provable. The proof of this implication can be formalized in the system itself, and therefore the statement "p is not provable", or "not P(p)" can be proven in the system.

But this last statement is equivalent to *p * itself (and this equivalence can be proven in the system), so *p * can be proven in the system. This contradiction shows that the system must be inconsistent.

Is it even possible to write a comprehensive, bug free programming language?

No it is not. The reason is bevause of one of the most fundamental theorems in logic - Godel's Incompleteness Theorem, which states, 'There is no complete consistent system of first order logic'. It follows that any system derived from first order logic - for example a programming language - cannot be complete - able to carry out any calculation - and consistent. The same logic can be applied to languages. No language can be both completely descriptive and consistent.]]>

The statementmeans that all all objects for all objects with some property, then every individual object has the property.

More precisely, suppose that X is a set of declarative sentences including the sentenceand suppose D is a designator which occurs in a sentence in X. Suppose thatis the sentence obtained by putting D in place of every free occurrence of 'x' in %phi then X thereforeis a valid argument.

Suppose X is the set consisting of the two statements

(1)

Uranium is an element (2)

We may taketo be the statementand D to be 'Uranium' thenis the statement(3)

Therule then states (1) and (2) imply (3).

The statementmeans that you can never create an inconsistency by naming a thing provided the name is not already used for something else.

More precisely suppose that X is a set of declarative sentences among which is a sentence of the formand suppose D is a proper name which occurs somewhere in X. Suppose that that is the sentence got by putting D in place of every free occurrence of 'x' inThencan be added to X without creating an inconsistency.

Suppose X is the set consisting of the three statements:

TheRule states that if X is consistent then so is the set Y consisting of X together with the sentenceIn fact X is inconsistent.

]]>