Logic & Proofs

Our first objective is to see the most important logical constructions in the natural language when applied to both everyday matters and mathematics. We are well aware that the backbone of our everyday speech is formed by statements (also known as declarative sentences). These do declare or state something unlike interrogative sentences, which pose a question, or imperative ones, those are to persuade you to do something. For example,

The quick brown fox jumps over the lazy dog

is an example of a statement. Another one is

Today is Thursday and 2 + 3 equals 5.

Most basically, some statements are true and all the others are false. Grammatically, you can pose a general question to a statement (Does the quick brown fox jump over the lazy dog? ), whose required answer labels the statement either as true (Yes, it does) or as false (No, it doesn’t). The distinction between true and false is very well known while being one of the hardest to define.

Example: It is true that 2 + 3 equals 5, as far as the arithmetic holds true and we understand the numbers correctly. It depends on the current date whether today is Thursday. It is still not known to the science if each perfect1 number is even.

The sentence this sentence is true can be either true or false without a contradiction but there hardly is a way to check which possibility takes place. The sentence this sentence is false can be neither true nor false, for either assumption leads to a contradiction: if the statement is true, then it must be false as it says, etc.

Hence, our ‘most basic’ analysis is far from being exhaustive. Nevertheless, neither unsolved mathe-matical problems nor artificial self-referential examples can prevent us from gaining command of logic.

The reason for that is that we are going to study just well-behaved models of real-world sentences.

We reserve the name ‘statements’ for such models and reiterate that every statement is either true or false but not both.

Some statements are compound, which means they are composed of one or more simpler statements. E.g., 2 equals 3 or 1 equals 1; it is not the case that 2 equals 1; somebody believes that 2 equals 3.

Let us consider the constructions able to produce compound statements, such as . . . or . . . , . . . but . . . , if . . . then . . . , it is not the case that . . . , somebody believes that . . . , etc. Any such construction is called a (logical) connective if the truth of the compound statement depends exclusively on which of the simpler statements are true.

Example: When is it the case that A or B is true (where A and B stand for some arbitrary statements)? If and only if at least one of the statements A and B is true. So, . . . or . . . is a logical connective. Yet each student knows that . . . is not. Indeed, one can consider the statements ∅ = ∅ and π < 3.14159265358979323847. Both are true, whereas each student knows that ∅ = ∅ is likely true and each student knows that π < 3.14159265358979323847 is likely false. That is, a statement’s A being true does not suffice to make the statement each student knows that A either true or false.

We call a statement a (logical) atom, if it cannot reasonably be split into simpler ones using logical connectives. So, 2 equals 3 or 1 equals 1 is not an atom, yet 2 = 3 and somebody believes that 2 equals 3 are.

Now, we are going to fix the traditional meaning of the most important connectives found in mathematics. The meaning of a connective is nothing more than the way the compound statement’s truth depends on the truths of its parts. From now on, we will use letters to denote arbitrary statements: e.g., A and B; if A then B. We will use 1 for truth and 0 for falsity. So we obtain the following truth table.

There are plenty of constructions in natural languages which can be seen as logical connectives. In general, this costs them a part of their meaning. (Is it true that 0 = 0 although 1 = 1?) The following tables show a few roughly equivalent ways to present basic logical connectives in English as well as the logical symbols and common names for the latter.

Equivalences, tautologies and valid arguments.

Suppose we have two statements F and G built from some simpler statements (A_1), . . . , (A_n) using logical connectives. (We will use the notation like F((A_1), . . . , (A_n)) then.) The statements F and G are (logically) equivalent if (and only if) they are both true or both false, whatever truth values the statements (A_1), . . . , (A_n) have. We shall write F ≡ G in this case.

The statement F built from (A_1), . . . , (A_n) is a tautology if it is true for any truth values of (A_1), . . . , (A_n). Tautologies can be understood as laws of logic.

Arguments.

Naturally, when making an argument we make some assumptions firstly, and then draw a conclusion. We hope that the conclusion is always true whenever all our assumptions are true (our statements may be true or false depending on situation, whence this ‘always’ comes). In such a case, the argument is called valid. (One can equivalently put it this way: it is never the case that all the assumptions are true whereas the conclusion is false.) Consider the following argument:

Today is Thursday. It rains every Thursday. Therefore, 3 = 1 + 2.

It is not very convincing despite the fact the conclusion is known to be always true (while it depends on today’s date whether the first assumption is true). Moreover, as the conclusion is known to be true, the argument is useless. Let us modify it a little:

Today is Thursday. It rains every Thursday. Therefore, it is raining today.

This is much better, although both the assumptions and the conclusion are quite doubtful and still depend on what day it is today. The conclusion is now guaranteed to be true whenever the assumptions hold true. If they do not, all bets are off, indeed. This guarantee holds always, everyday, for whatever situation. We need know nothing about the truth values of those statements in any particular situation to be sure that the conclusion is no less true than the assumptions and new errors are thus impossible.

One can render this argument into symbols as follows:

(T∧(T→R)) → R

where T means ‘today is Thursday’ and R means ‘it is raining today’. (Please notice the model: if the assumptions are (A_1), . . . , (A_n) and the conclusion is C, we construct the formula ((A_1)∧. . .∧(A_n)) → C). It is easy to see that the resulting statement is a tautology. In general, an argument is valid if the respective statement is a tautology (but the converse is not necessary).

The Language of Mathematics

Now, let us try to discover some inner structure in logical atoms. Let us split the atoms! As every atom is an indicative sentence, a rudimentary linguistic analysis suggests that each such sentence should have its subject and predicate. Basically, the predicate is what is being said and the subject is what it is being said about. For example, in the sentence

The quick brown fox jumps over the lazy dog,

‘the quick brown fox’ can be seen as the subject while ‘jumps over the lazy dog’ as the predicate. We can change our sentence a bit:

The slow gray cat jumps over the lazy dog.

Here the same predicate is said about another subject. In general, we see that the expression

x jumps over the lazy dog

turns into a statement when one replaces its part x (which is called a variable for it varies) with the name of a reasonable thing. Neglecting the grammatical terminology, the expression

x jumps over y

which turns into a statement when substituting some names for the variables x and y, can also be called a predicate. The former predicate contains just one variable and is thus called unary, while the latter one is called binary for it has two distinct variables. Likewise, we can speak about an n-ary predicate with variables (x_1), . . . , (x_n).

In general, a predicate (or property) is an expression which turns into a statement (either true or false) after one substitutes some reasonable object names for all its variables. Each statement can be looked upon as a 0-ary (nullary) predicate.

The following expressions are typical predicates: x is even, x is greater than y. They turn into statements (e. g., 4 is even, 3 is greater than 7) if we substitute numbers for variables. On the other hand, the predicate x is a son of y can be turned into a statement when substituting human names.

It is natural to associate a domain with a predicate, whence the objects are taken from. For example, the domain of the predicate x is even could be natural or integer numbers, while the same domain choice does not make much sense for x is a son of y.

One can easily construct new predicates from some given ones applying logical connectives. E. g., x is even and it is not the case that y is greater than x. But there is a more interesting way to do so. Namely, it is possible to express some meaning about the whole domain: there is some x such that x is even; all x are even; there are many x which are even; there exists a unique even x; most of x are even; there are infinitely many x being even, etc.

Such constructions are called quantifiers. A quantifier binds some variable in a predicate so that it is no more available for a substitution (such a variable is called bound; otherwise it is still free). Indeed, the predicate either x is even or x is odd may be turned into the statement either 7 is even or 7 is odd, while the expression for each 7, either 7 is even or 7 is odd does not make much sense.

Among many conceivable quantifiers, two are the most important. These are the existential quantifier there exists some x such that. . . and the universal quantifier for each x it holds that. . . . We will sometimes write A(x) for a predicate A with a variable x (like x is. . . , x does. . . , etc.). For example, one can write even(x) instead of x is even; here A itself can be expressed by words as to be even.

Let us translate some English phrases into logical symbolism. All roses are red. In order to translate this one, we need predicates of redness and ‘roseness’, that is, Rs(x) will stand for x is a rose and R(x) for x is red. The domains for these predicates must be chosen reasonably, say as ‘all flowers’ or even ‘all the real things’. Then our phrase is rendered as ∀x (Rs(x) → R(x)). Please notice the implication here: we are effectively asserting that x is red—yet under a condition: namely, that x is a rose. We are saying nothing about objects which are not roses, nor we are asserting anything to be a rose.

No rose is red. This one may sound as an equivalent to the negation of the previous one but it is far from that. There are a few (equivalent) ways to put this into symbols: ∀x*(Rs(x)→¬R*(x))(everything being a rose is not red ), ¬∃x:(Rs(x)∧R(x)) (it is not the case that there is something being both a rose and red), ¬∃x:(R(x)∧R(x)), ∀x*(R(x)→¬Rs(x)) (everything red is not a rose).

Observe that “on a distant planet” where no rose exists, both ∀x(Rs(x)→R(x)) and ∀x(Rs(x)→¬R(x)) would be true since the implication’s assumption Rs(x) would fail for every x from that planet, which would make both implications true. So, these two formulas do not negate each other.

But how can one translate the negation of the first phrase? ¬∀x*(Rs(x)→R(x)), of course, or ∃x:(Rs(x)∧¬R(x)) equivalently (there is something being a rose but not red). These transformations under negation are not at all complicated: they are governed by few simple laws (see below).

Some quantifiers can be expressed via others. E.g., ∃x:A(x) is usually considered to be equivalent to ¬∀x*(¬A(x)) (‘some x satisfies the property A if and only if it is not the case that the property A fails for every x’), and dually, ∀x(A(x)) can be seen equivalent to ¬∃x(¬A(x)). If we have equality at our disposal, we can express there exists a unique such x that A(x) as ∃x:(A(x)∧∀y*(A(y)→y=x(A(x)))).

In general, two predicates are (logically) equivalent if they hold (or do not) ‘simultaneously’. It is a too big task for us now to make this ‘definition’ precise. Thus, we have ∃x:A(x)≡¬∀x(¬A(x)) and ∀x(A(x)).