Logic: Overview – Foundations of Mathematics

Quando orientur controversiae, non magis disputatione opus erit inter duos philosophos, quam inter duos Computistas. Sufficiet enim calamos in manus sumere sedereque ad abacos, et sibi mutuo dicere:

Calculemus!

When controversies arise, there will be no more need for debates between two philosophers than there is between two computers. It will be enough for them to take their pencils into their hands, sit at their abaci, and say to each other:

Let's compute!

Gottfried Leibniz

Logic is the business of writing down our reasoning in such a way that anyone who comes along can think what we thought, in a way that unambiguously compels assent. It is a useful tool across mathematics (why we learn it as part of this course) and a field of mathematical study in its own right, with applications to computer science and engineering, linguistics, and philosophy.

In some sense, logic is just a way of encoding ordinary argumentation. Though some facts about logic seem counterintuitive, we will see that, once we decide that we care about whether sentences are true or false, and that a few basic operations behave the same way they do in ordinary rhetoric, there is really no other option. We must accept the counterintuitive results along with the intuitive ones, and reject some of our intuitions. This theme of being able to formalize some, but not all, of our intuitions is a common one across mathematics.

What we'll learn in this class is only a piece of "propositional logic" and "predicate logic", which in turn is only a piece of the branch of mathematics that is logic.

Besides the statement-based theory we'll learn, logicians also study other, nonstandard systems of reasoning, which are just as beautiful and interesting as what we'll deal with. But in some way those other systems all differ from the basic way that people construct and interpret arguments.

Don't worry, the logicians will forgive us if we use the word "logic" just for a slice of their very deep and beautiful field.

Perhaps the important thing about the logic we'll learn (so-called predicate logic) is its computational flavor. That is, if we write out an argument in terms of logical symbols, and if we are good enough at logical computations, we can decide whether the argument is right or wrong. We can be sure (as sure as we are that the only solution of $x^2-6x+9=0$ is $x=3$ ) that the argument is correct.

Overview of Logic

Statements (this page). The basic unit of logic is the statement or proposition.
Not & And. Statements can be made more interesting by combining them. We can write propositional formulae to discover useful facts about how statements relate to each other in general.
Or. Another little word.
Conditionals. If-then statements are the bread and butter of mathematical proofs.
Order of Logical Operations. Just like arithmetic operations, the order of logical operations matters.
Logic in Proofs. Simple chains of statements can be used to make deductions and structure proofs.
Quantifiers. All about ``for all" and ``there is".
Uniqueness. We all like to feel special. But "unique" is something else!
A Case Study: Divisibility. An illustration of how logic comes into a familiar idea.
Watch Out! Some common pitfalls to avoid.

Statements

Logic deals with statements.

Definition. A statement is a sentence which is either true or false, and not both.

This isn't a philosophy course, so we won't concern ourselves with what it means for something to be true. I'll refer to that idea as capital-T Truth. We're interested in the more mundane concept of little-t truth, which we don't need to know much about, other than it comes in two flavors (true and false), and we're going to be dealing with sentences which have to be one and can't be both.

Being a statement imposes two kinds of constraints:

a form or grammatical constraint: the statement must be a sentence. In fact it should be a declarative sentence with a subject and a verb.
a meaning or semantic constraint: the statement must be either true or false, and not both.

Practice Question. Which of the following are statements? For each non-statement, explain why it's a nonstatement. For each statement, explain how you know it's a statement.

The only solution of $x^2-6x+9=0$ is $x=3$
$\frac{9}{3}$
The improper Riemann integral of a function might exist without the function being integrable.
$2^3 + 3^2 = 17$
What can we say about the sequence $\langle f_n\rangle$ ?
$2^x + x^2 = 17$
Foreign cars are better than domestic cars.
Euclid was left-handed.
The function $x\mapsto\Phi(x)$ is harmonic for $x\neq 0$ .
This sentence is false.

a: This is a statement (it's true)
b: This is not a statement (it's not a sentence)
c: This is a statement.
d: This is a statement (it's true)
e: This is not a statement (it's a sentence, but not a declarative sentence)
f: This is not a statement.
g: This is not a statement.
h: This is a statement.
i: This is not a statement.

We're ready for our first proof!

Theorem. The sentence This sentence is false is not a statement.

Proof. Let's denote the sentence This sentence is false by the letter $S$ .
If $S$ were a statement, then $S$ would be either true or false.

If $S$ were true, then by the meaning of $S$ we could conclude that $S$ would have to be false. So $S$ would be both true and false. (This, however, is not allowed for statements.) So $S$ can't be true.
If $S$ were false, then by the meaning of $S$ we could conclude that $S$ would have to be true. So $S$ would be both false and true. (This, however, is not allowed for statements.) So $S$ can't be false.

We've just established that $S$ cannot be a true statement, and that $S$ cannot be a false statement. But those are the only two types of statements. So $S$ must not be a statement at all. $\Box$

Because this is a course about proofs, let's dwell on the proof we just saw.

First, notice that the claim being proved is set apart from the text clearly, so that everyone knows what we are doing: we are proving that This sentence is false is not a statement.
Next, we have indicated where the proof itself starts (with the boldface word Proof). This may seem a bit over-the-top, but it's clear anyway.
We've also given a clear indication of when the proof ends: we say so explicitly ("So $S$ must not be a statement at all.") and give a special symbol: $\Box$ .
One good trick to make this proof more readable was the first line of the proof: we replaced This sentence is false with the letter $S$ . We didn't have to do this, but it saved us some headaches from reading things like
"If This sentence is false were false, then by the meaning of This sentence is false, we could conclude that This sentence is false would have to be true."
The clarity of all of the above was helped by formatting: the use of symbols, italics, boldface, and indentation.

Finally, I want to point out that this, our first proof, was also our first reductio ad absurdum or proof by contradiction. We'll talk more about that later, but notice that we started by supposing the opposite of what we wanted to establish: we wanted to show $S$ was not a statement, but we assumed $S$ was a statement to begin with. Then we painted ourselves into a logical corner. That's the essence of a reductio ad absurdum.

What the sentence This sentence is false shows is that being a statement has to do with both grammar (form) and semantics (meaning): the very similar sentence This sentence appears in black type is definitely a statement, even though its form is the same.