Chapter 1: Nuts and Bolts

Introduction
Mathematical reasoning is best understood as the description of certain patterns of mathematical
argument. he key elements in mathematical arguments are mathematical proofs. Doing mathematics
is a creative activity. It heavily involves guessing, approximation, error connection and many other of
those concepts, which are mostly associated to the methodology of the empirical sciences. To argue
scientifically, you exhibit a mathematical proof, but math is not only a deductive science, you can
have an empirical approach: trial and error, experimentation, guesswork. Nevertheless, you must still
work through axioms or hypotheses (etc…) when presenting mathemethatics to the other people. In
this view mathematical proofs are primarily communication devices.

1.1 arguments and proofs

The key concept about mathematical reasoning is “arguments” that are also called proofs. An
argument is a finite sequence of mathematical statements.

The proof of a theorems is an argument, which we write down to convince (ourselves and as well)
other people that the statement we are interested in is true. So, it’s an argument to the effect that
the statement of interest follows from the truth of a given set of assumption and correctness of the
rules of inference. In everyday mathematical practice those rules of inference are normally referred to
as logic.

There is a distinction between rhetorical and logical arguments:

1. the former are arguments which you may be inclined to accept because of the way they are
presented to you or because of a momentary lapse of reason.
2. The latter are arguments which nobody can coherently force you to reject because they are
constructed following logic rules. But what are those rules?

In mathematics there is indeed a remarkable agreement on the rules for reasoning that must be taken
for granted for a proof to be valid – i.e., acceptable by the scientific community. Is this so in other
areas and in economics and social sciences? This is the goal of this course: to illustrate the extent to
which the methodology of economics and social sciences can benefit from the sort of argumentative
rigor provided by mathematical logic. For an economic argument to be about economics some initial
modelling assumptions must be made, as you will appreciate from the very first exercises below. Such
modelling choices are not, in general, uniquely determined by the real-world problem at hand. This
makes room for the possibility of rational disagreement among the outputs of distinct models.

Mathematical reasoning rests on proofs, which can be of essentially two kinds:

1. Informal proofs: arguments aimed at establishing that a given statement is a consequence of a
given set of hypotheses. Arguments take the form of a chain of statements, the last element
being the proved statement. Each intermediate statement is either taken as obvious (e.g. by
relevant definitions, mathematical facts, etc.) or it is obtained from such statements by means
of logical deductions or it is a consequence of general mathematical knowledge. If this involves
 rather long sub-chains of deductions, it is common practice to establish them separately as
Lemmas, which can later be used as a shortcut in the argument.

2. Formal proofs: Finite sequences of formal expressions such that each element of the sequence
is one of the following:
- a formal expression labelled as a hypothesis;
- an instance of an axiom of the well-specified axiom system within which the proof is being
written;
- the conclusion granted by a rule of inference of the well-specified proof system within which
the proof is being written which takes previous elements of the sequence as arguments.

In all mathematical disciplines, with the exception of certain areas of mathematical logic, proofs are
presented informally. So, by the above characterization, the inferential machinery used to move from
one step to the next one is taken for granted. Formal proofs link logic to algorithmic reasoning: if we
had an algorithm that translate informal proofs in formal ones then we wouldn’t need human beings
anymore.

N.B. Logic’s purpose: from the fact that a valid proof is a logical chain of reasoning which transmits
truth from the hypotheses to a conclusion two very important facts follow (!):
– By learning logic, you will not learn to tell which hypotheses are true, but only which valid
consequences you can derive from what you take to be true;
– You can validly prove ridiculous things if you carry out a correct proof from ridiculous
hypotheses.

1.2 mathematical statements

Mathematical statements (sentences) are the object of all mathematical reasoning. A mathematical
statement is anything (any well-formed linguistic expression) which can be either true or false.
Remember that it is not the business of logic to tell you what is true or false but just if the reasoning is
valid or not. A more practical definition: a linguistic expression counts as a sentence if you can think of
a decisive experiment which will either prove it or disprove it. In mathematical statements, you
should avoid linguistic ambiguities to the greatest possible extent. Natural language is inevitably
ambiguous and mathematical reasoning tires to get rid of ambiguity by the greatest possible extend.

Ex. ““The editor-in-chief of A.C. Milan is vegetarian” is not a mathematical statement because the guy
does not exist for what we know, so there is not a possible experiment to do.

Terminology
When a proof of a sentence θ is a available to us we normally say that θ is a theorem. A proof of a
sentence θ is not to be taken as a demonstration of the truth of θ. It should rather be taken as a
demonstration of the fact that the truth of θ is a (logical) consequence of the hypotheses which have
been used in its proof (i.e., you can’t prove the truth of anything unless you assume the truth of
something). A valid proof then is a logical chain of reasoning which transmits truth from the
hypotheses to a conclusion:
1. Theorem: a very important result which adds to the stock of knowledge about a specific
subject
 2. Lemma: a preliminary result which makes the actual theorem much easier to read
3. Proposition: important result, often listing the properties of certain mathematical objects
4. Corollary: a noteworthy logical consequence of a previously provided results.

Connecting mathematical statements

Mathematical reasoning never takes sentences in isolation, but instead it investigates relations among
statements.
Example: if a number n is divisible by 2, then n is even (N Z).
The statement is a combination of two parts, p and q (simples), that give r (complex). There are
several ways of connecting statements. Suppose p and q are statements. Then:

“p and q”: the conjunction of p and q, “p ∧ q”

1. “Not p”: the negation of p, “¬p”. Read it as “not p” or “it is not the case”

“p or q”: the disjunction of p and q”, “p ∨ q”. Read it as “either p or q”

2.
3.
4. “If p then q”: implication, “p→q”.

Remember than whereas I can change the order of conjunction and disjunction to “p and q” and “p or
q”, with the implication “If p then q” is different from “if p then q”.
5. There is also “if and only if” which is actually the combination of more connectives: “if p then
q” and “if q then p”.

N.B. “Unless” is equivalent to “if not…then”

Exercise 4. Let p and q be as above. Translate the following English sentences by means of
appropriate use of the connectives:
(1) “Since Thelonious Monk is my favorite pianist, 4 is not even”
(2) “Although 4 is even, Thelonious Monk is not my favorite pianist”
(3) “Not only 4 is even, but Thelonious Monk is also my favorite pianist”

This exercise is important because it highlight three important aspects:

1. The rules of connecting mathematical statements are independent of any meaning you may
attach to them. All you require is that they are statements.
2. the meaning of connectives is again independent of the interpretation of the statements they
connect. Which is another way of saying that logic is entirely formal.
3. formalizing natural language statements is a very telling exercise in mathematical modelling.
You get the great benefit of putting your problem in a form which is amenable to
mathematical reasoning, especially if it is of the kind which can be solved algorithmically. But
you pay a cost for doing so: your model is at best a good approximation of the phenomenon
you are interested in. Hence you’ll get an answer which is going to be as good as this
approximation.

If I say “Sarah passed maths but failed statistics. If I do the Boolean mathematical translation, it would
be “q and not p” but I loose information: I lose the word “but” which reveals the failure of an
expectation. Thus, “q and not p” is different to “but”.
1.3 Boolean
matrices and
their inevitability

The Boolean matrices define the meaning of the connectives (when asked for a definition of a
connective, write down the matrice).

Implication
When asked for a justification do the following. Example with the implication Let us begin with the
most important of them all: the connective “→”. Not yet. Let us instead pause for a second to
consider the difference between writing “→”, as I just did, and writing → (without the air quotes). Of
course, I am referring in both cases to the same concept, but in the first case I am just mentioning it
whereas in the second I am using it.

Take in consideration this statement, which is considered to be true for all n and then substitute
numbers in order to stick to the values of the table in different cases.
“If n is prime greater then 2, then n is odd.

V1: “if 6 is prime greater then 2 then 6 is odd”. We know that the statement is true for all integers, so
it must be true even for 6.

V2: “if 9 is prime greater then 2 then 9 is odd”. We know that the statement is true for all integers, so
it must be true even for 9 (whenever the consequence is true, we don’t care about the antecedent”.

V3: no substitution can be made. In fact, if I say, “if 7 is prime greater then 2 then 7 is even”. The initial
q is “n is odd” but we are negating it with “n is even” so the whole sentence would be false because
the premise is true, and the conclusion is false. The initial sentence is true for all “n” so the only way
to make it false it is changing it”.
V4: “if 3 is prime greater then 2 then 3 is odd”. We know that the statement is true for all integers, so
it must be true even for 3.

Conjunction
For it to be true both sentences have to be true. Let’s find a justification for the definition of
conjunction using the sentence “if n is multiple of 2 and n is multiple of 3, then n is multiple of 6”:
- n = 7, so n is not a multiple of 2 and 3, so 7 can’t be a multiple of 6.
- n = 9, so n is not a multiple of 2, but it is of 3, and still n is not a multiple of 6.
- n = 4, so n is a multiple of 2, but it is not of 3, and still, it is not a multiple of 6.
- n = 12, so n is multiple of both 2 and 3, and finally it is also a multiple of 6 .

Disjunction and biconditional implication

Recall that ↔ is equivalent to considering both directions of an implication. The biconditional
expresses the equivalence of two sentences whenever both components are always evaluated in the
same way, meanwhile the disjunction is inclusive, so for it to be true at least one of the two
sentences have to be true. Arguments to prove disjunction and biconditional.
1.4 Mathematical reasoning with implication
Let us begin by observing that a conditional sentence of the form p → q can be read in several,
equivalent, ways, including:
- if p then q: read it in this way so that you don’t get confused
- p implies q
- p is a sufficient condition for q
- q is a necessary condition for p
- q if p
- p only if q
- q given p
- q whenever p

Remarks (high frequency in the exams)

1. p: “you’ll get a PhD” is a statement but “someone will get a PhD “is not a statement
2. Suppose p is a short for: “you’ll get a PhD” and q: “you’ll get a Bachelor. Of course, if you don’t
get a Bachelor degree (¬q) you will not be able to get a PhD (¬p), i.e., ¬q → ¬p.
With the method of Boolean matrices to be developed in full detail in Section 2.3.1, you will
have a logical justification as to why we read this as “p only if q”, that is to say, “q is a
necessary condition for p”. Note that ¬q → ¬p is logically equivalent to p → q, namely q → p
and ¬q → ¬p.
Given p → q
1. q→p is the converse of p→q
2. ¬q → ¬p is the contra positive (logically equivalent to p → q)
3. ¬(p → q) is the contrary,

If a biconditional sentence of the form p↔q is evaluated to 1, then we say that the implication is
satisfied in both directions, which explains the symbol used for it.

Ways of proving implication

Theorem 1
We can prove theorem 1 which is “if n is prime greater then 2, then n is odd” in 2 different ways
(direct proof and proof by contraposition) using 3 definitions
- Definition 1. n is even if and only if n = 2k.
- Definition 2. n is odd if and only if it is not even.
- Definition 3. n is prime if and only if n is divisible by 1 and by n only.
Direct proof: the proof consists in a finite sequence of statements which follow from what is given
and end with what is wanted. First step is divide what’s given (anything that comes before the word
“then”) from what is wanted
- Given: n is prime and greater then 2. It’s the antecedent, in this case is complex.
- Wanted: n is odd. It’s the consequence.
Since 2 ̸= 1 our hypothesis also implies that n ̸= 2. Thus, n is not divisible by 2. However (*) holds (i.e.,
is true) if and only if n is not even (as an immediate consequence of Definition 1). Hence Definition 2
implies that n is odd, which is what we wanted

Proof by contraposition
- Given: the negation of the consequent. In this case “n is even”
- Wanted: the negation of the antecedent. In this case “either n is not prime, or n is smaller
than 2”. (Since the initial statement is a conjunction, we have the negation of a conjunction
when either p or q is false).
From our supposition (“n is even”) and Definition 1, we obtain that n is divisible by 2. Two cases are
possible: either n ≤ 2 or n > 2.

If n ≤ 2 we obtain what we wanted (because we negate that n > 2) whereas if n > 2, then it is not the
case that n is prime (since n is divisible by 2 and different from 2) and again we obtain what we
wanted.
In either case we have reached our desired conclusion.

There’s another way of proving implication that is proof by contradiction

- Given: (i) n is a prime > 2 and (ii) n is even
- wanted: a contradiction

Assumption (ii) is called the absurd hypothesis and corresponds to the supposition that will lead to
the desired contradiction. So, suppose n is even, i.e. that there exists k such that n = 2k (by definition
1). But then n cannot be prime (by definition 3) contradicting the assumption in (i), namely that n is
indeed a prime greater than 2. Hence, we reject hypothesis (ii), and conclude that n must be odd.
N.B. Proof by contraposition and proof by contradiction are indirect methods of proof.
exercise:

Theorem 2: there exist infinitely many prime numbers.

Proof. Suppose by way of contradiction, that it is not the case that there exist
infinitely many primes, that is to say, that the number of primes is finite, let us
say it is n. Since n is finite, all prime numbers could be listed, say as follows:
p1, p2,... pn.
To obtain the required contradiction, let us construct the following number
P =p1 ·p2 ·...·pn +1.
A moment’s reflection shows that P thus constructed is larger than each of the
primes in the sequence. Now, either P is prime, or it isn’t.
- If P is prime then p1, p2, . . . pn does not contain all prime numbers, which
contradicts the hypothesis.
- if P is not prime, then P must be divisible by some of the primes p1, p2, . . .
pn in the list of all primes. But whichever prime we pick, the division will
give us a remainder of 1, therefore P is not divisible by any of the primes in
the list, contradicting the assumption to the effect that all primes are
contained in P.
In both cases a contradiction is reached. Hence, we must reject the hypothesis
that there exists a largest prime number. But this implies that there are infinitely
many primes.
Exercise 11
An online retailer advertises the following “buy two books and get a free drink”. You heard many
complaints and decided to fast check. What do you do? The advert can be formalized as follows: first
we identify the “smallest” mathematical statements
- b: you buy two books
- f: you get a third book for free

The logical form of the ad is therefore b→f. There are only four possible logical cases which amount to
the Boolean table for “→”. Quite clearly then, the shop is cheating if it happens that one buys two
books but does not receive the third one for free, which clearly coincides with the unique row in the
Boolean table which evaluates to 0 the implication expressed by (62). Remark: this exercise shows
that in natural language we sometimes use the word “and” to mean a connective which is not “∧”.

1.5 Formalizing natural language

Formalizing natural language means take the statements from natural language and convert them in
sentences. it’s hard because there is no algorithm for this. However, there’s an informal procedure to
follow: The most important point of this procedure is the first one: “read carefully the expression”. To

- p ∧ q is mathematically wrong. This means that I haven’t understood the statement clearly
stress it consider the example “Sara was texting on the stairs, and she fell”.

- p → q is the best approximation

Consider the following example:

“If Jim is happy, Jules is said and if Jules is said, Jim is said”
- p is short for “Jim is happy”
- q is short for “Jules is sad”
- ¬p is short for “Jim is sad”.
In this case being sad is clearly the opposite of being happy. Then we need not introduce a new letter
for “Jim is sad”, which then is formalized by ¬p. Reasonable as this way of reasoning may sound to
you, it is based on a very strong assumption about the feelings involved. Quite clearly “being happy”
and “being sad” are considered to be binary. However simple introspection is sufficient to convince
many of us that the following are extremely common situations in which you may not feel happy buy,

said” with r. In this case the approximation would be (p → q) ∧ (q → r).

but that needn’t be considered sadness. A better approximation would be labelling the short “Jim is

Formalizing “unless”
Consider the following example: “You will fail the exam unless you work hard”. The meaning in English
should be pretty obvious: “working hard is a necessary condition for you to do well, i.e. not to fail the
exam”. So, if you do not work hard, then you’re in for a fail, i.e.
¬q → p
which (as you will be able to prove in full mathematical detail after the material of Section 2.6) is

¬ ¬q ∨ p,
logically equivalent to

q ∨ p.
and indeed, to

Summing up: “unless” is translated here as “if not, . . . then”, which is equivalent to “or” (!).
However formalizing formalization of “unless” using disjunction seems less appropriate in other
contexts. Consider for instance the following: “Open 24h unless it’s Sunday
Which reasonable means that Sundays represents an exception to the rule expressed by p. That is
both the following hold:
- If p then¬q
- If ¬q then p.
 - Therefore p ↔ ¬q, which, as you will be able to prove by yourself, is logically equivalent to
(p∨q)∧¬(p∧q).

Such examples show that formalization might not be a straightforward matter, and that it might be
argued that the connectives of ordinary language differ in meanings from the connectives of formal
logic in rather subtle ways. When it comes to formalization then, one has to look at the context rather
carefully to determine the correct reading.

1.6 Quantifiers (beyond Boolean Logic, first ordering lesson)

- ∃: “there is” or “there exists” (existential quantifier)
- ∀: “for all” or “for any” (universal quantifier)

Let’s consider the equation

m1 m2
F=G 2
r

The reason this is referred to as Newton’s law of universal gravitation is to do with the fact that if
holds true for any two particles in the universe. This fact is clearly essential to its being a “law”, but
there is no trace of it in the equation. This is because physicists read it with implicit universal
quantification: holds for all m1 and m2 in the universe.

Logicians instead tend to be explicit about their quantifiers since one may easily run into trouble.

example 1
For example, consider the expression
x > 0 → x ≥ 1. (12)
Is it true or false? Well, it depends! Note that strictly speaking this means that is not a sentence,
unless that is, we specify the domain of x (the expression is to consider a statement unless the
domain of quantification is specified, otherwise too ambiguous. Once this is done, there will be no
doubt about its truth-value.

(12) is true when x is restricted to the integers Z. To see that the claim is indeed true, observe that

words, the sentence is true for all x ∈ Z. Things change though, if x is allowed to range over the reals
there are no integers between 0 and 1. This clearly means that “x > 0” is sufficient to “x ≥ 1”. In other

(denoted as usual by R). To see this let x = 1/π. It certainly satisfies the antecedent of (12) but fails to

(12). In yet other words, there exists an a ∈ R for which the sentence is false.
satisfy its consequent. We refer to 1/π as a counterexample to the universally quantified sentence

Mentioning quantifiers is therefore necessary to avoid dreadful mathematical confusion, but alas it is
not sufficient. Order matters too.

example 2
Consider the following sentences where the domain of quantification is N, and < is interpreted as the
natural order relation on it “less than”:
(1) ∃y such that ∀x, x < y;
(2) ∀x ∃y such that x < y.
The former says that y is the largest natural number, which of course cannot exist and hence the
sentence says something false (of the natural numbers). The second expresses the (true) statement to
the effect that you can find a greater number than any given one. Hence, order does matter.

example 3
A key axiom of rational preferences in microeconomics. It says that a rational agent’s preferences are
transitive, which can be expressed as follows:
If xPiy and yPiz then xPiz, (TR)
where “xPiy” reads as “agent i prefers x to y”. So the property makes explicit the requirement to the
effect that the binary relation which formalizes the concept of preference to the effect that the binary
relation which formalizes the concept of preference should be transitive. In good presentations of the

z ∈ X are legitimate objects of preference for agent i. The domain of preferences/choices plays a key
subject (TR) always refers to some suitably specified domain of preference, so let us assume that x, y,

role in defining the very concept of “rational preference”. So it must be satisfied by all substitutions of
x,y,z allowed by the suitably specified domain of preference X. In other words (TR) should be written

∀x∀y∀z if xPiy and yPiz then xPiz (Definition 4)

as

Note that (TR) comes in the form of an implication, whose antecedent consists of a conjunction. We

∀x∀y∀z((xPiy ∧ yPiz) → xPiz).

can thus rewrite it using propositional connectives instead of their metalinguistic expression, i.e

Going back to Definition 4, recall that an implication is false just we are able to find a,b,c∈X such that
i prefers a to b, i prefers b to c and (but!) i does not prefer a to c. In symbols:

∃a, ∃b, ∃c
Definition 5 (Negation of transitivity).

∈X such
that aPib,
bPic, ¬(aPic).
We refer to

In other words, ∃a, ∃b, ∃c ∈ X for which the sentence is false means that:
that as a counterexample to the universally quantified sentence.

Remember The Negation Rules: When we negate a quantified statement, we negate all the
quantifiers first, from left to right (keeping the same order), then we negate the statement.

¬[∀x ∈ A,P(x)] ⇔ ∃x ∈ A,¬P(x).

¬[∃x ∈ A,P(x)] ⇔ ∀x ∈ A,¬P(x).
1.

¬[∀x ∈ A,∃y ∈ B,P(x,y)] ⇔ ∃x ∈ A,∀y ∈ B,¬P(x,y).

2.

¬[∃x ∈ A,∀y ∈ B,P(x,y)] ⇔ ∀x ∈ A,∃y ∈ B,¬P(x,y).

3.
4.
Unrelated, but important, when it comes time to negate the statement remember how to negate an

Example: ∀n(if n is prime greater then 2, then n is odd)

implication: ¬[IFP, THENQ]⇔P ANDNOTQ

The negation is ∃m(n is prime greater then 2 and n is odd).

Remember:
1. Order matters
2. A single counterexample is sufficient to masse a universally quantified statement false
In logic it is fundamental to specify the domain of quantification in order to make a proposition a
mathematical statement, because if it is not specified you don’t know which elements you are taking
in consideration, and you cannot build a proof.

1.7 The

principle of mathematical induction

The principle of mathematical induction provides the choice tool for proving statements about
recursively defined sets. That is to say sets that are defined by recurring to their elements. Such
method is known as proof by induction.
The steps for a
proof by
induction
are
1. The basis
step.
2. The
hypothesis
step.
3. The
inductive
step.
Where our
basis step
is to validate
our statement
by proving it
is true when n equals 1. Then we assume the statement is correct for n = k, and we want to show that
it is also proper for when n = k+1. The idea behind inductive proofs is this: imagine there is an infinite
staircase, and you want to know whether or not you can climb and reach every step. If you can reach
the first step (basis step), you can get the next step. And if you can ascend to the following step, then
you can go to the one after it, and so on. Therefore, if it is true for the first step, then we will assume
it is also appropriate for the kth step (guess). What is more, if it is correct for the kth step, it must be
proper for the k+1 step (inductive).
We say that a set is defined recursively when its elements are used to define the set itself. The most
notable case in point is the Dedekind-Peano recursive analysis of the set N of natural numbers:
- 0 is a natural number;
- if n is a natural number, n + 1 is a natural number;
- nothing else is a natural number. Many functions are defined recursively in mathematics.