The foundations of logic

The best way to think is to put one truth in front of the other and start again. The logical rules give us the means because they guarantee that we always move from truth to truth. If the premises are true, the conclusion of logical reasoning cannot be false, it is true and necessarily true. For example, the rule of detachment allows us to move from the two premises if A then B and A to the conclusion B. The premises are the starting points of our reasoning: axioms, definitions, hypotheses or observations. If they are true and if the logical rules are respected then the entire sequence of reasoning is necessarily true, all the steps up to the conclusion.

The composition of statements

A fact is determined by the attribution of a property to an individual or a relation between several individuals.

A concept is a property or a relation. A property, or quality or trait, is attributed to a being. A relation is between several beings. When a relation is between two beings, it can be considered to be a property of the couple. A relation between three beings is a property of the triplet, and so on for relations between more beings.

We can tell the facts by naming concepts and individuals. For example, Socrates is human is the statement of a fact. is human names the property of being human.

We form compound statements from statements of facts with logical connectors. For example, that all human beings are mortal can be stated by for all x, if x is human then x is mortal.

if then is the conditional. for all x is the universal quantifier. The conjunction and, the disjunction or, the negation not, and the existential quantifier there is an x such that are the other fundamental logical connectors.

All statements of a theory are composed from statements of facts with fundamental logical connectors.

The biconditional if and only if is defined from the conditional and the conjunction: A if and only if B equals by definition (if A then B) and (if B then A).

To avoid ambiguity it is often necessary to put parentheses. For example A and (B or C) is different from (A and B) or C.

Constants and variables

Names are constants or variables. A constant always names the same being. A variable names any individual that can be chosen from a domain of individuals, the domain of variation of the variable.

Let A(x) be a statement which contains the variable x and which contains neither for all x nor there is an x such that. We then say that the occurrences of x in A(x) are free.

The occurrences of x in for all x, A(x) are bound by the universal quantifier for all x. Likewise the occurrences of x in there is an x such that A(x) are bound by the existential quantifier. An occurrence of a variable is free if and only if it is not bound.

A(x) is the scope of the quantifier for all x in for all x, A(x), and of the quantifier there is an x such that in there is an x such that A(x). For an occurrence of a variable to be bound by a quantifier, it must be within its scope. In general, for reasons of clarity, it is forbidden for the same variable to have free and bound occurrences in the same statement, or for it to have bound occurrences in scopes of different quantifiers. But these prohibitions are not fundamental. The same variable can have free and bound occurrences, and occurrences bound by different quantifiers, in the same statement, without making it lose its meaning. The statements thus obtained are less clear, but accepting them simplifies the rules of composition of statements and the rules of deduction.

If A(x) contains for all x or there is an x such that, only free occurrences of x in A(x) are bound by the first for all x in for all x, A(x), and by the first there is an x such that in there is an x such that A(x).

Names can be simple or compound. Compound names are made from simple names with functions. Functions are also called operators. For example 1 is a simple name, the addition + is a function, 1+1 is a compound name. Compound names can be variable, x+y for example.

Functions are not always numeric. For example the father of is a function which associates the father of x with x.

A function can always be identified with a relation, therefore with a concept. A one-argument function f can be identified with the binary relation y = f(x). If it has two arguments, it can be identified with the ternary relation z = f(x, y). A function with n arguments can always be identified with a relation between n+1 terms.

A theory is always formulated with fundamental concepts and a domain of individuals, which is the domain of variation of the variables. If there are several kinds of individuals, we can always bring them together in a single domain and define bounded quantifiers: for all x, if x is of the kind K then and there is an x such that (x is of the kind K and are the universal and the existential quantifiers bounded by K. In for all x, if x is of the kind K then A(x) and there is an x such that (x is of the kind K and A(x)), A(x) is the scope of the bounded quantifiers.

A predicate is a statement that contains one or more free variables. A predicate A(x) with a free variable x is the name of a property: x has this property if and only if A(x). Likewise, a predicate with n free variables is the name of a relation between n terms. A concept can be defined in a theory if and only if it can be named by a predicate of this theory. Logic is also called the calculus of predicates, the calculus of concepts, the calculus of relations or the calculus of functions. A predicate A(x, ...) with n free variables defines a function with n arguments which to x, ... associates the true if A(x, ...) is true and the false if A(x, ...) is false.

Fundamental concepts and concepts defined from them are always named by constants. First-order logic only allows quantification on individuals, not on the concepts attributed to them. We can also state generalities about concepts with concept variables. We thus obtain higher order logics. But first-order logic is the most fundamental, because higher-order logics are always formulated from it, considering concepts as individuals and the attribution relation of a concept as a fundamental concept.

In this chapter, only first-order logic is explained, because it is the most fundamental logic.

The composition of truth

We can calculate the truth in a way that resembles calculating with numbers:

True and True = True

True and False = False and True = False and False = False

True or True = True or False = False or True = True

False or False = False

not True = False

not False = True

If True then True = If False then True = If False then False = True

If True then False = False

The truth of if A then B is only the falsity of A and not B. It does not depend on a particular relation of causality between the condition A and the consequence B. For example if it is day then 2+2=4 is always true whether it is day or not. Likewise for if 2+2=5 then it is day.

If we represent the true by 1 and the false by 0 then the conjunction is the multiplication:

1 x 1 = 1

0 x 0 = 0 x 1 = 1 x 0 = 0

Disjunction looks like addition:

0 + 0 = 0

0 + 1 = 1 + 0 = 1

except that 1 + 1 does not equal 1, while True or True = True.

When a statement contains one or more free variables, its truth is not determined, because the individuals named by the variables are not identified. All free variables must be bound, or replaced by constants, for the truth of a statement to be determined.

For all x, A(x) is true if and only if all statements A(a) where a is a constant chosen in the domain of the variable, are true.

There is an x such that A(x) is true if and only if there is a constant a chosen in the domain of the variable such that A(a) is true.

A(a) is the statement obtained by substituting a for all free occurrences of x in A(x).

For all x, A(x) looks like an infinite conjunction, the conjunction of all statements A(a) where a is a constant in the domain of the variable.

There is an x such that A(x) looks like an infinite disjunction, the disjunction of all statements A(a) where a is a constant in the domain of the variable.

The rules of truth composition show that the truth of statements composed with logical connectives is always determined by the truth of the component statements.

When we state a law by leaving its variables x, y, A free, we must understand that they are bound by universal quantifiers, for all x, for all y, for all A, otherwise the truth of the law is not determined.

The fundamental rules of deduction

A reasoning resembles a construction game. We compose statements from those we already have, or on the contrary, we extract a component from a composed statement.

For each logical connector, we have two fundamental rules of deduction. One introduces the logical connector by allowing a statement to be composed, the other eliminates the connector by allowing a statement to be decomposed. For example, the detachment rule is the rule of elimination of the conditional.

By definition of a logical consequence, a statement is a logical consequence of premises if and only if it is impossible for it to be false if the premises are true. The fundamental rules of deduction allow us to find all logical consequences of all finite lists of premises.

The rules of deduction are stated with statement variables A, B, C. These rules must be understood as if the free variables were bound by universal quantifiers: for all statement A, for all statement B, for all statement C .

Some rules are particularly simple:

B is a logical consequence of the two premises A and if A then B.

A and B is a logical consequence of the two premises A and B.

Both A and B are logical consequences of the single premise A and B.

Both A or B and B or A are logical consequences of A.

C is a logical consequence of the three premises A or B, si A alors C and si B alors C.

A is a logical consequence of not not A.

The principle of reduction to absurdity allows us to conclude that a hypothesis is false if it leads to a contradiction:

If B and not B are both logical consequences of premises P and A then not A is a logical consequence of premises P.

Premises P are any finite list of premises, including the null list: no premises.

The rule for introducing the conditional allows us to incorporate a hypothesis into the conclusion:

If B is a logical consequence of premises P and A then if A then B is a logical consequence of premises P.

The rule of elimination of the universal quantifier makes it possible to apply laws to particular cases:

A(a) is a logical consequence of for all x, A(x).

a is a constant, a variable, or a variable compound name. A(a) is obtained by substituting a for all free occurrences of x in A(x).

The rule for introducing the existential quantifier allows us to prove existence by example:

There is an x such that A(x) is a logical consequence of A(a).

a is a constant, a variable, or a variable compound name. x is a variable which has no free occurrence in A(a). A(x) is obtained by substituting x for one or more occurrences of a in A(a), not necessarily all.

The rule for introducing the universal quantifier makes it possible to generalize to all cases which satisfy the same conditions:

If A(x) is a logical consequence of premises P in which the variable x has no free occurrence then for all x, A(x) is a logical consequence of premises P.

For example, if B(x) is a logical consequence of premises P and A(x) then if A(x) then B(x) is a logical consequence of premises P. If x has no free occurrence in the premises P then for all x, if A(x) then B(x) is a logical consequence of the premises P.

The rule for eliminating the existential quantifier allows us to introduce a new constant:

A(a) is a logical consequence of there is an x such that A(x).

a is a new constant. It should not be mentioned in earlier stages of reasoning. A(a) is obtained by substituting a for all free occurrences of x in A(x).

When A(a) is a logical consequence of premises P which do not mention a, it is always necessary to specify whether a is a new constant or a variable. If a is a constant we can only use it to prove the existence: there is an x such that A(x). If a is a variable, we can also use it to prove the generality: for all x, A(x).

The twelve preceding rules make it possible to find all the logical consequences if they are supplemented by the following three:

A is a logical consequence of A.

If A is a logical consequence of premises P then A is a logical consequence of premises P and B.

The rule of transitivity of logical consequences: if A is a logical consequence of premises P and if all premises P are logical consequences of premises Q then A is a logical consequence of premises Q.

That these fifteen rules are sufficient to find all logical consequences of all finite lists of premises is a consequence of the completeness theorem of first-order logic, proven by Kurt Gödel in his doctoral thesis in 1928.

In these fifteen rules, A, B, C are variables whose domain of variation is the set of all statements correctly formed with the concepts of a theory, fundamental or defined from fundamental concepts, and the logical connectors, fundamental or defined from fundamental logical connectors. A(x) is also a variable whose domain of variation is the set of all correctly formed statements, which may or may not contain the variable x. x is a variable whose domain of variation is the set of all variable names of individuals. a is a variable whose domain of variation is the set which contains all constants of individuals, all variable names and all the variable compound expressions, for the individuals of a theory. P and Q are variables whose domain of variation is the set of all finite lists of correctly formed statements, the empty list included.

The truth of the fifteen fundamental rules of deduction is obvious. It can be proven immediately from the truth composition rules for logical connectives. It results from the definitions of logical connectors and of the logical consequence relation.

From the fundamental rules, one can prove all the derived rules, which also state obvious logical consequence relations.

A proof must always show that it is a proof. For reasoning to be logically correct, it must be obviously logically correct. It is necessary that for each statement, an obvious rule, fundamental or derived, shows that this statement is a logical consequence of the premises on which it depends.

We can formulate all theories without requiring constants of individuals and functions. A function with n arguments is replaced by the relation between n+1 terms which is equivalent to it. A constant of individual is replaced by the property of being that individual. Individuals are always named by variables. The rule of elimination of the existential quantifier is:

If the variable x has no free occurrence in B then B is a logical consequence of the two premises for all x, if A(x) then B and there is an x such that A(x).

Logically possible worlds

We define a theory with fundamental concepts, a domain of individuals, axioms and definitions. The domain of individuals is the domain of variation of the variables. Definitions define new concepts from fundamental concepts or concepts already defined from fundamental concepts. Axioms are the fundamental laws that give us the means to reason with fundamental concepts and those defined from them. The theorems of the theory are the logical consequences of its axioms and definitions.

An atomic fact is determined by the attribution of a fundamental property to an individual or of a fundamental relation between several individuals.

A logically possible world is a set of atomic facts. A logically possible world can also be called a world, for short.

An atomic statement states an atomic fact. An atomic statement is true in a world if and only if the atomic fact it states is an element of this world.

Once the truth of atomic statements is determined, the truth of all statements composed with logical connectives and fundamental concepts, or concepts defined from fundamental concepts, is also determined.

When all the axioms of a theory are true in a world, that world is possible according to the theory. A model of a theory is a possible world according to that theory.

Any set of atomic statements determines a logically possible world in which they are all true. A set of atomic statements cannot be contradictory because atomic statements do not contain negation. If there is no negation, there cannot be any contradiction.

Logical laws

Logical laws can be defined in two equivalent ways:

• A statement is a logical law if and only if it is true in all worlds.

• A statement is a logical law if and only if it is the conclusion of logical reasoning without hypothesis.

“All worlds” in the first definition means all logically possible worlds that can be defined with the concepts of the statement.

The conclusion of logical reasoning can be hypothesis-free because the principle of reduction to absurdity and the rule for introducing the conditional make it possible to free their conclusion from dependence on a premise.

The equivalence of these two definitions results from the completeness theorem of first order logic. It has an intuitive justification: hypotheses select the worlds where they are true among all possible worlds. If there are no hypotheses, there is no selection. A law which does not depend on any hypothesis must therefore be true in all worlds. And if our logic is complete, it must enable us to find all the laws true in all worlds by finding the conclusions of reasoning without hypothesis.

Logical laws are unconditioned, absolute, categorical, anhypothetical truths, because they do not depend on any conditions. They are also called tautologies. They are necessary truths. They cannot be false. They cannot not be true.

A statement is logically necessary if and only if its negation is not logically possible.

A statement is logically possible if and only if it is true in at least one world.

Logical laws are logically necessary statements.

The deduction theorem: if A then B is a logical law if and only if B is a logical consequence of A.

Proof: if B is a logical consequence of A then if A then B is a logical consequence of the absence of hypothesis, according to the rule of introduction of the conditional, therefore a logical law. Conversely, if if A then B is a logical law, both A and if A then B are logical consequences of A, therefore B is a logical consequence of A, according to the rule of detachment and the rule of transitivity of logical consequences.

If B is a logical consequence of A then it is not logically possible for A to be true without B also being true, because the truth of if A then B is the falsity of A and not B. The logical consequence relation is therefore an infallible guarantee that we always move from truth to truth.

A finite list of premises is always equivalent to its conjunction. The relations of logical consequence are therefore always equivalent to logical laws: A is a logical consequence of the premises P if and only if if the conjunction of the P then A is a logical law.

Pure tautology if A then A is a logical law, because A is a logical consequence of A. The definition of the biconditional and the rule of introduction of the conjunction show that A if and only if A is also a logical law.

The law of no contradiction not(A and not A) is a logical law, according to the rule of elimination of conjunction and the principle of reduction to absurdity.

The law of the excluded middle A or not A is a logical law.

Proof: A or not A and not(A or not A) are both logical consequences of A and not(A or not A), according to the rule of introduction of the disjunction. not A is therefore a logical consequence of not (A or not A), according to the principle of reduction to absurdity. A or not A and not(A or not A) are therefore both logical consequences of not(A or not A), according to the rule of introduction of the disjunction. not not (A or not A) is therefore a logical law, according to the principle of reduction to absurdity. A or not A is therefore a logical law, according to the rule of elimination of double negation.

For any statement A, either A is true or A is false, but there is no third possibility: the middle is excluded. This law is true because it has been assumed that all statements are correctly formed from fundamental concepts, or concepts defined from them, with logical connectors. There is therefore no ambiguity about the meaning of A. But if a statement does not have a determinate meaning then it is not true, but it is not false either, because its negation does not have a determinate meaning.

A theorem reveals that individuals reveal the universal

In a theorem individuals are identified by constants. In general these constants are fundamental constants, mentioned in the axioms, or defined constants, identified by a definition. Let a be a constant mentioned in the theorem T(a) and A(a) the conjunction of the axioms and definitions of which T(a) is a logical consequence. If A(a) then T(a) is a logical law. For all a, if A(a) then T(a) is also a logical law. When we mention the conditions on which it depends, a constant can always be considered a variable. For example, if T(π) is a theorem about the number π, then for all π, if π is the quotient of the circumference of a circle by its diameter then T(π) is also a theorem.

Theorems about an individual reveal properties and relations that necessarily result from the conditions on which that individual depends. Any individual which satisfies the same conditions necessarily has the same properties and the same relations. An individual is always an example for universal truths. These truths are universal, because they are necessary.

The rule of elimination of the existential quantifier makes it possible to introduce new constants, which are not mentioned in the axioms and definitions. If a theorem T(a) contains a constant a which is not mentioned in the conjunction A of the axioms and definitions of which T(a) is a logical consequence, then if A then there is an a such that T(a) is a logical law. Even then, a theorem reveals that an individual reveals the universal, because it reveals that an individual reveals a universal possibility.

For a theory to reveal universal possibilities, it is necessary and sufficient that it is not contradictory. A contradiction is a conjunction of a statement and its negation. A theory is contradictory if and only if a contradiction is a logical consequence of a conjunction of its axioms. A theory that is not contradictory is coherent, or consistent.

The completeness theorem of first order logic is equivalent to the following statement:

A theory is coherent if and only if it has a model.

More precisely, a finite or countably infinite set of axioms is coherent if and only if it has a countable model. A set is countable if and only if all its elements can be numbered by natural numbers.

A model is a world in which all the axioms of the theory are true. It is a possible world whose existence is authorized by the universal laws of the theory, it is therefore a universal possibility.

A theory of all theories

A metatheory is a theory that focuses on one or more theories. First order logic is a theory of all theories. It is a universal metatheory.

A theory of all theories is necessarily a theory of itself, since a metatheory is a theory.

First-order logic is its own metatheory. When we prove that the rules of first order logic are true and that they are sufficient to find all logical laws, we use first-order logic. Should we see a vicious circle?

A false theory can prove itself to be true, since it can prove falsehoods. If first-order logic were false, then it could still prove that it is true. That it proves that it is true therefore does not distinguish it from a false theory. Should we conclude that the proofs it gives that it is true are worthless?

Just look at the proofs. The proofs of the truth of the fundamental rules of deduction are immediate, very clear, obvious and irrefutable. They simply result from the definitions of the logical consequence relation and of logical connectors. They leave no room for doubt.

A false theory that proves its own truth is very different from first-order logic, because a false theory always reveals its falsity in one way or another, whereas first-order logic always reveals the truth.

The truth of first-order logic is obvious, because it is a theory of statements, and because it attributes obvious properties and relations to them. The truth of the existence of statements does not pose any difficulties. A statement is an audible form that can be spoken by a speaker, or a form that can be written on a piece of paper. Statements exist because speakers and written records exist or can exist. The concepts that logic attributes to statements are also obvious: is a statement atomic or compound? If it is compound, what is its first logical connector? What is or are the statements connected by this logical connector? If it is atomic, what is the fundamental concept? What is or are the individuals to which this concept is attributed? Is an occurrence of a variable free or bound? To know whether a statement is a logical consequence of other statements, it is enough to reason about such obvious properties and relations. We can thus be sure that our premises are always true, and if we respect logic, we are then sure that our conclusions are also true.

First-order logic is one of our best tools for recognizing knowledge because it provides the means to recognize the logical correctness of all reasoning. It is fundamental for all universal devices for observing knowledge. It is like a sun which reveals to all minds all the truths accessible by the power of reasoning.

The world of all worlds

Let D be a domain of individuals, C a list of fundamental concepts, and F the set of all atomic facts determined by the concepts of C attributed to the individuals of D.

A set y is a part of a set x if and only all elements of y are elements of x. A part of x is included in x. It is a subset of x.

A part of F is a logically possible world defined with the concepts of C and the individuals of D.

The set P(F) of parts of F is the set of all logically possible worlds defined with the concepts of C and the individuals of D.

When the fundamental concepts and the domain of individuals are determined, P(F) is the world of all worlds.

If the domain of individuals and the list of fundamental concepts are finite or countably infinite, then the set of all atomic facts F is also finite or countably infinite.

The set of parts of a countably infinite set is infinite but is not countable. This is a theorem proven by Cantor.

If the set F of atomic facts is countably infinite, we can represent the set P(F) of all worlds with an infinite binary tree:

If we have numbered all the atomic facts, each infinite branch of the tree, starting from its root, represents a possible world: the atomic fact number n is an element of this world if and only the segment number n of this branch is green. A segment is a direct line between two nodes. The root of the tree is the lowest node. The segments of a branch are numbered starting from the root.

We can see this infinite binary tree, we can therefore see all its branches, we can therefore see the set of all its branches, we can therefore see an infinite uncountable set which represents the world of all worlds.

Complement: Cantor's theorem

There is not any one-to-one function between a set and the set of its parts.

A one-to-one function (or a bijection) is a function that can be reversed:

A function f from E into F is one-to-one between E and F if and only if E is the domain of definition of f and if for all y in F there is a unique x in E such that y = f(x).

If there is a one-to-one function between two sets, they have exactly the same number of elements, because we can marry each element of one with an element of the other.

A set E is countably infinite if and only if there is a one-to-one function between E and the set of natural numbers.

The proof of Cantor's theorem is by reduction to absurdity: suppose that there is a one-to-one function f between a set E and the set P(E) of its parts. Let A be the set of all elements x of E such that x is not an element of f(x). A is an element of P(E). Let a be the element of E such that A = f(a). Is a an element of A? By definition of A, a is an element of A if and only if a is not an element of A. This leads to a contradiction: a is and is not an element of A. Therefore the initial hypothesis is false.

A corollary of this theorem is that the set of parts of a countably infinite set is not countable.