Basics of logic and proof techniques¶
Part 1 · Numbers and logic · Chapter 2 · lecture notes by Fabio Furini · Chapter PDF
1. Logical symbols¶
-
the symbol “\(\forall\)” is called the universal quantifier and is read “for every”, “for all”, “for each”
-
the symbol “\(\exists\)” is called the existential quantifier and is read “there exists”, “there exist”
-
the symbol “\(\Rightarrow\)” is called logical implication and is read “implies” or “if … then”
-
the symbol “\(:\)” is read “such that”
-
the symbol “\(\in\)” is read “belongs to”
-
the symbol “\(\notin\)” is read “does not belong to”
-
the symbol “\(\vee\)” is called logical disjunction and is read “or”
-
the symbol “\(\wedge\)” is called logical conjunction and is read “and”
-
the symbol “\(\neg\)” is called logical negation and is read “not”.
2. Universal implications and proofs¶
Predicates (or properties) and propositions (or statements)
-
Consider the following assertion:
\[\begin{equation} \label{TT} ``{\rm the~natural~number~} n {\rm ~is~odd}'' \end{equation}\]and let us ask whether it is true. Obviously the answer is: “it depends on \(n\)”. Indeed, in \(\eqref{TT}\) the symbol \(n\) represents a variable that can take different values and make the assertion true or false.
A sentence of this kind is called a predicate (or property): its truth or falsity depends on the values of the variable(s) appearing in it.
-
Now consider the following assertion:
\[\begin{equation} \label{TTT} ``{\rm for~every~natural~number~} n, {\rm ~if~} n {\rm ~is~odd~then~} n^2 {\rm~ is~odd}'' \end{equation}\]which we can write more formally as follows:
\[\begin{equation} \label{TTTT} \forall n \in \N ~~(n {\rm ~~odd~~} \Rightarrow n^2 {\rm ~~odd~~}) \end{equation}\]In this case we say that the variable \(n\) is not free, but bound by the quantifier \(\forall\). As a consequence, \(\eqref{TTTT}\) is true or false “once and for all” and is called a proposition (or statement).
In particular, the components of \(\eqref{TTTT}\) are the set \(\N\), two predicates defined on \(\N\) given by
\[ p(n) : ``n {\rm~odd}'' {\rm~~and~~} q(n) : ``n^2 {\rm~odd}'' \]and the implication
\[ p(n) \Rightarrow q(n). \]
Definition 1: of universal implication
In general, a statement involving a set \(A\), two predicates \(p(x)\) and \(q(x)\) whose argument \(x\) ranges over \(A\), and the logical structure:
is called a universal implication.
Most theorems consist of universal implications, in which the predicate \(p(x)\) plays the role of the hypothesis and the predicate \(q(x)\) plays the role of the thesis (conclusion).
-
In particular, \(\eqref{TTTT}\) is a proposition (or a statement):
Proposition 1
\[\begin{equation} \label{CC} \forall n \in \N ~~(~n {\rm ~~odd~~} \Rightarrow n^2 {\rm ~~odd}~) \end{equation}\]In this case one is easily convinced that the proposition is true, but how can we prove it rigorously?
-
For example, is it enough to observe that \(3\) is odd and \(3^2=9\) is odd to claim that the proposition is true? Certainly not, since the proposition requires the universal implication to hold for every natural number. However, there are infinitely many odd numbers: how can we prove a universal implication for infinitely many numbers?
-
The key procedure is this: we consider a generic \(n\) satisfying the hypothesis (being odd) and we prove that \(n\) satisfies the thesis (its square is odd).
Let us see how to proceed to prove the previous proposition:
Proof
Let \(n\) be odd; we prove that then \(n^2\) is odd.
Any odd number can be written in the form \(2\:k + 1\), for a suitable \(k \in \N\). We also observe that \(2\:k\) is an even number for any \(k \in \N\).
So let \(n = 2k + 1\) be an odd number (\(k \in \N\)); we therefore need to write \(n^2\) as an even integer plus one. We have:
\[ n^2 = (2\:k + 1)^2 = 4\:k^2 + 4\:k +1 = 2\:(2\:k^2 + 2\:k) +1 . \]Since \(2\:(2\:k^2 + 2\:k)\) is an even integer, \(n^2\) is odd. □
To prove the correctness of a universal implication such as \(\eqref{JJ}\), we consider a generic \(x\) satisfying the hypothesis \(p(x)\) and we try to prove that the thesis \(q(x)\) is true.
- Let us now prove a similar relation for even numbers:
Proposition 2
Proof
Let \(n\) be even; we prove that then \(n^2\) is even.
So let \(n = 2\:k\) be an even number (\(k \in \N\)); we therefore need to write \(n^2\) as an even integer. We have:
Since \(2\:(2\:k^2)\) is an even integer, \(n^2\) is even. □
2.1 Counterexamples¶
Counterexamples are an important technique for proving the falsity of a universal implication.
-
Let us ask, for example, whether the following universal implication is true or false:
\[\begin{equation} \label{TEST} \forall n \in \N ~~(~n {\rm ~~prime~~} \Rightarrow n {\rm ~~odd}~) \end{equation}\]A moment's reflection shows that this proposition is false. Indeed, the number 2 is prime but it is even.
To claim that a universal implication is true, a proof is needed (an example is not enough), whereas to prove that a universal implication is false, one counterexample is enough.
- The universal implication requires that every \(x\) satisfying the hypothesis also satisfies the thesis: therefore, if we find even a single example of \(x\) that satisfies the hypothesis but not the thesis, this means that the universal implication is false. Not “false in one case”, but simply “false”, because the universal implication is true or false once and for all.
Definition 2: of counterexample
In general, an example that satisfies the hypothesis but not the thesis of a universal implication, and that therefore proves its falsity, is called a counterexample.
-
The formal proof that the previous universal implication is false is the following:
Proof
The number \(2\) is a counterexample to the universal implication: “For every natural number \(n\), if \(n\) is prime then \(n\) is odd". □
The negation of the proposition
is the proposition
This particular \(x\) is a counterexample.
3. Law of contraposition¶
- It is an indirect proof technique
The universal implication
is logically equivalent to
The second implication is called the contrapositive of the first.
-
For example: since we know that the universal implication (proposition ↗) holds
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~odd~~} \Rightarrow n^2 {\rm ~~odd}~) \end{equation*}\]the following proposition holds:
Proposition 3
\[\begin{equation} \label{DD} \forall n \in \N ~~(n^2 {\rm ~~even~~} \Rightarrow n {\rm ~~even~~}) \end{equation}\]Proof
Let \(n^2\) be even; we prove that then \(n\) is even. We prove \(\eqref{DD}\) relying on the truth of \(\eqref{CC}\).
If \(n\) is not even then it is odd and therefore \(n^2\) is odd by \(\eqref{CC}\). This case contradicts the hypothesis that \(n^2\) is even (hence it cannot occur).
Consequently \(n\) is even and \(\eqref{DD}\) is proved. □
-
The reasoning used in the previous proof has general validity, and shows precisely that if \(\eqref{AA}\) is true then \(\eqref{BB}\) is true; moreover, if the second is true then the first is true (because “not not \(p(x)\)” is logically equivalent to \(p(x)\)), so the two are logically equivalent.
The equivalence between \(\eqref{AA}\) and \(\eqref{BB}\) is called the law of contraposition. It is a method of indirect proof that consists in proving \(\eqref{BB}\) to show that \(\eqref{AA}\) is true (it requires proving that the negation of the thesis implies the negation of the hypothesis).
When using the law of contraposition, one must be able to construct the correct negation of a given proposition or property.
-
Given any two predicates or properties \(p(x)\) and \(q(x)\), we list schematically some rules for constructing the negation of a proposition or property.
The negation of
\[ ``{\rm for~every~~} x \in A, {\rm~~} p (x) {\rm~~holds}'' \]\[ \forall x \in A ~~\big(~p(x)~ \big) \]is
\[ ``{\rm there~exists~~} x \in A {\rm~~for~which~} p (x) {\rm~~does~not~hold} '' \]\[ \exists x \in A ~~\big(~\neg p(x) ~\big) \]The negation of
\[ ``{\rm there~exists~~} x \in A {\rm~~for~which~~} p (x) {\rm~~holds}'' \]\[ \exists x \in A ~~\big(~p(x)~ \big) \]is
\[ ``{\rm for~every~~} x \in A, {\rm~~} p (x) {\rm~~does~not~hold} '' \]\[ \forall x \in A ~~\big(~\neg p(x) ~\big) \]The negation of
\[ ``{\rm } p (x) {\rm ~~holds~and~~} q (x) {\rm ~~holds}'' \]\[ \big(~p(x) \wedge q(x)~\big) \]is
\[ ``{\rm } p (x) {\rm ~~does~not~hold~or~~} q (x) {\rm ~~does~not~hold}'' \]\[ \big(~\neg p(x) ~\vee~ \neg q(x)~\big) \]The negation of
\[ ``{\rm } p (x) {\rm ~~holds~or~~} q (x) {\rm ~~holds}'' \]\[ \big(~p(x) ~\vee~ q(x)~\big) \]is
\[ ``{\rm } p (x) {\rm ~~does~not~hold~and~~} q (x) {\rm ~~does~not~hold}'' \]\[ \big(~\neg p(x) ~\wedge~ \neg q(x)~\big) \]
4. Sufficient conditions and necessary conditions¶
Definition 3: of sufficient condition
A sufficient condition is one that, if satisfied, guarantees the truth of the proposition.
Definition 4: of necessary condition
A necessary condition is one that must be satisfied for the proposition to be true.
Let \(p(x)\) and \(q(x)\) be any two predicates or properties. If \(p(x)\) implies \(q(x)\), formally:
then:
-
\(p(x)\) is a sufficient condition for \(q(x)\)
-
\(q(x)\) is a necessary condition for \(p(x)\)
-
We have seen that the following universal implication is true (proposition \(\eqref{CC}\)):
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~odd~~} \Rightarrow n^2 {\rm ~~odd}~) \end{equation*}\]Hence “\(n\) odd” is a sufficient condition for “\(n^2\) odd” and “\(n^2\) odd” is a necessary condition for “\(n\) odd”.
-
Let us now prove that the following proposition is also true:
Proposition 4
Proof
Let \(n^2\) be odd; we prove that then \(n\) is odd.
So let \(n^2 = 2\;(2\;k^2 +2\;k)+1\) be an odd number (\(k \in \N\)), since \(2\;(2\;k^2 +2\;k)\) is an even number). We therefore need to write \(n\) as an even integer plus one. We have:
Since \(2\;k+1\) is an odd integer, \(n\) is odd. □
In this way we have proved that “\(n^2\) odd” is a necessary and sufficient condition for “\(n\) odd” and also that “\(n\) odd” is a necessary and sufficient condition for “\(n^2\) odd”:
Proposition 5
-
We have seen that the following universal implication is true (proposition \(\eqref{TEST_tris}\)):
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~even~~} \Rightarrow n^2 {\rm ~~even}~) \end{equation*}\]Hence “\(n\) even” is a sufficient condition for “\(n^2\) even” and “\(n^2\) even” is a necessary condition for “\(n\) even”.
-
Let us now prove that the following proposition is also true (direct proof, without using the law of contraposition as seen previously in \(\eqref{DD}\)):
Proof
Let \(n^2\) be even; we prove that then \(n\) is even.
So let \(n^2 = 2\;(2\;k^2)\) be an even number (\(k \in \N\)); we therefore need to write \(n\) as an even integer. We have:
Since \(2\;k\) is an even integer, \(n\) is even. □
In this way we have proved that “\(n^2\) even” is a necessary and sufficient condition for “\(n\) even” and also that “\(n\) even” is a necessary and sufficient condition for “\(n^2\) even”:
Proposition 6
Example 1: necessary and sufficient conditions
For example, for a square matrix of real numbers, the fact that its determinant is different from zero is a necessary and sufficient condition for it to be invertible.
Proposition 7
Proof
Let \(n>2\) be a prime number; we prove that then \(n\) is odd.
If \(n\) is not odd, it is even. But no even number greater than two is prime, a fact that contradicts the hypothesis that \(n\) is prime and greater than two (hence this case cannot occur).
Consequently \(n\) is odd. □
-
Hence “\(n\) odd” is a necessary condition for “\(n\) prime > 2” and “\(n\) prime > 2” is a sufficient condition for “\(n\) odd”.
-
However, “\(n\) odd” does not imply “\(n\) prime > 2”, since for example the number \(9\) is not prime (counterexample). That is:
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~ odd~~} \nRightarrow n {\rm ~~prime~number~greater~than~} 2~) \end{equation*}\]Hence “\(n\) odd” is a necessary but not sufficient condition for “\(n\) prime >2” and “\(n\) prime > 2” is a sufficient but not necessary condition for “\(n\) odd”.
Proposition 8
Proof
Let \(n\) be a number divisible by six; we prove that then \(n\) is even.
If \(n\) is not even, it is odd. But no odd number is divisible by six, a fact that contradicts the hypothesis that \(n\) is divisible by six (hence this case cannot occur).
Consequently \(n\) is even. □
-
Hence “\(n\) even” is a necessary condition for “\(n\) divisible by 6” and “\(n\) divisible by 6” is a sufficient condition for “\(n\) even”.
-
However, “\(n\) even” does not imply “\(n\) divisible by 6”, since for example the number \(2\) is even but not divisible by six (counterexample). That is:
\[\begin{equation*} \forall n \in \N ~~(~n {\rm ~~even} \nRightarrow ~ n {\rm ~ divisible~by~~} 6) \end{equation*}\]Hence “\(n\) even” is a necessary but not sufficient condition for “\(n\) divisible by 6” and “\(n\) divisible by 6” is a sufficient but not necessary condition for “\(n\) even”.
Example 2: necessary/sufficient but not sufficient/necessary conditions
Being a square implies being a rectangle:
since all squares are rectangles.
Hence “being a rectangle” is a necessary condition for “being a square” and “being a square” is a sufficient condition for “being a rectangle”.
But being a rectangle does not imply being a square
because there are rectangles that are not squares.
Hence “being a rectangle” is not a sufficient condition (but it is a necessary one) for “being a square” and “being a square” is not a necessary condition (but it is a sufficient one) for “being a rectangle”.
5. Proofs by contradiction¶
- It is an indirect proof technique
Definition 5: of proof by contradiction
In general, a proof by contradiction consists in assuming that the hypothesis of the theorem and the negation of the thesis are true, and deducing from these facts a contradiction of any kind.
- We illustrate proof by contradiction with the following theorem.
Theorem 1
There is no rational number whose square is \(2\).
Proof
Suppose, by contradiction, that there exists a number \(r \in \Q\) such that \(r^2 = 2\).
We can write \(r = \frac{n}{m}\) with \(n,m \in \Z\), \(m \neq 0\).
Moreover, we can assume that the fraction \(\frac{n}{m}\) is already reduced to lowest terms, that is, “simplified” (in other words: \(n\), \(m\) have no common factors).
We then have the chain of implications:
so \(n^2\) is even; but then by \(\eqref{HHHHHHHHH}\) \(n\) is also even and we can write \(n = 2k\) for some \(k \in \Z\).
Hence the relation \(n^2 = 2\:m^2\) can be rewritten as:
So \(m^2\) is even. But then by \(\eqref{HHHHHHHHH}\) \(m\) is also even.
Therefore both \(n\) and \(m\) are even, and this is a contradiction, because we had assumed that the fraction \(\frac{n}{m}\) had already been simplified.
The proof can be found in Euclid's Elements (around 300 BC). □
6. Logic and sets¶
The language of logic and the language of sets are two sides of the same coin.
6.1 Logical implication and set inclusion¶
-
There is a parallel between the relation of set inclusion and logical implication. To explain it, consider the universal implication:
\[\begin{equation} \label{KK} \forall n \in \N ~~(n {\rm ~~divisible~by~} 4 \Rightarrow n {\rm ~~divisible~by~} 2) \end{equation}\]If we denote by:
\[ D_4 =\big\{ ~~ n \in \N: n {\rm~~is~divisible~by~~} 4 ~~\big\} {\rm ~~and~~} D_2 =\big\{ ~~ n \in \N: n {\rm~~is~divisible~by~~} 2 ~~\big\} \]we can observe that the universal implication written above is equivalent to the assertion:
\[ ``D_4 \subseteq D_2 '' \]Indeed, this inclusion means that every element belonging to \(D_4\) also belongs to \(D_2\), that is, that every natural number divisible by \(4\) is also divisible by \(2\).
The universal implication:
is equivalent to the set inclusion:
6.2 Equality of sets and universal implications¶
-
Proving the equality of two sets, i.e., \(A=B\), requires proving two universal implications. Formally:
\[\begin{equation} \label{FFF} \forall x ~~(x \in A \Rightarrow x \in B) {\rm ~~~~~~and~~~~~~} \forall x ~~(x \in B \Rightarrow x \in A). \end{equation}\] -
Stating that \(A \subsetneqq B\) means stating that “Every element that belongs to \(A\) also belongs to \(B\), and there exists an element of \(B\) that does not belong to \(A\)”. Formally:
\[\begin{equation} \label{GGG} \forall x ~~(x \in A \Rightarrow x \in B) {\rm ~~~~~~and~~~~~~} \exists x \in B: x \notin A. \end{equation}\]
6.3 Set operations and logical operations¶
There is a relation between operations on sets and logical operations. Precisely:
-
Set intersection is defined by means of “and” (logical conjunction).
-
Set union is defined by means of “or” (logical disjunction).
-
Set difference and the complement operation are defined by means of “not” (logical negation).
-
The distributive properties of union and intersection of sets:
Remark 1: distributive properties (sets)
Given three sets \(\red{A}, \blue{B}\) and \(\orange{C}\) we have:
- They can be rewritten in terms of predicates by observing that the intersection symbol \(\cap\) corresponds to the conjunction \(\wedge\) (“and”) and that the union symbol \(\cup\) corresponds to the disjunction \(\vee\) (“or”).
Remark 2: distributive properties (predicates)
Given three predicates \(\red{p(x)}, \blue{q(x)}\) and \(\orange{r(x)}\) we have:
- De Morgan's laws:
Proposition 9: De Morgan's laws (sets)
Given the sets \(\blue{B}, \orange{C} \subseteq \violet{U}\), we have
- They can be rewritten in terms of predicates by observing that the complement operation corresponds to the negation \(\neg\) (“not”).
Proposition 10: De Morgan's laws (predicates)
Given two predicates \(\blue{q(x)}\) and \(\orange{r(x)}\) we have: