Preliminaries: Philosophy, Rigour, and Logic

(These first few paragraphs are mostly a discussion of philosophy; the impatient reader can safely skip to Logic (A Practical Primer)

Perhaps the best way to begin this discussion is with some history. Math has been around for a very long time, but it’s practice has seriously changed over the centuries. In general, as time progresses, math has become less and less concrete, less and less intimately connected to the real world, and more and more abstract. The ancient Greek mathematicians, for example, did not believe in either “infinities” or “irrational numbers”, both concepts which are now central and fundamental to not just the study of higher math but also to concepts we learn as early as high school.

Moving away from an intimate connection with what can be measured and quantified, from the physical world, carries with it dangers. We cannot reason using “common sense” about such nonsensical quantities as infinity, for example; we can’t ascertain what properties these objects have, because they aren’t endowed with any properties by the natural world. Instead, we must define these objects. Often times these definitions take the form of specifying exactly what properties something has; for example, one could say “negative one is defined to be the number which, when added to one, yields zero” (indeed, after we have defined zero, one, and addition, this is one way we can define negative one). Another word for these definitions is a set of axioms; the words axiom and definition carry slightly different connotations, but ultimately the reference the same idea - the things we start with to begin our reasoning.

Once we have defined objects and chosen axioms, we need some way to reason about those objects; i.e., to derive conclusions about them based only on their definitions. This comes in the form of logic. I don’t know much about the philosophical ramifications of these things, so I won’t dig too deep into unpacking what a logic actually means, but for our purposes a logic is a set of rules which can be applied to the properties of objects to deduce other properties of objects. The rules of inference we will be using most closely resemble first order logic, although in my day to day as a math student I don’t think very often about how closely I’m conforming to that paradigm and so I will almost certainly stray outside what is technically allowed by first-order logic. The logic used by mathematicians is not a particularly well-defined concept; the general metric a proof or argument is evaluated by is usually something along the lines of “could the reader turn this proof into a truly formal argument given sufficient time”. (Which, you will note, not only is a criteria which depends on the reader but also isn’t actually information the writer usually has. This is the cause for a tremendous amount of headache, as well as some particularly amusing jokes in the mathematical community, but is superior to every alternative method by dint of it’s general efficiency.)

The rest of these notes will be dedicated to a very loose overview of logic.

Logic (A Practical Primer)

Predicates

First order logic is also called “predicate calculus”. Practically speaking, a predicate is a descriptor which can be applied to any object to generate a truth value (either true or false). For example, the pattern “X is a man” is a predicate, which can be applied to (ignoring tenses, assuming ‘is’ includes ‘was’) “Socrates” (with the value of true), “the table I am working at” (with the value of false), and “you” (with a value which depends on who is reading this text). Indeed, any rule which assigns to each object the value of either true or false is a predicate. Predicates can also describe multipile objects; for example, the pattern “X is the same as Y” is a predicate which applies to two objects.

It is important to note that your ability to determine the truth value of a sentence has no bearing on that sentence representing a predicate; for example, the sentence “X is a forblewabel” is a perfectly valid predicate, even if you have no idea what a forblewabel is (if you do, please tell me). The issue with that sentence is forblewabel is not defined; we have no way to deal with this concept.

Logical Connectives

First order logic supplies a set of symbols or “connectives” with which to deduce the truth values of predicates from the truth values of other predicates, most of which I will outline here. I’ll also include the symbols I’ll use for them. One of the best way to describe these rules is with a truth table, which displays the truth value of an expression using logical connectives based on the truth value of the predicates involved.

• Conjunction (and) ($\land$). The expression $P(x)\land Q(x)$ is true only if both $P(x)$ and $Q(x)$ are true, and false otherwise.

• Disjunction (or) ($\lor$). The expression $P(x)\lor Q(x)$ is true if at least one of $P(x)$ or $Q(x)$ is true.

• Negation ($\lnot$). The expression $\lnot P(x)$ is true if $P(x)$ is false, and false if $P(x)$ is true.

• Implication ($\implies$). The expression $P(x)\implies Q(x)$ is true if $P(x)$ and $Q(x)$ are both true, or if $P(x)$ is false. Another way of saying implication is “if … then”; “$P(x)$ implies $Q(x)$” is the same as saying “if $P(x)$, then $Q(x)$” or “$Q(x)$ is true if $P(x)$ is true” (note the ORDER of the predicates in the last expression!). Implication / if … then has the following truth table:

• Biconditional (if and only if) ($\iff$). The expression $P(x)\iff Q(x)$ is true whenever $P(x)$ and $Q(x)$ have the same truth value.

Quantification

The reason we like first order logic is the ability to quantify predicates. Because our predicates depend on variables, we can have a discussion about which variables they may be true or false for. There are really only two ways we do this: existential quantification, and universal quantification. When we specify an existential quantifier for a predicate, we specify that there exists some value for $x$ such that $P(x)$ is true. We write this $\exists x$ s.t. $P(x)$, or “there exists an $x$ such that $P(x)$ is true”. Here $P(x)$ can be a compund predicate as well; I’ll often shorten “there exists” to “there is”. The expression $\exists x$ s.t. $P(x)$ is true if there is some value for $x$ such that $P(x)$ is true, and false otherwise. Similarly, universal quantification asserts that for every possible value of $x$, $P(x)$ is true. We write this $\forall x, P(x)$ or “for all $x$, $P(x)$ is true”. One could also say “for any $x$…”; in math, all and any are the same (this is an important concept; proving something for every object is the same as proving it for any particular object so long as you don’t assume anything additional about that object.).

Existential quantification can be though of as an “or” ranging over every possible value of a variable; similarly, universal can be though of as an “and” ranging over every possible variable.

Order of operations / Evaluating Expressions

The order of operations we use to evaluate expressions is:

1. Anything in parenthesis
2. Negation
3. And
4. Or
5. Quantification
6. Implication / Biconditional

We say two expressions are equivalent if they always evaluate to the same thing. For example, examining the truth tables shows that $\lnot\lnot P(x)$ is equivalent to $P(x)$. This phenominon is something known as the law of the excluded middle, and is very useful in math (although not true in every logic - see intuitionistic logic).

Proofs - How we use logic in math

Math can be thought of as beginning with some axioms (which we’ll discuss further in the next chapter) and using first order logic to assert the truth of (possibly quantified) statements. This process is proof. In math, we don’t write out explicitly the rules of logic we’re using very often, as doing so would make the proof difficult for most to read and understand.

There are some expressions who’s truth value can be determined without knowing anything about the variables. These are called identities, and are a result of the first order logic we use; an example would be the identity $P(x)\lor\lnot P(x)$ is always true. There are two ways to prove identities: one can either carefully use the rules of evaluation to demonstrate what the expression evaluates to, or write down a truth table with every possible value of the basic predicates and then try to evaluate the express. The first process requries some creativity, while the second process quickly becomes tedious as the complexity of the expression grows.

For example, we can prove that $P(x)\lor \lnot P(x)$ is always true as follows:

We can similarly prove an identity called DeMorgan’s Law, which says that $\lnot(P(x)\lor Q(x))$ always has the same value as $(\lnot P(x))\land (\lnot Q(x))$.

Using these two laws we can deduce that $\lnot(P(x)\lor\lnot P(x))$ is always false, and also has the same truth value as $\lnot P(x)\land \lnot\lnot P(x)$. Examining the truth table for negation yields that $\lnot\lnot P(x)$ is equivalent to $P(x)$, and similarly, the truth table for and shows that $P(x)\land Q(x)$ is equivalent to $Q(x)\land P(x)$; from these two facts we can deduce that $\lnot P(x)\land \lnot\lnot P(x)$ is equivalent to $P(x)\land \lnot P(x)$. Thus we obtain (since $\lnot (P(x)\lor\lnot P(x))$ was always false) that $P\land \lnot P(x)$ is always false.

Problems

See below for a list of problems. When doing these problems, try to concentrate on connecting the symbolic manipulations you’re doing to an intuitive understanding of the statements you’re making. One of the most valuable techniques to bring to a mathematical proof is the ability to translate between intuitive statements and rigorous statements. When doing proofs, try to prove them in both symbols and words. If you only have time for one, opt for words. When doing truth tables, try to think about why the truth table works out the way it does.

• Problems

  Here are some problems designed to get you started thinking in terms of first order logic.