LR - Logical Reasoning A First Course
LR - Logical Reasoning A First Course
LR - Logical Reasoning A First Course
Logical Calculations
Chapter 1
What is ‘logic’ ?
It stands to reason
3
4 CHAPTER 1. WHAT IS ‘LOGIC’ ?
Remark 1.1.1 The word ‘logic’ comes from Greek. It is the first part from
the Greek expression ‘logikè technè’, which means: reasoning techniques,
1.2. FORMAL LOGIC 5
Zeitschrift, 1935.
6 CHAPTER 1. WHAT IS ‘LOGIC’ ?
far. Boolean logic on the other hand, will be discussed further (see Chap-
ter 3), and so will natural deduction (Chapter 11 onwards). Both logical
systems have had many applications, not only in mathematics, but also in
computer science:
• Modern logic is used in mathematics in areas that include set theory,
functional analysis, algebra and discrete mathematics.
• Modern logic is important in computer science especially in areas like
programming, database theory, computer architecture and verifica-
tion.
Nowadays, one prefers to use the term ‘formal logic’ instead of ‘modern
logic’, in order to express that the general science of reasoning is written as
precisely as possible. This is done with logical formulas, and hence the use
of ‘formal’.
Remark 1.2.1 Judges, politicians, philosophers, and also ‘ordinary’ people
like you and I, use natural language when reasoning. Formal logic attempts
to separate the logical laws from ordinary (spoken and written) language.
This is needed, because language is often too ‘rich’ in meaning and hence
not precise enough to avoid writing the logical laws in a manner that can
be subject to double interpretations. In the following chapter, we will con-
tinuously make the association with language, in order to explain where the
logical formulas come from. However, when it is a question of precision of
reasoning, logic will dissociate itself from language and will often take its
own separate way. This is necessary in order to preserve the consistency,
which is the guarantee that as long as we keep faithful to the rules, we can
never derive an incorrect conclusion. Via this process of doing our best to
avoid ambiguity and double interpretations, both mathematics and computer
science can be made ‘trustworthy’. This leads to quality and good products.
1.3 Exercises
1.1 Check in each of the following cases whether the given rule is correct.
If it is, give arguments to show this. If it is not, give a counterexample.
There are K’s which are also M’s
(a) All K’s are L’s
There are L’s which are M’s
No one K is an M
(b) All K’s are L’s
No one L is an M
Chapter 2
Abstract propositions
2.1 Propositions
Modern, formal logic has as a basic concept the so-called proposition. This
is a purely technical term, and you must not think of the ordinary English
word ‘proposition’ (‘proposal’), but instead, think of something like a special
kind of a (linguistic) ‘sentence’.
What is a proposition? It is a grammatically correct sentence which (at
this moment, at this place, etc.) is either true or false. Here are some
examples of propositions:
(1) It is raining.
(2) There are birds which cannot fly.
(3) 2 + 2 = 5.
(4) π is bigger than three.
(5) p2 + q 2 = r2 .
Proposition (3) is completely written in the ‘language of mathematics’
(and is false in our world). In proposition (4), ordinary language is mixed
with the mathematical symbol π. Sentences in the language of mathematics
(like (3)), or sentences which are mixed with the language of mathematics
(like (4)), are allowed as propositions.
Note that proposition (5) is grammatically correct, not because of English
grammar, but because of the grammar of mathematical formulas. Moreover,
7
8 CHAPTER 2. ABSTRACT PROPOSITIONS
fits the same pattern: take x ≥ −1 for a, x ≤ 0 for b and ‘x2 + x is positive’
for c.
Logic is primarily the study of abstract patterns rather than the ‘real’
concrete propositions. This is to clarify what the essence is. We do not lose
anything via the use of abstract patterns because, once we know how the
reasoning laws work for abstract propositions, we can apply them without
any difficulties to concrete propositions by replacing the occurrences of the
proposition variables a, b etc., by the concrete propositions.
By abstracting over propositions, one goes even further. Patterns like the
above mentioned ‘(a and b) implies not-c’ still contain words from natural
language (‘and’, ‘implies’, ‘not’). In order to avoid in logic the double
meanings that usually occur in natural language, we replace these words by
symbols, the so-called connectives.
In logic, one usually limits the number of connectives to the following:
(In Chapter 3 we will come back to these connectives and will explain
in detail what they represent. The ⇔, for example, which we have only
vaguely described with ‘if and only if’, will be defined more precisely.)
We can now describe, with the help of these connectives, the above-
mentioned pattern ‘(a and b) implies not-c’ in a fully abstract form, without
words from natural language:
(a ∧ b) ⇒ ¬c .
All the abstract propositions that we reach during the construction, are
called sub-formulas of the formula that we have finally built. The sub-
formulas of ((a ∧ b) ⇒ (¬c)) are hence: a, b, c, (a ∧ b), (¬c) and also
((a ∧ b) ⇒ (¬c)) itself.
In this definition, you may question the number of parentheses and may
rightly believe that they are used excessively. We will in Section 2.5 see how
we can reduce the number of parentheses without affecting the intended
meaning of the formula.
Remark 2.3.3 The word ‘recursive’ literally means ‘running back’. What
runs back in a recursive definition? We are actually going forward in the
building of our abstract propositions: from a and b to a ∧ b, from c to
¬c, etc. This word ‘recursive’ does not really refer to the building of the
propositions, but rather to breaking them down into smaller pieces. This
process of breaking down into smaller pieces is needed when we come across
a ready-made formula which we want to check whether it is an abstract
proposition.
propositions, until we reach the bottom (the level of (basis), the proposition
variables). This breaks the recursion (the running back via the definition).
!
! ¬❅!
!❅
⇒
!
!! ❅! ❅!
!∧❅ ❅
a b c
Figure 2.1: The tree of ((a ∧ b) ⇒ (¬c))
Such a tree has nodes (the black buttons), branches (the connecting lines)
and labels (the symbols at the nodes, like b, ¬ and ⇒). The nodes at the
end of the tree (in this case: the nodes with labels a, b and c) are called
leaves. At the node at the top of the tree, the so-called root, there is a label
which is called the main symbol of the formula, in this case ⇒.
Characteristic for a tree is that it has a root, that all nodes are connected
to each other and that there are no loops. (A loop occurs, for example, when
there is a branch between the nodes labeled b and c. In such a loop you
can go continuously round.) As can be seen, trees in the above graphical
figure, are drawn upside down. The root is in the air, the leaves grow on
the ground. You can draw the horizontal mirror image of such trees, and
then you get ‘normal’ trees.
Note that the tree of an abstract proposition does not need any paren-
theses in order to clarify the structure of the formula:
(1) In order to see how the tree is built, we begin at the bottom, with the
leaves, and then we follow the branches to the top.
(2) In order to see how the tree can be decomposed or broken down, we
begin from the top, at the root, and we follow the branches to the
bottom in order to find the different parts.
In the tree one can also see what the subformulas are: (a ∧ b) can be
found as a sub-tree of the whole tree. Namely as the tree of Figure 2.2.
2.5. DROPPING PARENTHESES 13
!
!! ❅!
!❅
∧
a b
Figure 2.2: The tree of (a ∧ b)
This holds for every node in the tree: the tree below a node represents a
sub-formula.
+ −
14 CHAPTER 2. ABSTRACT PROPOSITIONS
It should be noted that not everyone uses the same priority scheme.
Sometimes, in logic, ∧ has higher priority than ∨ and in arithmetic × may
be stronger than : .
In the case where priorities do not give a definite answer (as in example
(iii)), one usually applies the left-associativity rule: ‘left is applied first’, or:
first come, first serve. Then we read a ∧ b ∨ c as (a ∧ b) ∨ c. Be careful
however. Sometimes we also see the right-associativity rule: right is applied
first. That this can make a lot of difference can be seen in the formula a∧b∨c:
right-associativity represents it as a ∧ (b ∨ c), which is very different from
(a ∧ b) ∨ c (as we will see in Section 3.2). See also the following example:
The priority scheme for connectives and the associativity rules enable
one to economize on parentheses. In addition, it is common to leave out the
outside parentheses.
Summary: You can cut down the number of parentheses by
(1) applying a priority scheme,
(2) using the left- (or right-)associativity rule and
(3) removing the outside parentheses.
Convention 2.5.2 In the rest of this book we will use the priority scheme
from the beginning of this section. Also, we will remove the outside paren-
theses. However, we will neither use the left- nor the right-associativity rule.
Instead, we will when necessary, keep the extra parentheses needed to avoid
ambiguity. Hence, in the formula a ∧ b ∨ c, we add parentheses to describe
what we mean exactly. This could be either (a ∧ b) ∨ c or a ∧ (b ∨ c).
Example 2.5.3 By applying (1) and (3) given above, we can write the
abstract proposition ((a ∧ b) ⇒ (¬c)) completely without parentheses, as
follows: a ∧ b ⇒ ¬c. Note that for readability, it is sometimes useful to keep
some parentheses; hence for this example, we may write (a ∧ b) ⇒ ¬c.
the case that it is both raining and cold’ and the second (which is actually
(¬a) ∧ b): ‘It is not raining and it is cold’. (In the first case, it can very
well not be cold, and perhaps it can also be raining.)
2.6 Exercises
2.1 Check in each of the following cases whether the given expressions are
propositions or not. If yes, say whether this proposition is simple or
complex. If no, give reasons why not.
(a) It is freezing and yet it is not cold, because it is not windy.
(b) if x < 0 then x := x + 1 else x := x − 1.
(c) The queen of Great Britain lives in Liverpool.
(d) Either x < 0, or x = 0 and y < 0.
(e) How is this.
(f) Romeo and Juliet.
(g) Elephants don’t exist.
(h) If x = 0, then x.
2.2 For each of the following concrete propositions, write an abstract
proposition which corresponds to it:
(a) I love you and will always be true to you.
(b) If it is raining, then I will stay home and will open a bottle of
wine.
(c) x ≤ 1 or x > 2.
(d) I will go to play tennis, if you bring balls with you.
(e) I will go to the movies, unless something happens.
(f) x2 > 4 if, and only if, x > 2 or x < −2.
2.3 Give the following propositions in words again, with ‘it is raining’ for
a, ‘it is windy’ for b and ‘I am wet’ for c.
(a) a ∧ ¬b
(b) ¬(a ∧ b)
(c) (a ⇒ c) ∧ (b ⇒ ¬a)
(d) c ∨ ¬c
(e) c ⇔ a
16 CHAPTER 2. ABSTRACT PROPOSITIONS
(f) ¬¬a.
2.4 Show how the following abstract propositions are built according to
Definition 2.3.1.
(a) (a ⇒ (b ⇒ a))
(b) ((¬(a ⇒ b)) ⇔ (a ∧ (¬b)))
(c) ((¬(¬a)) ⇒ ((¬a) ∧ b))
(d) (a ⇒ ((b ∧ a) ∨ c)).
2.5 Show that:
(a) In every abstract proposition in which the symbol ‘¬’ does not
appear, the number of proposition variables is one more than the
number of connectives.
(b) In every abstract proposition where no parentheses are dropped
out, the number of parentheses is equal to twice the number of
connectives.
2.6 (a) Draw the trees of the abstract propositions of Exercise 2.4.
(b) For each of the abstract propositions of Exercise 2.4, give the
main symbol.
2.7 Give all the sub-formulas of the abstract proposition
Truth tables
P Q P ∧Q
0 0 0
0 1 0
1 0 0
1 1 1
17
18 CHAPTER 3. TRUTH TABLES
• the inclusive ‘or’. You say: ‘I feel hungry. I’ll fetch a roll or a sand-
wich’. This can mean that you come back with a roll and a sandwich,
without you uttering a false statement. So the word ‘or’ means here:
the one or the other or both. The both-option is ‘open’ (inclusive). In
order to precisely express the inclusive character of ‘or’, a combination
of ‘and/or’ is used in language (especially the official language): ‘The
information meeting is for the benefit of travelers to France and/or
Italy’.
• the exclusive ‘or’. On lottery tickets one finds: ‘Congratulations. You
have won a TV or 500 pounds’. In this case you have a right for
one of the two, but not to both. You should therefore understand
here: one or the other (and not both). The both-option is ‘closed’
(exclusive). Also here, language provides possibilities for avoiding
ambiguity. When we mean the exclusive ‘or’, we use ‘either ... or ...
(but not both)’: ‘You have won either a tv or 500 pounds (but not
both)’.
P Q P ∨Q
0 0 0
0 1 1
1 0 1
1 1 1
Here one can see that P ∨ Q is only false, when both P and Q are false.
As soon as (at least) one of the two is true, P ∨ Q becomes true too.
In this book we don’t use any separate standard symbol for exclusive ‘or’.
Those who want to express in logic ‘either P or Q (but not both)’, can
for example use: (P ∨ Q) ∧ ¬(P ∧ Q) (i.e.: P or Q, but not: P and Q). A
shorter way is: ¬(P ⇔ Q), but in order to show that this expresses ‘the
same’ formula, we must wait till Section 3.5.
a b c a∧b (a ∧ b) ∨ c a b c b∨c a ∧ (b ∨ c)
0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 1 0
0 1 0 0 0 0 1 0 1 0
0 1 1 0 1 0 1 1 1 0
1 0 0 0 0 1 0 0 0 0
1 0 1 0 1 1 0 1 1 1
1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
In these tables, it is clear that (a∧b)∨c and a∧(b ∨c) ‘calculate’ different
things. The first three columns in both tables (the ‘input’-possibilities for
a, b and c) are the same. But the ‘results’, which appear in the last column,
are different. The last column of the left table differs in two places from
the last column of the right table. For example, when the values of a and b
20 CHAPTER 3. TRUTH TABLES
P ¬P
0 1
1 0
P ¬P ¬¬P
0 1 0
1 0 1
This implies that: when P has the truth-value 0, then also ¬¬P has the
truth-value 0; and when P has the truth-value 1, then also ¬¬P has the
truth-value 1. Therefore P and ¬¬P have the same truth-values or are
equivalent, whatever P is.
3.4. THE IMPLICATION P ⇒ Q 21
P Q P ⇒Q
0 0 1
0 1 1
1 1 1
We still have one case left, namely when P is true (1) and Q is false (0).
(This case does not occur in the example above.) Take the example: ‘If 4
is bigger than 3, then 2 + 2 is equal to 5’. Now, there is no possibility for
ambiguity. In this case, P ⇒ Q says that from something true, something
false must follow, and this can never be the case. So, in this case, the
truth-value of P ⇒ Q is equal to 0.
22 CHAPTER 3. TRUTH TABLES
P Q P ⇒Q
0 0 1
0 1 1
1 0 0
1 1 1
arrow from right to left. Hence, P ⇔ Q can be described as: ‘If P then Q,
and if Q then P ’. Written as an abstract proposition: (P ⇒ Q) ∧ (Q ⇒ P ).
This allows us to calculate the truth-table for ⇔:
P Q P ⇒Q Q⇒P (P ⇒ Q) ∧ (Q ⇒ P )
0 0 1 1 1
0 1 1 0 0
1 0 0 1 0
1 1 1 1 1
P Q P ⇔Q
0 0 1
0 1 0
1 0 0
1 1 1
expresses a mutual implication, one from left to right and one from right to
left.
In this respect, one also speaks of equivalence, which is ‘having the same
value’ (P ⇔ Q is true when P and Q always have the same value, both 0
or both 1). (See also the end of Section 3.2 and Chapter 5).
P Q P ∧Q P ·Q P ↓Q P ∨Q P +Q P ↑Q
0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1
1 0 0 0 0 1 1 1
1 1 1 1 1 1 1+1=1 1
3.7 Exercises
3.1 Give the truth-tables of the abstract propositions of Exercise 2.4.
3.2 For which values of a, b and c one gets 0 in the truth-table of
4.1 Truth-functions
We have seen that for each abstract proposition, we can make a truth-
table. Such a truth-table shows how different truth-values of the proposition
variables lead to the truth-value of the whole proposition. The number of
lines in such a truth-table depends on the number of proposition variables:
(1) For an abstract proposition with one proposition variable, one needs
two lines (one for 0 and one for 1). For example:
a ¬a a ⇒ ¬a
0 1 1
1 0 0
(2) For an abstract proposition with two proposition variables, one needs
four lines. For example:
a b ¬a ¬a ∨ b
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
27
28 CHAPTER 4. THE BOOLEAN BEHAVIOUR OF PROPOSITIONS
(3) For an abstract proposition with three proposition variables, one needs
eight lines. See the two tables at the end of Section 3.2.
Remark 4.1.1 The Cartesian product is called after the French philoso-
pher René Descartes (1596 – 1650), whose name is written in Latin as:
Cartesius. He wrote a famous book1 in which he explained what the ‘scien-
tific method’ is and why it is important. The character of the book is mainly
philosophical, but in an appendix, he applies his own ideas to develop a rel-
evant new area for that time: the analytical method, which is the theory of
algebraic similarities and their relation with geometry.
Let us call the above function f . Then for example, it holds that f (0, 1) =
1. From this, we see that the choice a = 0 and b = 1 leads to the value 1
for the whole proposition ¬a ∨ b.
If we do the same for the abstract proposition (a ∧ b) ∨ c (see Section 3.2),
then we get as domain for (a, b, c) a set of eight elements:
{(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.
(We can also see this as a collection of all the sequences of 0s and 1s, with
length 3. Such a sequence of length 3 is also called a triple. In general: the
1 R. Cartesius: Discours de la méthode pour bien conduire sa raison et chercher la
• Also the abstract propositions a and ¬¬a have the same Boolean
function:
⎧
⎨ a
0 2→ 0
⎩
1 2→ 1
It is not difficult to see that this table implies that any abstract propo-
sition of the form P ⇒ Q is equivalent to one of the form ¬P ∨ Q.
Take for example P = c ∨ d and Q = ¬¬e. Then P ⇒ Q is equal to
(c ∨ d) ⇒ ¬¬e and ¬P ∨ Q is equal to ¬(c ∨ d) ∨ ¬¬e. If we now choose
values for c, d and e, then P gets a value (0 or 1) and so does Q. But
the value of P ⇒ Q is then equal to that of ¬P ∨ Q, exactly like that
of a ⇒ b is equal to that of ¬a ∨ b for given values of a and b. Hence,
(c ∨ d) ⇒ ¬¬e (of the form P ⇒ Q) has – for every triple of values of
c, d and e – the same value as ¬(c ∨ d) ∨ ¬¬e (of the form ¬P ∨ Q).
b c ¬c
0 0 1
0 1 0
1 0 1
1 1 0
c ¬c
0 1
1 0
Remark 4.2.1 In this section we always began with the truth-function and
afterwards we looked for ‘suitable’ abstract propositions which fit this truth-
function.
Those who do not want to search wildly like above, can instead look for
such suitable propositions in a canonical (or standard) way. We give here
the canonical propositions that can be found from f and g. Detect, with
the use of these examples, the standard recipe for finding such propositions.
Check also that both examples ‘make sense’.
For f : ((¬a ∧ ¬b) ∨ (¬a ∧ b)) ∨ (a ∧ b).
For g: (¬b ∧ ¬c) ∨ (b ∧ ¬c).
You see that this principle works (except when the result is always 0, see
for this case Section 4.4), but the drawback is that you get fairly complex
formulas.
32 CHAPTER 4. THE BOOLEAN BEHAVIOUR OF PROPOSITIONS
This means for example that, in practice, a proposition having the form
P ⇒ Q can be exchanged with the equivalent proposition ¬P ∨ Q, and
vice versa. This exchange of one proposition by an equivalent one, is called
calculating with propositions. We return to this point in detail in Chapter 6.
Remark 4.4.1 In some computer science books one expresses the fact that
an abstract proposition is a tautology, by writing it inside (left and right)
brackets. Hence, one writes: [b ∨ ¬b], [a ⇒ (b ⇒ a)], but not: [b ∧ ¬b] or
[a ⇒ ¬a].
a b a⇒a b⇒a a ⇒ (b ⇒ a)
0 0 1 1 1
0 1 1 0 1
1 0 1 1 1
1 1 1 1 1
• In the same way, we can see that all contradictions are equivalent (or
have the same truth-values).
• However, not all contingent propositions are equivalent. See for ex-
ample, the truth-tables of a ∧ b and a ∨ b.
With the introduction of True and False, we can extend our definition
of abstract propositions (Definition 2.3.1) with a second basis case:
(The original basis-step of this definition, which said that all proposition
variables are abstract propositions, has now become Basis (case 1).)
The words True and False are called proposition constants. They can
‘take part’ in the building of abstract propositions, in the same way as
proposition variables. The abstraction goes actually less far than with
proposition variables like a and b, which can be substituted by well-formed
propositions. It will be clear that True can only be substituted by a propo-
sition which is always true (like 0 = 0 or x ≥ x) and False can only be
substituted by a proposition which is always false (like 0 = 1 or x < x).
Examples of abstract propositions according to the new definition include:
a ⇒ False, (a ∧ True) ⇔ a.
We can, for example, specialize a ⇒ False to: ‘If it is raining, then 0=1’,
but not to: ‘If it is raining, then 0=0’ (because ‘0=0’ can only be true) and
also not to ‘If it is raining, then x > 2’ (because x > 2 can either be true or
false).
Below we give the truth-tables for the above propositions. By doing so,
we see that the first example is a contingent proposition, and the second is
a tautology:
36 CHAPTER 4. THE BOOLEAN BEHAVIOUR OF PROPOSITIONS
4.5 Exercises
4.1 Which Boolean functions correspond to:
(a) a ⇒ ¬b
(b) ¬(a ∧ b)
(c) a ∧ (b ∨ c)
(d) ¬a ∨ (a ∧ ¬c)
(e) a ⇒ (b ⇒ a) and a ⇒ a
(f) (a ∧ b) ∨ b and (b ∧ c) ∨ (b ∧ ¬c).
4.5 Give an example of a tautology with only proposition letter a, without
True or False, and with only parentheses and
(a) connective ⇒
(b) connectives ∨ and ¬
(c) connectives ∧ and ¬
(d) connective ⇔
4.6 Show the equivalence of
(a) False ⇒ a and True
(b) True ⇒ a and a
(c) a ⇒ False and ¬a
(d) a ⇒ True and True
4.7 Show that every abstract proposition which is built only with propo-
sition letter a and connective ⇒, is either a tautology, or equivalent
to a (hence a contingency).
4.8 (a) Show that there are infinitely many classes of equivalent propo-
sitions.
(b) Show that every class of equivalent propositions has infinitely
many propositions.
38 CHAPTER 4. THE BOOLEAN BEHAVIOUR OF PROPOSITIONS
"
" "
True
a ∨ ¬a " a⇒a
} tautologies
a ⇒ (b ⇒ a)
" "
¬a ∨ b a⇒b
} contingencies
"
" "
¬¬¬a
¬a a ⇒ False
" "
a ∧ ¬a
"
¬(a ⇒ a) } contradictions
False
Chapter 5
Standard equivalences
val
Remark 5.1.1 One usually gives a meta-symbol such as == a lower pri-
ority (see Section 2.5) than all ‘language symbols’, such as the connectives.
val val
Hence we should read P == Q ∧ R as P == (Q ∧ R).
39
40 CHAPTER 5. STANDARD EQUIVALENCES
We start with simple cases of propositions that have the same truth-
values, and which are also intuitively obvious:
Commutativity:
val
P ∧ Q == Q ∧ P ,
val
P ∨ Q == Q ∨ P ,
val
P ⇔ Q == Q ⇔ P .
Note that the ⇒ is missing here: P ⇒ Q does not have the same truth-
value as Q ⇒ P ; see the corresponding truth-tables, which differ in the last
column:
P Q P ⇒Q P Q Q⇒P
0 0 1 0 0 1
0 1 1 0 1 0
1 0 0 1 0 1
1 1 1 1 1 1
The Commutativity rules are easy to remember because as you may have
noticed, the connectives ∧, ∨ and ⇔ are their own mirror image on the
vertical axis. (This is not the case though for the connective ⇒.)
Remark 5.1.2 The word ‘commutativity’ comes from the Latin word ‘com-
mutare’, which is ‘to exchange’.
Other very common cases of ‘having the same truth-values as’ or ‘being
equivalent to’ include:
Associativity:
val
(P ∧ Q) ∧ R == P ∧ (Q ∧ R),
val
(P ∨ Q) ∨ R == P ∨ (Q ∨ R),
val
(P ⇔ Q) ⇔ R == P ⇔ (Q ⇔ R)
Remark 5.1.3 The word ‘associativity’ comes from the Latin word ‘asso-
ciare’, which means ‘to associate’, ‘to relate’.
P Q R P ⇔Q (P ⇔ Q) ⇔ R Q⇔R P ⇔ (Q ⇔ R)
0 0 0 1 0 1 0
0 0 1 1 1 0 1
0 1 0 0 1 0 1
0 1 1 0 0 1 0
1 0 0 0 1 1 1
1 0 1 0 0 0 0
1 1 0 1 0 0 0
1 1 1 1 1 1 1
Remark 5.1.4 We will soon explain a method with which we can ‘ex-
change’ a formula with another equivalent one. There, we shall use as much
as necessary the Commutativity rule and the Associativity rule, but without
saying so. For example, we write b ∨ (a ⇒ c) instead of (a ⇒ c) ∨ b without
giving a reason (this reason would have been: ‘Commutativity’).
With the Associativity rule, we will even go further: we write for example:
P ∧ Q ∧ R without explaining how the parentheses are written: (P ∧ Q) ∧ R
or P ∧ (Q ∧ R). This is justified because these two propositions have the
same truth-values.
For the same reason, one writes P ∨ Q ∨ R and P ⇔ Q ⇔ R without
parentheses. Be careful: outside logic P ⇔ Q ⇔ R usually means something
different! (See the following section.)
Remark 5.1.5 With the last sentences, we depart from Chapter 2. There,
we made sure that a formula can only be ‘read’ in one way, even if the
parentheses were dropped. With formulas like a ∧ b ∧ c, this cannot work
any more, and hence we avoided such formulas. (Unless we assume the left
or right associativity, but we did not want to commit ourselves to these in
Section 2.5).
This is no longer the case. The formula a ∧ b ∧ c can now equally mean
(a∧b)∧c or a∧(b∧c). These are two different propositions, although they are
equivalent, i.e. have the same truth-values! (That they are different shows
even more clearly by drawing their trees.)
• if ... then. The proposition ‘If I come, then I will bring a bottle of
wine with me’ expresses only the implication. The first proposition,
‘I come’, can be true or false. I don’t need to come at all . But if I
come, I will bring a bottle of wine with me (at least, I promise this).
I would only have said a falsity if I do come and don’t bring with me
any bottle of wine.
The word ‘therefore’ between two propositions expresses hence much more
than only the truth of the implication: it also gives the truth of the first
proposition and as a conclusion the truth of the second proposition.
For this reason it is confusing that ‘⇒’ is not only used for ‘if ... then’,
but also for ‘therefore’. Moreover, it happens in sequence. For example:
x2 ≥ 0 ⇒ x2 + 2x + 1 ≥ 2x + 1 ⇒ (x + 1)2 ≥ 2x + 1
This is not an example of a string of two implications, but of a ‘truth at
the beginning’ followed by two (mathematical) conclusions. In order to be
precise, we have:
(3) And from this, again on mathematical grounds, the truth of the final
conclusion (x + 1)2 ≥ 2x + 1 follows.
Idempotence:
val
P ∧ P == P ,
val
P ∨ P == P .
Remark 5.3.1 The word ‘idempotence’ comes from Latin. ‘Idem’ means
‘the same’ and ‘potentia’ means ‘power’. It is actually the case for both
∧ and ∨ that the ‘second power’ of P is equal to P itself. You see this
better when you replace ‘∧’ by the multiplication sign (see Section 3.6):
val
P ∧ P == P becomes in that case P · P = P , and hence P 2 = P . In the
val
same way you can write P ∨P == P as P + P = P , again a kind of second-
power, but then for ‘+’. (In Section 3.6 we saw that not only 0 + 0 = 0 in
Boolean logic, but also that 1 + 1 = 1!)
Double Negation:
val
¬¬P == P .
Remark 5.3.2 ‘Double Negation’ is also called ‘involution’, after the Latin
‘involvere’, which is ‘to wrap’: when P becomes wrapped in two ¬’s, it keeps
its own truth value.
Inversion:
val
¬True == False,
val
¬False == True.
The rules below say what happens with True and False if they come
across an ∧ or an ∨:
True/False-elimination:
val
P ∧ True == P ,
val
P ∧ False == False,
val
P ∨ True == True,
val
P ∨ False == P .
5.4. RULES WITH TRUE AND FALSE 45
Remark 5.4.1 In Boolean algebra (see Section 3.6 and Remark 3.6.1)
where ∧ is written as ‘.’ and ∨ is written as ‘+’, True stands for the number
1 and False for 0. The above True-False-laws then become:
P . 1 = P,
P . 0 = 0,
P + 1 = 1,
P + 0 = P.
Check that this is indeed the case, both for P = 1 and for P = 0.
Another important rule which involves False, is the following:
Negation:
val
¬P == P ⇒ False
val
(Remember when reading this formula that == has the lowest priority!)
We already saw the equivalence of ¬P and P ⇒ False at the end of
Chapter 4. The above rule expresses that ‘not-P ’ ‘means’ the same as ‘P
implies falsity’.
Other important rules with True and False are:
Contradiction:
val
P ∧ ¬P == False
Excluded Middle:
val
P ∨ ¬P == True.
Remark 5.5.1 The word ‘distributivity’ comes from the Latin ‘distribuere’,
which is: ‘to distribute’ or ‘to divide’. In the first rule, for example, P and
∧ are together divided over Q and R, because Q becomes P ∧ Q, and R
becomes P ∧ R. One usually says by the first equivalence that ∧ distributes
over ∨. By the second it is the case that ∨ distributes over ∧. Both are
hence the case.
The following two rules treat the confrontation of ¬ on one hand with ∧
resp. ∨ on the other. Also ¬ distributes in a certain sense, but it ‘exchanges
∧ and ∨’ (this means: ∧ becomes ∨ and vice versa):
De Morgan:
val
¬(P ∧ Q) == ¬P ∨ ¬Q,
val
¬(P ∨ Q) == ¬P ∧ ¬Q
5.6. RULES WITH ⇒ 47
Remark 5.5.2 These rules are called after Augustus De Morgan, a mathe-
matics lecturer at the University College London, who published in 1847 the
book ‘Formal Logic’.1
Implication:
val
P ⇒ Q == ¬P ∨ Q.
The following rule says something about the ‘permutation’ of both sides of
an implication P ⇒ Q. This can only happen properly if both sub-formulas
get a ¬:
1 A. De Morgan: Formal Logic: or, The Calculus of Inference, Necessary and Proba-
Contraposition:
val
P ⇒ Q == ¬Q ⇒ ¬P .
We can check this with the truth tables. But we can also check it as
follows:
(1) P ⇒ Q is equivalent to ¬P ∨ Q (by the Implication rule)
(2) and this is equivalent to Q ∨ ¬P (by Commutativity),
(3) which is equivalent to ¬¬Q ∨ ¬P (by Double Negation),
(4) which in its turn is equivalent to ¬Q ⇒ ¬P (by Implication, again).
(In Chapter 6 we shall write such an argument with more structure.)
Bi-implication:
val
P ⇔ Q == (P ⇒ Q) ∧ (Q ⇒ P ).
Self-equivalence:
val
P ⇔ P == True.
This can be seen as follows: First look at the formula P ⇒ P , the ‘self-
implication’, with unique arrow. It holds that:
(1) P ⇒ P is equivalent to ¬P ∨ P , by Implication, and
(2) ¬P ∨ P is in its turn equivalent to True, by (Commutativity and) Ex-
cluded Middle, therefore
val
(3) P ⇒ P == True.
5.8. EXERCISES 49
5.8 Exercises
5.1 Prove that:
(a) P ⇒ Q is not equivalent to Q ⇒ P .
(b) P ⇒ Q is not equivalent to ¬P ⇒ ¬Q.
(c) P ⇒ (Q ⇒ R) is not equivalent to (P ⇒ Q) ⇒ R.
(d) P ⇔ Q ⇔ R is not equivalent to (P ⇔ Q) ∧ (Q ⇔ R).
5.2 In a mathematics book we read:
y = x2 + 2x + 2 ⇒ y = (x + 1)2 + 1 ⇒ y ≥ 1.
As true as a die
val
6.1 Basic properties of ==
We begin with a proof of a lemma (i.e., an auxiliary theorem), which says
val
that the meta-symbol == is reflexive, symmetric and transitive:
Lemma 6.1.1
val
(1) Reflexivity: P == P .
val val
(2) Symmetry: If P == Q, then also Q == P .
val val val
(3) Transitivity: If P == Q and if Q == R, then P == R.
• Proof of part (3) When in the truth-table, P and Q have the same
columns, and also Q and R have the same columns, then the columns
of P and R must also be equal.
51
52 CHAPTER 6. WORKING WITH EQUIVALENT PROPOSITIONS
Remark 6.1.2 The name ‘Reflexivity’ for (1) means something like ‘refer-
ring back to oneself ’: P is in relation with itself (P ). The name ‘Symmetry’
for (2) does not need any explanation. With ‘Transitivity’ one means in
mathematics a ‘transfer-of-property’: if P is related to Q and Q is related
to R, then P is also related to R. (‘Trans-ire’ is Latin for ‘to continue’.)
val
Now we give an important relation between the meta-symbol == and
the connective ⇔:
val
Lemma 6.1.3 If P == Q, then P ⇔ Q is a tautology, and vice versa.
val
Proof: When P == Q, then P and Q have the same column of zeros
and ones in the truth-table. Hence, at the same height in these columns, P
and Q always have the same truth-value (either both 0, or both 1). In the
column of P ⇔ Q there is hence always a 1, and so this is a tautology.
On the other hand, when P ⇔ Q is a tautology then in the column of
P ⇔ Q there is everywhere a 1, hence at the same height in the columns
of P and Q the same truth-values must appear (either both 0, or both 1).
val
Hence, these columns must be completely equal, and so P == Q.
val
Example: we compare the standard equivalence ¬(P ∨ Q) == ¬P ∧ ¬Q
(one of the two rules of De Morgan) with formula (¬(P ∨ Q)) ⇔ (¬P ∧ ¬Q),
denoted ϕ in the table below:
P Q P ∨Q ¬(P ∨ Q) ¬P ¬Q ¬P ∧ ¬Q ϕ
0 0 0 1 1 1 1 1
0 1 1 0 1 0 0 1
1 0 1 0 0 1 0 1
1 1 1 0 0 0 0 1
Since the two columns under ¬(P ∨ Q) and ¬P ∧ ¬Q are equal, it follows
val
that ¬(P ∨ Q) == ¬P ∧ ¬Q. The last column shows that the formula
ϕ ≡ (¬(P ∨ Q)) ⇔ (¬P ∧ ¬Q) is a tautology.
Remark 6.1.4 The symbol ‘≡’ is usually reserved for ‘being identical to’.
It is a meta-symbol, used to ‘talk about’ formulas. Similarly, ̸≡ means ‘being
not identical to’.
So we have for example: 1 + 2 ≡ 1 + 2, because the two formulas are
identical; but 1 + 2 ̸≡ 2 + 1, 1 + 2 ̸≡ (1 + 2), 1 + 2 ̸≡ 3.
Just above the present Remark, we noted in passing that the formula
represented by ϕ is identical to the formula (¬(P ∨ Q)) ⇔ (¬P ∧ ¬Q). This
is because we introduced ϕ – right above the table – as a kind of ‘name’ for
the latter formula.
6.2. SUBSTITUTION, LEIBNIZ 53
We have seen at the end of the previous chapter two examples of this:
val val
• P ∨ Q == Q ∨ P (Commutativity), hence also ¬P ∨ Q == Q ∨ ¬P .
Here we have substituted the formula ¬P for the letter P in the first
equivalence.
val val
• P ⇒ Q == ¬P ∨ Q (Implication), hence also Q ⇒ ¬P == ¬Q ∨ ¬P .
Here we have substituted Q for the letter P and at the same time we
have substituted ¬P for the letter Q.
Substitution is not as simple as it seems. We must carry it out consis-
tently (for all P ’s, for example, none can be forgotten and not be substituted
for). And we may do it simultaneously as in the last example.
The following lemma does not deal with substitution (for a letter P , Q,
. . . ), but with a single replacement of a sub-formula of a bigger formula.
(Be careful: such a sub-formula can be a single letter like P , but this is not
at all necessary!) When we replace this sub-formula by an equivalent one,
the resulting ‘whole’ formulas are also equivalent:
Lemma 6.2.3 (Leibniz) If in an abstract proposition φ, sub-formula ψ1
is replaced by an equivalent formula ψ2 , then the old and the new φ are
equivalent.
In the notation of Chapter 1 this is written as follows:
val
ψ1 == ψ2
val
. . . ψ1 . . . == . . . ψ2 . . .
(the old φ) (the new φ)
In this picture you must read . . . ψ1 . . . and . . . ψ2 . . . as being
literally the same formulas, except for that one part where in the one we
have ψ1 and in the other we have ψ2 .
Remark 6.2.4 This lemma is called ‘the rule of Leibniz’ or ‘Leibniz’s law’
in honor of G. W. Leibniz, a German mathematician who lived from 1646 to
1716. Gottfried Leibniz developed the principles of differential and integral
analysis, approximately at the same time as the Englishman Isaac Newton.
With these principles, the foundation of ‘modern’ mathematics was set up.
In addition, Leibniz is also considered as the originator of modern (formal)
logic, because he was the first to search for the fundamental properties of the
connectives. For centuries, the work of Leibniz has had a great influence on
the development of logic and mathematics.1
1 See for example: Bertrand Russell: A Critical Exposition of the Philosophy of Leib-
Example 6.2.5
val val
• Because P == ¬¬P , then by Leibniz also P ∨ Q == (¬¬P ) ∨ Q.
Here, the sub-formula P in P ∨ Q is replaced by the equivalent sub-
formula ¬¬P , which results in (¬¬P ) ∨ Q. Because the sub-formulas
are equivalent, then so are the whole formulas.
val
• Because ¬(P ∧ Q) == ¬P ∨ ¬Q, the following equivalence holds by
val
applying Leibniz: P ⇒ (Q ⇒ ¬(P ∧ Q)) == P ⇒ (Q ⇒ (¬P ∨ ¬Q)).
val
• Leibniz and Substitution can occur together: Because P ∧ True == P ,
val
we also have ((Q ∨ R) ∧ True) ∨ S == (Q ∨ R) ∨ S. We can see this
as follows:
val
– Here, first Q ∨ R is substituted for P in P ∧ True == P ; because
val
of Substitution, it is the case that (Q ∨ R) ∧ True == Q ∨ R.
– Thereafter, Leibniz is applied to ((Q ∨ R) ∧ True) ∨ S as follows:
the sub-formula (Q∨R)∧True is replaced by the equivalent Q∨R.
val
(1) ¬(P ⇒ Q) == ¬(¬P ∨ Q) by applying Leibniz to the Implication rule
val
(namely: P ⇒ Q == ¬P ∨ Q),
val
(2) ¬(¬P ∨ Q) == ¬¬P ∧ ¬Q by selecting one of the rules of De Morgan,
val
namely: ¬(P ∨ Q) == ¬P ∧ ¬Q, and applying Substitution of ¬P
for P ,
val val
(3) ¬¬P ∧ ¬Q == P ∧ ¬Q by the Double Negation rule (¬¬P == P )
and Leibniz.
Between the braces, the reason (or the hint ) for the equivalence of the
formula above and the formula below is given. As we already said, Substi-
tution and/or Leibniz are rarely named in the hint.
Note that Lemma 6.1.1 has as a consequence that each pair of proposi-
tions in the above scheme are equivalent, especially the first with the last.
Often, this work begins in order to establish the equivalence of the first and
last propositions. Hence, the scheme above can have the following conclu-
sion:
val
¬(P ⇒ Q) == P ∧ ¬Q.
It describes the interesting observation that the implication P ⇒ Q is
not true if and only if P is true and Q is not. (But we knew this already.)
We give a second more involved example. With this example, we show
that the proposition P ⇔ Q is equivalent to (P ∧ Q) ∨ (¬P ∧ ¬Q). In words:
P ⇔ Q holds if and only if P and Q are both true or none of them is true.
P ⇔Q
val
== { Bi-implication }
(P ⇒ Q) ∧ (Q ⇒ P )
val
== { Implication, twice }
(¬P ∨ Q) ∧ (¬Q ∨ P )
val
== { Distributivity }
(¬P ∧ (¬Q ∨ P )) ∨ (Q ∧ (¬Q ∨ P ))
val
== { Distributivity, twice }
(¬P ∧ ¬Q) ∨ (¬P ∧ P ) ∨ (Q ∧ ¬Q) ∨ (Q ∧ P )
val
== { Contradiction, twice }
(¬P ∧ ¬Q) ∨ False ∨ False ∨ (Q ∧ P )
val
== { True/False-elimination, twice }
(P ∧ Q) ∨ (¬P ∧ ¬Q)
This whole calculation depends on repeatedly applying Leibniz and Sub-
stitution, without mentioning these applications! Sometimes this may not
6.4. EQUIVALENCE IN MATHEMATICS 57
(Here we have: When the one has truth-value 1, then so does the other .
A consequence of this is that: When the one has truth-value 0, then so does
the other .)
We can also speak in more general terms about equivalence by not speak-
ing about 0 or 1, but about ‘true’ or ‘false’, respectively. In such a general
case we may have all sorts of domains. Hence, not only domains with zeros
and ones, but also domains with for example N or Z. (The symbol N is
used for the set of all natural numbers, i.e. the set with elements 0, 1, 2,
and so on. The symbol Z stands for the set of integers or integer numbers,
consisting of 0, 1 and −1, 2 and −2, . . .. See also Part III, Section 19.1.)
If we admit this kind of domains as well, this means that truth-tables are
no longer suitable, because there are now too many (even infinitely many)
possibilities, instead of 2n .
P and Q are then equivalent when:
(1) Whenever P is true in the domain, then so is Q,
58 CHAPTER 6. WORKING WITH EQUIVALENT PROPOSITIONS
With this generalization of the concept ‘is equivalent to’ we can also,
as described in the above method, ‘calculate’ with mathematical formulas
where in the hints we can have ‘Mathematics’ (or ‘Algebra’, or something
like that) to express that a certain equivalence has its justification not on
logical grounds, but on mathematical ones. See the following example, where
we use (among other things) the mathematical motivation that the formula
0 < x < 2 is equivalent to the formula 0 < x < 1 ∨ x = 1 ∨ 1 < x < 2:
0 < x < 2 ∧ x ̸= 1
val
== {Mathematics }
(0 < x < 1 ∨ x = 1 ∨ 1 < x < 2) ∧ ¬(x = 1)
val
== { Distributivity }
(0 < x < 1 ∧ ¬(x = 1)) ∨ (x = 1 ∧ ¬(x = 1))∨
(1 < x < 2 ∧ ¬(x = 1))
val
== { Mathematics (left and right), Contradiction (middle) }
0 < x < 1 ∨ False ∨ 1 < x < 2
val
== { True/False-elimination }
0<x<1∨1<x<2
6.5 Exercises
6.1 Show that:
val val val val
(a) If P == Q and Q == R and R == S, then P == S.
val val val
(b) If P == Q and Q = ̸=
= R, then P =
̸=
= R.
(c) If P ⇔ Q is a tautology and Q ⇔ R is a tautology, then P ⇔ R
is a tautology.
val
(P =
̸=
= Q means: P is not equivalent to Q.)
6.2 Show the following equivalences by calculating with propositions. Al-
ways state precisely:
(1) which standard equivalence(s) you use,
(2) whether you apply Substitution or Leibniz, or both,
(3) and how you do this.
val
(a) ¬P ∧ ¬P == ¬P
val
(b) P == ¬P ⇒ False
val
(c) (P ⇒ Q) ∨ ¬(P ⇒ Q) == True
val
(d) P ∧ (Q ∨ Q) == P ∧ Q
val
(e) P ⇒ ¬Q == ¬(P ∧ Q)
6.3 Show with calculations that:
val
(a) P ⇒ Q == (P ∧ Q) ⇔ P
val
(b) P ∧ (P ∨ Q) == P
val
(c) P ∨ (P ∧ Q) == P
val
(d) P ∧ (P ⇒ Q) == P ∧ Q
val
(e) P ∨ (¬P ∧ Q) == P ∨ Q
6.4 Show with calculations that 0 < x2 − 2x + 1 < 9 is equivalent to
x ̸= 1 ∧ −2 < x < 4.
6.5 Show with a calculation that the following formulas are tautologies:
(a) ¬(P ⇒ Q) ⇔ (P ∧ ¬Q)
(b) ((Q ⇒ P ) ⇒ ¬Q) ⇔ (¬P ∨ ¬Q)
(c) P ∨ ¬((P ⇒ Q) ⇒ P )
60 CHAPTER 6. WORKING WITH EQUIVALENT PROPOSITIONS
Strengthening and
weakening of propositions
P Q ¬P ¬P ∧ Q P ⇒Q
0 0 1 0 1
0 1 1 1 1
1 0 0 0 0
1 1 0 0 1
61
62 CHAPTER 7. STRENGTHENING AND WEAKENING
• ‘x > 10’ is stronger than ‘x > 0’. This holds on mathematical grounds:
if x is greater than 10, then x is greater than 0, but not vice versa
(take x = 5). You can also say: ‘x > 10’ gives more information than
‘x > 0’, because if x > 10 then you know, apart from x is greater than
0, also that x is not between 0 and 10, and also that x is not precisely
10.
Note that with the above definition of ‘stronger’, it can happen that P is
called stronger than Q, when in fact it is as strong as (i.e.: equivalent to)
Q. Something similar holds for ‘weaker’.
val
We express that ‘P is stronger than Q’ with P |== Q, and ‘Q is weaker
7.2. STANDARD WEAKENINGS 63
∧-∨-weakening:
val
P ∧ Q |== P ,
val
P |== P ∨ Q.
With Substitution (Q for P and at the same time P for Q) and with
Commutativity the following follows (see Proposition 7.4.1):
val
P ∧ Q |== Q and
val
Q |== P ∨ Q.
Recalling the earlier discussion about ‘stronger’ and ‘weaker’ (‘The truer
something is, the weaker it is’) it is no longer surprising that False is the
strongest proposition and True is exactly the weakest (‘The truest is the
weakest’):
Extremes:
val
False |== P ,
val
P |== True.
False P True
0 0 1
0 1 1
val
7.3 Basic properties of |==
val
In Section 6.1 we gave the basic properties for == . We give now lemmas
val val val
describing the properties of |== and ==| and the connection with == .
VAL
7.3. BASIC PROPERTIES OF |== 65
The proof of (1) follows from the truth-tables: if at every 1 in the column
of P also a 1 occurs in the corresponding place in the column of Q, then
we can never have the situation where ‘the truth-value of P is 1 and the
truth-value of Q is 0’, in other words, the truth-value of P ⇒ Q is never 0,
therefore it is always 1. A similar argument applies for the other direction.
Part (2) follows from part (1) and Lemma 7.3.1, part (2).
66 CHAPTER 7. STRENGTHENING AND WEAKENING
Be careful that here, we are talking about substitution, and this means
that: all letters P must be replaced by one and the same formula.
Example 7.4.2 One of the standard weakening rules expresses the fact that
val
P ∧ Q |== P . From this, it follows with Substitution that for example also
val
(Q ⇒ R) ∧ (P ∨ Q) |== Q ⇒ R.
But now the case ‘Leibniz’. You would expect that the following general
val
rule holds for |== (a kind of ‘Leibniz for weakenings’, see also Section 6.2),
but this does not appear to be the case:
val
ψ1 |== ψ2
val
. . . ψ1 . . . |== . . . ψ2 . . .
(the old φ) (the new φ)
We give two examples, one where things work and the other where things
go wrong:
val val
• P |== P ∨ Q and also P ∧ R |== (P ∨ Q) ∧ R.
val val
• P |== P ∨ Q, but not ¬P |== ¬(P ∨ Q)
val
(instead : ¬P ==| ¬(P ∨ Q)).
¬P
val
==| { ∧-∨-weakening }
¬P ∧ ¬Q
val
== { De Morgan }
¬(P ∨ Q)
val
Note that we have used here the symbol ==| in the margin in order to
express that ¬P is weaker than ¬P ∧ ¬Q. This follows (exclusively) by
Substitution (hence without Leibniz!) from the first ∧-∨-weakening rule.
The final conclusion from this calculation (use Lemma 7.3.3) is indeed:
val
¬P ==| ¬(P ∨ Q).
The rule of Leibniz does therefore not work in general for calculations
val val
like the above one with |== or ==| in the margin. We therefore reserve the
val
rule of Leibniz for the case that == appears in the margin.
As an exception, we add the following standard equivalences, which make
things easier in some cases. Both standard equivalences are an application
val
of the rule of Leibniz for |== , which does hold in these special cases:
Monotonicity:
val val
If P |== Q, then P ∧ R |== Q ∧ R,
val val
If P |== Q, then P ∨ R |== Q ∨ R.
val val
These rules are also valid with ==| everywhere instead of |== . This
follows from part (2) of Lemma 7.3.1.
val
Above we gave a calculation with ==| in the margin. Such calculations
val
are useful if we want to reach a final conclusion of the form . . . ==| . . . .
val
Similarly, one can make calculations with |== in the margin.
val val
Of course it is not useful to use both |== and ==| together in one calcula-
tion, because this stands in the way of reaching a final conclusion. Example:
the following calculation is correct:
P ∧Q
val
|== { ∧-∨-weakening }
P
val
==| { ∧-∨-weakening }
P ∧ R,
but no conclusion can be reached. It even holds that P ∧ Q and P ∧ R
are incomparable!
68 CHAPTER 7. STRENGTHENING AND WEAKENING
Remark 7.4.3 One may compare the rule of Leibniz with what happens
when calculating in algebra. There for example, for multiplication, a sort of
‘Leibniz’ holds with equality (if x = y, then also x · z = y · z), but not with
greater-than-or-equal: if x ≥ y, then we don’t know for sure that x·z ≥ y ·z.
This depends on the ‘sign’ of z: if z is positive or 0, then this holds. If z
on the other hand is negative, then it does not follow that x · z ≥ y · z, but
that x · z ≤ y · z.
A special case of this is multiplication with −1: if x = y, then −x = −y,
but if x ≥ y, then −x ≤ −y. Hence, also in this last case Leibniz does not
apply.
7.5 Exercises
7.1 Check for every pair of the propositions given below whether they
are comparable (one is stronger than the other), or whether they are
incomparable.
(a) P ∨ Q and P ∧ Q
(b) False and True
(c) P and ¬(P ∨ Q)
(d) P and ¬(P ⇒ Q).
7.2 Check whether the following propositions are valid:
val val val val
(a) If P |== Q, Q |== R and R |== S, then P |== S
val val val
(b) If P |== Q and Q |== P , then P == Q
val val val
(c) If P |== Q and P |== R, then Q == R
val val
(d) If P |== Q and P |== R, then Q and R are incomparable.
7.3 Show with a calculation:
val
(a) P ⇒ Q |== (P ∧ R) ⇒ (Q ∧ R)
val
(b) ¬(P ⇒ ¬Q) |== (P ∨ R) ∧ Q
7.4 Show with calculations that the following formulas are tautologies:
(a) (R ∧ (P ⇒ Q)) ⇒ ((R ⇒ P ) ⇒ Q)
(b) ((P ⇒ (Q ∨ R)) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)
7.5. EXERCISES 69
71
72 CHAPTER 8. PREDICATES AND QUANTIFIERS
By this command, the state of the computer has changed from for exam-
ple S ′ = ⟨x = 25, y = 12⟩ to S ′′ = ⟨x = 25, y = 30⟩.
8.2 Predicates
We divert our attention from propositions of everyday life (‘It is a beautiful
day today’) to propositions in mathematics and computer science. As we ex-
plained already, object variables occur regularly in these latter propositions
8.2. PREDICATES 73
The predicate 3m + n > 3 has two object variables and hence it is called
a two-place or a binary predicate. The corresponding graph is hence two-
dimensional.
A predicate with one object variable, like m ̸= 4 on R, is called a one-
place or a unary predicate. The graph which corresponds to it is one-
dimensional. In this case the graph consists of the reals (e.g. represented
as a horizontal line) where the point with coordinate 4 is excluded. The
predicate m ̸= 4 is always True, except if m = 4.
For predicates with three or more variables it becomes more difficult to
draw the graphs, because we will need to go to third or higher dimensions.
74 CHAPTER 8. PREDICATES AND QUANTIFIERS
❇
❇ ↑
❇ n
❇
❇
❇
❇
❇
❇
! ❇ !
(−1, 2) ❇ (1, 2)
❇
1 ❇
❇
❇
1 m→
Figure 8.1: The predicate 3m + n > 3
8.3 Quantifiers
In Chapter 2 we have seen how one can build new propositions from old
ones by using the connectives. In this section we explain another method
of building propositions. Such a method is based on the use of predicates.
First, we give a couple of examples: Look at the predicate m ̸= 4, where
m has the domain Z. This is not a proposition, it will become one only
after filling a value for m.
Now there are also two other methods of making a proposition from
m ̸= 4.
• universal Put at the beginning of the predicate the words: ‘For every
m it holds that...’. This gives here : ‘For every m it holds that m ̸= 4’.
This is a proposition, because it can only be true or false (in this case,
with m an arbitrary integer number, it is false).
We write this as follows: ∀m [m ∈ Z : m ̸= 4], which should be read as
the proposition: ‘For all m, with m an element of Z, it holds that m
is different from 4’.
The signs ∀ and ∃ are called quantifiers, respectively the universal quan-
tifier and the existential quantifier . Propositions starting with a quantifier,
like ∀m [m ∈ Z : m ̸= 4] and ∃m [m ∈ Z : m ̸= 4], are called quantified
predicates.
It is worth noting that ∀m [m ∈ Z : m ̸= 4] is no longer a ‘real’ predicate.
You can actually no longer fill a value for m in the whole formula. Try it
out with m = 5. Then you get ∀5 [5 ∈ Z : 5 ̸= 4] which doesn’t make any
sense. To sum up, the one-place predicate m ̸= 4 (where you could replace
m by 5 say) is made by the ∀-quantification into a ‘zero-place or nullary
predicate’, in other words, into a proposition.
One says in this case that the variable m, which was first free (hence
‘replaceable’), became bound by quantification. It is important to classify
in a complex formula which variables are bound and which are free. As an
example of such a formula we take ∃k [k ∈ Z : k 2 + l2 = 8], in which the k is
bound, but the l is free. This means that the formula is a unary predicate
(‘in l’), and therefore it is not a proposition.
Remark 8.3.1 The symbol ∀ is nothing more than an A upside down, with
the ‘A’ of ‘All’. Similarly, ∃ is a mirror-image of an E, with ‘E’ standing for
‘Exists’. The word ‘quantifier’ is derived from the Latin ‘quantitas’ which
means ‘quantity’. Indeed, both ‘For all...’ and ‘There exists...’ have a lot to
do with quantity. ‘For all...’ is concerned with total quantity, ‘everything’,
the ‘universal’ quantity. For this reason ∀ is called the ‘universal quantifier’.
‘There is...’ is concerned with the fact that the quantity is not-empty, there
must exist at least one. From this fact, the name ‘existential quantifier’
follows.
Take some domain D and let A(x) be a predicate over D (this means
that the variable x has domain D). Then the following holds:
Examples:
• ∀m [m ∈ N : m ≥ 0] is true, because 0 ≥ 0, 1 ≥ 0, 2 ≥ 0, ...
• ∀m [m ∈ Z : m ≥ 0] is false, because it does not hold for instance that
−3 ≥ 0.
• ∃m [m ∈ N : m < 0] is false, because there is no natural number m for
which it holds that m < 0.
• ∃m [m ∈ Z : m < 0] is true, because for instance −3 < 0.
From these examples it is clear that the domain of the quantifier is very
important: the truth/falsity of the proposition depends on the domain.
It is also important to note that the truth of a quantified predicate (i.e.,
a predicate which starts with ∀ or ∃) cannot, in general, be decided with
a truth-table. If the domain is not too big, i.e. finite then we can indeed
make a list of all the possibilities for the values of the variables, on the basis
of which we can reach a conclusion, but for an infinite domain this is no
longer possible.
Example 8.3.2 For the proposition ∀m [m ∈ {0, 1, 2, 3} : m2 < 10] we can
make the following list:
m m2 < 10 truth value
0 02 < 10 True
1 12 < 10 True
2 22 < 10 True
3 32 < 10 True
From this we see that ∀m [m ∈ {0, 1, 2, 3} : m2 < 10] is true, because filling
any value for m from the set {0, 1, 2, 3}, gives as truth value: True. Note
however, that the construction of such a list only works because the set
{0, 1, 2, 3} is finite.
Remark 8.3.3 With this example we can see that ∀ is actually a repeated
∧: instead of ∀m [m ∈ {0, 1, 2, 3} : m2 < 10] we can also write a repeated
conjunction, namely: 02 < 10 ∧ 12 < 10 ∧ 22 < 10 ∧ 32 < 10. Of course,
this is only the case when the domain is finite. (If the domain is infinite we
get a conjunction of infinitely many propositions, which is not allowed as a
formula in our logic. Albeit that ∀m [m ∈ N : m ≥ 0] can be written in a
suggestive manner as 0 ≥ 0 ∧ 1 ≥ 0 ∧ 2 ≥ 0 ∧ . . . , this latter expression
is no longer a ‘legitimate’ proposition.)
Similarly, one can see ∃ as a repeated ∨. As an example: take the propo-
sition ∃k [k ∈ {0, 1, 2, 3} : k 3 = 8]. It is not hard to see that this is equivalent
to the proposition 03 = 8 ∨ 13 = 8 ∨ 23 = 8 ∨ 33 = 8.
8.4. QUANTIFYING MANY-PLACE PREDICATES 77
Remark 8.4.1 It is also usual to omit the domain description True, be-
cause True does not give any ‘information’ (recall what we said about this in
Section 7.2). So for example, we write ∀x [True : A(x)] as ∀x [A(x)]. Hence,
in the case of such an ‘empty’ domain description, where there is no domain
mentioned between the square brackets, there are two possibilities:
– There is a sensible, informative domain description, but since ‘every-
body’ knows what that is, we omit it for convenience’s sake. Or:
– The domain is described with True and hence does not restrict the rest
of the formula in any way, therefore we omit it.
computing and structured programming. See e.g. his book A Discipline of Programming,
New Jersey, 1976.
8.5. THE STRUCTURE OF QUANTIFIED FORMULAS 79
¬ !
!
!! ❅!
!❅
=
m 4
Figure 8.2: The tree of ¬(m = 4)
∀ m❦
! ¬❅!
! ❅
!
!! ❅!
!∈❅
m Z !
!! ❅!
!❅
=
m 4
Figure 8.3: The tree of ∀m [m ∈ Z : ¬(m = 4)]
∀ m❦
!
! ❅
! ❅
!! ❅! ❅❦
!∈❅ ❅
∃ n
!
m R ! ❅
! ❅
! ❅! ❅!
!∈❅ ❅
!
! ❅!
n N !>❅
!
! ❅!
!+❅ 3
!
! ❅!
!·❅ n
!
3 m
Figure 8.4: The tree of ∀m [m ∈ R : ∃n [n ∈ N : 3m + n > 3]]
8.6 Exercises
8.1 The two-place predicate A(m, n) on R2 is given by:
m < 3 ∧ m > n + 1.
(a) Check whether A(2, 0), A(2, 1) or A(2, 2) return the truth-values
False or True.
(b) Draw a graph of the predicate.
8.6. EXERCISES 81
(c) Give a simple formula for the one-place predicate A(2, n). Draw
a graph for this predicate too.
(d) Do the same for A(m, 1), A(m, 4) and A(m, m − 2).
8.2 M is the set of all people. The following predicates are given on M
respectively M2 :
M an(x) ≡ ‘x is a man’,
W oman(x) ≡ ‘x is a woman’,
Child(x, y) ≡ ‘x is a child of y’,
Y ounger(x, y) ≡ ‘x is younger than y’.
Give the following expressions in the form of formulas:
(c) There is a real number which is greater than 0 and there is a real
number which is smaller than 0.
(d) There is no real number which is both greater than 0 and smaller
than 0.
8.6 As Exercise 8.3.
(a) For each natural number, there is a natural number which is
greater than it by 1.
(b) There is no natural number which is greater than all other natural
numbers.
(c) The sum of two natural numbers is greater than or equal to each
of these two numbers.
(d) There are two natural numbers the sum of whose squares is 58.
8.7 As Exercise 8.3. D is a subset of R.
(a) If x is an element of D, then so is x + 2.
(b) There is an element of D which is greater than or equal to all
the elements of D (i.e. D has a maximum).
(c) D has precisely one element.
(d) D has precisely two elements.
8.8 Draw the trees of the following predicates. Write x2 as x ↑ 2 before
drawing the tree.
(a) m < 3 ∧ m > n + 1
(b) x2 + y 2 = z 2 ∧ x ≤ 10 ∧ y ≤ 10 ∧ z ≤ 10
8.9 Draw the trees of the following propositions:
(a) ∀m [m ∈ D : m ≤ 10]
(b) ∃m [(m ∈ D) ∧ (m > 2) : m2 < 15]
(c) ∀x [x ∈ R : ∃y [y ∈ R : y > x2 ]]
(d) ∀m [m ∈ N ⇒ m2 > m] ∨ (2 + 2 = 4)
Chapter 9
Standard equivalences
with quantifiers
• From this it follows for example that, for whatever values of x and y,
we have that ¬(x = 0 ⇒ y > 2) is equivalent to x = 0 ∧ ¬(y > 2).
83
84 CHAPTER 9. EQUIVALENCES WITH QUANTIFIERS
From the second example it seems that we must still generalize the con-
cept of equivalence in order to deal with predicates (we have actually seen
this already in Section 6.4). We give the definition for two-place predicates.
For one- or three-place predicates, a similar definition holds.
Example 9.1.2
Note that the domain description A(x) is itself also a one-place predicate!
In general, A and B can be many-place predicates, or zero-place pred-
icates (propositions). We don’t want to continuously distinguish A, A(x),
A(x, y) etc. and hence we use in this chapter the letters P and Q, without
x’s and y’s. These are the same letters P and Q used for abstract propo-
sitions (see Chapter 3), but here they mean abstract predicates instead of
abstract propositions. Always keep in mind that object variables like x and
y can occur in P , Q etc. (we just don’t say which). We do not take into
account whether such an abstract predicate P is one-, two-, many-, or even
zero-place.
We give in this chapter the most important equivalences for formulas
with quantifiers.
First, there is the rule which says that bound variables can take another
name without any problems:
Bound Variable:
val
∀x [P : Q] == ∀y [P [y for x] : Q[y for x]],
val
∃x [P : Q] == ∃y [P [y for x] : Q[y for x]].
val
∀m [m ∈ Z : ∃n [n ∈ N : 3m + n > 3]] ==
∀l [l ∈ Z : ∃k [k ∈ N : 3l + k > 3]].
Note that the above exchange rule holds only for bound variables. It does
not hold for free ones.
Example 9.2.1 The formula m + n < 6 is really different from the formula
m + i < 6. You can’t change the free n into the free i, or vice versa,
because these n and i can get different meaning outside these formulas. If
for example we already had the declaration: ‘Let n = 1 and i = 3’, then the
first formula would be equivalent to m + 1 < 6 and the second to m + 3 < 6,
and these have evidently different content.
Domain Splitting:
val
∀x [P ∨ Q : R] == ∀x [P : R] ∧ ∀x [Q : R],
val
∃x [P ∨ Q : R] == ∃x [P : R] ∨ ∃x [Q : R].
One-element rule:
val
∀x [x = n : Q] == Q[n for x],
val
∃x [x = n : Q] == Q[n for x].
88 CHAPTER 9. EQUIVALENCES WITH QUANTIFIERS
Empty Domain:
val
∀x [False : Q] == True,
val
∃x [False : Q] == False.
Of these, perhaps you did not expect the first. However, the equivalence
of ∀x [False : Q] to True can be argued as follows: Does the (arbitrarily
chosen) predicate Q hold for all x’s in the empty domain (denoted ∅)? For
this we must answer the question (see also the following section): does it
always hold that (x ∈ ∅) ⇒ Q? Yes this holds, because x ∈ ∅ is equivalent
to False, and False ⇒ Q is a tautology (check this!), therefore the answer
is indeed True!
Perhaps you don’t find such an argument convincing. For this reason, we
give another example where we split the domain D into D itself and ∅, the
empty set. We use again Leibniz for quantified predicates (see Section 9.7):
∀x [x ∈ D : R]
val val
== { True/False-elimination, using that x ∈ ∅ == False }
∀x [x ∈ D ∨ x ∈ ∅ : R]
val
== { Domain Splitting }
∀x [x ∈ D : R] ∧ ∀x [x ∈ ∅ : R]
val val
== { again because x ∈ ∅ == False }
∀x [x ∈ D : R] ∧ ∀x [False : R]
val
Therefore ∀x [x ∈ D : R] == ∀x [x ∈ D : R] ∧ ∀x [False : R]. This makes
val val
sense if ∀x [False : R] == True, but not if ∀x [False : R] == False.
9.5. DOMAIN WEAKENING 89
(And for those who still think that this argument is vague, we ask them
to take this rule as given: we bluntly postulate that the Empty Domain
rules hold.)
Domain Weakening:
val
∀x [P ∧ Q : R] == ∀x [P : Q ⇒ R],
val
∃x [P ∧ Q : R] == ∃x [P : Q ∧ R].
Example 9.5.1
Note that ∧ on the left changes to ∨ on the right and vice versa.
In Remark 8.3.3 at the end of Section 8.3 we saw, that ∀ is really a
repeated ∧, and ∃ is a repeated ∨. This we find again in the following
standard equivalences for quantified predicates, which we call ‘De Morgan’
again, because they resemble the rules with this name in Section 5.5:
De Morgan:
val
¬∀x [P : Q] == ∃x [P : ¬Q],
val
¬∃x [P : Q] == ∀x [P : ¬Q].
These standard equivalences say, read from left to right, what happens
when we move a ¬ ‘to the inside’. The ¬ sticks in this case to Q (not to
the domain description P ! ) whereas the quantifier ‘flips over’: ∀ becomes
∃ and vice versa. This ‘flipping over’ of the quantifier looks a lot like the
change of ∧ to ∨ (and vice versa) in the ‘old’ case of De Morgan.
We give a description in words which expresses that these new rules of
De Morgan are actually quite obvious:
• (¬∀ = ∃¬) If in a certain domain not all x’s satisfy Q, then there
must be x’s in that domain such that ¬Q holds, and vice versa. That
is: ‘not every = some not’.
9.6. DE MORGAN FOR ∀ AND ∃ 91
• (¬∃ = ∀¬) If in a certain domain there are no x’s for which Q holds,
then in that domain all x’s must satisfy ¬Q. That is: ‘not > every not’.
A side remark: note that ‘not every’ is completely different from ‘every
not’. The same can be said for ‘at least one not’ (= ‘some not’) and ‘not at
least one’ (= ‘none’).
Example 9.6.1
val
• ¬∀n [n ∈ N : n > p] == ∃n [n ∈ N : n ≤ p],
val
• ¬∃n [n ∈ N : n2 = 3] == ∀n [n ∈ N : n2 ̸= 3].
val
(Here we implicitly use mathematical truths like ¬(n > p) == n ≤ p.)
With the help of the rules of De Morgan we can do the following calcu-
lation:
¬∀x [x ∈ D : ¬P ]
val
== { De Morgan}
∃x [x ∈ D : ¬¬P ]
val
== { Double Negation (and Leibniz) }
∃x [x ∈ D : P ]
The conclusion is:
val
¬∀x [x ∈ D : ¬P ] == ∃x [x ∈ D : P ],
In words: ‘not every not = at least one’. This equivalence is sometimes
written like ¬∀¬ = ∃.
The ‘mirror-image’ calculation is:
¬∃x [x ∈ D : ¬P ]
val
== { De Morgan}
∀x [x ∈ D : ¬¬P ]
val
== { Double Negation (and Leibniz) }
∀x [x ∈ D : P ]
The conclusion is:
val
¬∃x [x ∈ D : ¬P ] == ∀x [x ∈ D : P ].
In words: ‘not one not = every’, also written as ¬∃¬ = ∀.
Also in the last two conclusions the domain D does not actually take
part; it remains unchanged.
92 CHAPTER 9. EQUIVALENCES WITH QUANTIFIERS
You see that substitutions are allowed, both in the domain description
on the left of the colon, and in the predicates on the right of the colon.
Something similar happens for the rule of Leibniz:
Note that with a ∃-formula, the predicates P and Q can simply be ex-
changed around the colon, but that for a ∀-formula the ¬ sign appears
twice.
The reason for this is actually that the Domain Weakening rule for ∃
val
returns a ∧, and P ∧ Q == Q ∧ P , but that Domain Weakening for ∀
val
returns a ⇒, for which we have: P ⇒ Q == ¬Q ⇒ ¬P . See the following
two calculations, where this plays a role:
∀x [P : Q] ∃x [P : Q]
val val
== { True/False-elim. } == { True/False-elim. }
∀x [True ∧ P : Q] ∃x [True ∧ P : Q]
val val
== { Domain Weakening } == { Domain Weakening }
∀x [True : P ⇒ Q] ∃x [True : P ∧ Q]
val val
== { Contraposition } == { Commutativity }
∀x [True : ¬Q ⇒ ¬P ] ∃x [True : Q ∧ P ]
val val
== { Domain Weakening } == { Domain Weakening }
∀x [True ∧ ¬Q : ¬P ] ∃x [True ∧ Q : P ]
val val
== { True/False-elim. } == { True/False-elim. }
∀x [¬Q : ¬P ] ∃x [Q : P ]
Above, we argued for the correctness of the above two formulas via a
reasoning. In Part II of this book we will see how we can reason in general.
The above given reasonings are special examples of the general reasoning
schemes which we will introduce in Part II. If you are still not convinced
by the reasoning put forward so far, we give again a calculation according
to the methods that we have developed in the previous chapters. We only
give the calculation for the second formula. This calculation, given below,
is more involved than the corresponding reasoning, and perhaps even more
involved than you would like. (Which is another reason why you should
take seriously the method of reasoning that we will present in Part II.)
∀x [P : Q ⇒ R] ⇒ (∃x [P : Q] ⇒ ∃x [P : R])
val
== { Implication, twice }
¬∀x [P : Q ⇒ R] ∨ ¬∃x [P : Q] ∨ ∃x [P : R]
val
== { De Morgan }
∃x [P : ¬(Q ⇒ R)] ∨ ¬∃x [P : Q] ∨ ∃x [P : R]
val
== { ‘exchange trick’, three times }
∃x [¬(Q ⇒ R) : P ] ∨ ¬∃x [Q : P ] ∨ ∃x [R : P ]
val
== { Domain Splitting }
∃x [¬(Q ⇒ R) ∨ R : P ] ∨ ¬∃x [Q : P ]
val val
== { by ¬(Q ⇒ R) ∨ R == Q ∨ R }
96 CHAPTER 9. EQUIVALENCES WITH QUANTIFIERS
∃x [Q ∨ R : P ] ∨ ¬∃x [Q : P ]
val
== { Domain Splitting }
∃x [Q : P ] ∨ ∃x [R : P ] ∨ ¬∃x [Q : P ]
val
== { Excluded Middle }
∃x [R : P ] ∨ True
val
== { True/False-elimination }
True
val
Midway, we used the equivalence ¬(Q ⇒ R) ∨ R == Q ∨ R. We leave it
to the reader to do the calculation which establishes this equivalence.
(1) Because the formula ∀x [False : Q] is a tautology for every Q, then also
the formula ∀x [False : ¬Q] is a tautology, and hence so is ∀x [Q : True]
(by the ‘exchange trick’ from the previous section). More specifically,
the formulas ∀x [True : True] and ∀x [False : True] are both tautolo-
gies.
(2) The fact that the formula ∃x [False : Q] is a contradiction, implies
also that the formula ∃x [Q : False] is a contradiction (again with the
‘exchange trick’). More specifically therefore, both ∃x [True : False]
and ∃x [False : False] are contradictions.
TAUTOLOGIES AND CONTRADICTIONS 97
val val
We shall also use for quantified formulas the notations |== and ==| for
‘stronger’ and ‘weaker’. We note that Lemma 7.3.4 is still valid:
val
If P |== Q, then P ⇒ Q is a tautology, and vice versa.
We end this section with some examples.
First we show the following:
The idea which will finally work is to use the fact that the following
equivalence holds:
val
∀x [P : Q ⇒ R] ⇒ (∀x [P : Q] ⇒ ∀x [P : R]) == True
(We called this the ‘monotonicity of ∀’ at the end of the previous section.)
Note that both Q ⇒ R and ∀x [P : Q] ⇒ ∀x [P : R] are sub-formulas of this
long formula!
Here is now the calculation:
True
val
== { ‘Monotonicity of ∀’ }
∀x [P : Q ⇒ R] ⇒ (∀x [P : Q] ⇒ ∀x [P : R])
val
== { Assumption that Q ⇒ R is a tautology }
∀x [P : True] ⇒ (∀x [P : Q] ⇒ ∀x [P : R])
val
== { ∀x [P : True] is a tautology, see above }
True ⇒ (∀x [P : Q] ⇒ ∀x [P : R])
val
== { Implication and Inversion }
False ∨ (∀x [P : Q] ⇒ ∀x [P : R])
val
== { True/False-elimination }
∀x [P : Q] ⇒ ∀x [P : R]
val
From this it follows that (∀x [P : Q] ⇒ ∀x [P : R]) == True, therefore:
the formula ∀x [P : Q] ⇒ ∀x [P : R] is a tautology, but only under the
assumption that Q is stronger than R! .
Finally, we show the following:
∀x [P : R] ⇒ ∀x [P ∧ Q : R] is a tautology.
Also here we have very few problems believing this intuitively. In fact,
P is weaker than P ∧ Q. From this we get after a little reflection that the
domain description P gives a domain which is as big or maybe bigger than
the domain described by P ∧ Q. If hence, for all x’s in that ‘bigger’ domain
the predicate R holds, then in particular it holds for all x’s in the ‘smaller’
domain.
But again, a calculation gives the desired certainty:
∀x [P : R] ⇒ ∀x [P ∧ Q : R]
val
== { Domain Weakening }
∀x [P : R] ⇒ ∀x [P : Q ⇒ R]
val
== { R is stronger than Q ⇒ R; use now the above lemma }
True
9.10. EXERCISES 99
(We leave to the reader the calculation which shows that R is stronger
than Q ⇒ R.)
Remark 9.9.4 The examples at the end of this section show that the method
of calculation ‘works’ also for complex quantified formulas and for proofs
about them. Exactly like at the end of the previous section, it is possibly
the case that the result remains unsatisfactory, because calculations do not
always fit our initial instincts. Also things that seem to be ‘obvious’ in these
examples are not so easily ‘proved’. This is the price one pays for ‘absolute
certainty’. Nevertheless, this certainty may still be achieved in a simpler
manner: The reasoning method with the help of ‘derivations’ which we shall
give in Part II, will in the above cases fit the intuition better and will give
shorter ‘proofs’.
9.10 Exercises
9.1 Look at the following two predicates on Z2 :
A(m, n) = m < n,
101
102 CHAPTER 10. OTHER BINDERS OF VARIABLES
Example 10.2.1
• The finite set which consists of the numbers 0, 1, 2 and 3 is written as
{0, 1, 2, 3}. The order does not matter: {3, 1, 0, 2} is the same set. Ev-
ery element counts but only once: also {3, 1, 1, 1, 0, 0, 2} is the same as
{0, 1, 2, 3}. (Sometimes this is not assumed and e.g. {3, 1, 1, 1, 0, 0, 2}
is taken to be different from {0, 1, 2, 3}; in that case we don’t speak
of ‘sets’, but of multi-sets. These are also called bags in computer
science.)
• A set with one element, like {6}, is a one-element set or singleton.
Note that {6} is a set, which is different from 6, a number.
• The (finite) set without elements is called the empty set. Notation:
∅.
10.2. THE SET BINDER 103
For bigger sets, possibly infinite, there are again other notations. Stan-
dard sets have their own names, for example: N (the natural numbers) and
Z (the integer numbers).
Also, a set can be written with a predicate, which the elements must
satisfy. Braces are also used for such sets.
If we for example want to write the set of the integer numbers m which
satisfy the predicate −3 ≤ m ≤ 1 ∨ m > 5, we can use the standard mathe-
matical notation:
{m ∈ Z| − 3 ≤ m ≤ 1 ∨ m > 5}.
This way of forming sets is called comprehension. This word comes from
the logic of the seventeenth century and means something like ‘concept’:
with the help of the braces one expresses a new set concept.
The comprehension-notation has bindings of variables, exactly like quan-
tified formulas. The m, which was free in the predicate −3 ≤ m ≤ 1∨m > 5,
is bound in the above expression for the corresponding set. We can see this
for example, because the rule of the Bound Variable is also valid here. We
can describe this set just as well with k instead of m:
{k ∈ Z| − 3 ≤ k ≤ 1 ∨ k > 5}.
It is important to note that the result of the set binding is different from
the quantifier binding:
• Binding a variable with a quantifier returns as a result a predicate (or,
if there are no more free variables, a proposition). See the examples
at the beginning of this chapter.
• Binding a variable with the set binder {. . . | . . .} on the other hand,
gives (the word says it already) a set . A set is an ‘object’, that can
never become True or False, even after filling values for free variables.
(2) m’s in D are those things that get collected (as long as they satisfy the
predicate P ).
In computer science, another notation which separates these two roles of
m, is sometimes used for the description of a set. The name of the bound
variable stays in front, but the things which get collected are put at the
end . With this separation, the notation of computer science gives some
flexibility, as we will see.
If for example, exactly like above, we want to collect integer numbers m,
then things look as follows:
(Set . . . : . . . : m).
The above example becomes in this computer science notation (where we
implicitly assume that m ∈ Z, so Z is the domain of m):
(Set m : −3 ≤ m ≤ 1 ∨ m > 5 : m).
The word Set points to the fact that this is a set in computer science
notation. The variable which becomes bound (in this case m) will be placed
at the first sequence of dots, exactly like for quantifier binding. The second
sequence of dots, is reserved for the predicate which the numbers m must
satisfy to be in the set. And what is collected is put in the third sequence
of dots. In this case, we simply have m, which means that we are precisely
collecting these numbers m which are in the domain and satisfy the predi-
cate. Hence, the set which we get is equal to the subdomain, consisting of
all domain elements that satisfy the predicate.
This notation expresses also that we can collect other things than m’s
(and this is a great advantage), for example m2 ’s:
(Set m : −3 ≤ m ≤ 1 ∨ m > 5 : m2 ).
Here we get the set of all m-squares where m comes from a subdomain
which can be written as {−3, −2, −1, 0, 1, 5, 6, 7, . . .}. Now the set that we
get is different from that subdomain: in the set there is now 4 (because
4 = (−2)2 ), but not 16 (because neither −4, nor 4 is in the domain).
Note that after the last colon and hence in general, we can have an
abstract function-value which describes what the objects collected in general
look like. They can be m, but also m2 or |m − 5| + 3.
Such a set formula in computer science notation has therefore the follow-
ing form:
(Set x : P : F ).
Remark 10.2.2 There is also a mathematical notation for the more gen-
eral case where function-values are collected. The last example becomes in
this notation:
10.3. THE SUM BINDER 105
%5
Note that the k in the ‘entry’ xk is still free, but in k=0 xk it is bound.
Again, in computer science one sometimes uses a variant notation: in-
stead of the above one writes
(Σk : 0 ≤ k < 6 : xk ).
In order to calculate with the sum of a sequence, one uses the available
rules. For example, if n is positive, then the Split rule is valid:
(Σk : 0 ≤ k < n + 1 : xk ) = (Σk : 0 ≤ k < n : xk ) + xn .
In order to ensure that this rule also holds for n = 0, one agrees on the
Empty-sum convention:
(Σk : False : xk ) = 0.
With this convention, the following calculation ‘makes sense’ (of course
this is a rather strange detour, because (Σk : 0 ≤ k < 1 : xk ) is already
directly equal to x0 , by definition):
(Σk : 0 ≤ k < 1 : xk )
= { Split rule }
(Σk : 0 ≤ k < 0 : xk ) + x0
= { Mathematics }
(Σk : False : xk ) + x0
= { Empty-sum convention }
0 + x0
= { Mathematics }
x0
Similarly, there is a notation for the product of the elements in a sequence.
For this, one uses the Greek letter Π (capital letter ‘pi’, the ‘P’ of ‘Product’).
Also here some simple rules hold, such as:
(Πk : 0 ≤ k < n + 1 : xk ) = (Πk : 0 ≤ k < n : xk ) · xn .
Comparable with the above, the Empty-product convention is valid:
(Πk : False : xk ) = 1.
Example 10.4.1 {k ∈ Z|0 < k < 20} is the mathematical notation for
the set of numbers between 0 and 20. The (finite) quantity (or number of
elements) of these numbers is given by #{k ∈ Z|0 < k < 20}, therefore
#{k ∈ Z|0 < k < 20} = 19.
There is also a variant computer science notation for the number of ele-
ments of a finite set. We give an example:
(#i : 0 < i ≤ 100 : i2 < 90).
This gives ‘the number (quantity) of integer numbers greater than 0 and
smaller or equal to 100 for which the square is smaller than 90’. (The number
required is therefore nine.) Note here again that the binding changes: the
variable i is free in both the predicates 0 < i ≤ 100 and i2 < 90, but is
bound in (#i : 0 < i ≤ 100 : i2 < 90).
The general form in this case is hence:
(# x : P : Q),
with P and Q as predicates. The meaning is: the number of x’s for which
P and (also) Q hold.
the scope of the ∀x is everything behind it, up to the end of the formula,
hence including the subformula starting with the ∃-binder. So the scopes
of ∀x and ∃y overlap.
It will be obvious that in this case it is not allowed to use the bound
variable name x for both bound variables, since then the subformula y < x
would become x < x. Then we are in trouble, since it is no longer obvious
that the first x in x < x is linked to the ∃-binder, and the second to the
∀-binder.
In general, each binder occurring in a formula has a well-defined scope,
which can be found as follows. First determine the subformula with that
binder as its main symbol (which is the subformula which begins with the
binder). Then, the scope of the binder is the part of that subformula after
the binder. One alternatively calls this the scope of the bound variable
belonging to the binder.
10.6 Exercises
10.1 Write the following as a set of the form {. . . | . . .} and also with the
set binder (Set . . . : . . . : . . .):
(a) The set of all real numbers between −10 and 10, but not equal
to 0.
(b) The set of natural numbers which are not even.
(c) The set of all integer numbers that are multiples of six.
(d) The set of all natural numbers which are the sum of two squares
of natural numbers.
10.2 Show that (Set m, n : (m, n) ∈ Z × N : 6m + 9n) is the set of all
integer multiples of three.
10.3 Calculate:
%99
(a) k=0 k
&99
(b) k=0 (−1)k
%
(c) ( k : −10 ≤ k ≤ 10 : k 33 )
(d) (#k : −10 ≤ k ≤ 10 : k 2 > 9)
10.4 Describe the scopes of all binders occurring in
(a) the formula in Figure 8.4,
(b) the formulas occurring in Exercise 8.9.
Part II
Logical Derivations
Chapter 11
Reasoning
(1) ¬(P ⇒ Q)
val
== { Implication }
(2) ¬(¬P ∨ Q)
val
== { De Morgan }
(3) ¬¬P ∧ ¬Q
val
== { Double Negation }
(4) P ∧ ¬Q
(In order to easily be able to talk about such calculations, we use here
the numbers (1) to (4) to refer to the lines.)
Note that ¬(P ⇒ Q) is not a tautology and neither is P ∧ ¬Q. The
calculation only shows that they are equivalent . But by Lemma 6.1.3
one can derive from the above calculation a second conclusion, namely
111
112 CHAPTER 11. REASONING
¬(P ⇒ Q) ⇔ P ∧ ¬Q.
val
• We have also seen calculations where now and then the symbols ==|
val val
or |== instead of == appeared in the margin. In Section 7.4 we saw
for example:
(1) ¬P
val
==| { ∧-∨-weakening }
(2) ¬P ∧ ¬Q
val
== { De Morgan }
(3) ¬(P ∨ Q)
¬(P ∨ Q) ⇒ ¬P.
• The arguments or reasons are also present (between the braces), and
we mention the name of the applied rules.
• The method works with small steps, which enables a good overview.
• A calculation can be built from top to bottom, but also from bottom
to top. Sometimes it is even useful to work ‘from both directions’ and
to try and complete the reasoning in the middle. This method allows
all this.
11.1. THE STRENGTH AND WEAKNESS OF CALCULATIONS 113
In many cases the method works quickly and smoothly. We must how-
ever realize that there are nevertheless disadvantages associated with this
method:
• The method is successive. This means that you make a chain of propo-
sitions which always appear in pairs related by some reason. In the
first example above, this happens as follows: (1) is paired with (2),
then (2) is paired with (3), and finally (3) is paired with (4). Only
the end conclusion bridges a bigger distance than from (k) to (k + 1);
it relates the beginning and the end of the chain: (1) with (4).
This leads to the disadvantage that one can only derive the conclusion
on the grounds of the last result. The proposition which occurs in line
(k + 1) in the calculation, is ‘reached’ with the help of the proposition
which immediately precedes it, i.e., in line (k). You can not therefore
use as a reason for proposition (k + 1) the proposition of line (k − 5)
for example, or the propositions of lines (k − 5) and (k) together .
• The method gives little guidance during the calculation process. In the
worst case, one can endlessly apply standard equivalences hoping it
will lead to the desired result. This is obviously neither efficient nor
desirable and in practice it rarely happens, because one will gradually
develop a feel for such kind of calculations. But the fact remains
that one always has this undesirable feeling of uncertainty during the
calculation. One is always asking: ‘Which standard equivalence should
I now actually use?’
• The method forces you sometimes to take a path that you don’t really
wish to take. Especially for proofs in both mathematics and computer
114 CHAPTER 11. REASONING
science, there are other, more satisfying tools available than just the
rewriting of formulas via standard equivalences. We show this in the
following two sections.
∗ Assume: we know (i) ‘If P then Q’, and (ii) ‘If Q then R’.
Yet, this is all quite normal and resembles how we usually reason. In order
to show this, we give in the following section an example of a reasoning in
mathematics. This example is not very simple, and hence, you should do
your best to follow what is happening. It is however worth the effort because
it illustrates important aspects of abstract reasoning.
In case we have, next to (an )n∈N , a second sequence: (bn )n∈N , we may
construct the sum-sequence of the two: (an + bn )n∈N , which is the following
sequence: a0 + b0 , a1 + b1 , a2 + b2 , . . . .
A sequence (an )n∈N is called convergent , if the sequence has a limit.
For example, the sequence 0, 12 , 23 , 34 , . . . is convergent, with limit 1, but the
sequence 1, 2, 4, 8, . . . is not convergent.
Now the following theorem holds:
Proof:
∗ Let (an )n∈N and (bn )n∈N be two convergent sequences of real numbers.
∗ Then |(an +bn )−(A+B)| = |(an −A)+(bn −B)| ≤ |an −A|+|bn −B|.
(We give the name (iii) to this inequality.)
Comment: This is an example of an intelligent mathematical calcula-
tion, in which we apply the triangle inequality: for all numbers x and
y it holds that |x + y| ≤ |x| + |y|.
∗ Now we set free the n that we had chosen above and we assume that
it is going towards ∞.
∗ Then obviously by (i) and (ii), both |an − A| and |bn − B| will go
towards 0.
∗ Hence, their sum, |an − A| + |bn − B|, will also go towards 0 if n goes
towards ∞.
11.3. AN EXAMPLE FROM MATHEMATICS 117
– The hypothesis that we have the sequences (an )n∈N and (bn )n∈N .
– The hypothesis that both sequences converge.
– The hypothesis that A is the limit of the first sequence and B is
the limit of the second.
– The temporary hypothesis that we have a fixed number n in N.
(Later we remove this hypothesis, and we let n move towards
∞.)
completion, is usually written down from the beginning to the end, without explanation of
how the writer actually reached this proof. An inexperienced reader gets the impression
that everything was conceived in the given order .
Don’t be intimidated by this style of mathematical proofs. What you see is only
the end result. During the building process of a difficult proof, usually a large pile of
paper is used (most of which ends up in the wastebasket). During this proof process,
progress is achieved by working sometimes forwards and sometimes backwards. Before
the completion of the proof, many failed attempts may have taken place and a lot of
creativity was probably needed.
It is the habit, when writing the proof in the end, of not showing much if any of this
creative process. What matters in the end is that the proof is correct and convincing.
This style of proofs, which is actually quite beautiful (and does not lose any of that
beauty by the above remarks), was actually started by Euclid, who wrote thirteen very
famous books (‘The Elements’ ) on geometry (see T.L. Heath: The Thirteen Books of
Euclid’s Elements, Dover Publications, 1956). These books are full of beautiful mathe-
matical proofs. Euclid wrote them in Alexandria in Egypt, around 325 B.C.!
118 CHAPTER 11. REASONING
In the following sections we show that those two items: hypotheses and
inferences, fit well together. We begin with inferences.
11.4 Inference
An inference in a reasoning is always of the kind:
From one or more propositions (the so-called premisses)
follows a new proposition (the conclusion).
The premisses must be valid , if they are to be ‘of service’. We will
later explain precisely what this means. In what follows think of valid
propositions as things like:
• Hypotheses that are assumed but are not yet ‘retracted’ or ‘with-
drawn’.
Remark 11.4.1 In case n = 0, when there are zero premisses, you must
read this as follows:
val
Q is a correct conclusion from zero premisses if True |== Q,
because a conjunction of zero propositions is by definition equivalent to True.
11.4. INFERENCE 119
val
In that case Q == True should hence be valid, and so, Q too must ‘hold’.
This is the case if Q is a tautology, or is itself a valid hypothesis, or a proven
theorem or something like that.
With this sort of logical calculations, the premiss appears just above
the conclusion. In general, this is not necessary when reasoning: The
following situation is just as acceptable, as long as l < m (and as long
as the formula in line (l) holds, which we will come back to later):
...
(l) ¬(¬P ∨ Q)
...
{ De Morgan on (l): }
(m) ¬¬P ∧ ¬Q
...
Note that the justification ‘{ De Morgan on (l): }’ does not serve now
to connect lines (m − 1) and (m), but is exclusively meant to express
why you are allowed to add the line with number (m).
Another example of a conclusion from one premiss:
...
(l) ¬P ∧ ¬Q
...
{ From (l) it follows that: }
(m) ¬Q
...
The correctness of the justification ‘{ From (l) it follows that: }’ is
here a consequence of the standard weakening
val
¬P ∧ ¬Q |== ¬Q.
Note that in the above scheme, k and l must both be smaller than m,
but that the order of the lines (k) and (l) does not matter: the line
with number (l) can also occur under the line with number (k).
• Three premisses. Example:
...
(k) P ∨Q
...
(l1 ) P ⇒R
...
(l2 ) Q⇒R
...
{ By (k), (l1 ) and (l2 ): }
(m) R
...
The statement of the above line can be verified without any difficulty
using truth-tables.
{ Tautology: }
(k) P ∨ ¬P
...
(l1 ) P ⇒R
...
(l2 ) ¬P ⇒ R
...
{ By (k), (l1 ) and (l2 ): }
(m) R
...
From P1 , . . . , Pn follows Q,
with n a natural number that gives the number of premisses : 0, 1 or more.
The inference as a whole is correct if Q is a correct conclusion from P1
to Pn (see the beginning of this section), hence if
val
(P1 ∧ . . . ∧ Pn ) |== Q.
11.5 Hypotheses
There are three kinds of hypotheses, which we must distinguish:
(1) The pure hypothesis. This is a (temporary) proposition which is as-
sumed, without side-effects. We give some examples:
– ‘Assume: P ∧ ¬Q.’
– ‘Assume: ∀x [x ∈ N : P ].’
– ‘Assume: the sequence converges.’ (If we know which sequence
is referred to.)
– ‘Assume: n is greater than 10.’ (If it is a ‘known’ n.)
– ‘Assume: the function f is continuous.’ (If f has already been
introduced or defined and is still ‘known’.)
√
– ‘Assume: 2 is a rational number.’ (For example in √ order to
show that this hypothesis is ‘impossible’, and that 2 cannot
hence be a rational number.)
(2) The generating hypothesis. This introduces a new name (it is ‘gen-
erated’). This name is used for an ‘arbitrary’ variable from a certain
domain. This domain is given beforehand and will (in general) have
11.5. HYPOTHESES 123
more than one element. From these elements we choose one, but we
don’t say which.
You should not take it literally that this name is ‘new’. Usually it will
be a letter which has been used thousands of times before, but which
happens to be ‘available’ at the moment.
The hypothesis in question here is the hypothesis that the element
with the ‘new’ name belongs to the given domain.
Examples:
We will only rarely consider the third kind of hypotheses, the identifying
ones, in this book. This third kind is concerned with definitions which we
treat only on the side in this book.
The first two kinds of hypotheses, on the other hand, the pure and the
generating hypotheses, play a big role in reasoning. Therefore, we will come
back to them in more details.
• The hypotheses which precede the ‘real’ reasoning, are used to specify
the situation in which the reasoning takes place. These hypotheses
are fixed at the beginning and stay in use till the end .
See the mathematical example from Section 11.3. There, the situ-
ation is first described in the announcement of the proposition and
thereafter, for completeness, it is specified explicitly by the following
hypotheses:
– hypothesis 1: ‘Let (an )n∈N and (bn )n∈N be two convergent se-
quences of real numbers’.
This can actually be seen as four hypotheses given at the same
time:
11.7. EXERCISES 125
• The pure and generating hypotheses which are assumed during the
reasoning process, usually serve a specific goal:
We will not explain here how these last two claims actually work. We
postpone this explanation to Chapters 12 and 15.
11.7 Exercises
11.1 Assume that the following is true:
‘If the weather is good, then Charles will go to the lake and not to his
aunt. If Charles goes to the lake or if he goes to the sea, then he will
be fishing.’
11.2 Take a circle C with centre M . Take further a triangle D where the
three corner points occur on C, whereas one side of D goes through
M.
Give a reasoning which shows that D is a rectangular triangle.
12.1 ‘Flags’
Implication is not popular when ‘calculating with formulas’: We have al-
ready seen that a formula of the form P ⇒ Q is often directly rewritten to
¬P ∨Q with the help of a standard equivalence called (indeed) ‘Implication’.
When reasoning however, implication plays a major role. Based on this,
we concentrate in this chapter on implication. We do this in combination
with conjunction which is itself also of extreme importance during reasoning.
(The conjunction is by the way always important, also when calculating
with logical formulas.)
127
128 CHAPTER 12. REASONING WITH ∧ AND ⇒
{ Assume : }
(1) P ∨ (Q ⇔ R)
..
.
(l) ...
..
.
(m) ...
The hypothesis occurs here in line number (1) and stretches to line (l).
Its validity is hence assumed up to and including line (l). In the lines below
(l), including line number (m), the hypothesis is no longer valid.
We can also assume hypotheses inside other hypotheses, as we shall see
in the first example of the following section. Also we can, as we shall see
later, make a new hypothesis after a previous one has been closed (we also
say withdrawn or retracted ).
((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)
is a tautology (see Section 11.2). In the ‘flag notation’ the complete reason-
ing looks as shown on the following page.
In that flag proof, we see that before every line, there is an argument
given between braces, either ‘{ Assume: }’, or ‘{ By . . . : }’.
For arguments of this last kind – of the form ‘{ By . . . : }’ – we can even
be more specific, since ‘By’ is actually a bit vague.
Let us look in more details at such arguments.
We see ‘{ By (1) }’ just before the line with number (3). In this case, the
reason is that the conjunction (P ⇒ Q) ∧ (Q ⇒ R) has as a consequence
that its left hand side holds: P ⇒ Q. This is justified by the standard
∧-∨-weakening rule
val
P ∧ Q |== P (∗),
val
which gives via Substitution that: (P ⇒ Q) ∧ (Q ⇒ R) |== P ⇒ Q.
12.2. INTRODUCTION AND ELIMINATION RULES 129
A similar thing holds for the right hand side (see Section 7.2):
val
P ∧ Q |== Q (∗∗),
val
from which, again by Substitution, we get (P ⇒ Q) ∧ (Q ⇒ R) |== Q ⇒ R.
This is used – again with a ‘by’-argument – in line number (4).
Here is the full reasoning in flag style. Please compare it carefully with
the reasoning ‘in words’, as given in Section 11.2:
{ Assume: }
(1) (P ⇒ Q) ∧ (Q ⇒ R)
{ Assume: }
(2) P
{ By (1): }
(3) P ⇒Q
{ Once again by (1): }
(4) Q⇒R
{ By (3) and (2): }
(5) Q
{ By (4) and (5): }
(6) R
{ By (2) and (6): }
(7) P ⇒R
{ By (1) and (7): }
(8) ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)
The two weakening rules (∗) and (∗∗) actually say what you can do if you
come across a conjunction when reasoning from top to bottom. Because this
is very natural (and also very obvious), we shall make a separate reasoning
rule, which we call ∧-elimination. The rule says how the conjunction sign
∧ can be ‘gotten rid of’, or eliminated .
For clarity, we write this rule as a scheme (the four vertical dashes ∥∥
mean that anything can appear there, we are in the middle of a reasoning):
130 CHAPTER 12. REASONING WITH ∧ AND ⇒
∧-elimination:
∥∥
(k) P ∧Q
∥∥
{ ∧-elim on (k) : }
(m) P
∧-elimination:
∥∥
(k) P ∧Q
∥∥
{ ∧-elim on (k) : }
(n) Q
application of an implication: when you know ‘If P then Q’, then this means
that: as soon as you (also) know P , then you may conclude Q.
Also here we make an elimination rule, the ⇒-elimination, which says
how you can use ⇒ (and immediately get rid of, or eliminate it: in the end
result Q, the original ⇒ can no longer be found). This rule looks as follows:
⇒-elimination:
∥∥
(k) P ⇒Q
∥∥
(l) P
∥∥
{ ⇒-elim on (k) and (l) : }
(m) Q
The order of the lines with numbers (k) and (l) is not important here.
However it must be that k < m and l < m. Note also here that we are
doing forward reasoning (from top to bottom): we start first with the fact
that we already ‘know’ P ⇒ Q. If we then also get to ‘know’ P , then we
can use it to derive the conclusion Q.
Be careful: We have not at all said that we will be successful in deriving
P if we know P ⇒ Q. If we can’t derive P then the application of the
rule ⇒-elimination is not possible. This risk will always be present with an
⇒-formula: perhaps you ‘know it’ without being able to directly use it.
Also with ⇒-elimination, Substitution is permitted.
Finally we look closer at the arguments before the lines with numbers
(7) and (8), in the example given in the beginning of this section. In both
cases one sees that a flag-pole ends. Each of these flag-poles corresponds
to a hypothesis. In the first case, for example, the hypothesis P from line
number (2), which led to the conclusion R in line number (6), is retracted.
This whole reasoning from line number (2) to line number (6) is summarized
in the conclusion which appears in line (7): P ⇒ R. (Everything between
(2) and (6) is forgotten, it was only necessary in order to reach (6) from (2)
in a correct way, in this case also using (1).)
In short, this is an application of a general method in order to obtain an
implication of the form ‘. . . ⇒ . . .’ as a conclusion. This method is a form
of backward reasoning: we want to reach P ⇒ Q and so we investigate how
132 CHAPTER 12. REASONING WITH ∧ AND ⇒
a reasoning above P ⇒ Q must look like. Hence, we work here from bottom
to top.
This general rule of ‘getting’ (‘introducing’ ) an implication is summarized
in the following ⇒-introduction rule (instead of the vertical strips we use a
.
‘hole’ .. , which still has to be filled).
⇒-introduction:
{ Assume : }
(k) P
..
.
(m − 1) Q
{ ⇒-intro on (k) and (m − 1) : }
(m) P ⇒Q
{ Assume: }
(1) (P ⇒ Q) ∧ (Q ⇒ R)
{ Assume: }
(2) P
{ ∧-elim on (1): }
(3) P ⇒Q
{ ∧-elim on (1): }
(4) Q⇒R
{ ⇒-elim on (3) and (2): }
(5) Q
{ ⇒-elim on (4) and (5): }
(6) R
{ ⇒-intro on (2) and (6): }
(7) P ⇒R
{ ⇒-intro on (1) and (7): }
(8) ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)
∧-introduction:
..
.
(k) P
..
.
(l) Q
..
.
{ ∧-intro on (k) and (l) : }
(m) P ∧Q
Our goal is to show that this is a tautology, via a natural reasoning. This
formula is hence our goal , which we write at the bottom of the page. (We
don’t know how long the reasoning will be, and hence we reserve some space
above our goal.)
We begin hence as follows:
..
.
(m) (P ⇒ (Q ∧ R)) ⇒ ((P ⇒ Q) ∧ (Q ⇒ (P ⇒ R)))
The ‘hole’ is where the dots occur. There we must add the reasoning
which from top to bottom will lead to the goal. But in order to succeed, it
makes sense to keep looking at the bottom as long as possible. Hence, we
start with reasoning in the ‘wrong’ direction, from bottom to top, by trying
to replace our goal by another, preferably simpler goal.
This can be done here because the goal formula in line number (m)
is an implication. The standard way to derive an implication, is via the
rule ⇒-intro. The corresponding abstract reasoning must hence look as
follows:
{ Assume: }
(1) P ⇒ (Q ∧ R)
..
.
(m − 1) (P ⇒ Q) ∧ (Q ⇒ (P ⇒ R))
{ ⇒-intro on (1) and (m − 1): }
(m) (P ⇒ (Q ∧ R)) ⇒ ((P ⇒ Q) ∧ (Q ⇒ (P ⇒ R)))
136 CHAPTER 12. REASONING WITH ∧ AND ⇒
The left hand side of the implication in line number (m), namely the for-
mula P ⇒ (Q ∧ R), now occurs on top of the reasoning-under-construction,
in a flag (this means, it is added as a hypothesis). The right-hand side of
this implication is the new goal at line number (m − 1). Note that this new
goal is located ‘under’ the hypothesis, and so in order to derive it, we can
use the hypothesis in (1).
We keep trying to solve the goal. The new goal, which replaces the old
one is: (P ⇒ Q) ∧ (Q ⇒ (P ⇒ R)). This is a conjunction. Therefore, it
makes sense to try solving this goal with ∧-intro:
{ Assume: }
(1) P ⇒ (Q ∧ R)
..
.
(l) P ⇒Q
..
.
(m − 2) Q ⇒ (P ⇒ R)
{ ∧-intro on (l) and (m − 2): }
(m − 1) (P ⇒ Q) ∧ (Q ⇒ (P ⇒ R))
{ ⇒-intro on (1) and (m − 1): }
(m) (P ⇒ (Q ∧ R)) ⇒ ((P ⇒ Q) ∧ (Q ⇒ (P ⇒ R)))
Note that we apply ∧-intro ‘under’ the flag in line (1): the flag pole of
the flag in line (1) extends over lines (l) and (m − 2), until it ends after
line (m − 1). So, although the assumption in line (1) does not play any
role in the application of the ∧-introduction rule, it doesn’t prevent this
application either (as long as the flag structure remains unchanged).
We now obtained two new goals from the old one: P ⇒ Q in line number
(l) and Q ⇒ (P ⇒ R) in line number (m − 2). Both can still be made
smaller by trying ⇒-intro. Hence, when applying the standard scheme
for ⇒-introduction twice, we may extend the derivation as shown on the
following page.
The reasoning obtained, still has two holes: one between lines (2) and
(l − 1) and another one between (l + 1) and (m − 3). Both have to be filled,
although the order in which this is done is irrelevant: one may start filling
either the first or the second hole.
12.3. THE CONSTRUCTION OF AN ABSTRACT REASONING 137
{ Assume: }
(1) P ⇒ (Q ∧ R)
{ Assume: }
(2) P
..
.
(l − 1) Q
{ ⇒-intro on (2) and (l − 1): }
(l) P ⇒Q
{ Assume: }
(l + 1) Q
..
.
(m − 3) P ⇒R
{ ⇒-intro on (l + 1) and (m − 3): }
(m − 2) Q ⇒ (P ⇒ R)
{ ∧-intro on (l) and (m − 2): }
(m − 1) (P ⇒ Q) ∧ (Q ⇒ (P ⇒ R))
{ ⇒-intro on (1) and (m − 1): }
(m) (P ⇒ (Q ∧ R)) ⇒ ((P ⇒ Q) ∧ (Q ⇒ (P ⇒ R)))
Let us start with the first hole. For this, we temporarily isolate the first
part of the reasoning, from line (1) up to line (l − 1). So we only consider:
{ Assume: }
(1) P ⇒ (Q ∧ R)
{ Assume: }
(2) P
..
.
(l − 1) Q (Here below we imagine the rest of the reasoning.)
{ Assume: }
(1) P ⇒ (Q ∧ R)
{ Assume: }
(2) P
{ ⇒-elim on (1) and (2): }
(3) Q∧R
..
.
(l − 1) Q (etc.)
{ Assume: }
(1) P ⇒ (Q ∧ R)
{ Assume: }
(2) P
{ ⇒-elim on (1) and (2): }
(3) Q∧R
{ ∧-elim on (3): }
(4) Q (etc.)
So the first hole has been successfully dealt with. What is left, is the
second hole.
But it is not difficult to also close this second hole, following the same
principles that we have just used for the first hole:
– firstly, apply another time the ⇒-introduction rule (because of the ⇒ in
line (m−3), becoming line (10) below): this gives the flag in line number (7),
and the new goal R in line number (9) below;
– and secondly, use another ⇒-elim followed by an ∧-elim to close the last
gap.
The end result is the reasoning that is written here below.
12.3. THE CONSTRUCTION OF AN ABSTRACT REASONING 139
{ Assume: }
(1) P ⇒ (Q ∧ R)
{ Assume: }
(2) P
{ ⇒-elim on (1) and (2): }
(3) Q∧R
{ ∧-elim on (3): }
(4) Q
{ ⇒-intro on (2) and (4): }
(5) P ⇒Q
{ Assume: }
(6) Q
{ Assume: }
(7) P
{ ⇒-elim on (1) and (7): }
(8) Q∧R
{ ∧-elim on (8): }
(9) R
{ ⇒-intro on (7) and (9): }
(10) P ⇒R
{ ⇒-intro on (6) and (10): }
(11) Q ⇒ (P ⇒ R)
{ ∧-intro on (5) and (11): }
(12) (P ⇒ Q) ∧ (Q ⇒ (P ⇒ R))
{ ⇒-intro on (1) and (12): }
(13) (P ⇒ (Q ∧ R)) ⇒ ((P ⇒ Q) ∧ (Q ⇒ (P ⇒ R)))
(2) Now you have a reasoning with one or more ‘holes’. Try to fill each of
these holes from top to bottom by deriving conclusions. Try to ‘direct’
this reasoning towards the goal which occurs under such a hole. (This
simply takes place by applying elimination rules.)
Often (but not always) this process can be completed using this gen-
eral strategy. In some more complex cases however (see for example Sec-
tion 14.2), it is necessary in the course of step (2) to devise new goals, which
can hence lead you to return again to step (1). We will not go into these
details further. You will learn it yourself by doing exercises.
Step (1) is important indeed, but not that problematic. If you know what
to do in order to simplify a goal, this step can be done smoothly. This is
also the case if you are reasoning with more connectives than just ⇒ and
∧ (as in the previous section), or with quantifiers. Also for a mathematical
reasoning, step (1) is often an excellent preparation.
The advantage of step (1) is that it helps you to get started and it enables
you to get a clear picture of the overall structure.
Usually, step (2) is the most difficult. There, creativity is really needed,
whether one is dealing with a purely logical reasoning as in the previous
section, or with a difficult mathematical theorem.
Hence, although you know well what a ‘correct reasoning’ precisely is, the
real problems will remain. But the thinking about these problems is made
much simpler, thanks to the flag-structured representation of a derivation-
to-be, which gives you a pictorial overview of the state of affairs. Your eyes
may dwell over the formulas, in order to decide which new step is possible
to continue your proof attempt in order to fill the hole(s).
Regrettably, it is possible that you choose the wrong direction, but in
that case you can always withdraw to plan a new attack. ‘Reculer pour
mieux sauter’: step back for a better jump – as the Frenchman says.
12.5 Exercises
12.1 Give the justifications (arguments) for the following derivations:
(a) { ... }
(1) P ∧P
{ ... }
(2) P
{ ... }
(3) (P ∧ P ) ⇒ P
(b) { ... }
(1) P
{ ... }
(2) Q
{ ... }
(3) P ∧Q
{ ... }
(4) Q ⇒ (P ∧ Q)
{ ... }
(5) P ⇒ (Q ⇒ (P ∧ Q))
(c) { ... }
(1) P
{ ... }
(2) P ⇒Q
{ ... }
(3) Q
{ ... }
(1) (P ⇒ Q) ⇒ Q
{ ... }
(2) P ⇒ ((P ⇒ Q) ⇒ Q)
12.5. EXERCISES 143
(b) { Assume: }
(1) (P ⇒ Q) ∧ P
{ ∧-elim on (1): }
(2) ...
{ ∧-elim on (1): }
(3) ...
{ ⇒-elim on (2) and (3): }
(4) ...
{ ... }
(5) ...
12.3 Show via an abstract reasoning that the following formulas are tau-
tologies:
(a) ((P ⇒ Q) ⇒ P ) ⇒ ((P ⇒ Q) ⇒ Q)
(b) P ⇒ ((P ∧ Q) ⇒ Q)
(c) (P ⇒ Q) ⇒ ((P ∧ R) ⇒ (Q ∧ R))
(d) ((P ∧ Q) ⇒ R) ⇒ (P ⇒ (Q ⇒ R))
144 CHAPTER 12. REASONING WITH ∧ AND ⇒
13.1 Validity
Abstract reasonings in the system of natural deduction, as were given in
the previous chapter, are also called derivations. They deal purely with
logic and not with mathematics. All justifications are also only of a logical
val
nature, like for example ‘∧-intro’ and ‘⇒-elim’. Also if we add ‘ == ’ or
val
‘ |== ’, we can still speak of ‘derivations’ (see the following chapter).
In derivations, one mostly finds hypotheses which fit a certain pattern.
This chapter will deal with such patterns. We will explain both the con-
sequences which these patterns have on the validity of propositions (this
section), and the general form of these patterns: the structure of the con-
text (see the following section).
A hypothesis has only a finite life. In the previous chapter, we gave the
exact life cycle of a hypothesis inside a flag by drawing a ‘flag-pole’ on the
left hand side.
If a hypothesis is withdrawn (the flag-pole ends), then you cannot use it
anymore. It will then turn up as the left hand side of the conclusion (an
implication) which immediately follows it, but the hypothesis as such is no
longer available.
In addition, everything that was derived as a conclusion ‘under’ this
hypothesis (hence everything that occurs next to the corresponding flag-
145
146 CHAPTER 13. THE STRUCTURE OF THE CONTEXT
pole), also loses its validity after the withdrawal of the hypothesis. The
reason is, that for these conclusions the hypothesis might have been (directly
or indirectly) needed, so that these conclusions depend on the hypothesis.
Hence, as soon as the hypothesis is declared non-active, the same will also
hold for the conclusions that depend on it.
This means that, by deriving conclusions in a reasoning you must pre-
cisely know what is still ‘valid’, and what is not. In order to make this
precise, we repeat the last example from the previous chapter, however
without the justifications.
(1) P ⇒ (Q ∧ R)
(2) P
(3) Q∧R
(4) Q
(5) P ⇒Q
(6) Q
(7) P
(8) Q∧R
(9) R
(10) P ⇒R
(11) Q ⇒ (P ⇒ R)
(12) (P ⇒ Q) ∧ (Q ⇒ (P ⇒ R))
(13) (P ⇒ (Q ∧ R)) ⇒ ((P ⇒ Q) ∧ (Q ⇒ (P ⇒ R)))
From the above, we can easily read what is valid and where it is valid.
• the hypothesis in (1) is valid up to (and including) line (12), but not
in (13),
• the hypothesis in (2) is valid up to (and including) line (4), but not
further,
• the conclusions in the lines (3) and (4) are also valid up to (and not
further than) line (4),
• the conclusion in line (5) is valid up to (and including) line (12) (and
indeed, we also use it in line (12)),
13.2. NESTED CONTEXTS 147
• the hypothesis in line (6) is valid up to (and including) line (10) (we
use it in line (8)),
{ Assume : }
(k) P
..
.
(m − 1) Q
{ ⇒-intro on (k) and (m − 1) : }
(m) P ⇒Q
Here you see that the conclusion P ⇒ Q in line number (m) is derived
from the hypothesis in line number (k) and the conclusion from this hy-
pothesis in line number (m − 1), but that both line (k) and line (m − 1) (and
everything in between) are no longer valid in line number (m). This one
specific case deviates from the Validity condition.
Check yourself that in the example of Section 12.3, the validity condition
has always been respected, except when applying ⇒-intro.
flag1
flag2
∥∥
∥∥
flag3
flag4
∥∥
∥∥
∥∥
∥∥
We clearly see here that every pair of flag-poles is nested in the following
way:
In the first case, the first flag-pole starts before, and ends after the other.
See for example the poles of flag 1 and flag 2, or of flag 1 and flag 4. In the
second case, the first flag-pole ends before the second begins. For example:
the flag-poles of flag 2 and flag 3 (or flag 4).
Hence, it can never happen that one flag-pole begins after another and
also ends after it. In this case these two poles are not ‘nested’.
in his book Symbolic Logic, an Introduction, New York, The Ronald Press Co., 1952.
This notation is also used by R. Thomason in his book Symbolic Logic, an Introduction,
MacMillan, 1970.
13.3. OTHER NOTATIONS 149
P ⇒ (Q ⇒ P )
is derived, first in the flag notation, and then in computer science notation.
{ Assume: }
(1) P
{ Assume: }
(2) Q
{ Still valid (1): }
(3) P
{ ⇒-intro on (2) and (3): }
(4) Q⇒P
{ ⇒-intro on (1) and (4): }
(5) P ⇒ (Q ⇒ P )
|[ P
◃
|[ Q
◃
P
]|
Q⇒P
]|
P ⇒ (Q ⇒ P )
The above derivations can also be given in a shorter form (A reader can
still see how things fit together). The short flag derivation looks as follows:
(1) P
(2) Q
(3) P
And the short computer science version can take the following form:
|[ P
◃
|[ Q
◃
P
]|
]|
• Pretty clear.
• Gives a good overview.
13.4 Exercises
13.1 (a) For each of the line numbers of your solution to Exercise 12.4 (c),
say where the proposition which occurs on that line is valid (i.e.
allowed to be used).
(b) Do the same for your solution to Exercise 12.4 (d).
13.2 (a) For each of the line numbers of your solution to Exercise 12.4 (c),
say which is the context.
(b) Do the same for your solution to Exercise 12.4 (d).
Chapter 14
val
¬P == P ⇒ False.
153
154 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
(I) ¬ -intro
If we are in a situation where the goal is ¬P (and hence ¬P occurs under
the hole):
..
.
(m) ¬P
{ Assume : }
(k) P
..
.
(m − 2) False
{ ⇒-intro on (k) and (m − 2) : }
(m − 1) P ⇒ False
{ Negation on (m − 1) : }
(m) ¬P
{ Assume : }
(k) P
..
.
(m − 1) False
{ ⇒-intro on (k) and (m − 1), and Negation : }
(m) ¬P
All this is enough justification for adding the following rule, which we
denote as ¬-intro, to our reasoning system:
14.1. REASONING WITH ¬ 155
¬ -introduction:
{ Assume : }
(k) P
..
.
(m − 1) False
{ ¬ -intro on (k) and (m − 1) : }
(m) ¬P
(II) ¬ -elim
If, on the other hand, we want to derive a conclusion from ¬P (which hence
occurs above the hole):
∥∥
(k) ¬P
∥∥
∥∥
(k) ¬P
{ Negation on (k) : }
(k + 1) P ⇒ False
∥∥
After this we are ready for ⇒-elim, provided that we can also derive P :
∥∥
(k) ¬P
{ Negation on (k) : }
(k + 1) P ⇒ False
∥∥
(l) P
{ ⇒-elim on (k + 1) and (l) : }
(m) False
We condense the obtained scheme into a new elimination rule for ¬:
156 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
¬ -elimination:
∥∥
(k) ¬P
∥∥
(l) P
∥∥
{ ¬ -elim on (k) and (l) : }
(m) False
From the scheme you see how ¬P can be used (in forward direction): if
you can also derive P , then you have False. (And this can be very useful,
see Section 14.3.)
By the way: another justification for the ¬ -elimination rule follows from
val
the standard equivalence ‘Contradiction’: P ∧ ¬P == False, which gives
val
in particular that ¬P ∧ P |== False.
¬(P ⇒ Q) ⇒ ¬Q.
We do this in phases. The first step is easy. Very quickly, we get the
following :
{ Assume: }
(1) ¬(P ⇒ Q)
..
.
(m − 1) ¬Q
{ ⇒-intro on (1) and (m − 1): }
(m) ¬(P ⇒ Q) ⇒ ¬Q
The goal is now ‘¬Q’, which appears in line (m − 1). It asks for the
¬ -intro-rule:
14.2. AN EXAMPLE WITH ⇒ AND ¬ 157
{ Assume: }
(1) ¬(P ⇒ Q)
{ Assume: }
(2) Q
..
.
(m − 2) False
{ ¬ -intro on (2) and (m − 2): }
(m − 1) ¬Q
{ ⇒-intro on (1) and (m − 1): }
(m) ¬(P ⇒ Q) ⇒ ¬Q
Now things become a bit difficult. The goal ‘False’ can no longer be
made smaller, so we are confronted with the question: ”How can we get
‘False’ from lines (1) and (2)?” It makes sense to realize that ‘¬(P ⇒ Q)’
in line (1) may help us, since it can lead to False with ¬ -elim – but only
if we can derive ‘P ⇒ Q’. We therefore consider P ⇒ Q as a new goal , see
below.
{ Assume: }
(1) ¬(P ⇒ Q)
{ Assume: }
(2) Q
..
.
(m − 3) P ⇒Q
{ ¬ -elim on (1) and (m − 3): }
(m − 2) False
{ ¬ -intro on (2) and (m − 2): }
(m − 1) ¬Q
{ ⇒-intro on (1) and (m − 1): }
(m) ¬(P ⇒ Q) ⇒ ¬Q
line number (1) with it. But we’re not yet so far. So it still has to be
derived.
{ Assume: }
(1) ¬(P ⇒ Q)
{ Assume: }
(2) Q
{ Assume: }
(3) P
{ Still valid (2): }
(4) Q
{ ⇒-intro on (3) and (4): }
(5) P ⇒Q
{ ¬ -elim on (1) and (5): }
(6) False
{ ¬ -intro on (2) and (6): }
(7) ¬Q
{ ⇒-intro on (1) and (7): }
(8) ¬(P ⇒ Q) ⇒ ¬Q
14.3. REASONING WITH FALSE 159
Note that the lines numbered (2) to (5) of this reasoning contain a deriva-
tion of P ⇒ Q from Q alone. The pattern behind this is worth while to be
remembered, since it occurs more often. We have encountered this pattern
before: in the lines numbered (1) to (4) in Section 13.3 we derived Q ⇒ P
from P .
Be careful, however: we cannot, for example, derive P ⇒ Q from P alone.
(I) False-intro:
We first recall the ¬ -elim rule from Section 14.1, (II), which tells us how
we can ‘use’ ¬P : try to also derive P and then we get False. Obviously,
False appears at the bottom line of the rule scheme.
This has an unexpected consequence, if we turn this round: by a change
of perspective we see that the ¬ -elim rule also tells us how to obtain False.
Namely, if you want to get False, you can try to first derive a formula ¬P
and then to derive P (or the other way round).
So the elimination-rule for ¬ may also be considered to encapsulate an
introduction-rule for False, which we express as follows:
False-introduction:
..
.
(k) ¬P
..
.
(l) P
..
.
{ False-intro on (k) and (l) : }
(m) False
..
.
(m) False
(II) False-elim:
There is also a way to eliminate False. If the situation is such that False
occurs above the hole:
∥∥
(k) False
∥∥
then we are lucky, as anything follows from False, because False is stronger
val
than every P . (See the rule ‘Extremes’: False |== P , from Section 7.2.)
Hence no matter which goal P we had, we are done:
False-elimination:
∥∥
(k) False
∥∥
{ False-elim on (k) : }
(m) P
Note that we have to respect the flag structure when applying a rule. In
particular, when we succeed in deriving False under a number of flags, as
suggested in the scheme above, then we may conclude to any proposition
P , but only under the same flags (i.e.: under the same hypotheses).
It will be obvious that we will never succeed in deriving False without
at least one hypothesis in a flag: because then ‘everything’ would ‘always’
(unconditionally) be true; and ‘truth’ would turn out to be a meaningless
notion – which it is not.
val
¬¬P == P,
(I) ¬¬ -intro:
If we want to derive ¬¬P :
..
.
(m) ¬¬P
¬¬ -introduction:
..
.
(k) P
..
.
{ ¬¬ -intro on (k) : }
(m) ¬¬P
162 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
(II) ¬¬ -elim:
And if we have already derived ¬¬P :
∥∥
(m) ¬¬P
∥∥
¬¬ -elimination:
∥∥
(k) ¬¬P
∥∥
{ ¬¬ -elim on (k) : }
(m) P
(1) Introduction of ¬P :
{ Assume : }
(k) P
..
.
(m − 1) False
{ ¬ -intro on (k) and (m − 1) : }
(m) ¬P
..
.
(m) P
Now things go further as follows: Assume ¬P and try under this hypoth-
esis to get False. If we do this we get:
{ Assume : }
(k) ¬P
..
.
(l) False
..
.
(m) P
This does actually not look very convincing. In order to derive P , one
introduces ‘out of the blue’ a flag with ¬P . The form of the proposition P
(for example, its main symbol) didn’t give a clue for doing this.
164 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
proof by contradiction:
{ Assume : }
(k) ¬P
..
.
(m − 2) False
{ ¬ -intro on (k) and (m − 2) : }
(m − 1) ¬¬P
{ ¬¬ -elim on (m − 1) : }
(m) P
Apparently, the method does make sense. If you succeed in closing the
hole between line number (k) and line number (m − 2), then you have
completed the derivation.
Why should you still be careful with such a ‘proof by contradiction’ ?
Because it can easily lead you to an unnecessary and ‘illogical’ path, as we
explain now.
Often one comes across a reasoning where the dots are filled with a perfect
reasoning that leads to P , while the hypothesis ¬P in rule number (k) is
not used at all . Then this P , together with the hypothesis ¬P , leads with
¬ -elim to the goal False in line number (m − 2), and we may continue with
the proof-by-contradiction scheme as displayed above.
But since, in this case, ¬P has not been used ‘under’ the flag in the
reasoning leading to P , you could have also derived the P in line number (m)
directly – without the ¬P -flag! Hence, in such a case the lines with number
(k), (m− 2) and (m− 1), including the flag and the mentioned justifications,
are redundant, and distracting from the ‘essence’ of the reasoning.
In summary, ‘proving by contradiction’ can be very useful, but only if you
have exhausted all other possibilities of deriving P ’directly’. If you don’t
have any other choice, then you can try ‘proving by contradiction’.
14.6. REASONING WITH ∨ 165
(I) ∨-intro:
If the goal is P ∨ Q:
..
.
(m) P ∨Q
..
.
(m − 1) ¬P ⇒ Q
{ Implication and Double Negation on (m − 1) : }
(m) P ∨Q
..
.
(m − 1) ¬Q ⇒ P
{ Implication, Double Negation and Commutativity : }
(m) P ∨Q
{ Assume : }
(k) ¬P
..
.
(m − 2) Q
{ ⇒-intro on (k) and (m − 2) : }
(m − 1) ¬P ⇒ Q
{ Implication and Double Negation on (m − 1) : }
(m) P ∨Q
14.6. REASONING WITH ∨ 167
∨-introduction:
{ Assume : }
(k) ¬P
..
.
(m − 1) Q
{ ∨-intro on (k) and (m − 1) : }
(m) P ∨Q
∨-introduction:
{ Assume : }
(k) ¬Q
..
.
(m − 1) P
{ ∨-intro on (k) and (m − 1) : }
(m) P ∨Q
That is to say: if you are in the lucky position that P has already been
derived, then P ∨ Q may immediately be concluded, with as argumentation:
‘∧-∨-weakening’. (Of course, this is also possible when Q has been derived,
val
since Q |== P ∨ Q also holds. The latter is an easy consequence of the same
weakening rule, by applying Substitution and Commutativity.)
However, be aware of the fact that this approach leads only now and then
to the desired goal P ∨ Q, since it is often the case that P ∨ Q is indeed
derivable, whereas this holds for neither P , nor Q alone. So usually we need
the general strategy of ∨-intro as given above.
168 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
∥∥
(k) P
{ Assume : }
(k + 1) ¬Q
{ Still valid (k) : }
(k + 2) P
{ ∨-intro on (k + 1) and (k + 2) : }
(k + 3) P ∨Q
(II) ∨-elim:
If P ∨ Q occurs above the hole:
∥∥
(k) P ∨Q
∥∥
∥∥
(k) P ∨Q
∥∥
{ Double Negation and Implication on (k) : }
(l) ¬P ⇒ Q
∥∥
(k) P ∨Q
∥∥
{ Double Negation and Implication on (k) : }
14.6. REASONING WITH ∨ 169
(l) ¬P ⇒ Q
∥∥
(m − 1) ¬P
{ ⇒-elim on (l) and (m − 1) : }
(m) Q
From the last scheme you see how P ∨ Q can be used (in forward di-
rection): if you can also derive ¬P (note the ¬ -symbol!), then you can
derive Q. A shortened version of the above scheme is our elimination rule
for ∨:
∨-elimination:
∥∥
(k) P ∨Q
∥∥
(l) ¬P
∥∥
{ ∨-elim on (k) and (l) : }
(m) Q
∨-elimination:
∥∥
(k) P ∨Q
∥∥
(l) ¬Q
∥∥
{ ∨-elim on (k) and (l) : }
(m) P
170 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
The new goal R can no longer be split up. Hence we proceed on the
upper side, where ∧-elim leads to three consequences. (To simplify things,
we also apply ∧-elim to a conjunction of three formulas.)
{ Assume: }
(1) (P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)
{ ∧-elim on (1): }
(2) P ∨Q
{ ∧-elim on (1): }
(3) P ⇒R
{ ∧-elim on (1): }
(4) Q⇒R
..
.
(n − 1) R
{ ⇒-intro on (1) and (n − 1): }
(n) ((P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)) ⇒ R
But now it is not clear how we can proceed further. The replacement of
14.7. A MORE DIFFICULT EXAMPLE 171
{ Assume: }
(1) (P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)
{ ∧-elim on (1): }
(2) P ∨Q
{ ∧-elim on (1): }
(3) P ⇒R
{ ∧-elim on (1): }
(4) Q⇒R
{ Assume: }
(5) ¬R
..
.
(n − 3) False
{ ¬ -intro on (5) and (n − 3) }
(n − 2) ¬¬R
{ ¬¬ -elim on (n − 2): }
(n − 1) R
{ ⇒-intro on (1) and (n − 1): }
(n) ((P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)) ⇒ R
{ Assume: }
(1) (P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)
{ ∧-elim on (1): }
(2) P ∨Q
{ ∧-elim on (1): }
(3) P ⇒R
{ ∧-elim on (1): }
(4) Q⇒R
{ Assume: }
(5) ¬R
{ Assume: }
(6) Q
{ ⇒-elim on (4) and (6): }
(7) R
{ ¬ -elim on (5) and (7): }
(8) False
{ ¬ -intro on (6) and (8): }
(9) ¬Q
{ ∨-elim on (2) and (9): }
(10) P
{ ⇒-elim on (3) and (10): }
(11) R
{ ¬ -elim on (5) and (11): }
(12) False
{ ¬ -intro on (5) and (12): }
(13) ¬¬R
{ ¬¬ -elim on (13): }
(14) R
{ ⇒-intro on (1) and (14): }
(15) ((P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)) ⇒ R
∥∥
(k) P ∨Q
∥∥
(l) P ⇒R
∥∥
(m) Q⇒R
∥∥
{ Case distinction on (k), (l) and (m) : }
(n) R
14.9. REASONING WITH ⇔ 175
(I) ⇔-intro
If the goal is P ⇔ Q:
..
.
(m) P ⇔Q
after which the goal in line number (m − 1) can be replaced by the two goals
P ⇒ Q and Q ⇒ P (think of ∧-intro).
Each of these goals is an ⇒-formula, which can be reached in a natural
way via ⇒-intro (‘Assume P , prove Q’, respectively ‘Assume Q, prove P ’).
This brings us to the following ⇔-intro rule:
⇔-introduction:
..
.
(k) P ⇒Q
..
.
(l) Q⇒P
..
.
{ ⇔-intro on (k) and (l) : }
(m) P ⇔Q
176 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
(II) ⇔-elim
Also when an ⇔-formula occurs above the ‘hole’ and hence can be used,
the standard equivalence ‘Bi-implication’ is useful. With this equivalence,
P ⇔ Q can be replaced by (P ⇒ Q) ∧ (Q ⇒ P ), which with ∧-elim returns
both P ⇒ Q and Q ⇒ P .
With these new results we can proceed in the usual way: we can (for
example) use P ⇒ Q by trying to derive P and then apply ⇒-elim, and we
can do something similar with Q ⇒ P .
⇔-elimination:
∥∥
(k) P ⇔Q
∥∥
{ ⇔-elim on (k) : }
(m) P ⇒Q
⇔-elimination:
∥∥
(k) P ⇔Q
∥∥
{ ⇔-elim on (k) : }
(n) Q⇒P
14.10 Exercises
14.1 Give derivations for the following tautologies. Use only the natural
deduction rules as described in Chapters 12 and 14.
(a) ¬Q ⇒ ¬(P ∧ Q)
(b) ¬(P ∧ Q) ⇒ (P ⇒ ¬Q)
(c) (P ∧ ¬Q) ⇒ ¬(P ⇒ Q)
14.10. EXERCISES 177
((P ∨ Q) ∧ (P ⇒ R) ∧ (Q ⇒ R)) ⇒ R.
(a) |x + 4| ≥ 12 x + 2
(b) (x ≥ 2 ∨ x = −1) ⇒ x3 − 3x − 2 ≥ 0
(c) x2 = y 2 ⇔ (x = y) ∨ (x = −y)
14.9 Prove the following tautologies by means of natural deduction (you
can omit the justifications):
178 CHAPTER 14. REASONING WITH OTHER CONNECTIVES
179
180 CHAPTER 15. REASONING WITH QUANTIFIERS
(I) ∀-intro:
We begin with the ∀-quantifier and we consider the situation where the ∀-
formula ∀x [P (x) : Q(x)] occurs under the ‘hole’. In other words: we are
looking at how a ∀-formula can be introduced by means of natural deduction.
Let us deliver as an example a proof that
x2 − 2x − 8 = (x + 2)(x − 4) > 0;
this last holds because both x + 2 and x − 4 are greater than 0 (since x itself
is greater than 4).
Hence, x2 − 2x > 8.’
An important step in this proof is ‘Take a real x greater than 4’. In order
to give a proof of x2 − 2x > 8 for all real numbers greater than 4, it is
enough to take an arbitrary real number greater than 4 and to deliver for
this arbitrary number the requested proof.
This first step has actually two parts:
– Take a real number greater than 4,
– call it x.
We can also exchange these two steps:
– Declare a variable x,
– assume that x ∈ R and x > 4.
Both this declaration of x and the corresponding hypothesis about x, viz.
x ∈ R ∧ x > 4 have only a temporary validity. They serve for reaching the
15.1. REASONING WITH ∀ 181
{ Assume: }
(1) var x; x ∈ R ∧ x > 4
..
.
{ Assume: }
(1) var x; x ∈ R ∧ x > 4
(2) Then x2 − 2x − 8 = (x + 2)(x − 4) > 0,
(3) hence x2 − 2x > 8
(4) Conclusion : ∀x [x ∈ R ∧ x > 4 : x2 − 2x > 8]
∀-introduction
{ Assume : }
(k) var x; P (x)
..
.
(m − 1) Q(x)
{ ∀-intro on (k) and (m − 1) : }
(m) ∀x [P (x) : Q(x)]
Remark 15.1.3 Sometimes the goal has the form ∀x [True : Q(x)] or even
∀x [Q(x)] (see Remark 8.4.1 in Section 8.4). Then the domain description
is either True or it is ‘invisible’. In the latter case one has omitted, for
convenience’s sake, a well-known domain description P (x) – for example,
P (x) ≡ x ∈ Z. When we use ∀-introduction according to the above rule,
the flag should contain the omitted P (x) as an assumption, so the flag text
should look like ‘var x; P (x)’. In the case that P (x) is True, we may simply
write ‘var x’ in the flag.
(II) ∀-elim:
What can we do with a ∀-formula that occurs above the ‘hole’ and is there-
fore usable? If we for example know that the following holds:
∀x [−1 < x < 2 : x3 − 3x − 2 < 0],
how can we use this? With the formula on its own, we cannot do much, but
as soon as we have a number between −1 and 2, then we can use it. For
example: 0 is such a number, hence 03 − 3 · 0 − 2 < 0. This is indeed true,
because here we√have that −2 is smaller than 0. It gets more interesting
when we take 12 2. This also occurs between −1 and 2, hence we can in a
√ √
similar way conclude that: ( 12 2)3 − 3. 12 2 − 2 < 0. This is already more
exciting.
15.1. REASONING WITH ∀ 183
∀-elimination
∥∥
(k) ∀x [P (x) : Q(x)]
∥∥
(l) P (a)
∥∥
{ ∀-elim on (k) and (l) : }
(m) Q(a)
The latter formula says that P (x) ⇒ Q(x) holds for every x. Especially
if we fill x by a then the following holds:
P (a) ⇒ Q(a).
(The fact that this is a tautology follows easily from a logical calculation,
see Part I. But here we want to show that it is also easy to reason with ∀.)
The start of the derivation is simple, the main symbol ⇒ requires the
rule ⇒-intro:
{ Assume: }
(1) ∀x [P (x) : Q(x) ∧ R(x)]
..
.
(n − 1) ∀y [¬Q(y) : ¬P (y)]
{ ⇒-intro on (1) and (n − 1): }
(n) ∀x [P (x) : Q(x) ∧ R(x)] ⇒ ∀y [¬Q(y) : ¬P (y)]
{ Assume: }
(1) ∀x [P (x) : Q(x) ∧ R(x)]
{ Assume: }
(2) var y; ¬Q(y)
..
.
(n − 2) ¬P (y)
{ ∀-intro on (2) and (n − 2): }
(n − 1) ∀y [¬Q(y) : ¬P (y)]
{ ⇒-intro on (1) and (n − 1): }
(n) ∀x [P (x) : Q(x) ∧ R(x)] ⇒ ∀y [¬Q(y) : ¬P (y)]
{ Assume: }
(1) ∀x [P (x) : Q(x) ∧ R(x)]
{ Assume: }
(2) var y; ¬Q(y)
{ Assume: }
(3) P (y)
..
.
(n − 3) False
{ ¬-intro on (3) and (n − 3): }
(n − 2) ¬P (y)
{ ∀-intro on (2) and (n − 2): }
(n − 1) ∀y [¬Q(y) : ¬P (y)]
{ ⇒-intro on (1) and (n − 1): }
(n) ∀x [P (x) : Q(x) ∧ R(x)] ⇒ ∀y [¬Q(y) : ¬P (y)]
186 CHAPTER 15. REASONING WITH QUANTIFIERS
{ Assume: }
(1) ∀x [P (x) : Q(x) ∧ R(x)]
{ Assume: }
(2) var y; ¬Q(y)
{ Assume: }
(3) P (y)
(I) ∃-intro:
If the goal is ∃x [P (x) : Q(x)]:
..
.
(m) ∃x [P (x) : Q(x)]
..
.
(m − 1) ¬∀x [P (x) : ¬Q(x)]
{ De Morgan and Double Negation on (m − 1) : }
(m) ∃x [P (x) : Q(x)]
after which the new goal, the ¬ -formula ¬∀x [P (x) : ¬Q(x)], may be ob-
tained backwards by ¬-intro:
{ Assume : }
(k) ∀x [P (x) : ¬Q(x)]
..
.
(m − 2) False
{ ¬-intro on (k) and (m − 2) : }
(m − 1) ¬∀x [P (x) : ¬Q(x)]
{ De Morgan and Double Negation on (m − 1) : }
(m) ∃x [P (x) : Q(x)]
188 CHAPTER 15. REASONING WITH QUANTIFIERS
This justifies the extension of our natural deduction system with the
following rule:
∃-introduction
{ Assume : }
(k) ∀x [P (x) : ¬Q(x)]
..
.
(m − 1) False
{ ∃-intro on (k) and (m − 1) : }
(m) ∃x [P (x) : Q(x)]
(II) ∃-elim:
If on the other hand we ‘know’ that ∃x [P (x) : Q(x)] (which occurs above
the hole):
∥∥
(k) ∃x [P (x) : Q(x)]
∥∥
then we can again replace ∃x [P (x) : Q(x)] by ¬∀x [P (x) : ¬Q(x)], but now
‘forward’:
∥∥
(k) ∃x [P (x) : Q(x)]
∥∥
{ Double Negation and De Morgan on (k) : }
(l) ¬∀x [P (x) : ¬Q(x)]
∥∥
15.3. REASONING WITH ∃ 189
This latter formula is a ¬ -formula, and hence we can for example try to
derive the ‘complementary’ formula ∀x [P (x) : ¬Q(x)] with the intention of
reaching False by means of ¬-elim:
∥∥
(k) ∃x [P (x) : Q(x)]
∥∥
{ Double Negation and De Morgan on (k) : }
(l) ¬∀x [P (x) : ¬Q(x)]
..
.
(m − 1) ∀x [P (x) : ¬Q(x)]
{ ¬-elim on (l) and (m − 1) : }
(m) False
Filling the hole between the lines numbered (l) and (m − 1) can now
begin by aiming first at the goal ∀x [P (x) : ¬Q(x)] in line (m − 1). The
main symbol of this goal is ∀, hence it makes sense to try and reach this
goal with ∀-intro. The new goal becomes ¬Q(x), which asks for ¬-intro,
etcetera.
In this manner, we have a strategy at our disposal to ‘use’ (or ‘eliminate’)
a proposition of the form ∃x [P (x) : Q(x)]. This strategy is: try to derive
∀x [P (x) : ¬Q(x)], and if you succeed, then you have False. This may help
you further in developing a derivation. Again, we lay this down in a natural
deduction rule:
∃-elimination
∥∥
(k) ∃x [P (x) : Q(x)]
∥∥
(l) ∀x [P (x) : ¬Q(x)]
∥∥
{ ∃-intro on (k) and (l) : }
(m) False
Again the advice is: handle with care! Note, for example, that we have
¬Q(x) in the predicate of line number (l) (with a ¬-sign), whereas line
number (k) has Q(x) only.
190 CHAPTER 15. REASONING WITH QUANTIFIERS
var y; y ∈ R
you want to prove ∃x [x ∈ R : ln(x) > y], then you can call every
15.4. ALTERNATIVES FOR ∃ 191
This ∃∗ -intro-rule works in practice very nicely, and requires much less
work than the method from the previous section (the one where ∃ was
replaced by ¬∀¬). Therefore we follow from now on the following standard
strategy for an ∃-formula that, as a goal, occurs directly under the hole: we
do nothing with it, leave it as it is and wait till a suitable ‘witness’ appears.
We can try to find this witness with the help of our knowledge (which occurs
above the hole). If this witness shows up, we are done. If it doesn’t, we
are still free to try the original, albeit long-winded method ‘∃-intro’ from
Section 15.3.
We shall now show that the rule ∃∗ -intro is indeed correct. For this, we
assume that P (a) and Q(a) both hold and then we show, exclusively with
the earlier given rules, that then also ∃x [P (x) : Q(x)] holds. Because we
fully trust these earlier rules, we conclude that the new rule is acceptable.
We start hence from the following situation:
{ Assume: }
(1) P (a)
{ Assume: }
(2) Q(a)
..
.
(n) ∃x [P (x) : Q(x)]
192 CHAPTER 15. REASONING WITH QUANTIFIERS
{ Assume: }
(1) P (a)
{ Assume: }
(2) Q(a)
{ Assume: }
(3) ∀x [P (x) : ¬Q(x)]
..
.
(n − 1) False
{ ∃-intro on (3) and (n − 1): }
(n) ∃x [P (x) : Q(x)]
Now the ∀-formula ∀x [P (x) : ¬Q(x)] occurs above the hole. To which
we can directly apply ∀-elim, because in line number (1) we have that a
satisfies P . The result from this ∀-elimination is ¬Q(a). Hence, together
with Q(a) from line number (2), we easily reach the goal False. This gives:
{ Assume: }
(1) P (a)
{ Assume: }
(2) Q(a)
{ Assume: }
(3) ∀x [P (x) : ¬Q(x)]
{ ∀-elim on (3) and (1): }
(4) ¬Q(a)
{ ¬-elim on (4) and (2): }
(5) False
{ ∃-intro on (3) and (5): }
(6) ∃x [P (x) : Q(x)]
15.4. ALTERNATIVES FOR ∃ 193
We must make an important remark about the ∃∗ -intro rule: it does not
always work. You must have some luck in order to be able to find the
‘witness’ a which satisfies both P and Q. It even turns out that in many
cases such a witness cannot be found at all , no matter how hard you look
and no matter how clever you are.
Luckily, the method ∃-intro from the previous section – based on the
equivalence of ‘∃’ and ‘¬∀¬’ – is still available for such cases. If it is
possible at all to derive ∃x [P (x) : Q(x)], then it will be possible with the
‘original’ ∃-intro. Even though this may probably require some work.
Said differently, sometimes there may well exist an x which satisfies P
and Q, but without anyone being able to give such an x. In such a case we
cannot do more than noting that the non-existence of such an x leads to
a contradiction. Hence the assumption that ¬∃x [P (x) : Q(x)] (which is by
De Morgan ∀x [P (x) : ¬Q(x)]) leads to False. This is precisely what the
method of the previous section gives, as can easily be checked.
∃x [x ∈ R : cos(x) = x].
We may for example have reached this conclusion by drawing the graphs
of the functions y = x and y = cos(x) in one figure and by noting that
these graphs have a meeting point (as a matter of fact, they have a unique
meeting point, but this does not matter here).
We want to use this knowledge in order to show that
∃u [u ∈ R : sin2 (u) + u = 12 ].
The situation is hence as follows:
(1) ∃x [x ∈ R : cos(x) = x]
..
.
(n) ∃u [u ∈ R : sin2 (u) + u = 12 ]
In order to reach the goal in line number (n), it would be nice to find a
‘witness’ a with a ∈ R and sin2 (a)+a = 12 . If we have such a witness, we can
then apply ∃∗ -intro. We follow the standard strategy for this rule, which
194 CHAPTER 15. REASONING WITH QUANTIFIERS
(1) ∃x [x ∈ R : cos(x) = x]
{ ... }
(2) Pick an x with x ∈ R and cos(x) = x
{ Mathematics : }
(3) Hence is 1 − 2 sin2 ( 12 x) = x, . . .
{ Mathematics : }
(4) hence sin2 ( 12 x) + 12 x = 12 .
{ Mathematics : }
(5) Moreover we have 12 x ∈ R
{ ∃∗ -intro on (5) and (4) : }
(6) hence ∃u [u ∈ R : sin2 (u) + u = 12 ]
∃∗ -elimination
∥∥
(k) ∃x [P (x) : Q(x)]
∥∥
{ ∃∗ -elim on (k) : }
(m) Pick an x with P (x) and Q(x).
It is indeed important here that the x that we ‘pick’ in line number (m)
be ‘new’ with respect to the proof-under-construction. On grounds of (k),
we have picked an arbitrary element which satisfies P and Q; we need to
give this element a name which we did not already know, so that we do not
cause confusion.
And what about the x which already exists in line number (k)? Yes, but
the x in line number (k) is a bound variable, which is hence only known
within the ∃-formula in line number (k). Hence the x in line number (m)
(‘Pick an x’) is definitely new with respect to the earlier x in line number (k).
Remark 15.4.1 You can see now why such an extra rule ‘Pick an x with
P (x) and Q(x)’ is needed. As you know, the x which occurs after the ∃ in
∃x [P (x) : Q(x)] does not live any more outside this formula.
If we want to work with such an x outside this formula, then we must
introduce it from new again. This is exactly what we do in the sentence
‘Pick an x with P (x) and Q(x)’.
But of course we must not get in a mess with an x which occurs somewhere
else in the derivation, for example a free x which occurs somewhere below
line number (k). What will happen if x is not new at the moment where we
want to write line number (m)? Then we simply take another letter, which
is definitely new. And hence we write in line number (m), if y is such letter:
(m) Pick a y with P (y) and Q(y).
Remark 15.5.1 In the formula (∗) there are three sub-formulas which begin
with a quantifier. We have chosen the bound variables in such a way that
they are different in each of these three sub-formulas: x is the bound variable
in the first, y is the bound variable in the second and z is the bound variable
in the third.
In general this is a good habit, in order to avoid confusion. If you happen
to come across quantified sub-formulas with the same bound variables, then
first, make these variables different. This is always possible, due to the
standard equivalence ‘Bound Variable’, see Section 9.2.
Example: you may change ∀x [P (x) : Q(x)] ⇒ ∀x [P (x) : Q(x) ∨ R(x)]
into ∀x [P (x) : Q(x)] ⇒ ∀y [P (y) : Q(y) ∨ R(y)].
{ Assume: }
(1) ∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]
..
.
(n − 1) ∃z [P (z) : R(z)]
{ ⇒-intro on (1) and (n − 1): }
(n) (∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]) ⇒ ∃z [P (z) : R(z)]
{ Assume: }
(1) ∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]
{ ∧-elim on (1): }
(2) ∃x [P (x) : Q(x)]
{ ∧-elim on (1): }
(3) ∀y [Q(y) : R(y)]
..
.
(n − 1) ∃z [P (z) : R(z)]
{ ⇒-intro on (1) and (n − 1): }
(n) (∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]) ⇒ ∃z [P (z) : R(z)]
Now we can proceed further with the lines numbered (2) and (3). The
latter is a ∀-formula, which is still not usable via ∀-elim, as long as we don’t
have a b such that Q(b). But on line number (2), an ∃-formula above the
hole, we can apply ∃∗ -elim:
{ Assume: }
(1) ∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]
{ ∧-elim on (1): }
(2) ∃x [P (x) : Q(x)]
{ ∧-elim on (1): }
(3) ∀y [Q(y) : R(y)]
{ ∃∗ -elim on (2): }
(4) Pick an x with P (x) and Q(x).
..
.
(n − 1) ∃z [P (z) : R(z)]
{ ⇒-intro on (1) and (n − 1): }
(n) (∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]) ⇒ ∃z [P (z) : R(z)]
198 CHAPTER 15. REASONING WITH QUANTIFIERS
{ Assume: }
{ ∧-elim on (1): }
(2) ∃x [P (x) : Q(x)]
{ ∧-elim on (1): }
(3) ∀y [Q(y) : R(y)]
{ ∃∗ -elim on (2): }
(4) Pick an x with P (x) and Q(x).
{ ∀-elim on (3) and (4): }
(5) R(x)
..
.
(n − 1) ∃z [P (z) : R(z)]
{ ⇒-intro on (1) and (n − 1): }
(n) (∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]) ⇒ ∃z [P (z) : R(z)]
But now we can ‘close’ the derivation: we were (see line number (n − 1))
looking for an a with P (a) and R(a), which we have now found. To be
precise, x ‘does what is required’: we know now, that both P (x) (see line
number (4)) and R(x) (see line number (5)) hold. Hence the complete
derivation becomes:
{ Assume: }
(1) ∃x [P (x) : Q(x)] ∧ ∀y [Q(y) : R(y)]
{ ∧-elim on (1): }
(2) ∃x [P (x) : Q(x)]
{ ∧-elim on (1): }
15.6. EXERCISES 199
15.6 Exercises
15.1 Prove the following. Always put the declaration of x and the corre-
sponding hypothesis in a context flag.
(a) ∀x [x ∈ R ∧ x < 0 : x3 + x2 − x − 1 ≤ 0]
(b) ∀x [x ∈ R : cosh2 (x) − sinh2 (x) = 1]
Note that sinh(x) = 12 (ex − e−x ) and cosh(x) = 12 (ex + e−x ).
15.2 You are given:
∀x [x ∈ R : ex − 1 ≥ x].
Prove that:
∀y [y ∈ R ∧ y > 0 : ln(y) ≤ y − 1].
Describe clearly where the ∀-elimination or the ∀-introduction are
used.
Hint: Use the substitution: [ln(y) for x].
15.3 Give derivations for the following tautologies using the methods given
in Section 15.1:
(a) ∀x [P (x) ∧ Q(x)] ⇒ ∀y [P (y)]
(b) ∀x [P (x) ⇒ Q(x)] ⇒ (∀y [P (y)] ⇒ ∀z [Q(z)])
15.4 As Exercise 15.3 (D is a given set, a and b are given elements of D):
200 CHAPTER 15. REASONING WITH QUANTIFIERS
Applications
Chapter 16
Sets
{x E D IP(x)}
because, for the problems that will be considered in this chapt~r it fits
10 2
bette~than the computer science notation. This notation (see_Section - )
describesthe set of all x -s in the domain D for which the predicate p hold ·
Below we show how you can use sets of the form {x E DIP(x)} in a
12 and 15
Proofor in a reason ing. For this we give exactly as in chapters
203
CHAPTER 16
· SEtrs
204
sirn·i
eli mi na tio n rul es, wi th which we can work in a 1ar Way
. d . d
mtro uctwn an
to before.
of E :
(I) , E-intro' via Property to the set
for an arb itra ry ob jec t t whether it belong s
e
How can we decid . .
ob v1
.
0u s tha t t i:rmst first be an element
of
thi s, 1t 1s
{x E D /P(x) }? For st hold for this t. We can
state this asa
the pre dic ate P mu
D. Moreover,
Property of E :
Property of E :
tE{xED/P(x)} ~ tED/\P(t)
the
ur se , the for mu la t ED /\ P(t) should be readas
Remark 16.1.1 Of co l, we giv e symbols connected withset
s
/\P (t) . In ge ne ra '
conjunction (t ED) log ica l sy mb ols .
tha n
such as 'E ', higher priority
of the form t E {x E D/P(
x)},
n of a statement
Hence , for the introductio
s:
we may proceed as follow
(l) t ED
(m - 1) P(t)
d (m - 1): }
{ Property of E on (l) an
(m) t E {x E D/P(x)}
such that it
ch oo se the bo un d va ria ble in {x E D /p (x)}
d It it wise to sion. If there
r _fr ee in t, oth erw ise we run the risk of confu b
oes nobtloc cu , Y
are pro ems wi th va ria bl Fo r ex am ple
int o e na me x, w~ can rename it.
renaming it th e equivalent formula t E {y E D/P(y)}
instead oft E { x!'o/~(zj} ~s e
· , via· Property
(II) 'E zim of E :
-e
On the other hand 'f t t E {x E D/P( x)} ' the
n what can we
e can d ,_1 we kn ow tha p(t)
derive? W enve 11two _cone1us1•ons, namely that both t E D antd ment
hold. So we have th e cJ.O owmg two 1 .c e
0 f th c D /P ( ) . rue s J.O rthe elimination of a sta
e wrm t E {x E X }.
.
uNJVERSAL SET A D UB ET
16.2·
205
1111
1111
Remark 16,1.2 W shall not use the names E-intro and E- lim
teadwe use the phrase 'Property of E '. in-
This means for example, that on the basis of the above definition, we can
replaceA ~ B , either forwards or backwards by the equivalent proposition
Vx[x EA: XE BJ.
Property of ~ :
A~B I\ tEA ~ tEB
(m- 2) xE B
{ V-in ro on (1) and (m _ 2): }
(m - 1) Vx[x EA: x E B]
{ Definiti on of~ on (m _ l): }
(m) A~B
1111
(k) A~ B
1111
(l) tEA
1111
{ Property of C on (k) and (l): }
(m) t EB
Remark 16.2.2 We shall not in what follows use the names
'c;;,-intro'
and
'r;.-elim',because-as we just saw above- they are not needed.
A = B d~/ A ~ B I\ B ~ A.
With the above definition, we are able now to reason with sets.
(l) A~ B
(m - 2) B ~ A
{ A-intro on (l) and (m - 2): }
(m - 1) A~ B !\ B ~ A
{ Definition of= on (m - 1): }
(m) A= B
There are hence two new 'holes' with two new goals, which can both be
rewritten backwards by means of the definition of ~. If we for example
work further with the first new goal, we get:
{ Assume: }
(k) var x; x E A
(l - 2) x EB
{ V-intro on (k) and (l - 2): }
(l - 1) Vx[x EA: x EB)
6.3. EQUALITY OF ET 209
(m - ) B ~ A
{ /\-in ro on (l) and (m - 2): }
(m - 1) A ~ B /\ B ~ A
{ Definition of= on (m - 1): }
m) A=B
Property of = :
A = B ~ Vx[xEA<=>xEB]
1111
(k) A= B
111
1
{ Definition of = on (k) : }
(m) A~BI\B~A
{ /\-elim on (m): }
(m + 1) A~B
{ /\-elim on (m): }
(m + 2) B~A
Properties of =:
A=Bl\t EA ~ tEB
A=B l\tEB ~ tEA
16.4-I T R A D
211
ark 16.3.3 A g n ral
Rm
hold Jar qu 1· . ·1 -
i . i u -
. rormula(or v by u wh r
in a J'
01
th J0 ,mu la.
Th· i in parti ular th case for qu li y of
1
findtwoexampl .of thi fa ct: · n th t
xt abo w
_ Th inclusion A ~ A always holds {see Section
16 2) N
A ==B. By the 'general rule of Leibniz '' we may hence· · ow as um
A ~ A for examp le the second one, by B . Thus we havereplac
sho
e an A ·
. in
thatA ~ B is a conse quence of A = B. wn directly
_ Assume A== B and t E A. By the general rule o1 Le ·b · ·t t ll
. . 2 nt z 'l JO OW
that t E B. (This is a second manner to 1·ustit.y the Proper,,,+· .
',}, r i'les O1 = given
above.}
Remark 16.3.4 The names '=-intro' and '=-elim ' will not be used any-
more.
Example 16.4.1
t wi h u 1 m nt . al o ction 16.7.)
(H 1 0 . th mp
A nd B i h union of
An th r mbin i n f
t n in h 1m n whi h r i h r in A or in B (or i
nd B. hi
i in h union f A and B if i in at l ast on:
bo hi). S id diffi r n ly:
A nd B i writt n A U B and pronoun c d
of th two. Th union of
A union B.
A d finition:
Example 16.4. 2
• {nEN ln >5}U{nENln<lO}==N ,
• ZUN =Z,
the Propert
From the definitions of intersection and union , together with
of E (see Section 16.1) , we get two useful properties:
Property of n:
t E A nB val t E A I\ t E B
Property of U :
t E A U B val t E A V t E B
nt to True -
(We have left out the part 't E U ', because this is equival
see Section 16.2. Use True-elimination.)
In what follows we shall use these properties a lot .
. Thi m n
Both intersection and union are commutative and associative
that:
A nB = B n A, A u B = B u A,
coMPLEME T
J6.5-
213
n (B n ) (A u B) u
U (B U ) .
Th e qu li i diffi ul pr V
. li d bo f r x mpl wi h h
JU . prop r-
h h ommu ivi
0 nd h
l logi 1 mbol /\ nd
V.
of . 1 . ng pro f on an r 11
dh n
i a con equence of h a o f l
/\ .
B cau e of he commutativ
ity' and associativity proper
can u ually drop the parenthe ie of n and u
ses for repeated intersection
~:ion. Hence one writes for and repeated
example A n B n C for the
tripleA B and C. It does inter ection of h
no~ actually_ matter how
long as all the three sets are we combine the e as
mcluded m the combinatio
alwaysthe same. n. The resul i
We get for example An B
n C as follows:
1 first combine A and C
into A n C, and then inters
B , or ect the result with
16.5 Complement
Aswe said already in Section
16.2, we consider all sets as
set U. Take now such a set part of a universal
A which is part of U. Then
A is the set of all elements the complement of
of U which do not occur in
of A is written as Ac. A. The complement
The definition of Ac is henc
e:
Property of c :
t E Ac val -, ( t E A)
(2) ,(x EA n B)
val
{ Property of n: }
(3) ,(x EA!\ x EB)
val
{DeMorgan}
(4) ,(x E A) V ,(x E B)
val
- { Property of c, twice: }
(5) XE A c V XE Bc
val
- { Property of U : }
(6) XE A c U Bc
Property of \ :
tEA\B ~ tEA I\ ,(tEB)
(l ) x E \( n B )
val { pr p r f\ : }
(2) x E A /\ -,( E A n B)
val { Prop rt of n : }
(3) E A I\ -,(x E A I\ x E B)
va l { De Morgan: }
(4) x E A/\ (,(x E A) V ,(x E B))
va l { Distributivity: }
(5) (x EA I\ ,(x EA)) V (x EA I\ ,(x EB))
val { Contradiction: }
(6) False V (x EA I\ ,(x EB))
val { True/False-elimination: }
(7) x E A I\ ,(x E B)
val { Property of \ : }
(8) xEA\B
(n-1) A\B==A
{ ⇒-intro on ( 1) and (n - l): }
(n) A~ B 0 ⇒ A\B ==A
At first sight, we may want to close the hole with a calculation. Note
that the goal in line number (n - l) is the equality of the sets A\ B and A.
Hence it is enough to give a calculation from which it follows that (for all
x E U) the following holds:
X E A\B val X E A.
DIFFERE CE
16,6- 21
. doe no eem to wor k:
13utth
(2) xEA \ B
~ { Prop r of \ : }
( 3) x E A I\ , (x E B)
~ { ??? }
(n- 2 ) x EA
{ Assume: }
(l) A~ BC
(m) A\B ~ A
(n-3) A~ A\B
{ /\-intro on (m) and (n - 3): }
(n -2 ) A\B~A I\ A~A\B
{ Definition of= on (n - 2): }
(n-l) A\B=A
{ ⇒-intro on (1) and (n-1):}
(n) A~ Bc =} A\B = A
{ Assume: }
(l) A~ B C
{ Assume: }
CHAPTER 16. SET
21
(2)
{ r p r y f \ on (2) : }
X E A (\ -,( E B)
( )
{ /\- lim n ( ) : }
( ) E
{ \I-in r n (2) nd ( ) : }
( ) 'v'x[ E A\B: E A]
{ D finiti n of ~ on (5): }
(6) A\B ~ A
{ As ume: }
(7) ~x; x EA
(8) \fy[yEA:yEBC]
{ V-elim on (8) and (7): }
(9) XE BC
{ Property of c on (9): }
(1) A~ B C
(2) YM x · x E A\B
(3) x E A I\ ,(x E B)
(4) xEA
(5) Vx[x E A\B : x EA]
(6) A\B~A
(7) var x; x EA
(8) Vy[Y E A: y E B 0 ]
(9) XE B 0
If we change the last result of the above reasoning a little bit, by replacing
the final A by B, it will not always be valid:
Property of 0:
rh val
t E VJ False
{ Assume: }
(1) A~B]
{ Assume: }
(2) varx; xEA\B
{ Property of\ on (2): }
(3) x E A!\ ,(x E B)
{ /\-elim on (3): }
(4) xEA
{ Property of~ on (1) and (4): }
(5) xEB
{ /\-elim on (3): }
(6) ,(x EB)
{ ,-elim on (6) and (5): }
(7) False
{ V-intro on (2) and (7): }
(8) Vx[x E A\B: False]
{ Property of 0 on (8): }
(9) A\B = 0
{ =>-intro on (1) and (9): }
(10) A~B=>A\B==0
THE EMPTY SET
16,7.
223
We can rep lace a pa rt. of t h r oning , n m ly h P rt . .
. fl g by a calculatio n. W n r pl 1'
inside a PP nn g in h
m num b r ( ) o (7) h
following:
(S') x E A A , (x E B )
~ { Monotoni ity on (3') u (1): }
(4') x E BA , (x E B )
~ { Contrad i ti on on (4'): }
(7,) Fa l se
Lemma 16.7.2
A~B ⇒ A\B=0.
1111
(k) A =0
1111
(m) t EA
{ Property of 0 on (k): }
(m+ 1) Vx[x EA: False]
{ V-elim on (m + 1) and (m): }
(m+ 2) False
Remark 16.7.3 We shall not use the names '0-intro' and '0-elim' any
further.
16.8 Powerset
Every set has subsets. Even the empty set has a subset: itself! For
a given
set A you can form the set of all its subsets, the so-called powerset
of A.
Notation: P(A).
Be careful: an element of P(A) is itself a set, namely a subset of A.
Example 16.8.1
• Take A = {5, 8}. The elements of P(A) are the subsets of A, hence
the sets: 0, {5}, {8} and {5, 8}.
• Take A= {1, 2, 3}. Then:
P(A) = { 0,{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} .
Hence for example {1, 3} E P(A), 0 E P(A), {2} E P(A), but not
2 E P(A), because2 is not a subset of {1, 2, 3}, but an element of it.
• Take A= 0. Then P(A) is the one-element set (!) {0}.
• Take A = N. Then the fallowing sets are for example elements
P(N): of
Property of P :
v al CC A
CEP (A) - -
{ Assume: }
(1) A~ BI
{ Assume: }
(2) var X; XE P(A)
(n - 2) X E P(B)
{ \I-intro on (2) and (n - 2), definition of~: }
(n - l) P(A) ~ P(B)
{ =>-intro on (1) and (n - 1): }
(n) A~ B ~ P(A) ~ P(B)
226 CHAPTER 16.
ET
{ Assume: }
(1) A~B,
{ Assume: }
(2) Yfil X; X E P(A)
{ Property of P on (2): }
(3) X ~A
(n - 3) X ~B
{ Property of P on (n - 3): }
(n-2) XEP(B)
{ \I-intro on (2) and (n - 2), definition of~: }
(n - 1) P(A) ~ P(B)
{ =>-intro on (1) and (n - 1): }
(n) A~ B => P(A) ~ P(B)
Note that we have moved here from the element-level, for example (see
line (2)) XE P(A), to the (sub)set-level, for example (see line (3)) X ~ A.
Now we can easily complete the proof, because it is intuitively clear that
the propositions X ~ A in line number (3) and A ~ B in line number
(1) together have as conclusion that X ~ B. This latter can be shown as
follows:
{ Assume: }
(1) A~ B
{ Assume: }
{ Property of P on (2): }
CARTESIAN PRODUCT
16.9·
227
(3) X~A
{ A sume: }
(4) var x; x E X
(5) xEA
{ Property of~ on (1) and (5): }
(6) XE B
(7) X~B
{ Property of P on (7): }
(8) XE P(B)
So, if A and B are sets, then the Cartesian product A x B consists of all
pairs (a, b) where a EA and b EB. From this it follows directly that:
Property of x :
_(a,b)EAxB ~ aEA J\ bEB
Example 16.9.1
A~ B =;- A 2 ~ B 2 •
{ Assume: }
(1)
(n-1) rB 2
'AR i. 11A H
1 .9. 22
hi giv
{ A um : }
(l ) A~B
(n - 2) 2
\:/(x, y) [(x, y) EA : (x, y) E B 2 ]
{ D finition of ~ on (n - 2): }
A2 ~ B
2
(n - 1)
{ =>-intro on (1) and (n - 1): }
(n) A ~ B =>A 2 ~ B 2
{ As um e: }
(1) A ~ BI
{ Assume: }
2
(2) Yfil: (x , y); (x, y) E A
{ Property of x on (2): }
(3) xE A/\yEA
{ /\-elim on (3): }
(4) xE A
{ Prop erty of~ on (1) and (4): }
(5) xE B
{ /\-elim on (3): }
(6) y EA
{ Prop erty of ~ on (1) and (6): }
230 CHAPTER 16. SETS
(7) y∈B
{ ∧-intro on (5) and (7): }
(8) x∈B∧y ∈B
{ Property of × on (8): }
(9) (x, y) ∈ B 2
{ ∀-intro on (2) and (9): }
(10) ∀(x,y) [(x, y) ∈ A2 : (x, y) ∈ B 2 ]
{ Definition of ⊆ on (10): }
(11) A2 ⊆ B 2
{ ⇒-intro on (1) and (11): }
(12) A ⊆ B ⇒ A2 ⊆ B 2
Finally, it is good to know when two pairs are equal – and when they are
not. The pair (a, b) is equal to (a′ , b′ ) if, and only if, both a = a′ and b = b′ .
So in N × Z, the pair (2, −2) is only equal to itself, and to no other pair
like (2, 2) or (0, −2). Moreover, if (x, y) = (2, −2), then x = 2 and y = −2;
and also the other way round. Of course, we may allow some mathematical
calculations, such as (2 + 3, −2 + 1) = (5, −1), because 2 + 3 = 5, etc.
We state this ‘equality for pairs’ as another Property of ×:
Property of × :
val
(a, b) = (a′ , b′ ) == a = a′ ∧ b = b ′
16.10 Exercises
16.1 Check whether the following propositions always hold. If so, give a
proof; if not, give a counterexample.
(a) A ∪ B = B ∩ C ⇒ A\B = ∅
(b) A\B = ∅ ⇒ A ∪ B = B ∩ C
16.10 As Exercise 16.9:
(a) P(A) ∩ P(B) = P(A ∩ B)
(b) P(A) ∪ P(B) = P(A ∪ B)
16.11 Take A = {1, 2, 3, 4}, B = {1, 4} and C = {1}.
(a) Give B × A, B × B and B × C.
(b) What is B × ∅?
(c) How many elements does A × B × C have?
16.12 Prove or give a counterexample:
(a) A × B = B × A
(b) A ⊆ B ⇒ A × C ⊆ B × C
(c) A × A ⊆ B × C ⇒ A ⊆ B ∩ C
(d) A × B = C × D ⇒ A = C
Chapter 17
Relations
Example 17.1.1
• The relation 'is-a-child-of'. This relates children and parents, as in
the sentence: 'Prince Charles is-a-child-of Prince Philip'.
• The relation 'is-greater-than' (or simply: '> '). This is usually a re-
lation between pairs of numbers. For example, the proposition '5 is-
greater-than 3' holds, but not '3 is-greater-than 5 '.
233
H PTER 17. RELATIO
234
R== {(1,0),(2,2),(2,3)}.
2
B
0
2 0
1
0
0 1 2 A
Not only R == {(1, 0), (2, 2), (2, 3)}, but every subset of Ax B det rmin
a r lation between A and B. As we see in our examp le #(A) ==3 and
#(B) ==4, h nee #(A x B) == 3 x 4 ==12. A set with 12 element h
212 ubs ts, hence between these A and B there are 2 12 ==4096 different
relations po sible. The R above is only one of these!
Two extrem cases are the empty relation, RJ_ ==0, and the full relation
RT = A x B. The empty relation holds if there is no connection at all
between any element of A and any element of B (no elements are related),
the full relation holds if every element of A is related to every element of
B. (What do the Cartesian graphs of RJ_ and RT look like?)
(2) In the second case, the connections are directly described by putting
the letter R between the relevant elements of A and B: 2R3 says that
2 E A is related to 3 E B. (Hence we don't write R(x, y) as is standard
for predicates , but we use the infix-notation: xRy, with the symbol R
betweenthe elements.) Instead of this letter R, we can also use an arrow, for
example: 2--? 3. A diagram which expresses this is the arrow graph, where
arrows are drawn between the points which are related. In our example,
this is given in Figure 17. 2.
1
0
A B
Figure 17.2: The arrow graph of the relation R with lRO 2R2 and 2R3.
00 1 2 3 4
... N
(1) Reflexivity
A relation R on A is said to be reflexive if:
•
X
igur 17.4: For a reflexive relation on A, every poin x i r lat d to its lf.
• ' val 'on the set of all abstract propositions; this is reflexive becau e
it is always the case that P val P (see Lemma 6.1.1 (1)).
• ' ~ ' and ' ~ ' on the set of all abstract propositions.
(2) Symmetry.
A relation R on A is called symmetric if:
X • • y
_______)
• '==
' on .
• 'has-direct-connections-with ' on the set V of all airport ( urning
that every flight has also a return flight).
• '>', '<', ' 2::', ' :S;' on JR. Counterexample for the last relat ion: 5 ~ 7
but not: 7 < 5.
• Similarly for: 'is-the-boss.-of ' (unless no-one is the boss in the com-
pany !).
(3) Transitivity.
A relation R on A is called transitive if:
• ' val ' on the set of abstract propositions, because if P _va_l Q and
Q val R, then also P val R (see Lemma 6.1.1 (3)).
• '~
r--' and ' ~~ ' on the same set.
• '=', '>', '<','~'and'::;' on IR. For all x, y and z E JR.it holds for
example that: if x ::; y and y ::; z, then x ::; z.
• 'is-a-child-of'.
• 'is-the- boss-of'.
• 'has -direct-connection-with'.
Example 17.4.1
L nE
ndn ~ 2. W y f kl E Z h
k ==l mod lo n if k _ l ·
l ipl of n. .
(A multip l oJ n 1
a rnu h n m d .
rib numb r whi h i th pr du
. g r nd n h n £ r x mp l 3.n r -
~f
: i'.~) ndO(b u 0 = 0.n).)
5. bu l n i lf (b
Example 17 .4.2
• 27 ===7 modulo 5, because the difference 27 - 7 is a multipl of S.
We will use in this book a special notation for the relation 'is-equal-to-
modulo-n', namely =n·Hence our examples above are written as: 27 =s 7
3 ==ll 102 and 15 =23 15 respectively.
The definition of the relation =n
on Z is hence:
x =ny if x - y is a multiple of n .
We will prove now that =n is indeed an equivalence relation on Z.
For this we need to show :
(1) =n is reflexive: Vx[x E Z: x =n x].
(2) =n is symmetric: Vx,y[x, y E Z: x - ny =>y =n x].
(3) =n is transitive: Vx,y,z[x, Y, z E Z: (x =n y I\ y =n z) =>x =n
z].
(1) A proof of the reflexivity of =n begins as follows:
{ Assume: }
(1) var x; x E Z
(l -1) X =nX
mult iple of n.
H nee th full proof is as follows:
{ A um : }
(1) Yf!:[ x; XE Z
{ Mathematics: }
(2) O is a multiple of n
{ Mathematics: x - x ==0: }
(3) x - x is a multiple of n
{ Definition of =non (3): }
(4) X =n X
{ Mathematics: }
(2a) x-x=O·n
{ Mathematics: }
(2b) OEZ
{ :3*-intro on (2a) and (2b): }
(2c) :3k[k E Z : x - x = k • n]
{ Definition of 'multiple of n' on (2c): }
(3) x - x is a multiple of n
{ Definition of =n on (3): }
(4) X=n X
Lik~ this, we ~ak~ the proof much more difficult than is needed. The
st given reasoning is convincing enough. For this reason, in this kind 0!
fir
eavrvALENCE RELATION 2
17,4•
ll not bring to light th 'hidd n 3- quantifi r in propo · ion of
proofswet~ a multipl e of n '. S al o th follo wing two proof.
thefo,;rn,
We giv
now a proof of th symm try of =n.
(Z)
th
core of uch a proof w mu t how h =n
y⇒y =n h n :
In . multipl of n, th n Y - x i al o mul ipl f n . hi i n
If - Y a e b cause y - x is the inverse of x - y, h n if x - y = k . n
15
diffi ult to_nsk 'E z then y - x ==(- k) · n, and hence y - x i also mul ipl
certa1 ' )
for 8 N0 t that -k is also an element of Z .
of n. ( e
the proof becomes:
J-Ience,
{ Assume: }
(l) ~ x, y; x, y E Z
{ Assume: }
(2) X ==n
Y
{ Definition of =n on (2): }
Note that for convenience, we have combined two flags in line number
(1): the flag for x and the flag for y. This is possible here, because we strike
these flags out (retract them) together after line number (6).
(1) Yfil.X,yz;x,y,z EZ
{ Assume: }
(2) X =nY I\ Y =n Z
b gin wi h rt m a E A nd r h £ r 11 h 1 m n
If w d hen we g ta ub t K(a) S:;;A. W n d fin K(a) o whi h
ai r l f llow:
K(a) = {b E A laRb}.
u bset K (a) is called the equivalence cla 8 of a ( i h
Sueh a 1. . r p o
S. ilarly t o what we exp amed above m the case t hat aRb and Re
R) im . h' h . 1 a w
· elude that wit m sue an eqmva ence class every element i d
can con
(
w· h' r 1
ry other) element. it m such a class there is hence a kind of
to eve . ' d'
·mal relation: an arrow runs roun from every point to it elf and
maxi ver , an arrow runs between
moreo . every
. pair of different points within th·
c1ass (and hence for every pair of pomts. there are arrows in both directions ) ·
The relation R is hence the full relat10n on such a class.
From the definition of K (a) it follows that: if a is related to a', then a' i
. the equivalence class of a. But if a is not related to a', then a' is outside
~(a) and we can then l?ok for the equivalence class of a', or K(a'}· Now it
• simple t o prove that m such a case, also the whole class K (a') 1s outside
~~e class K(a), that hence K(a) n K(a') is empty. Because, from assuming
that x E K (a) n K (a'), a contradiction follows. We show this in a similar
way to what we did in Chapter 16 (see in particular Section 16.7):
{ Assume: }
(1) ,(aRa ') I
{ Assume: }
-----------,
(2) Yill: x; x E K(a) n K(a')
{ Property of n on (2): }
(3) x E K(a) I\ x E K(a')
{ Definition of K(a) resp. K(a') on (3): }
(4) aRx I\ a' Rx
{ Symmetry of Ron (4): }
(5) aRx I\ xRa'
246 CHAPTER 17. RELATIO
Hence, for any two equivalence classes - say the classes of a and a' -
corresponding to a given relation R, there are only two possibilities:
• the equivalence classes of a and a' coincide, i.e. K(a) = K(a'); this is
the case if aRa',
Apart from K( 4) , there are four more equivalence classes for =s:
K(O) =={ . .. , -20, -15, -10, -5, 0, 5, 10, 15, 20, ... },
K(l) =={ ... , -19, -14, -9, -4, 1, 6, 11, 16, 21, ... },
K(2) =={ ... , -18, -13, -8, -3, 2, 7, 12, 17, 22, ... },
K(3) =={ ... , -17, -12, -7, -2, 3, 8, 13, 18, 23, ... }.
EQUIVALENCE CLASSES 247
11.5,
--y y y ...
• z
..~280 305 s010
• • • •
1
•
2
• • •
6
•
7
• • •
uch as:
• all elements of all classes form togeth er precisel y the collection o all
ab tract propositioris {the union of the classes gi ves the whole col/.ec
-
tion hen ce: every proposit ion occurs in - precise ly - one class) .
The, figure at the end of Chapter 4 gives a clear idea of the class-division
{the partition ) that we obtain there.
If both relations R and S are between A and the same A, in other words
both are relations on A, then R and S can be connected either way and
henceboth R;S and S;R are well-defined. (In the above example , these are
respectively 'is-a-child-of-a-sister-of' and 'is-a-sister -of-a-child-of ' - which
obviouslyare different relations.)
We can also compose a relation R on A with itself, and then we get R;R,
also denoted by R 2 . So for example, 'is-a-child-of' composed with 'is-a-
child-of'is the same as 'is-a-child-of-a-child-of' (hence a grandchild). Note
2
that for the composed relation R , we have as before that xR z holds if
2
there is a (at least one) y such that xRy and yRz. For example, 'Anna
is-a-child-of-a-child-of Charles' if there is a person 'B' where 'Anna is-a-
child-ofB' and 'B is-a-child-of Charles'. Hence, one of the parents of Anna
(Bernard? Berta?) must be a child of Charles.
3
We can repeat the above process, to obtain R;R;R (or R ) , etc. For t
arr<lw E A it holds then that tR 3 w if there are u and v E A such that tRu ,
uRv and vRw. We can continue this process: R4, R 5 , ....
The transitive closure of R, denoted by R+, is the relation where
250 HAPTER 17. REL TIO
even but !-
½is not.
17.8. EXERCISES 251
17.8 Exercises
17.1 The relation R on {1, 2, 3, 4, 5} is given by the following table:
1 2 3 4 5
1 1 0 0 1 0
2 0 1 1 0 0
3 0 1 1 0 0
4 1 0 0 1 0
5 0 0 0 0 1
(A symbol 1 in line k and column l means that the number before line
k is related to the number above column l, a 0 means: these numbers
are not related.)
(a) Give an arrow graph of R.
(b) Give the directed graph which corresponds to R.
(c) What is so special with this R?
17.2 The relation R on {0, 1, 2, 3, 4} is given by:
xRy if (x = y) ∨ (2x = y).
(a) Give the Cartesian graph of R.
(b) Give the arrow graph of R.
(c) Give the directed graph of R.
17.3 Check whether each of the following relations is reflexive, symmetric
and/or transitive:
(a) R on Z with xRy if x + y is even.
(b) R on Z with xRy if x + y is a multiple of three.
(c) R on N+ with kRl if l is a divisor of k.
(For a definition of ‘divisor’, see Section 20.2.)
(d) R on P(U) with ARB if A ⊆ B.
17.4 Let V be a set and R a relation on V which is symmetric and transitive.
Prove:
∀x [x ∈ V : ∃y [y ∈ V : xRy]] ⇒ (R is an equivalence relation).
17.5 The relation R on R is given by
xRy if (xy > 0) ∨ (x = y = 0).
(a) Show that R is an equivalence relation.
252 CHAPTER 17. RELATIONS
Mappings
255
2 rfAPT R1 . 1APPJ G
graph (see Figure 18.1), and also an arrow graph (see Figure
18.2).
2 0
1 0 0
0 . .. N
0 1 2 3 4
-1
-2 0
lly this
Let R be a relation from A to B. When is R a mapping? Basica
A is related to
holds when we have what we suggested above: each a of
exactly one b i~ B. (A certain 'input' gives one 'output', no
less and no
more.) Hence, 1f we take a certain a, then:
- there is a certain b E B such that aRb,
th b is also unique: there cannot be a c different from b, 5uch
- but is '
that aRc.
.,.~APPJNGSFROM ON E SET TO A OTHER
18.l· lVJ
2 7
th abov giv _n xampl ' it i impl to h k h .
In_ articular F1gur 18.2). H n it hold h . h1 pr P r h ld
(see inthp r YE z·
. 0R - 2 bu n OR
Y for
°
an at i not allowed for a mapping i drawn h .
ma 1 lly on h l
Wh f Figures 18.3 and 18.4:
h8Jveso
There cannot be a point in A that is not relat d .
o any point in B
• d·
an ·
There cannot be a point in A that is related t t wo or more point
• . B o
1n ·
4 • • 2
3 • • 1
2 • • 0
1 • • -1
0 • • -2
on the
But be careful: A mapping can very well fit the situation drawn
point a
right half of Figure 18.3: there may be points b in B to which no
such a
in A is related. See the example of Figure 18.2, where - 1 E Z is
can very
point. Also, the situation drawn on the right half of Figure 18.4
wellhappen, namely that two (or more) different elements of A are related
18.2,
to one and the same element of B. See again the example in Figure
wherefor -2 E Z both OR- 2 and 4R- 2 hold.
~e
Re~ark 18.1.1 The strict condition that for every a E A there.mus_t
preciselyone b E B with aRb, is sometimes weakened in practi
ce: it is
258
CHAPTER 1 .
no no
outgoing incorning
arrows arrows
A B A B
enough that for a E A at most one such b E B exists {hence the non-
existence of such b is also acceptable) . In the latter case {when there are
a 's in A that are not related to any b 's in B ), one speaks also of a partial
funct ion. This means for example that the funct ion y = x:il is in this
view a 'good ' mapping from iR to , despite the fact that for x = 1 th~re
is no correspond ing value y. The same holds for the func tion described
by y = t an (x) , which is ojten called a mapping from to , although no
y- value is given to x = } + kri.
In this book we keep to the strict condition that a relation from A to B
can only be a mapping (or a function ) if for every a E A there is precisely
one b EB such that aRb.
A B A B
Figure 18.4: In a mapping , two outgoing arrows are not allowed, whereas
two incoming arrows are indeed allowed .
RACTERlSTICS OF A MAPPI G 2
rJIE cFIA
182
·· The characteristics of a mapping
l g.2 . c ion w d fl 'b d w h n J. n R b w n A nd B
pr vioLI · Thi d ription n b wri n in th form f
111the call d a mapping.
ti l1 be r lloW : 1
cforfllula. J.o V [x E A : 3 [y E B : Ry)] .
x Y
1
h r th new quantifi er 3 for th o- a ll d uniqu wtn :
We us . l one . . . . How can we prove now for a giv n x E A h
. precise Y
there isB . xRy]?
3t [YE . · e look first at the general case of a unique existence h nc a
For tins , f~he form ::it[Y EB: P(y)], for some predicate P. Thi formula
a [orrnula o
saY: . recisely one y E B with the property P(y).
There 1s P
. 'de this in two parts:
Wed1v1
·s at least one y E B with P(y), and
(1) t here l
e is at most one y EB with P(y).
(2) t her
For (l) we immediately get a formula:
:3y[Y EB: P(y)] .
For (2) we must think a bit. The simplest is to express 'at most one ' as
,no.t· two or more'. And this latter can be formulated as:
:ly[Y EB : xRy] I\
Vy1 ,Y2 [Y1,Y2 E B : (xRy1 I\ xRy2) =} (Y1= Y2)]
The last equivalence can be applied in proofs where unique existence
playsa role.
A mapping from A to Bis usually denoted not by the letter R of 'relati on ',
but for example by the letter F of 'function', or by lower-case letters: f , g.
1i PTER 1 .
260
fr m B. · w wn F: B. t'
If F i a m ppin . . norlllal
. c pping wn th r la 10n be " n E .. and b E B
pr t1 1or m '
cliff r n I : if a i r I t d t b w d~~ writ aFb. bu . ad w ~i
F (a) = b: Thi l t r not tion i farruh : on wn o 1 d o:
°
2 In thi
1. no
8 ion "e can "ri t th ear
li r d n'b e d· c h arac r . tic prope
of a mapping as follow :
Property of mapping F :A ~ B :
1 [y EB : F x) = y]
xx EA: :3
Remark 18.2.1 Ho does the abo e fit fo r fu ncti ons of more than one
2
ariable ? For example: z = sin (x + Y) or f ( Y - Y ~? . Th e
can still be seen a mappings from A to B. but then ith a Cart ian produc
fo r A: the first example can be a function from . th eco d from
to IR.
3 to . H ence, also functions of more than one ariab le fa ll under our
abstract concept of mappings.
• But how things are in B can vary quite a lot: there can be b's in B
which receive no incoming arrows at all and there can be some which
receive one incoming arrow , or two, or more , and even infinite! m n ·
(It depends on F how many letters a certain b in B will receiv ·)
We_now explain two different concepts that are important for a gi en
mappmg F : A ~ B: the image of a subset of the domain A and the
source of a subset of the range B.
JMAGEA D SOURCE
JB,3
• 2 1
(1) 1rnage .
t h A' 1 m in A.
urne fir . 1 h b . . m i m s i is in r ting
A .-.; .; wh r pr 1 . gin in A' will nd
to kn° h b in B th r 1v 1 r fr m , . (h
. Iy t . 11d h . n a in
Pr .c1 ubcollection of B 1 c t imag of A' und r F .
'f hl
I-In e:
F(A') ::: {b E Bl:3x[xEA': F(x) = b]}.
8.3.1 In computer science notation, th·
mark 1
}le tly as
is can be written more
follows:
elegan ==(Set x : x E A' : F( x ))
F(A') .
Example 18.3.2
• Look at the fu~ction ~in : JR ~ JR. For the subset J ==(0, n) of the
domain R (I is the interval of the numbers between o and n)
have: the image of I under sin (denoted by sin(!)) is (0, 1] {th~t %~
the interval of the_numbers betwee~ 0 and 1, including 1 itself). {Note
that in mathematics books, (0, 1r) is often written as (0, n).)
ote that the notation F(A') for the image of A' under the mapping F,
is 'abuse'of notation: we pretend here that F acts on a set, while actually,
Facts on elements of a set.
262 1-IAPT R 1 . MAPP!
s
R mar k 18.3.3 So w a sign a do11 ,bl rol to ach function -s b
th fir t pla .
su Ii an F act s on ar bitrary l m nt s of th domain
Ym ol p. ·
A . · in
only ondarily , w allow F lo act on sub ts A ' of A, as w ll. Th ' a~d
how v r a r la~ion b tw n th s two ro! s of F: w may consid r F ~
(h nc with F in th second role) as b mg a shorthand for h t (A)
F(a ') (with F in th first role), wh re a' ranges v r a ll I m nts 8of;,'. all
(2) Source
Consi der now a sub set B' of th e r ange B. It can be useful to know wher
t he arrows arrivin g in B h ave com e from (whi ch let te r wri te rs from A hav:
sent a lette r t o som eon e in th e subclub B'). This is call ed t he source of B'
unde r F. Not ation: F - (B'). Hence:
Example 18.3.4
• Look again at the function sin : IR --+ IR. Take the subset Z in the range
IR. What is the source under sin? This is the set of all the x 's in R
fo r which sin(x) E Z. This latter can only hold if sin(x) E {-1 , 0, 1},
because I sin(x) I :::;1. The answer is hence: the set of all the x 's such
that x is an integer multiple off.
In summary: sin-(Z) = {x E IR\x is a multiple of f}.
{In computer science notation this can be written more nicely in the
following form: sin-(Z) = (Set u : u E Z: u x ~).)
Remark 18.3.5 Take again the mapping F : A --+ B and let B' ~ B · The
symbol F - in F - (B') operates on the subset B', not on its elements! The
resu lt F - (B') is also called complete source instead of {simply) source. The
term 'inverse image' is also used.
IMAGE AND SOURCE
JB.3•
263
Wesumrnariz o~r know! dg bout im g and
. wordBand in a p1ctur : ur n again bo h
in Let F : A __.B b a mappin g nd ume h
B' c B. Th n: iv I
_-the image F(A') fall th nd P in
,4' f h rrow whi h b .
in . F (B') on i t of U h b . egin
- Th ourc gin P in of h
end in B'. rr w which
W how thi in Figur 18.5 .
•
-- ?
----
•
A'
•
• -- tJ
F(A')
?
?
F-(B')
----
•
•
B'
A B A B
Properties of 'image':
x EA' ~ F(x) E F(A')
') :::i [ XE A' : F( X ) = y ]
' Y E F(A
val ::ix
{ Assume: }
(1) YM x; x E A'
{ First property of 'image' on (1): }
(2) F(x) E F(A')
{ Property of 'source' on (2): }
(3) x E p- (F(A'))
{ V-intro on (1) and (3): }
(4) Vx[x EA': x E F-(F(A'))]
{ Definition of ~ on (4): }
(5) A' ~ p- (F(A'))
(1) There are mappings where each b in B has at least one incom·
arrow. Such a mappmg · ca 11ed a suryec
· 1s · Hence, for a surJ·ecfing
. tion.
,. d d 11 ion
the right half of Figure 18.3 changes: m ee a owed' is changed into
'not allowed'. See Figure 18.7.
(2) There are mappings where each b in B has at most one incomin
arrow. Such a mapping is called an injection. Hence , for an injectio~
the right half of Figure 18.4 changes. See Figure 18.8.
(3) There are also mappings where each b in B has precisely one incom-
ing arrow. Such a mapping is both surjective and injective. Such a
mapping is called a bijection.
(1) Surjection.
The characteristic property of a surjection is:
Property of 'surjection' F : A ~ B:
Vy[Y EB: =lx[x EA: F(x) = y]]
Hence , for a surjection it does not only hold that F (A) ~ B , we even
have F(A) = B: every bin B is the image of at least one a in A.
Example 18.4.1
· f ·· . .
• Th fun tion i h f ( ) = x" · ri
•J
for ry odd
and not ury tiv for v ry v n n E .
nE
Th xpon ntial fun tion with Jormula y = x · n urj
• mapping is from IR to b caus x is alway p sitiv .
A B A B
Figure 18.7: For a surjection there is for each b in B at least one incoming
arrow.
Remark 18.4.2 The word 'surjection' is French/Latin and means 'a throw-
upon'. A surjective mapping 'throws' the domain A 'upon ' the range B, the
whole range becomes hence covered.
A surjection is also called 'a mapping-onto': saying that 'f is a mapping
from A onto B ' means that f : A ---? B is a surjection.
(2) Injection.
For an inject ion F : A ---? B , the characteristic property is that for every
element b E B t here is at most one a E A with F(a) = b. Hence , there
can never be two diff erent a's in A which have the same image b in B
(see also Figure 18.8). Because of this last observation we can write the
'HAFTER 1 . M PPL
26
~ B :
Property of 'injection' F : A
VX1, x 2 [ 1 , 2 EA : (F(x1) = F(x2))
=>(x1 = x2)]
poin
every b in B n~ed to be an nd
For an injection F : A ~ B, no~ h arrow.
s m b, then there 1s only one u
of an arrow, but if an arrow end w b gin
a unique a E A where this arro
In the latter case, there is clearly
(hence with F(a) = b).
A B A B
incoming
re is for each bin B at most one
Figure 18.8: For an injection the
arrow.
Example 18.4.3
h
an injection. We can show this wit
• The function sin : IR.~ IR.is not 3 == ½J2.
a counterexample: sin( f) ==sin( 41!"
)
(3) Bijection.
A biJ.ection is at the same .time a surjection and an 1·~~· t IM.
· T
hl m n
that for every b E B there 1s precisely one a E A with F( a) = b:
Property of 'bijection' F: A~ B:
v'y[YEB: 3;[x EA: F(x) = y]]
Remark 18.4.5 The word 'bijection' contains the Greekprefix 'bi', which
means 'double'. This expresses the fact that a bijection is both a surjection
and an injection.
Example 18.4.6
• The function f : JR -4 JR with f (x) = xn is bijectivefor every odd
n E N (we already saw above that it is surjective and injective).
• The function sin is not bijective as a function from JRto JR,but it is as
a function from [O,~] to [O,1]. The same holds for cos. The function
tan is bijective as a function from (- i, i) to JR.
• The exponential function y = ex from JRto JRis not bijective, but it is
as a mapping from JR to JR+, the positive real numbers.
• Also the logarithmic function y = ln(x) is bijective as a mappingfrom
JR+to JR.
·.·•...
111111~
',
; . '
{ Assume: }
(1) F is an injection
{ Assume : }
(2) var x; x EA I
{ Assume: }
(3) F(x) E F(A')
(n) XE A'
(At the end one should actually add a couple of lines expressing how one
gets via =>-intro and \I-intro to Vx[x EA: (F(x) E F(A')) =>(x EA')]. For
convenience, we leave these steps out .)
For clarity, we will abbreviate F(x) with the letter y:
1 .J. 27L
(l )
()
}
()
')
{ D fin : }
y := F( x )
()
{ then (3) becomes: }
(5) y E F(A')
(n) XE A'
{ Assume: }
(1) F is an injection ~
{ Assume: }
(2) Yfil x; x EA~
{ Assume: }
(3) F(x) E F(A')
_,
{ Define: }
(4) y := F(x)
{ then (3) becomes: }
(5) y E F(A')
{ Property of 'image' on (5): }
(6) :3x'[x' E A' : F(x') = y]
{ 3*-elim on (6): }
(7) Pick an x' with x' E A' and F(x') =y
272 CHAPTER 1 . MAPP! GS
(n) . A'
(1)
(2)
{ : }
(3) F( (A')
{ D fin : }
( ) y := F(.)
{ th n (3) b om s: }
(5) y E F(A')
{ Prop rty of 'ima.g on (5): }
(6) 3. , [.·' E A' : F(. ·') = y]
{ :3*- lim on (6): }
(7) Pi k an . ·' with . ' E A' and F(. ·') = y
{ tvfath ma. i on (4) a.nd (7): }
( ) F. = F( ')
{ Pr p r of inj ctio n on (1): }
( ) Vu 1 u1 [u1 U2 EA : (F(u1) = F(u2)) =} (u1 = u2)]
) nd =} - lim on (9) ( ) (7) and ( : }
(10 .- .,
{ n ) and (10) : }
'fY
pE YAL MAPPI G
1 .4. 273
I X E A'
(11)
{ ::}-in r n ( ) n ( 11): }
(F(x) E (A' )) => ( E A' )
(12)
r r ady: hi i a d riv i n h
Bn w n in h ompl
pro f
of L rnrna1 .4. 7.
This is very simple with the help of the above proven Lemma 18.4. 7:
{ Assume: }
(1) Yfil x; x E F-(F(A'))
{ Property of 'source' on (1): }
This means that the points in A and B are paired to each other via F.
In Figure 18.9, an example is given of such a pairing.
Hence, in the case of a bijection F from A to B, to each a in A there
corr spends precisely one b in B, but we can just as well say that to each b
in B there corresponds precisely one a in A.
This means that we can turn all the arrows round and we get again a
mapping, this time from B to A. This mapping, which gives the same
relation as F but in the other direction, is called the inverse of F and is
denoted by F - 1 • Note that, the inverse of F exists only if F is a bijection!
A B
Figure 18.9: Example how a bijection from A to B pairs the elements to-
gether.
e inverse function
For each bijection F : A -+ B there is hence a uniqu
sely the opposite
p-1 : B -t A. Be~aus_esuch an inverse function does preci
:
of what the funct10n itself does, the following follows easily
Vx[xEA: F- (F(x)) ==x].
1
a, hence
In fact, if F(a) == b, then p-i returns point b back to point
p- 1 (F(a)) ==F- (b) ==a.
1
their inverses:
We give a couple of examples of bijective functions and
Example 18.5.2
2 is a bijection.
• The square function f : JR+ --+ JR+ with f (x) == x
ad of JR+
(Remark: If we took JR {all real numbers) as domain inste
tion.) The
(the positive real numbers), it would not have been a bijec1
(x) == ft.
inverse function J- : JR+-+ JR+ is the root funct1 ion: J-
1
e: JR+) has as
• The exponential function y == ex ( domain: JR, rang
e: JR).
inverse the natural logarithm y ==ln(x) (domain: JR+, rang
There is only one case for which p-- and p - i coincide. amely if pis
bijection, the~ it holds for every subset B'. ~ B that the source F -( B') t
equal to the image (!!) F - 1 (B'). Check tlus.
In this way, the following takes place in the corresponding arrow graph:
in order to calculate Go F (x), you first follow the arrow from x to F(x)
O f POSITE MAPPINGS
1 .6. 277
GoF
F G
► --...
G(F(x)) ==
X F(x) GoF(x)
.
A B C
Figure 18.10: The arrow graph of the composite mapping GoF.
(there is exac ly o~e), and then you foll~w the arrow from F(x) to G(F(x))
(again here there 1s exactly one). See Figure 18.1O.
(1)
{ G is a urjection hen }
(2) 3y y E B : G(y) == ]
{ 3*-elim on (2): }
(3) Pick a y with y EB and G(y) ==
{ Also F is a surjection hence: }
(4) 3x XE A: F (x) ==Y
{ 3 -elim on (4): }
(5) Pick an x w; h x EA. and F (x) =Y
{ From (5) and (3) we obtain: }
(6) G(F(x)) = G(y) = z
{ Proper t) of ·composite mapping on (6): }
(7) GoF(x) = z
{ 3* -intro on (5) and (7): }
(8) 3x x EA: GoF(x) = z
{ V-intro on (1) and ( ): }
(9) Vz z EC: 3x XE A: GoF(x) =Z
{ Definition of surject ion on (9): }
(10) GoF is a urjection
Then these mappings are equal , because on their common domain, the
set {−1, 0, 1}, we have that: F (−1) = G(−1) = 1, F (0) = G(0) = 0 and
F (1) = G(1) = 1. Hence they are indistinguishable in their behaviour.
On the other hand if we take F and G both on a larger domain such as
{−2, −1, 0, 1, 2}, or N, then they are no longer equal.
18.8 Exercises
18.1 The relation R on N\{0} is given by xRy if y = l.c.m.(8, x).
(The abbreviation l.c.m.(m, n) means: the least common multiple of
m and n.)
(a) Check that R is a mapping.
(b) Write the function values for x = 1, 2, . . . , 12.
(c) Give R({2, 4, 6, 8}) and R({1, 2, . . . , 12}.
(d) Give R← ({8, 24}) and R← ({1, 2, . . . , 12}).
18.2 The mapping f : R → R is defined by f (x) = x2 .
(a) Show that there are S, T ⊆ R such that f (S ∩ T ) ̸= f (S) ∩ f (T ).
(b) Show that there is an S ⊆ R such that f ← (f (S)) ̸= S.
(c) Show that there is a U ⊆ R such that f (f ← (U )) ̸= U .
18.3 Let f : A → B be a mapping and S, T ⊆ A. Prove that:
(a) S ⊆ T ⇒ f (S) ⊆ f (T ).
(b) f (S ∩ T ) ⊆ f (S) ∩ f (T ).
(c) f (S\T ) ⊇ f (S)\f (T ).
18.4 Let f : A → B be a mapping and U, V ⊆ B. Prove that:
(a) U ⊆ V ⇒ f ← (U ) ⊆ f ← (V ).
(b) f ← (U ∩ V ) = f ← (U ) ∩ f ← (V ).
(c) f ← (U \V ) = f ← (U )\f ← (V ).
18.5 Give examples of mappings f : N → N such that
(a) f is a bijection.
(b) f is an injection, but not a surjection.
(c) f is a surjection, but not an injection.
18.8. EXERCISES 281
283
284 FIAPTER 19. NUMBER AND TRUCTURES
On l o un wh I numb r fr ion . h n Z ~ Q. In fa v ry
who] numb r n l b wri t n a fr t1on: 5 = 5/1 = 20/4. El m nt
of Q ar al o all d rational numb er (from th Latin word ratio whi h
origin lly only m - nt 'calculation', but lat r came to also m an 'r io or
'fraction ) .
But , not all pos ible number values are in Q. For example v'2,th squar
root of 2, is not a rational number. Other examples of non-rational (or
irrational) numbers include 7r (the proportion between the circumt r nc
and the diameter of a circle) and e (the base of the natural logarithm).
Rational and irrational numbers together form the real numbers, who e s t
is denoted by JR. And so it holds that Q ~ R The set of the irrationa l
numbers is JR\Q.
We can also represent the real numbers as points on the number line: an
imaginary straight line which is infinite on both sides and where the whole
numbers are used as a scale.
Furthermore, at a higher level, we find the complex numbers - 'complex'
here means: 'composed' - denoted by C. These are numbers a+ bi where a
and b E IR and i is the so-called imaginary entity. Hence, a + bi is composed
from a real part a and an imaginary part bi. The symbol i is also described
as the square root of -1, since by axiom it holds that i = -1. This
2
number .J=I does not 'exist' in the real world, and for this reason i is called
'imaginary'. Nonetheless, complex numbers are very useful, for example to
calculate with equations. We refer to the mathematical literature for further
details.
Note that we have: IR ~ (C (indeed, if the b in a+ bi is equal to 0, then
we get the real number a).
In the rest of this chapter we concentrate first on the natural and whole
numbers. We will study their structure (Section 19.2) and the proof and
construction methods which are based on the natural and whole numbers
(Sections 19.3, 19.4, 19.5 and 19.6). Only towards the end will the big
number systems appear in the picture: (Q and IR (Sections 19.9 and 19.10),
and then with an eye to the question: How 'big' are they actually. We will
not be concerned with (C any more.
- ...
:~-
.
~~<r~:~
·.~(_;_
19.2. TEE TR T L 1B
2
ce whi h g
a p~~ ou pb p. nd hi h g
carrieu .
Tob mor pr J
(l) ounting mu tart m w h r : i art-numb r.
( ) Once ar d t h oun in<r on inu
2 : i d liv r
n w 12umbr . . .
(3) 1 i not known m advan when coun mg will fin· h: h r no d
nd~number.Ev n tronger. we can continue to count until he nd of ur
da . in princip le, the countmg goes on forever!
\Ve can formalize all this as follows.
_ ABa set of all the 'counting numbers we take (hence including 0).
_ ABa start-number we take O E N .
However we are still not there. Because no one can so far guarantee us
that we continuously obtain new numbers, which is actually an important
condition (see (2) above). In fact, in our abstract setting, it can well be for
example that s(s(s(s(O)))) = O or that s(s(s(s(s(O)))))= s(s(O)).
In the first case we are 'back to the beginning' after four counting steps,
in the second case we make a back jump after five steps (and again every
three following steps ... ). If we use the 'usual' numbers,
then we count in
the first case as follows: o, o,
1 2, 3, 1 2, 3 o,
1, 2, 3, ... and in the second case
our counting goes o 1 2 3 4 2 3 4 2 3 4 . .. This is not what we expect
fromcounting. ' ' ' ' ' ' ' ' ' ' '.
2 6 CHAPTER 19. UMBERS A D STRUCTTJJtEs
Inductive proofs
19•3
In the previous section we formally analyzed N th .
rnber . It appears that N is not just a t ' b'ut one e basis of all of
nu f . . se ·th
Theimportant actor m its structure is that th 1 wi a structure.
by one if we start with O and then co nt·muously e e ements of N will appear
one r
nction. The elements of N can be so co ns t ructed step epeat the succe or
fu . . . fi . b t .
'f we are chmbmg an m mte ladder with step 8 O 8 (O) 8 8 Y s ep, Just as
{As we have seen, this is related to , counting, h ' ( ( 0)), and so on.
th
appear one after one.) ' w ere e natural numbers
For this reason it is not . surprising that for th· ~r h
. is i ~ we ave a s . 1 1
principle ,that fits well with this stepwise buildin ~ecia. proo
. d t. u r fi d . g process. This prmciple
is called in uc ion. vve rst escnbe this proof pri·ncip · 1 .
· e m words and th en
later on, we present it formally. ,
We start with the situation that A(n) is a one-place pre d'icat e over the
domain N of natural numbers. We assume also that .c110 r th'1s pre d'1cate t he
•
followingtwo properties hold: '
(1) The predicate holds for 0.
(2) If the predicate holds for some arbitrary i in N, then it also holds for
the successor of i.
We can say this in another way:
(1) The proposition A(O) is true.
(2) The proposition A( i) ==>A( s(i)) is true for every i E N.
The second property can also be described as follows, by successively
filling0, s(O),s(s(O)) ... for i (hence by applying repeated V-elim):
(2') A(O)⇒ A(s(O)) is true,
(2") A(s(O)) ⇒ A(s(s(O))) is true,
(2"') A(s(s(O))) ::::=>A( s(s(s(O)))) is true ...
From this we can conclude that:
- A(O)is true (this appears in (1)),
- A(s(O))is true (from the previous line and (2'), by :::}-elim):
- A(s(s(O)))is true (from the previous line and (2"), by :::}-ehm):
- A(s(s(s(O))))is true (from the previous line and (2"'), by :::}-ehm).
And so on!
UCTUREs
CILAPTER 19. NUMBERS AWD STR
inductio n:
( ) A (O)
..
(l) ii E : A (i) ⇒ A (i + 1)_
{ Ind uct ion on (k) and (l ) : }
(m) n n E : A (n)
(k) A(O)
{ Assume: }
(k+ 1) var i; i EN
{ Assume: }
(k+2)
(l - 2) A(i + 1)
{ ⇒ -intro on (k + 2) and (l - 2): }
(l - 1) A(i) ⇒ A(i + 1)
{ Y-intro on (k + 1) and (l - 1): }
(l) Vi[i EN: A(i) ⇒ A(i + 1)]
{ Induction on (k) and (l): }
(m) Vn[n EN: A(n)]
In the part of the proof which must be filled in the second sequence of
dots, between line number (k + 2) and line number (l - 2), we can use that
A(i) holds for the i which is introduced in line number (k+ 1). This A(i) is
calledthe induction hypothesis or the induction assumption. The purpose
ofthis second part of the proof is to prove that A(i + 1) holds if we 'know'
that the induction hypothesis A( i) holds.
ote the big difference between the status of A( i) in this proof skeleton
(A(i) is an assumption that we may use between lines (k + 2) and (l - 2))
and that of A(i + 1) (which we may not use in these lines, because we still
haveto show it). Those who don't distinguish these two points, will get
greatlyconfused and will probably get lost.
Remark 19.3.2 The concept of 'induction' comes from the natural sci -
e~ces:if we observe in an experiment that a certain phenomenon covers a
:~g
~umberof cases, then it is reasonable to conjecture (and this is 'induc -
ion~that a pattern is in place. For example, if, for a large number of times,
wepick up a stone and then open our hand, and in each case the stone falls
290 CHAPTER 19. NUMBERS AND STRUCTURE~
down and n v r up· th n th conclusion that this stone will alway Jall do
is justifi d ( induction;. wr
The word 'induction' comes from Latin. 'To induce' means 'to lead to
And indeed the observed fact that the stone falls every time when you l
it go lead to the conclusion that the stone shall always fall. Similarly thi
truth of the two propositions A(O) and A(i) =} A(i + 1) (for every i), leadi
to the conclusion that A( n) must be true for every n E N.
The predicate A( n) over which the induction must go, is the formulc
(1 + h)n 2::1 + nh. For this A(n), we must first prove the basis A(O) anc
thereafter the step Vi[i EN: A(i) ⇒ A(i + 1)):
• The basis is not a problem, because (1 + h) 0 ==1 ==1 + Oh, and hencE
surely (1 + h) 0 2::1 + Oh. (Indeed, if a ==b, then it also holds (by the ruh
/\-V-weakening) that a = b V a > b , i.e. a 2::b.)
• The step is not difficult either; it amounts to cleverly applying somE
basic mathematics.
We give immediately a full proof:
{ Mathematics: }
(1) (1 + h) 0 ==1 ==1 + Oh, hence (1 + h) 0 2::1 + Oh
{ Definition of A(O) on (1): }
(2) A(O)
{ Assume: }
(3) Yfil. i; i E N
{ Assume (induction hypothesis): }
(4) A(i)
t •• ·, - • • • __ ,,,.,_ ,.,,,__,_
JJUCTIVE PR 0
J9.3-1 >
l
{ ..fa h ma i }
1
(1 h)' =( h) {l
1
h) ~ ( ( ) ) (1
6) . )(1 ) ==
1 (i 1)h ih ~ 1
2
(' l )h
{ H nc from hi i foll ha: }
(1 h )i 1 ~ 1 (i l )h
()
{ From (7) b definition of A(i • l ): }
() A(i I )
{ =}-intro on (4 ) and ( ): }
(9) A(i) =} A (i 1)
{ -intro on (3) and (9): }
(10) 'v\(i E : A (i ) ⇒ A (i 1)]
{ Induc tion on (2) and (10): }
b ·ause w now hav e 1 + h > O it follows from (1 + h)i 2::1 + ih (see lme
~umber(5)) that we must also have: (1 + h)i(l + h) 2 (1 + ih)(l + h) (see
line number (6)). (If also h < -1 was allowed, the last would not follow
292 CHAPTER 19. NUMBERS AND STRUCTURES
n mor .)
H n , induction giv s u an xtra po ssibility o show Vn[n E N : A(n)J
via th ' b i ' nd th ' t p . But do not forg t th t th old proof rule 'V-
intro i - a l O in th c when th domain is N - st ill a promi sing m thod
whi h i mor ov r oft n much f te r.
On t he ot her hand t here a re many cases of t ru e un iver a l propos itions on
t h doma in N where a proof wit h t he V-in t ro- ru le will succ d but will be
qui te painful. (Tr y it ou t with t he above exampl e!) And ofte n, t he att empt
wit h th e V-int ro-rule fails altogether and induction th en is the only way. S e
also th e following sections.
Remark 19.3.3 In proofs by induct ion, it is not enough to prove the 'step
formula ' Vk[k E N : A(k) =>A(k + 1)]: we also need a proof of the 'basis
formula ' A(0). Take for example the following predicate: A(n) = n < O.
Then, it is not very difficult to prove that
Vk[k E N: k < 0 =>k + 1 < O],
becausefork < 0 we may substitute False here, from which follows that
k < 0 ⇒ k + 1 < 0 is equivalent to True. Prom this it follows also that the
whole formula is True.
If however the conclusion Vn [n E N : n < 0] is now drawn with an appeal
to 'induction', you immediately see that something wrong is going on here. ; .. 1
And indeed, this is not a good inductive proof, because the basis formula
A(0) has not been checked. This is where the situation fails: one cannot ,;...
In the induction rule that we gave above, the start point is 0: first A(0)
must be shown and thereafter A( i) ⇒ A( i + 1) for every i starting at 0.
It is actually possible to take another start point, for example the start
poin t 2. So we take the 'basis' to be a proof of A(2) and we take the 'step'
to be a proof of A(i) ⇒ A(i + 1) for all i 2 2, and so induction will deliver a
proof of A( n) for all n from start point 2. Intuitively this is quite obvious.
It is also possible to have a start point which is negative , for example -3.
Th e latter appears strange at first sight, because we are no longer dealing
IU
with natural numbers , but are now using the whole numbers. However, a
closer look reveals that there is nothing strange about this: the set of all
whole number s bigger than or equal to - 3 looks very much like N, only with
a shift over -3: the start number is - 3 and the successor function delivers in \,.
t his case s (- 3) = -2 , s(s( - 3)) = -1, s(s(s(-3))) = O, s(s(s(s(-3)))) = 1, I
and so on. Hence {n E Z in 2 -3} has the same structure as N. I(
In t his way we can extend the proof method of 'induction ' by applying
it to an arbitrary start point a E Z.
u.mvcTJVE DEFINITION OF SETS OF UMB RS 2 3
19-4·
. from start point a in Z:
induction
(k) A(a)
{ Mathematics: }
(1) a1 - ao = 6 - 5 = 1 = 2°
{ Definition of A(0) on (1): }
(2) A(0)
{ Assume: }
(3) var i; i EN
{ 1a h m ic u of h d fi ni i n t r a d
+ 2 n a1 1: }
(6) a;+1 =
a i+ 2 - (2ai+1 - ) - (2 - ) ==2(a 1 - a,)
{ From (6) u (5): }
(7)
a i+2 - a ·+ 1 = 2. 2i = 2i+l
{ D fini ion of A(i + 1) on (7): }
() A(i + 1)
{ =}-intro on (4) and (8): }
Note that the observation ai+l - ai ==2i in line number (5) only holds for
thei which is introduced in line number (3). It is a direct consequence of the
induction hypothesis A _(i) from line number (4). The proposition A(i + 1),
henceai+2 - a i+ l ==2i+l, must here be proven separately, making use of
A(i).
Remark 19.4.2 I nductive definitions are also called recur sive definitions.
This latter name is actually mo tly used in more general settings, namely
when the emphasis is not on the structure of the natural numbers - as above
- but on a more general structure with a st art value and one or more possible
successors. The latter is the case for t rees, where a node can in deed have
many branches. See P art I, Section 2.3, for an example of a recursive
definition. See also Section 19. 6.
In this chapter we shall always speak of inductive definitions, even in the
latter case.
strong induction:
The proof which must be filled where the dots occur, will usually go in
the stand ard way by the rules \I-intro and =>-intro, hence in the form as it
appears in t he following scheme.
{ Assume: }
(1) Yfil k; k E N j
{ Assume (induction hypothesis) :}
(2) Vi [j E N /\ j < k : A (j)]
(l - 2) A(k)
{ ⇒-intro on (2) and (l - 2): }
(l - l) Vj [j E N /\ j < k : A (j)) ⇒ A (k)
{ V-intro on (1) and (l - 1): }
(l) Vk [k E N : Vj [j E N /\ j < k : A (j) ) ⇒ A (k)]
{ Strong induction on (l) : }
(m) Vn[n EN: A(n)]
the following proof. (Comm nt about h r asoning in line (5) are writ en
below th proof.)
}
(1) Y§I k; k E N
propositions. Recall that t his set contained for example the propositions a
and ((a I\ b) ⇒ (,c)).
In genera l, an inductive definition of a set F of formulas looks as follows:
- There is a number of 'basis cases ', where concrete formulas are indicated
which certainly belong to F.
- Next there is a number of 'step cases' which say how 'new' formulas of
F can be built from one or more 'old' formulas of :F.
We give some examples of inductively defined sets.
(()()())((())())
Verifythat this is indeed a construction tree, comparablefor example
to
that of Section 2.4- It is only drawn differently: instead of the nodes
, we
have parentheses formulas (which are actually the labels of the nodes)
and
insteadof the branches we have here horizontal lines, followed by a numbe
r
(1 or 2). Moreover, the tree is standing 'upside down'. Compare this tree
with that of Section 2.4.
From the construction tree, we can read from top to bottom, how the
formulain question is built, starting with (a number of) c 's (this is allowe
d
by the Basis) and then applying step a number of times. (In the
last case
the1 and 2 next to the horizontal line, mean that we are dealing with either
case1 or with case 2.) But also, by reading from bottom to top, we can
see
howthe formula can be continuously 'parsed' into smaller pieces until
we
reachthe 'basis parts' (here always €).
Finally, a question for the connoisseur: does the above diagram give
the
onlypossibilityfor a construction tree of ( () () ()) ((()) ())?
=
• The final conclusion cp E 7t comes from the Basis: c E ?t.
Then we must have cp e.
Because c is the empty parentheses formula, with no single opening or
closing parenthesis, the property holds for this basis case: cp has as many
opening as closing parentheses (namely O).
• The final conclusion <p E 1t comes from Step. Then there are two
possi billties:
=
- case 1: <p E 1t by the rule: if h E ?t, then (h) E ?t.
Hence cp (h) for some h for which we knew already that h E 7-l.
According to the induction hypothesis h has as many opening as closing
parentheses {the formula his constructed 'earlier' than the formula cp (which
srRUCT RAL D CT IO
19,7•
305
. t his cas e) and h m a in p in of
(h) 1~me tha formulas w hi h ar ru ural ind ion ·
~
caD _~ properti ) , n r 1i r i alr d
d ire ·f here ar in h m n
Bot hen
l 1 .r
this al o h d 1or ( h ) : i mu
lo ing pa r n h
each, k 1 of a.ch.
be property. .
t - e,ase2: E rl b h rul : if hi E rl and h-iE 7t h n h h
The n ==h 1 h 2 and w knew alr d ha b th h E '1J d 1 2 c. 1-l.
h · d t · h · 1 ' L n h2 E rt
According to t . in uc ion ypoth si we n ha .· h 1 h man op
·
. clo ing par nthe ay m of each and a O h h . n-
1n" h f 2 man op nma
do ing par~n es say n ~ each. (Aga in: this induction hypo h .
. baracteri tic for structura l mduction bo t h h and h
c . . . . ' 1 2 are cons ru ed
earlier than cp (which m this case l h1h2) hence we can alread ume
the property for both h1 and h2.)
But then h1fvzhas m n opening parenthesi s and also m , n clo ing
parenheses, and so also <.phas t he property.
And so we are done. The (unique ) basis case was trivial, and in the
two step cases we saw how the property has-as-many-opening-as-closing-
parentheses was passed on from earlier constructed formulas to later con-
structed ones (from the if '-side of the inductive definition to the then '-side ).
ABa second example, we start with P , the set of all abstract propositions.
What we will prove is the following simple lemma: if c.pE P and if we remo ·e
fromcpeverything which is not a parenthesis , then we get a pure parentheses
formula,hence a formula in H. Taking for example the abstract proposition
((a VTrue ) ⇒ (-,(a I\ b) V b)), we get the parentheses formula (()(())) .
Weprove this in order get more acquainted with the method of structural
induction.
Wefirst introduce a useful notation: if ({J is an abstract proposition then
cpis the corresponding parentheses formula, so for example:
( (a V True ) ⇒ (-,(a I\ b) V b)) = (()(())).
The lemma that will be shown now is the following:
Everyr.pE P has the property that cpE H.
Once more, we give here a proof by structural induction again in compact
form:
• Basis:
- case 1: cp is a proposition variable (for example a)·
Then cp==c. E H.
- case 2: cp- True or False.
Then: cp= c E H.
-
306 CHAPTER 19. NUMBERS AND STRUCTURES
• Step:
=
- case 1: cp (-,P) and we know: (-,P) E P by the fact that PE P.
This means that the abstract proposition P was constructed 'earlier'.
=
Then from the induction hypothesis it follows that P E 'H, (for P the
=( =(
property already holds). It can be easily seen that (-,P) ( P) (the '-,' sign
is thrown out, because it is not a parenthesis), hence cp ,P) P ) E 1i
(the last comes from step, case 1, of the definition of 'H, which says: if PE 1-f,
then so is ( P ) E 1i).
- case 2a: cp =(PI\ Q) and (PI\ Q) E P by the fact that PEP an d
QEP.
From the induction hypothesis it now follows that both PE 1i and Q E 1-f..
Now we have (PI\ Q) _ ( P Q) (the '/\' disappears), hence it follows
=
that: cp (P I\ Q) =( P Q) E 1i.
This latter statement ( P Q ) E 1i follows from step, case 2 and case 1
of the definition of 1i as follows: because both P E 1i and Q E 1-f., then (by
case 2:) P Q E 1i, and hence (by case 1:) ( P Q) E Ji.
- cases 2b, 2c and 2d: are similar to case 2a.
It is useful to study the above proof in two ways: not only in detail (how
does all the 'technicality' fit together), but also the gener al lines. With
respect to this latter: look in particular at how the desired property
- is first studied for the basis cases (and apparently holds there),
- and then for the different steps, where the property is passed on (for
example from P and Q to (P I\Q)). Especially this last idea is important, it
is the fundamental principle for the concept of 'induction' as we have seen
in the earlier sections.
Inductive definitions are also given for sets or other objects than num
bers or formulas, for example for tree shaped mathematical objects or for
derivations (in logic). We will not go into this here.
The induction proofs which are applicable on such sets, can be based on
either normal or strong induction, but also equally well on the above called
structural induction. The knowledge that we have built in the previous sec
tions and in this one, will be enough to enable us to deliver and understand
inductive proofs even in more complex situations.
19.8 Cardinality
In this section we go back to the basis of the natural numbers, counting.
The process of counting gives actually a ranking order between the counted
objects: when you are counting a set ('one, two, three, ... ') you actually
say: 'this is the first, this is the second, this is the third, ... '. You only
CARDINAL ITY
19,8. 307
h t a certain object is the eighty-th ird 'f
kI1°"'t :ond is. Hence, the successor relatio~ 1 1you fir~t know what the
eight~-se_after the 82nd comes the 83rd. p ays an important role in
unt1ng, . d . . . 1
co different m uction prmcip es which we d 'b .
The d h' escn ed 10 th .
. are relate to t is successor relation T l . e previous
ctions, . f · 11s was very cl h
se d ribed induction as a ormalization of the . ear w en
e esc . . passmg on of a f
w truction. In fact, this passmg on always happ .h proo or
a cons 1 f . h ens wit respect t 0
sor for examp e rom i tot e successor i+ 1 in th , ,. a
succes ' {O 1 . 1} t h e normal induction
m the set , , · · · ,J - o t e successor 7· in st rong · d t· '
or fro . h' 11e set of the natural · numb er .m uc h'10n·
ooked at m t 1s way, t
L
a, sequence o 1 successors, wh ere the ordering 'first ths 1sfi not mg h
else
t I1an f h h' d , . . rst, t en the
second, therea ter t e t 1r , .. . 1s essential. To be precise , we b egm • with
. t he
,zero'th '. The natural numbers . following this conception , 1corm th e m1t1al
.. .
art, of the so-called ordinal numbers. The actual theory of th d'
P h ,. fi · , ( . e or ma 1
numbersadds t e m mte wn~ten as w, and pronounced: omega) to the
natural numbers, and then contmues counting thereafter, so altogether we
get: 1, 2, 3, ... , w, w + 1, w + 2, ... , 2w, 2w + 1, ....
Counting can also serve another goal, namely not to know how many
elementsa set has, but to know if two sets have as many (or the same
numberof) elements. In the latter case we first count the first set and then
the other. If the counting in both cases delivers the same number, then the
setsare of the same size; otherwise they are not.
But in order to know whether two sets have the same number of elements
(are'of the same size'), counting is not necessary! It is equally trustworthy
to state that there is a bijection between the sets. This has nothing to do
with counting, it is purely concerned with sets and functions (like those of
the earlier chapters).
Example 19.8.1
• Assume that in a ballroom there are two groups of people: A group
W which only consists of women and a group lvf which only consists
of men. In order to know if these groups are of the same size, it is
enoughto ask every woman to choose one man. If by do·ing so) we get
a new group which only consists of pairs then W and NI are of the
same size. If this is not the case (this means, if there is still at least
one single man who has not been asked) or there is still at leaSt one
single woman which could not find a man}, then the sets W and NI
arenot of the same size.
• Look at the sets {5 10 15 ... 155} and {10, 20, 30, .. ·, 310}- These
' ' ' ' . b · · t · between them,
sets are of the same size) because there is a iJeCion
namely with the function f where f (n) = 2n.
308 CHAPTER 19. NUMBERS AND STRUCTURES
19.9 Denulllerability
You can also apply the concept 'are equinumerous' (or 'have the same car-
dinality ') to infinite sets, but this gives unexpected re ult . And in this
case , it is no longer clear that 'have the ame cardinality i a formalization
of 'being-of-the-same-size'.
Look for example at N (all natural numbers, including 0) and N+ (all
positive natural numbers, hence without th 0). Are th e of the same
size'? You would probably say: no, be au N+ i a strict ubset of N, in
fact 0 E N but 0 r/.N+.
However, this is only on ide of the tory . B cause N really has the
same cardinality as N+, via the bij ction f where f (n) = n + l. Hence the
elements of N and N+ can be pair d together without any one remaining
unpaired. Everything you can do with N, you can al o, in principle, do with
N+, by just reading 1 as 0, and 2 a 1, and so on ... Induction, for example,
can be treated equally well with N+ a with N (that is induction from start
point 1 instead of 0).
pENVMERABILITY
9·
19- 309
ay t hink th at th e intui t iv concept 'b .
50,you rn asit is to infinit e et . Howev r ' ha . ing-of-t h a.m siz ' d
P ly . ,b · ' ving th , · o
00t aP proxirnat 10n to mg-of-t h -sam -si , am ardina.li , .
best ap z ' we annot d0 b Y LS
the . • . t er
st of t his sect ion , we will loo k furth . ·
the re ~1 Th . . . r into s ts h'
Jn d'nality as n . ie ar surpri sing cas h w ich have h
!Jle card.Jcuss whet her all infinite s t hav t i
s1t r I In the n xt tion
·ill is , ~1) 1e sa me ard · I'
wew 1 same size as 1"1 , or wh et h r t h r ar , . 1n 1t (h n
are •oft 1e v n bigge r infinit
which has t he sa m e ca rdin ality as N • . . ·
A set V • , 18 infinit ly
rable. A counting or a n enum eration of V .18 6.. . countable or
d nurne • f a 1Ject1on J f N
e B, this enumeratio n we ca n actually count or enum rom to
f. ( ) listing them: 0 rt f (0), 1 H J(l) 2 H . erate he elem nt
ofVt,~ ly V =={f (0), f(l) , f(2) , ... }.) ' f (2), m such a way that
even ,u .
Inorderto show that V 1s denumerable , we can
ive a bijection from N to V (and show that this ma • . .
-g ppmg 1s mdeed a
biject ion), . . .
or,becausebemg equmumerous 1s symmetric:
_givea bijection from V to N (and show that this mapping is a bijection),
Examples of denumerable sets include:
_N+. We already saw that N has the same cardinality as N+.
- {n E N I n is even}. The mapping f where f(n) = 2n is a bijection
fromN to this set of the even natural numbers.
- z. Also Z has the same power as N! A bijection f : N ~ z is for
example:
1n if n is even
f(n) = ½(~
{
+ 1) if n is odd
This bijection does the following:
n lo 1 2 3 4 5 6
f (n) 0 1 -1 2 -2 3 -3
- N2. We recall that N 2 consists of all pairs of natural numbers. This
et has the same power as N itself! In order to show this , we give2 an
enumeration. For this we first systematically write the elements of N as
te matrix: see'the top of the following page .
aninfini
Then, we will enumerate or list the elements of this matrix. Of course
wemust do this in a suitable way. If we start with the first row,
QN (0 0) 1 ( )
thenw ' ' H 0, 1), 2 rt (0 , 2 ' .. . ' . nor t he fourth...
rr,h e never reach the second row neither the th ird , h the
i es ' S0 · bot cases
rna~me.also holds if we start with the first column.. m
PPmg 18 not a bijection (because it is not a surjection).
0 CR.\PTER - -_IBER A. -n TR,. -RE
0. 0 0. )
__o (1. 3)
:.. 0 (:.. 3)
(3. 0) (3. 3)
{-:. 0) (-!.3)
- ..
So , t he listing of is as follows:
0 r-+ {O, 0) 2 ,-. (0, 1) 5 ,-. {O, 2) 9 r-+ (0, 3) 14 r-+ (0, 4)
6 ~ (3, 0) 11 ~ (3, 1)
.. ,. .
2
It will be obvious that by doing so, we get a bijection from N to N . (Can
you find a formula which describes this mapping?)
What about Q, the set of all rational numbers? Although you may
oENVMERABILITY
19,9• 311
t it• this set is also denumerable! In O d
noteipec. g. of Q+' the set of the positi~e rat·r erl o how th i we fir t
listin . . 1ona . w
give a . a matnx, Just as we have don with 2 . arrange h
• palsin ·
ra-tio
1 1 1
1 5
1
2 3 4
I
2 2 2
2 5
2 3 4
T 2
3 3 3
3
3
2 3 4 5
I
4 4 4 4
4 4 5
I 2 3
5 5 5 5
5 4 5
I 2 3
1 1 1 1 1
I 2 3 4 5
2 2
I X 3 X 2
5
3 3 3
X 3
I 2 4 5
4
T X 4
3 X 4
5
5 5 5 5
I 2 3 X
4
· ay as we did for
2 ext,Welist the elements of this matrix, in the same w
' onlynow we will ignore the crosses:
312 CHAPTER 19. NUMBERS AND STRUCTURES
1 ~ ~1 X 7 ~ ~ X 15 1---+ ~5
3
19.10 Uncountability
An example of an infinite, but not denumerable set is {O,1F\ the set of all
mappings from N to {O,1}.
{ Assume: }
The set of all infinite O-1-sequences is denumerable.
Then there is a listing of this set, say:
0 ~ ((Jo, 1 r-, 'Pl, 2 ~ 'P2, 3 r-, r..p3,• , •
We write these sequences as follows:
'Po - aoo, ao1, ao2, ao3,
'Pl = a10, a11, a12, a13,
'P2 - a20, a21, a22, a23,
'P3 = a30, a31, a32, a33,
....
with every aij being either 0, or 1.
Looknow at the 'diagonal sequence' VJ==
aoo, au, a22, a33, ... .
314
s on he diagonal· of he a 1 ·-
The cle, er point of hi proof is the focu
then change e ery po "tion of h ·
ma rix ( he infinite equence I ) and
his we know hat it is definitel ·
diagonal ( his gives h equence x) . For
, ;.
new· with respect to all the equences
n or the diagonal argumen o
This proof me bod i called diagonal· atio
and lo~cian Georo- antor2. \ ·e
Cant or . after the German mathematician
will once a rrain come across this met
bod belo'\"\.
•
fir P (. ). must also b 11
J
u coUNTABILITY
19,10,
315
similar diagonal argument as abo c
With a · fall fu . ve 1or {O l} N
N the set o nct1ons from N to N . we can show als
that N ' . ' is nond enumerable o
t about JR? Earlier, we have seen that N '7l •
Wha also h ave th e same cardmality).. ' IL, and Q are 11d
hence Is this a enumerable
(and JI real numbers? also the case for JR the
. d . '
set of a,,,,8wer 1s: no. In or er to show this w
fhe ""' W . , e use again a £ f
1arcrument. e start with J = (0 ' 1) ' th e int . orm o Cantor 's
erval of all real numb
diagona . o d 1
tween O an · . ers
beA ume that I is nondenumerable. Then we I'
/: it is possible to write every number _ca~ 1st th e elements of I.
~ ' for example m as an infinite decimal
fract10n,
L:::0, 7500000· · · ,
0, 31415926535....
1L:::::
10
Hence, a possible listing of I looks in decimal notat· 10n as £o11
ows:
ro - 0, doo do1 do2 do3
withevery dij a 'decimal', hence a digit from the set {O,1, 2, ... , 9} of pos-
sibledecimals.
Looknow again at the diagonal, and more precisely look at the diagonal
whichstarts after the O and the comma. From this, we can make the real
numbers with
s = 0, doo d11 d22 d33 ....
Replace now all the decimals dii of s by other decimals, for example by
addingone to every decimal except 9, and replacing all 9s by Os. In this
waywe get a new real number, say
.t :::: 0, 8081 82 63 ... '
withthe property that Vi [i E N : dii -/ bi]• . .
~om this it follows that no single rj can be equal to ~' m fact, e J- th
th
decimalof rj (namely d .. ) is different from the j-th decimal oft (namely
8i), Hence t is a real n:~ber between O and 1, which is clearly not in th e
abovelisting ro, r1' r2, .... But that was a listing of the full interval (0, 1)!
Contradiction. .
na~onclusion: (0, 1) is not denumerable, and because the interval (0, 1) is
rally also not finite it must be nondenumerable.
'
r
316 CHAP TER 19. NUM BERS AlVD STR CT REs
The class of all denumerable sets , hence the sets which have t he same
cardinality as ~ , is represented with No (pronounced: aleph-zero). The class
of the sets which have the same cardinality as JR is called Ni (aleph-one)
and so we can go on. Hence:
- No consists of N, Z, (Q and other examples like N+ {n E Nin is even}
N 2 , 71}, Z 8 , Q2,(Q X z,.... '
19.11. EXERCISES 317
– ℵ1 consists of R, P(N) and other examples like {0, 1}N , NN , ⟨0, 1⟩, [0, 1],
R2 , P(N2 ), . . . .
– ℵ2 consists of P(R), P(P(N)), . . . .
– P(P(P(N))) is in ℵ3 , and so on.
(Some proofs of the above facts are very complicated and are beyond the
scope of this book.)
19.11 Exercises
19.1 Define on the structure ⟨N, 0, s⟩ the function v by
v(0) := 0,
v(s(i)) := i (i ∈ N) .
19.2 (a) Let s, v ∈ R. The arithmetic sequence with start value s and
common difference v is the sequence a0 , a1 , a2 , . . .where
ai = s + i · v (i ∈ N).
!n
Prove that: ∀n [n ∈ N : k=0 ak = (n + 1)s + 12 n(n + 1)v].
(b) Let s, r ∈ R where r ̸= 1. The geometric sequence with start
value s and common ratio r is the sequence a0 , a1 , a2 , . . . where
ai = s · ri (i ∈ N).
!n n+1
Prove that: ∀n [n ∈ N : k=0 ak = s 1−r
1−r ].
(a) ∀n [n ∈ N ∧ n ≥ 1 : 1 + 3 + . . . + (2n − 1) = n2 ].
!
(b) ∀n [n ∈ N ∧ n ≥ 1 : n−1
k=0 k = 3 n − 2 n + 6 n].
2 1 3 1 2 1
!n−1 3
(c) ∀n [n ∈ N ∧ n > 0 : k=0 k = 14 n2 (n − 1)2 ].
19.12 Every element n belonging to the structure ⟨N, 0, s⟩, has the following
form: s(s(. . . (0) . . .)), where the number of s’s is bigger than or equal
to 0.
In this structure, we can inductively define addition as follows:
m + 0 := m,
m + s(n) := s(n + m).
• Basis:
– Every l ∈ L is element of M.
• Step:
– case 1: if ϕ1 ∈ M and ϕ2 ∈ M, then ϕ1 + ϕ2 ∈ M.
– case 2: if ϕ1 ∈ M and ϕ2 ∈ M, then ϕ1 − ϕ2 ∈ M.
(a) Is there for every formula in M only one construction tree pos-
sible?
(b) Prove by structural induction that in every formula of M the
number of plus and minus signs are together one less than the
number of letters in the formula.
19.16 (a) Give an enumeration (i.e., a listing) of the odd whole numbers.
(b) Prove that every class of the equivalence relation ≡6 is denumer-
able.
(c) Prove that N × {0, 1} is denumerable.
19.17 (a) Prove that, if V and W are denumerable, then also V × W is
denumerable.
19.11. EXERCISES 321
ordered sets
20.l Quasi-ordering
In this chapter we are concerned with the concept of 'ordering', which is
importantin many areas of mathematics and computer science (and also
outsidethese!). If we say that a set is ordered, then we mean that there is a
relationon this set which deals with a 'relative order' of the elements. This
canbe: 'an element appears before (precedes) another', but also 'an element
appearsafter (succeeds) another' (an order can go either way!).
An 'ordering' is hence a relation (see Chapter 17) with special proper-
ties.What these properties are exactly, depends on the kind of ordering in
question.In this section, we will look at the so-called quasi-ordering,which
isa relation which has some of the essential properties of ordering, but not
all.
. In the other sections of this chapter, we discuss different kinds of ord_er-
mgS.It appears that also for sets of numbers like N, Q and JR,0rd e~mg
relationscan be given. (And so there is a connection with the previous
chapter).Think for example, of the relation 'smaller than', w?ich g'.ves an
o_rderingon N: if x < y then x precedes y; for the 'bigger than relat10n the
situationis otherwise: if x > y then x succeeds Y·
As t • bl to the structures of
Ch e with an ordering is a structure, compara e £
th apter 19 (see for example Section 19.2). In this way the set N orms :1•th
. e ordering relation 'smaller than' the structure (N, <). Such a struc ure
isalso 11 '
ca ed an ordered set.
323
Llf
324 CHAPTER 20. ORDERED SETS
The different kinds of (quasi- )orderings which exist fall under two ma·
group : the reflexive and the irreflexive ones. A structure (A, S) in
latter group has the following property:
t:
Vx[x E A: ,(x Sx) J,
ca ll d irreflexivity, which can be considered as a kind of absolute opposite
of reflexivity ( e Section 17.3 and here below). In fact in case of a reflexive
R w always have xRx, and in case of an irreflexive S we never have xSx.
For an irr eflexive relation S we can only have aSb if a and b are different
either a 'precedes' b, or a 'succeeds' b. Irr eflexiv ity is sure ly a natural
property of an ordering: if you say that Anna is longer than Bert, then you
explicitly mean that she cannot be as long; if c is smaller than d, t hen c is
not equal to d. In the ordered set (N, <), for example, the ordering < is
irreflexive (no natural number is smaller than itself).
20.2 Orderings
In Section 17.4 we saw that an equivalence relation is a relation that is
reflexive,symmetric and transitive. If a quasi-ordering is hence also sym-
metric,then it is an equivalence relation. But such an equivalence relation
isnot what we call an ordering, because of its property 'symmetry': if x
precedesy, and if y in turn precedes x, then something strange is happening
(asurningthat x i= y): we get into a circle, and the concept 'order' does
notmake much sense any more.
And so for a reflexive relation R to be a real ordering, it is undesirable
thatit be symmetric. Hence not always: if xRy then yRx. Even stronger,
thesituation that at the same time both xRy and yRx can hold, must
~evertake place (unless of course x is the same as Y)• We express th is
10the following property, which is called antisymmetry (~ kind ~f absolute
oppositeof symmetry). In the case of a reflexive relation this looks as
follows:
Yx,y[x,yEA: (xRy /\ yRx) ⇒ x = y]. .
Now h ·
. we ave the first important kind of ordermg, w ic
h' h is called reflexive
Partial d . . (S t·mes one a 1so 1eave8
outth 0 ~ ering, or in short: reflexive ordering. o_me1
e word 'reflexive' and simply speaks of ordering.)
326 CHAPTER 20. ORDERED SETS
Example 20.2.1
ings. In
• The structures (N, ~), (Z, ~) and (IR,~) are reflexive order
fact, we 'always' have: x ~ x (reflexivity), (x ::; y I\ y ::; x) =>
x ==y
(antisymmetry) and (x ~ y I\ y ~ z) =>x::; z (transitivity).
'~ ' by
The above structures remain reflexive orderings if we replace
'~'.
• Structures like (IR,<) and (IR,>) are irreflexive orderings.
(4) xix
{ \!'-intro: }
(5) Vx[xEN+ : xix]
- Antisymmetry:
{ Assume: }
(1) Yfil:X,y; x,y EN+/
{ Assume: }
(2) xly I\ ylx /
{ /\-elim on (2): }
(3) xly
{ Definition of I on (3): }
(4) :lk[k EN+ : k • x == y], say k
{ /\-elim on (2): }
(5)
Ylx
{ Definition of I on (5): }
(6)
:li[lEN+:z-y==x], sayl
{ Mathematics on (4) and ( 6): }
(7)
l-k•x-z - ·Y=x
328 CHAPTER 20. ORD ERED SETS
Not e that we used in the lines numbered (4) and (6), a short form of
:l* -elimination , via the word 'say ' , instead of with a sentence like 'pick a
k E ti[+ with k • x = y '.
Example 20.2.2
(These are not real proofs, we have only summari zed what the thr,
proofs should actually show. It should however be clear how the cor
plete proofs can be constructed, where proof techniques from Part
are used: flags, introduction- and elimination rules.)
• Let M be the set of all people (both the living and the dead) and S t
relation 'is-ancestor-of' , hence m 1 Sm 2 if m 1 is an ancestor of r,
Then (M, S) is an irreflexive ordering. Check this.
(T1iis a o ction 17 6 )
fy f or example that the refi xive ordering (Z < ) · ·
~fler\veordering (7l, <) , and vice versa. ' - corr, spond to th
i~ eX11
Example 20.3.1
• In (P(N), ~ ) the sets {0, 2, 3} and {0, 3} are comparable, because ob-
viously {0, 3} ~ {0, 2, 3}.
Also {0, 2, 3} is comparable with itself and with for example {0, 1, 2, 3}.
But {0, 2, 3} is incomparable with {0, 1, 3}.
The relations < and ~ on JR,see the last example, bring with them the
nice property that every two elements are comparable. In general a relation
with this property is called linear. Hence R on A is linear if:
'ix ,y[x, y EA: xRy V yRx V x = y].
(If R is reflexive, we can replace this by
'ix ,y[x, y EA: xRy V yRx].)
If the relation R on A is both linear and an ordering, then it is called a
linear ordering (other names are: a total ordering or a chain).
Hence the structure (A, R) is a reflexive linear ordering if R is (1) reflexive
and (2) antisymmetric and (3) transitive and (4) linear.
There are also irreflexive linear orderings, which are (1) irreflexive and
(2) strictly antisymmetric and (3) transitive and (4) linear.
In a diagram these relations can often be presented by a straight line
(hence the name 'linear'). Below, in Figure 20.1, we respectively give the
diagrams of the reflexive linear orderings (N, :::;), (Z, :::;) and (JR,:::;).(The
same diagrams correspond to the irreflexive linear orderings (N, <), (Z, <)
and (IR,<).)
C
ol
3'
2
1 1
0 0
- 1 - 1
-2
- 3,
I
I
- (5
<
- ( ) (5 8) becau e 5 ~ 5 and 5 = 5 ⇒ 8 ~ 8.
5
-
t hold that, for example, (5, 8) ::; (4, 12), (5, 8) ~ (4, 8) or
It do no
(5 ) _ 5 7).
po ible
T hen we have: (x , y)S3(x' , y' ), for t hl t here are two
reasons: (la) xS 1x' , or (lb) x == x' I\ yS2y'.
po ible
We also have: (x' , y')S 3(x", y") , for this there are two
reasons: (2a) x' S 1x", or (2b) x' == x I\ y' S2y".
11
The proof written above already starts to look like a proof from a math-
ematics book!
In the same vein, one may prove that the lexicographic ordering con-
structed from two reflexive orderings , is again reflexive. And moreover,
that the lexicographic ordering built from two linear orderings, is linear,
again.
th
refl:ox~ei~g completely different happens in the structure (IR.,<), the ir-
1ve(1lllea ) d .
'srnaUeth r or ermg structure of the real numbers with the relation
r an'· th
Which ar b' · ere, every number has many successors (all the numbers
Cessor. I~ /gger than this number), but no single number has a direct sue-
nothingcana~t, _ass ume that y is a direct successor of x. Then x < y and
caseWe alwa e ~n between x and y. But this is impossible, because in this
x <( ~ ys ave for example that
2 <: Y,
and~.
2 is also in JR.
C
Next to the 'direct succe sor' we obviously have the concept direct pre-
decessor'. Some examples:
Example 20.5.1
• In the irreflexive structure (N, <) ( and hence also in the refiexive
structure (N ~)) every element n has a direct predecessor (namely
n - l), except the number 0.
• In (N+, \ ) every element has at least one direct predecessor, except
the number l. For example, 3 and 2 are both direct predecessors of 6,
and l is a direct predecessor of 7.
• No single element of (JR,<) (resp. (JR,~)) has a direct predecessor.
• In the lexicographic ordering on N x N, described in the previous sec-
tion, every element (k, l) has a direct successor, namely (k, l + 1). But
not every element has a direct predecessor. For (0, 0) this is obvious,
because (0, 0) is the 'smallest' element, which has no single prede-
cessor. But also (1, 0), and (2, 0), and so on, don't have any direct
predecessors (whereas they each have an infinite number of 'normal'
predecessors)!
Hence, for some orderings, the concept 'direct successor' (or 'direct pre-
decessor') is useful, for others this is not the case. If we can speak about
direct successors (or direct predecessors), then the ordering structure can
often be given with a diagram, a so-called Hasse diagram. 1 Hasse diagrams
are especially informative for finite sets.
We give a couple of examples in order to illustrate what a Hasse diagram
looks like and how convenient such a diagram can be in order to get an
'image' of the structure.
First, we draw a diagram of the set {1, 2, ... , 10} with the divisibility
ordering' I '. Cf. Figure 20.2.
We see there how every labeled node is related in upward direction (via
a branch) to the nodes of the direct successors of that label.
For example: the node with label 2 is related in upward direction, by
three branches, to the nodes with labels 4, 6 and 10. These last three are
precisely the direct successors of 2 inside { 1, 2, ... , 1O}.
Helmut Hasse (1898 - 1979) was a known German number theorist. The diagrams
1
called after him, appear in his book Vorlesungen uber Klassenkorpertheorie, Physica-
Verlag, Universitat Marburg, 1967.
-- -&-------------~
337
JIASSE DIAGRAMS
20,5,
8
g 6
3 7
... , 10}, I )
Figure 20.2: A Hasse diagram for ( {1, 2,
{0,1,2}
{1,2}
{O} {2}
·I
(/J
1, 2}), ~)
Figure 20.3: A Hasse diagram for (P( {O,
I
C
It 1.6 not difficult to, tl .at such a max imum , 1'f 1•t x1.sts 1.s also ·
. is !Jene at most on max imum . ." r this w . ·, uniqu .
f he1e·te in a compa t form (s e ect i n 1 2 ,£0 hg1v _al sh rt pr of, which
we wn . . · r ow t 1 on pt , t
, is fonnahzed, wlu ch w pply h -re in the last J'1n ·f h a most
one . . e o. t proof b low).
Let (A' R) be. a.refl xiv) ord rmg with A' c - A · (A proo f torc
an irr. fi ·
orderinggoes suml arly. xiv
{ Assume: }
yg m1,m2; m1,m2 E A' ·•
{ Assume: }
1n 1 is a max imum of A' and so is m 2
{ Definition of 'maximum', twice: }
v'x[x E A' : xRm1] and Vx[x EA': xRm 2]
{ \7'-elim, twice, where x = m2 resp. x = m 1: }
m2Rm1 and m1Rm2
{ By antisymmetry of R: }
m1 = m2
{ =>-intro, V-intro: }
Vm1 ,m2 [m1,m2 EA':
(m1 is a maximum of A' and so is m2) =} m1 = m2]
• The reflexive ordering (P( {O,1 2}), ~) of Figure 20.3 has both a top:
{O 1, 2} and a bottom: 0.
If we take A ' = [O,1], the closed interval of all real numbers between o
and l (including O and 1), then this gives the same set of upper bounds
and the same set of lower bounds! This also holds if we we take A'
to be the two elements set {0, 1}, or the set [0, ¼lU [¾,1] or the set
{1, ½, ½,¼,.. .}. If on the other hand we take A' = N, then we will
have the same set of lower bounds, but an empty set of upper bounds.
Remark 20. 7.4 It is a bit tricky to see that a non empty set of upper
bounds does not always have a minimum. For a counterexample, look at the
sets V = {-1, -½,-½,-¼,...} and W = {l, ½,½,¼,... }. Consider now V
as a subset of VU W, both with the usual ordering ~. Then every element of
W is an upper bound of V, or, said differently: the set of all upper bounds
of V which come from V U W, is precisely this W. But obviously W does
not have any minimum, hence V has no least upper bound in VU W.
In order to see how proofs of upper and lower bounds go, we show the
following:
Lemma 20. 7.5 Let (A, R) be a reflexive ordering and A' be a non-empty
subset of A. Then for every lower bound a of A' and for every upper bound
b of A' we have that aRb.
DERING AND WELL-FOUNDEDNESS 343
weiiroR
8·
20-
proof:
{ j\ssurne: }
b ab EA
vara, ; '
:,;--
{ j\ssurne:_:
..:.}- ----::--:-:----:-;-:----- --;----;--:--: ~
1 r bound__ _ of_ A'__and________
a is a ~o:_:w~e::_: b is an upper bound__ of A' __,
{ Definition of 'lower bound' resp. 'upper bound ' : }
(l): Vx[x E A' : aRx] and (2): \7'x [x E A' : xRb ].
{ Given: }
A' is not empty.
{ Property of 0, and Remark 16.7.1: }
:ly[YE A']
{ :l*-elim: }
Pick a y with y EA ' .
{ V-elim, twice, on (1) and (2): }
aRy and yRb
{ By transitivity of R: }
aRb
{ =>-intro, Y-intro: }
Va,b[a,b E A :
(a is a lower bound of A' and b is an upper bound of A') ::::}aRb ]
Hence
bou d ' indeed as we expected: every lower bound 1s. 'under' every upper
enon h(au<lthe whole A' is 'in between'). Note that in this proof it was
tra~t ~o use an 'ar bitrary' y of the non-empty A' in order to derive by
good. vity th at aRb. Which y this is does not matter: every y in A' is
20,8
1 Well-ordering and well-foundedness
nthis
het section we ·11 . . ' .
Ps us to d 1. wi see that there is a general form of 'mduction which
rtg ensue 1ver p roois
0rderi c c1or irreflexive ordered sets, provide d t h at th e
res that th
ere always is a kind of 'basis'.
344 CHAPTER 20. ORDERED SETS
·I
induction (Section 19.5, see the case k = 0): without the Basis you cannot
take off.
(See also the Remark in Section 19.3, where we give an example of an
inductive proof which does not work, because the basis fails.)
We only consider irreflexive orderings in the present section, and start
with linear ones.
How can we ensure for an irreflexive linear ordering (A, S) that a kind of
basis exists, in order to be able to use 'induction'?
This amounts to the following minimum property:
· (
(C:
345
ORDERING AND WELL-FOUNDEDNESS
~
WEJLL
20,B· . h. d . ~T •
. fiexive lexzcograp zc 0'0 ering on 1'11 x N is a well-ordering.
. 20 . 5 that in . these orderings there are ele-
Ji/sothe zrreen in Section
, a, vrehave se ) h · h h
'k (l 0), (2 , 0 , ... - w zc ave pr edecesso rs, but no dir ect
rn,entsti \s ('such element s do not exist in N and {n E Z In 2: a}).
t· d h· h ·
predecesso too induction can be app ie , w zc is a consequence of the
Still,here
following.
. an be applied on eve ry well-ordering (A, S). In such a case,
· w h'1ch 1s · · of what
In duction f transfinite in· duc tion,
c · a d'irect generalization
0nespeaksto ng induction in Section 19.5. It can be formulated as follow s.
)led s ro
weca p b a predicate on A in the well-ordering (A, S). Then the principle
Let e .
finite induction says:
oftrans . .
if'fk[k EA: Vj[J EA I\ JSk: P(J)] ⇒ P(k)],
then'in[nEA: P(n)].
N te here that indeed we have 'the same' formulas as in Section 19.5,
bu~:ith N generalized to the arbitrary set A, and < to the well-ordered
relation S on A.
The induction hypothesis is hence in this case: Vj[j E A I\ jSk : P(j)].
So:for all 'S-predecessors' of k the predicate P already holds.
Remark 20.8.3 The word 'transfinite' points to the fact that with this form
ofinductionwe can go 'past finiteness '. Look for example at the irreflexive
phic ordering (N x N, <), where the ordering can be described as
lexicogra
follows(see Section 20. 3):
(0,0) < (0, 1) < (0, 2) < ... < (1, 0) < (1, 1) < (1, 2) < ... < (2, 0) <
(2,1)< (2,2) < ... < ....
Thislexicographicordering is a well-ordering, hence the being-true of a
predicateQ on N x N for all (n, m) E N x N can be proven with transfinite
induction.The 'step' of the induction is now not always 'finite ', in order
forexampleto be able to reach (1, 0), we must jump over an 'infinite hole'.
e constr t·
c:S uc ion tree as drawn in that section):
.
()s (())s (())()s ((())())s (()()())((())())
346 CHAPTER 20. ORDERED SETS
Now, the general case that we mentioned is the following: the principle
of transfinite induction holds for every irreflexive ordering ⟨A, S⟩ which has
the property that it is well-founded ; where ‘well-foundedness’ means:
every sequence . . . , x2 , x1 , x0 of elements of A, where xn+1 Sxn for all
n ∈ N, must be finite.
Hence the following must hold: if we start with an arbitrary x0 ∈ A,
and then we look for an x1 ∈ A where x1 Sx0 , and then again an x2 where
x2 Sx1 , and so on, then we reach a certain moment where we cannot go
further. (Compare with N and the relation <: if we start with an arbitrary
n0 ∈ N, and then take an n1 where n1 < n0 , and then an n2 where n2 < n1 ,
and so on, then definitely this must stop after some time.)
The set H of parentheses formulas with the ordering just described is well-
founded, as can be checked easily. Intuitively speaking, well-foundedness
ensures that with recursion (hence ‘going backwards’) we are always halted
by a ‘Basis’, and this is why induction becomes possible. Structures like
⟨Z, <⟩, where the basis is missing, are obviously not suitable for this.
This principle of transfinite induction for well-founded orderings, as de-
scribed here, has a lot to do with the structural induction that we have
described in Section 19.7. We leave out the full details and assume that the
above is sufficient to get the idea.
20.9 Exercises
20.1 Consider on N+ the relation R where xRy if the number of divisors
of x is smaller than or equal to the number of divisors of y.
(a) Show that 1Rx for every x ∈ N+ , and that for every prime num-
ber p and every x ̸= 1 we have that pRx.
(b) Show that ⟨N+ , R⟩ is a quasi-ordering.
(c) Is ⟨N+ , R⟩ also a reflexive ordering?
20.10 Σ∗ is the set of all finite sequences of zeros and/or ones, including the
empty sequence ε. We order Σ∗ by:
u ≤ v if u is a prefix of v.
(A prefix is an unbroken starting piece of length ≥ 0, example: ε, 0,
01, 010 and 0100 are all prefixes of 0100.)
(a) Give Hasse diagrams for this structure, one for the case the or-
dering is lexicographic, and another for the case that the ordering
is Cartesian (see the above Exercise 20.3).
(b) Say in both cases what the maximal and minimal elements are,
and what the maximum and minimum are (if they exist).
20.13 Let ⟨A, R1 ⟩ and ⟨B, R2 ⟩ be reflexive orderings and R3 be the reflexive
lexicographic ordering on A × B.
Prove that: if (x, y) is a maximal element of ⟨A × B, R3 ⟩, then x is a
maximal element of ⟨A, R1 ⟩ and y is a maximal element of ⟨B, R2 ⟩.
20.14 Determine in ⟨R, ≤⟩ the greatest lower bound and the least upper
bound (if they exist) of the following subsets:
20.15 (a) Let ⟨A, R⟩ be a reflexive ordering. Prove that every subset A′ of
A can only have at most one least upper bound.
(b) Give a general description of the least upper bound of a two-
element set {k, l} in ⟨N+ , | ⟩.
(c) The same question for the least upper bound of a two-element
set {A′ , A′′ } in the reflexive ordering ⟨P(A), ⊆⟩.
(d) What is the least upper bound of the following set (consisting of
three elements): {(x1 , . . . , xn ), (x′1 , . . . , x′n ), (x′′1 , . . . , x′′n )}, in the
reflexive ordering ⟨{0, 1}n, ≤⟩ of Exercise 20.7?
350 CHAPTER 20. ORDERED SETS