Читать книгу: «A course of plane geometry»

2
Preliminaries

The goal of this chapter is to present the main proof methods used in mathematics, and the basic elements of the elementary theory of sets, in order to establish the necessary theoretical basis for the axiomatic development of geometry, both euclidean and noneuclidean. We will explain the basic methods for proving conditional claims, such as the direct method, the cases method, the contraposition method, and the contradiction method. Other important methods, such as mathematical induction, will also be studied. In the case of the elementary theory of sets, we will establish the most basic results concerning equivalence relations and the equivalence classes determined by them. For a deeper presentation of these matters, we advice the reader to consult texts such as [3],[5],[6]. As a consequence, in the following sections we will freely state and use some results without providing a rigorous derivation. Nevertheless, the definitions will be presented in a coherent way, and with the standard notation used in the corresponding areas of knowledge.

2.1 Proof methods

The following is an informal but very practical presentation of the main strategies used for proving mathematical theorems.

2.1.1 Methods for proving conditional statements

As most theorems in mathematics are of conditional type or implications, i.e., have the form “claim 1 implies claim 2” or what amounts to the same “If claim 1, then claim 2”, we will start by making clear the precise meaning of an implication, and then we will present the main strategies used in proving statements of this type.

Meaning of the logical implication

The saying “Dog that barks does not bite” has conditional form, because we can put it in the form “If p is a dog that barks, then p is a dog which does not bite”. In our daily use and understanding of natural language, we tend to infer from this saying that if a dog does not bark, then the dog bites. In the strict logical sense, which is the sense adopted in mathematics, the saying does not say anything in case claim 1 does not hold. In that case, claim 2 may or may not hold. Hence, the saying does not tell us anything about dogs which do not bark. There might be nonbarking dogs which bite, and nonbarking dogs which do not bite. The only thing claimed by the saying is that no dog barks and bites.

Here is another example. If a father tells his son, “If you pass the grade, I will give you a bicycle”, and the son does not pass the grade, but the father gives the bicycle to him anyway, many of us would consider that the father did not keep his promise. In strict logical sense, the father kept his promise, because the implication “If you pass the grade, I will give you a bicycle” does not say what action should the father take in case the son does not pass the grade. It only says the action the father must take in case the son passes the grade.

In the context of the natural numbers = {0, 1, 2, . . .}, the claim

“If n is odd, then n² is odd”

is an example of a claim of conditional type. In the same context, the claim

“The sum of any two consecutive numbers is odd”

is, even though it does not seem at first, a claim of conditional type, because it can be stated equivalently as,

“If a, b are consecutive numbers, then a + b is odd”.

There is an important difference between the example of the father that makes a promise to the son, and the other three examples of conditional claims we have given. The latter can be rephrased putting before them a universal quantification. In this way, the claim “If p is a dog that barks, then p is a dog which does not bite” means the same as the claim “For all dog p, if p barks, then p does not bite”. Likewise, the claim “If n is odd, then n² is odd” is the same as claiming “For all n, if n is odd, then n² is odd”. And the claim, “If a, b are consecutive, then a + b is odd” is the same as saying “For all a, b, if a, b are consecutive, then a +b is odd”. This kind of rephrasing is not possible with the father’s promise.

Let us consider now an issue which will be very important later: the negation of a claim of conditional type. The distinction made in the previous paragraph is crucial in order to correctly negate conditional type claims. The negation of the father’s promise would be “The son passes the grade and the father does not give the bike to him”. The negation of the claim “For all dog p, if p barks, then p does not bite” is “There is at least one dog p, such that p barks and p bites” or “There exists a dog p, such that p barks and p bites”. Notice the introduction of the phrase “There is at least one dog p, such that” or “There exists a dog p, such that”. Likewise, the negation of “For all natural n, if n is odd, then n² is odd” is “There exists a natural n, such that n is odd and n² is not odd”; and the negation of “For all natural numbers a, b, if a, b are consecutive, then a +b is odd” is “There exists natural numbers a, b, such that a, b are consecutive and a + b is not odd”.

In order to prove this type of claims, there exist four main strategies: the direct method, the method by cases, the contraposition method, and the contradiction method.

Direct method

Let us assume that we have a claim of the form “claim 1 implies claim 2”. The direct method consists in assuming that claim 1 is true, and, using claim 1, seeing that claim 2 has to be true, by the means of logical deduction. In the course of the argument claim 1 can be used as many times as necessary as well as any other fact which is an axiom or that has been proved previously.

Let us prove, using this method, the claim

“If a, b are consecutive natural numbers, then a + b is odd”.

In this case claim 1 is “a, b are consecutive natural numbers” and claim 2 is “a + b is odd”.

Before starting the proof, let us write in a more precise way claims 1 and 2. Claim 1 can be stated more precisely as “a, b are natural numbers such that a = b + 1 or b = a + 1”; and claim 2 can be stated as “there exists a natural number n such that a +b = 2n + 1”. Writing claims 1 and 2 in this way, helps a lot in creating a correct proof.

Let us now prove, by the direct method, that

“If a, b are natural numbers such that a =b + 1 or b = a + 1, then there exists a natural n such that a + b = 2n + 1”.

We begin by writing:

“Let a, b be natural numbers such that a = b + 1 or b = a + 1”.

Then we write:

“There are two possibilities: a = b + 1 or b = a + 1”.

And we go on writing:

“Let us assume that a = b+1. In this case a+b = (b+1)+b = 2b+1. Then there exists a natural number n (n = b), such that a + b = 2n + 1.

Next, we consider the other case. We write:

“Let us now assume that b = a + 1. In this case a + b = a + (a + 1) = 2a + 1. Then there exists a natural number n (n = a), such that a + b = 2n + 1”.

and we finish the proof by writing:

“Since in both cases we arrived to the conclusion that there exists a natural number n, such that a + b = 2n + 1, we have that in every case there exists a natural number n such that a + b = 2n + 1.”

Method of proof by cases

This method can be considered as a special case of the direct method. It is used when we want to prove an implication “P implies Q”, in which the claim P is equivalent to a disjunction of several claims, i.e., when P is equivalent to a claim of the form “P₁ or P₂ or . . . or Pn”. The method is based on the equivalence between the claim “P implies Q” and the claim “P₁ implies Q, and P₂ implies Q, and . . ., and Pn implies Q”. In the example we gave when explaining the direct method, we used, without noticing it, the cases method, since claim 1 of that example was “a, b are consecutive natural numbers” which is equivalent to “a, b are natural numbers such that a = b+1 or b = a+1”, which in turn is equivalent to “a, b are natural numbers such that a = b+1, or, a, b are natural numbers such that b = a +1”. So what we did was to prove, separately, the two implications “If a, b are natural numbers such that a = b + 1, then a + b is odd” and “If a, b are natural numbers such that b = a + 1, then a + b is odd”.

Method of contraposition

This method is based on the observation that a claim of the form “claim 1 implies claim 2”, is logically equivalent to the claim “no(claim 2) implies no(claim 1)”. For example, to say that “if p is a dog that barks, then p is a dog which does not bite”, is the same as saying that “if p is a dog that bites, then p is a dog which does not bark”. Or to say “If you pass the grade, then I will give you a bicycle” is the same as saying “If I do not give you a bicycle, then you did not pass the grade”.

We say that “no(claim 2) implies no(claim 1)” is the contrapositive of “claim 1 implies claim 2”. An implication and its contrapositive say the same but in a different way.

Then, the method of contraposition consists in taking an implication we want to prove, and proving its contrapositive by, say, the direct method.

The constrapositive of

“If a, b are consecutive natural numbers, then a + b is odd”

is

“If a, b are natural numbers such that a + b not odd, then a, b are not consecutive”,

which put more precisely, is

“If a, b are natural numbers such that there is no natural n with a + b = 2n + 1, then a ≠ b + 1 and b ≠ a + 1”.

Let us prove the last claim.

We begin by assuming that a, b are natural numbers such that there is no natural number n for which a + b = 2n + 1. So, we write:

“Let a, b be natural numbers such that there is no natural number n for which a + b = 2n + 1.”

Then we change the form of this claim. We write:

“Then for every natural n, we have a + b ≠ 2n + 1”.

And then we write:

“But this means that for every natural number n, a + b ≠ n + (n + 1).”

And finish up by writing:

“This last claim tells us that a +b is different from all the possible sums of pairs of consecutive natural numbers, and therefore it cannot be that a, b are consecutive natural numbers.”

This concludes the proof.

The previous proof shows that “If a, b are natural numbers such that a + b is not odd, then a, b are not consecutive” and therefore “If a, b are consecutive natural numbers, then a + b is odd”.

Method of contradiction

This method is not only useful for proving implications, but for proving any type of claim. The idea is that if the negation of a claim A allows us to prove a contradiction, i.e., that some claim is true and that the same claim is false, then the claim A is necessarily true.

Let us prove by this method the claim “If a, b are consecutive natural numbers, then a + b is odd”.

We start by negating what we want to prove. In this case we obtain “There exists at least one pair of natural numbers a, b, such that a, b are consecutive and a + b is not odd”. We assume that this last claim is true and try to derive a contradiction. We write:

“Let a, b be natural numbers such that a, b are consecutive and a + b is not odd”.

Then we write:

“Since a, b are consecutive, then a = b + 1 or b = a + 1. In the first case a + b = (b+1)+b = (b+1)+b = 2b+1 and in the second case a+b = a+(a+1) = 2a + 1. In both cases it turns out that there exists a natural n such that a + b = 2n + 1.”

Now we try to also prove the negation of what we have just concluded. We write:

“On the other hand, since a + b is not odd, there is no natural number k such that a + b = 2k + 1.”

At this point one remarks that we have reached to a conclusion and also to its negation:

“We have thus arrived on one hand to the existence of a natural n such that a + b = 2n + 1, and on the other to the nonexistence of a natural k such that a + b = 2k + 1. This proves that our initial assumption that there exist natural numbers a, b which are consecutive and whose sum is not odd, cannot be true, and therefore its negation, “for all natural numbers a, b, if a, b are consecutive, then a +b is odd” must be true.

And this finishes the proof.

2.1.2 Methods for proving other types of statements

Since not all theorems of mathematics are claims of conditional type, we must consider other important types of claims and have strategies to prove them.

Proving “claim 1 implies claim 2”, when claim 1 is false

Sometimes when trying to prove an implication “claim 1 implies claim 2”, one notices that claim 1 is false. In this case there is nothing to do, because the implication is automatically true!

Proving biconditional claims

A claim of the type “claim 1 if and only if claim 2” is said to be an equivalence or of biconditional type. What this type of claim means is that either claim 1 and claim 2 hold, or neither claim 1 nor claim 2 hold. Sometimes the phrase “if and only if” is abbreviated as “iff”. This type of claim is equivalent to the claim “If claim 1, then claim 2, and if claim 2, then claim 1”. According to this, in order to prove “claim 1 if and only if claim 2”, one proves separately that “claim 1 implies claim 2” and that “claim 2 implies claim 1”.

Proving disjunctions

A disjunction is a claim of the type “P₁ or P₂ or . . . or Pn”. Let us first consider the case n = 2, i.e., claims of the type “P₁ or P₂”. This claim is equivalent to the claim “If no P₁, then P₂”. It is of course also equivalent to “If no P₂, then P₁”. Hence, one would prove any of these two reformulations, which being of conditional type, can be proved by using any of the methods we have already studied. Now, if n ≥ 3, the disjunction is equivalent to the claim “[no(P₁) and no(P₂) and . . . and no(P_n−1)] implies Pn”.

Proving existence claims

An existence claim is a claim of the type “There exists x, such that x has property 1”. There are essentially two ways to prove a claim of this type: by constructing or exhibiting an x having property 1, or by contradiction, i.e., assuming the negation of the existence, which is “For all x, x does not have property 1”, and deriving a contradiction.

Proving universal claims

A universal claim is one of the type “For all x, x has property 1”. These claims can be proved in at least two ways. One is by saying “Let x be a fixed but arbitrary (of the x one is talking about)” and then proving that x has property 1. The other way is by contradiction, i.e., assuming the negation of “For all x, x has property 1”, which is “There exists x, such that x does not have property 1”, and use this assumption to derive a contradiction.

Proving that “For all natural n ≥ 1, P(n) holds”

Let us suppose that for each natural n ≥ 1, we have a claim P(n), i.e., that we have an infinite list of claims P(1), P(2), P(3), . . ., and that we want to prove that each one of them is true. There is a very ingenious way to do this, known as Induction method. It is enough to prove the following two claims:

1. P(1)

2. “For all k ≥ 1, P(k) implies P(k + 1)”.

The reason why just proving these two claims proves that P(n) es true for each n ≥ 1 is as follows. What the second claim says is that each one of the infinite number of implications, “P(1) implies(2) implies P(3)”, “P(3) implies P(4)”, “P(4) implies)”, etc. is true. Let us see why, for example, P(4) must be true. We know that P(1) is true. Since “P(1) implies P(2)” is true, then P(2) must be true. Now, since “P(2) implies P(3)” is true, we have that P(3) has to be true. Again, since “P(3) implies P(4)” is true, P(4) has to be true.

Let us consider an example. Let us prove that for any natural n ≥ 1,

In this case P(n) is “1 + 2 + . . . + n = ”.

Let us verify that P(1) holds. P(1) is “”, which is true. Now, let k ≥ 1 be fixed but arbitrary. We wish to see that P(k) implies P(k+1), i.e., that implies 1+2+. . .+k+(k+1) = . Let us prove this implication by the direct method.

Let us assume that

This implies that

Now,

We conclude that 1 + 2 + . . . + k = , as desired.

There is a variant of this method known as Complete induction method. It consists in proving the following two claims:

1. P(1)

2. “For all k ≥ 1, (P(1) and . . . and P(k)) implies P(k + 1)”.

2.1.3 Symbolic representation

In the previous sections we tried as much as possible to explain everything in words, without using any special symbolism. Our intention in doing so was to not give the impression that logic is a dogmatic system or some invention, but a precise presentation of plain common sense.

Let us now introduce the basic notation and terminology used in logic. A nonempty set of objects D, of which claims can be made, will be called a context. For example, the set of natural numbers = {0, 1, 2, . . .} is a context; and the set of all humans, alive or not, which we could denote by H, is another context.

The claims in a context which have a defined truth value, i.e., which are either true or false, but not both, are called sentences, and are denoted by latin capital letters, with or without a subscript. Thus, the claim, in the context of natural numbers, “5 is even”, which has a defined truth value (it is false) is a sentence, and we could represent it by, say, P . If we have two claims P and Q, in the same context, the new claims “no P ”, “P and Q”, “P or Q”, “P implies Q”, “P if and only if Q”, are denoted by ¬P, P ∧ Q, P ∨ Q, P ⇒ Q and , respectively. A claim, in the context of natural numbers like “x is even” is neither true nor false, because we do not know the specific natural number x is representing. Then “x is even” is not a sentence in the context of the natural numbers.

Claims in a context which have one or several indeterminate subjects are called predicates. Predicates are symbolized by latin capital letters, with or without a subscript, followed by a list without repetitions of letters, separated by commas and enclosed in a pair of parenthesis, where each letter belongs to the list u, v, w, x, w, y, z, with or without a subscript. These letters, called variables, represent the indeterminate subjects which appear in the predicate that is being symbolized. According to this, we could symbolize the predicate “x is even” by P(x). A predicate like “x < y”, having two indeterminate subjects x and y, could be symbolized by P(x,y). If we want to symbolize a predicate like “two numbers add up 8”, which does not come with names for the indeterminate subjects, we choose names for the indeterminate subjects, like z₁ and z₂, and then rewrite it as z₁ + z₂ = 8. One can now symbolize it by Q(z₁, z₂).

When in a predicate all indeterminate subjects are replaced by specific elements of the context, one obtains a sentence. So, if in the predicate “x < y” (in the context of natural numbers), we replace x by 5, and y by 3, we obtain the claim 5 < 3 which is a sentence. Had we symbolized “x < y” by P(x, y), “5 < 3” would have been symbolized by P(5, 3). Now, since P(5, 3) is a sentence, we could represent it by Q if we wished. Another way to turn predicates into sentences is by adding quantifiers. So, if we take the predicate “x is even” in the context of natural numbers, and add the phrase “For all natural x” we obtain the claim “For all natural x, x is even” which is indeed a sentence in the context of natural numbers. It is false since there are natural numbers which are not even. If we denote by P(x) the predicate “x is even” in the context of natural numbers, then “For all natural x, x is even” is denoted by . In the same way, if to the predicate “x is even” we add the phrase “There exists at least a natural x, such that” we obtain “There exists at least a natural x, such that x is even” which is again a sentence. This sentence is true. This sentence would be denoted by . We could have also symbolize either of the sentences “For all natural x, x is even” and “There exists at least a natural x, such that x is even” simply by R. When we want to say that there exists a unique object satisfying a property S (x), one writes .

Now, if we take the predicate “x < y” in the context of natural numbers, and only replace the indeterminate subject x by an specific natural number, say 5, we do not obtain a sentence, but the new predicate “5 < y” which still has one indeterminate subject, y. If we were symbolizing the predicate “x < y” by P(x, y), then “5 < y” would be symbolized by P(5, y). Since P(5, y) is a predicate with a single indeterminate subject y, we could symbolize it by Q(y); but not simply by Q since it is not a sentence. What happens if we take the predicate in , “x < y”, and we add the phrase “For all y,”? We obtain “For all y, x < y”, which is a predicate with a single indeterminate subject, x. If we replace x by a specific natural number, say 3, we obtain “For all y, 3 < y”, which is a sentence. This sentence is false. Instead of giving x a specific value, we can add the phrase “There exists at least one natural x, such that”, obtaining “There exists at least one natural x, such that for all y, x < y”. This is a sentence which is false! It is not true that there is a natural number which is strictly smaller than every natural number. Had the initial predicate been “x ⩽ y” instead of “x < y”, we would have obtained a true sentence (why?). Let us suppose that instead of adding “There exists at least one natural x, such that” we had added “For all x, ”. We would have obtained “For all x, for all y, x < y”, which is a false sentence, since it says that for any two natural numbers x, y, x < y. Let us perform another experiment. What happens if we start by adding the phrase “There exists y, such that” to “x < y”, and then add to the answer the phrase “For all x,”? We obtain “For all x, there exists y such that x < y”. This is a true sentence. And what happens if we first add “There exists x such that” and then we add to the answer “For all y,”? We obtain “For all y, there exists x, such that x < y”. This is a false sentence, because if y = 0 there is no natural number x such that x < y. We observe the highly nontrivial changes caused by the different ways of quantifying a given predicate.

Let us now see how would we symbolize the claims we have just constructed. Let us symbolize “x < y” by P(x, y). The claim “For all x, x < y” in the context of natural numbers, can be symbolized by or by . The claim “There exists at least one natural x, such that for all y, x < y” in the context of natural numbers, can be symbolized by or . The claim “For all x, for all y, x < y” can be symbolized by or . The claim “For all x, there exists y, such that x < y” can be symbolized by or by . And the claim “For all y, there exists x, such that x < y” can be symbolized by or by .

We already have the elements to make clear the following important point. Remember that when we discussed the meaning of the logical implication, we pointed out that there was an important difference between a claim like “If you pass the grade, I will give you a bicycle” and a claim like “If p is a dog that barks, then p is a dog that does not bite”, or, if it is understood that we are making claims in the context of dogs, “If p barks, then p does not bite”. We said that the latter, as opposed to the former, is equivalent to a claim obtained by adding a universal quantification, in this case, adding “For all dog p, if p barks, then p does not bite”. Actually, even though it is not unusual to ignore the difference, it is important to consider “If p barks, then p does not bite” and “For all p, if p barks, then p does not bite” as claims of different nature. “If p barks, then p does not bite” is a predicate in the context of dogs, having an indeterminate subject p, and that we could symbolize by or simply by Q(p); while “For all p, if p barks, then p does not bite” is a sentence in the context of dogs, which could be symbolized by or by or by R, depending on the level of internal structure that we wish to make explicit. If we were to symbolize the claim “If you pass the grade, I will give you a bicycle”, we would write , where G symbolizes “the son passes the grade” and D symbolizes “The father give a bicycle to his son”. The claim “If you pass the grade, I will give you a bicycle” could also be symbolized by a single letter, say P .

With the symbolism we have just introduced, we can represent a number of rules which are used to change the form, but not the meaning, of a given claim. The symbol ≡ is called logical equivalence and it means that we can always transform a claim having the structure described by the formula on the left hand side, to a claim having the structure described by the formula on the right hand side, and vice versa, by substituting parts accordingly. Here are the rules more commonly used.

1. P ∨ Q ≡ Q ∨ P

2. P ∧ Q ≡ Q ∧ P

3. P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R

4. P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R

5. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

6. P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

7. ¬(P ∨ Q) ≡ (¬P ∧ ¬Q)

8. ¬(P ∧ Q) ≡ (¬P ∨ ¬Q)

9. ¬(¬P) ≡ P

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

Using parts 1. and 3. of the previous list, one can see that if we have claims P₁, P₂, . . ., Pn, then any formula in which each of these claims appears exactly once and in any possible order, and contains ∨, and no other logical symbol, is logically equivalent to the formula (. . . ((P₁ ∨ P₂)∨P₃) . . . . . . . . .)∨Pn. This last formula is denoted more simply as P₁ ∨ P₂ ∨ P₃ ∨ . . . ∨ Pn. For example, if we have P₁, P₂, P₃, P₄, then each of the formulae P₂ ∨ (P₄ ∨ (P₃ ∨ P₁)), (P₃ ∨ P₁) ∨ (P₂ ∨ P₄), (P₃ ∨ (P₁∨P₂))∨P₄), etc., is logically equivalent to ((P₁∨P₂)∨P₃)∨P₄, i.e., to P₁∨P₂∨P₃∨P₄. Using parts 2. and 4. of the previous list, one can obtain an analogous result in the case ∧ is the only logical symbol contained in the formula. For example, if we have P₁, P₂, P₃, P₄, then each of the formulae P₂ ∧ (P₄ ∧ (P₃ ∧ P₁)), (P₃ ∧ P₁) ∧ (P₂ ∧ P₄), (P₃ ∧ (P₁ ∧ P₂)) ∧ P₄), etc., is logically equivalent to the formula ((P₁ ∧ P₂) ∧ P₃) ∧ P₄, which is denoted by P₁ ∧ P₂ ∧ P₃ ∧ P₄.

2.1.4 More examples of proofs

In this section we will prove several claims, using the various methods of proof we have studied.

We will assume the following definitions and facts. The set of integers is the set = {. . ., −2, −1, 0, 1, 2, . . .}. An integer x is even if there exists an integer z such that x = 2z, and an integer x is odd if there exists an integer z such that x = 2z + 1. We will assume without proof that every integer is either even or odd, but not both. The natural numbers is the set = {0, 1, 2, . . .}. Notice that every natural is an integer. A natural x is even if there exists a natural z, such that x = 2z, and a natural x is odd if there exists a natural z such that x = 2z + 1. A natural number is even if and only if regarded as an integer, it is even; and a natural number is odd if and only if regarded as an integer, it is odd. This implies that every natural number is either even or odd (as natural number), but not both.

Example 1. In the context of natural numbers, prove that “if a, b are even, then a + b is even”.

Proof. We will use the direct method. Let a, b be natural numbers which are even. This means that there exist natural numbers k, l such that a = 2k and b = 2l. According to this, a + b = 2k + 2l = 2(k + l). Notice that the number k + l is a natural number. We conclude that there exists a natural number m (m = k + l), such that a + b = 2m, i.e., that a + b is an even natural number.

Example 2. In the context of integers, prove that “if n is even, then n² is even”.

Proof. We will use the direct method. Let n be an even integer. This means that there exists an integer k such that n = 2k. But this implies that n² = (2k)² = 2²k² = 2(2k²). Notice that 2k² is an integer, because k is an integer. In this way, we see that there exists an integer m (m = 2k²), such that n² = 2m, i.e., n² is even.

Example 3. In the context of integers, prove that “if a · b is even, then a is even or b is even”.

Proof. We will use contraposition. The negation of “a is even or b is even” is “a is not even and b is not even”. We want to see that if we assume this we obtain the negation of “a · b is even”, i.e., that “a · b is not even”. Let us therefore assume that “a is not even and b is not even”. This is the same as saying that “a is odd and b is odd”. But this means that there exist integers k, l such that a = 2k + 1 and b = 2l+1. Then a b = (2k+1) · (2l+1) = 4kl+2k+2l+1 = 2(2kl+k+l)+1. Since k, l are integers, 2kl + k + l is an integer, and we can conclude that there exists an integer m (m = 2kl + k + l) such that a b = 2m + 1. Hence, a · b is odd, which we know implies that a · b is not even. This concludes our proof.

Example 4. In the context of integers, prove that “if x² is even, then x is even”.

Proof. Let us prove this by contradiction. Let us assume the negation of “if x² is even, then x is even”, which is “there exists an integer x such that x² is even and x is not even”, and let us try to produce a contradiction. We know that x is not even, which implies that x is odd, and hence there exists an integer z such that x = 2z + 1. This implies that x² = (2z + 1)² = 4z² + 4z + 1 = 2(2z² + 2z) + 1. Now, since z is an integer, 2z² +2z is an integer, and then there exists an integer m (m = 2z² + 2z) such that x² = 2m + 1. This tells us that x² is an odd integer. And we know that this implies that x² is not even. But we had that x² is even. We have in this way arrived at “x² is not even and x² is even”, which is a contradiction.

Example 5. In the context of real numbers, prove that “if x y = 0, then x = 0 or y = 0”.

Proof. Let us prove this by contradiction. Let us assume the negation of “if x y = 0, then x = 0 or y = 0”, i.e., that “there exist real numbers x, y such that x · y = 0 and x ≠ 0 and y ≠ 0”. The fact that x ≠ 0 implies that there exists a real number z such that z · x = 1. Now, in x · y = 0, we can multiply both sides by z obtaining z · (x · y) = z · 0. At this point we assume without proof that any real multiplied by zero is zero. Then z · 0 = 0, and z · (x · y) = 0. The latter relation implies that (z · x) · y = 0, which is 1 · y = 0, or y = 0. In this way we have that “y = 0 and y ≠ 0”, which is a contradiction.

Example 6. In the context of real numbers, prove that “if x = 0 or y = 0, then x y = 0”.

Proof. We are asked to prove something of the form “claim 1 implies claim 2” where claim 1 is a disjunction. This leads us to try to do the proof by the method of cases. There are two cases x = 0 and y = 0. If x = 0, then x · y = 0 · y = 0; and if y = 0, then x · y = x · 0 = 0. In both cases we obtained x · y = 0.

Example 7. If r is a real number, its absolute value, |r|, is defined as r if r ≥ 0, and as −r if r < 0. In the context of real numbers, is it true that “|a + b|= |a|+|b|”?

Proof. What is being claimed is that for every pair of real numbers a, b, the equality |a + b|= |a|+|b| holds. This is actually false. To prove it, it is enough to find two specific real numbers a, b for which the equality fails. If we take a = 2 and b = −2, we have |a + b| = |2 + (−2)| = |0| = 0, |a| = |2| = 2 y |b| = | − 2| = 2, and |a + b| = |a| + |b| would mean that 0 = 2 + 2.

Example 8. Let us prove that for each natural number n ≥ 4, the inequality n! > 2n holds.

Proof. Let us prove this by induction. Let us denote by P(n) the claim “n! > 2n”. We want to see that P(n) is true for each n ≥ 4. We begin by verifying that P(4) is true. P(4) is 4! > 2⁴, which is true since 4! = 24 and 2⁴ = 16. Let k be a natural number with k ≥ 4. Let us see that P(k) implies P(k + 1). Assume that k! > 2k. Then (k + 1)! = (k + 1)k! > 2(2k) = 2k+1. The inequality (k + 1)k! > 2(2k) is obtained by multiplying the left hand sides and the right hand sides of the inequalities k + 1 > 2 (which holds since k ≥ 4) and k! > 2k.

2.1.5 Exercises

1. In the context of integers, prove that “for all n, n² + n + 1 is odd.”

2. In the context of real numbers, is it true that “if a = b, then a² = b²”?

3. In the context of real numbers, would it be true that “if a² = b², then a = b”?

4. Prove that in the context of real numbers, “ |a · b| = |a| · |b|”.

5. In the context of integers, prove that “if x² is odd, then x is odd”.

6. Prove in the context of real numbers that “for all a, |a| ≥ 0”.

7. Prove that “If n is an integer and n² +5 is odd, then n is even”.

8. Prove by the method of contradiction, that if n and m are odd integers, then n + m is an even integer.

9. If x, y are real numbers, then max(x, y) is defined as x if y ⩽ x and as y if x ⩽ y; and min(x, y) is defined as x if x ⩽ y and as y if y ⩽ x. Prove that if x and y are real numbers, then max (x, y) + min(x, y) = x + y.

10. Prove in the context of real numbers that “m² = n² if and only if m = n or m = −n”.

11. Prove that if a, b and c are real numbers with a ≠ 0, then there exists a unique solution to the equation ax + b = c.

12. A number is rational if it can be written as where p, q are integers with q ≠ 0. Would it be true that if a and b are rational numbers, then ab is also a rational number?

13. Prove by contraposition that if x and y are real numbers and x² + y² = 0, then x = 0 and y = 0.

14. Leibnitz proved that for every positive integer n:

(a) n³− n is a multiple of 3

(b) n⁵− n is a multiple of 5

(c) n⁷− n is a multiple of 7

In view of these results, can we conclude that for every pair of positive integers k, n, nk− n is a multiple of k?

15. Prove that is not a rational number.

16. Prove that n(n + 1) is divisible by 2 for all n ∈ .

17. A positive integer n is a perfect square if n = k² for some positive integer k. Prove or disprove the following proposition: “The sum of two perfect squares is also a perfect square”.

18. Prove that for each integer n, if 5n + 3 is even, then n is odd.

19. A real number is said to be irrational if it is not rational. Prove or disprove the following claim : “The product of two irrational numbers is an irrational number”.

20. Prove that if a natural number is such that the sum of its digits is divisible by 3, then the number is divisible by 3.

21. Prove by induction that:

(a) For each natural n ≥ 1, 1 + 3 + 5 + ... + (2n − 1) = n².

(b) For each natural n ≥ 1, 1 + 2 + 2² + ... + 2n = 2ⁿ⁺¹ − 1.

(c) For all real a, r where with n being a nonnegative integer.

(d) For each natural n ≥ 3, 2n + 1 ⩽ 2n.

(e) For each natural n ≥ 4, n² ⩽ 2n.

(f) For each natural .

(g) The sum of any three consecutive positive integers is divisible by 3.

(h) For each natural n ≥ 1, .

(i) For each natural n ≥ 2, .

(j) For each natural n, n⁵− n is a multiple of 5.

2.2 Elementary theory of sets

We begin by defining the fundamental concept of “set”.

Definition 1. A set is a well defined collection of objects which can be considered by our mind.

For example, the collection formed by all natural numbers 0, 1, 2, . . . is a set.

The objects that form a set are called elements of the set.

Sets are generally denoted by capital latin letters and the elements by lowercase latin letters. The fact that certain object x belongs to a certain set A, is symbolized by “x ∈ A” and is read “x belongs to A”. According to this notation, 7 ∈ . When certain object x does not belong to certain set A, we write “x ∉ A”.

There exist two methods for specifying a set, by extension and by comprehension. Giving a set by extension means giving a complete list of the elements of the set, enclosed by braces. For example, {2, 3, 4} is the set whose elements are the numbers 2, 3, 4. The order in which the elements are listed does not affect the set. For example, the set {2, 3, 4} is the same as the set {3, 2, 4}. A set defined by extension is also not affected by repeating any number of times any given element. For example, the set {2, 3, 4, 2, 4} is equal to the set {2, 3, 4}.

Specifying a set by comprehension consists in presenting the set as the collection of those elements belonging to a certain reference set, which satisfy certain condition. For example, the set specified by extension as {2, 3, 4}, can be said to consists of those natural numbers which are greater than 1 and less than 5. This is denoted by

In general, if X is a set and P(x) is a predicate about elements x of X, the set formed by all of the elements x of X such that P(x) is true, is denoted by

In the case of {x ∈ /1 < x and x < 5}, X is and P(x) is “1 < x and x < 5”.

Some or all the objects which form a set may in turn be sets! For example,

is a set. Its elements are 1 and {2, 5}, and it is therefore correct to write

It is not true that 2 ∈ X or that 5 ∈ X. Also Y = {1, {1}} is a set whose elements are 1 and {1}. Elements 1 and {1} are different objects!

If we consider for instance the set

we see that it does not have any element, but it would be wrong to deny its being a set, since it is formed by all the elements of a certain set which satisfy certain condition. In the same way the introduction of the number zero in mathematics was of utmost importance, it is also very important in mathematics to consider the collection having no elements as a set! This set is called the empty set and it is denoted by ∅ or {}.

Sets can be finite or infinite. For example, the set {2, 3, 4} is finite and has three elements. The empty set is finite and has zero elements. The set is infinite. The number of elements of a set A is called the cardinal of the set A, and it is denoted by |A|. Accordingly, |{2, 3, 4}| = 3. In order to express that a given set A is infinite, we will write |A| = ∞. We warn the reader that this is an informal use of the concept of the cardinal of a set. Georg Cantor found a precise way to define, for the first time in history, what it means that a set has the same number of elements than another, even if both sets are infinite! In particular, Cantor showed that some infinite sets have more elements than other infinite sets!

Definition 2. A set X is said to be a subset of another set Y , which is denoted by X ⊆ Y , if the claim is true. A set X is said to be equal to a set Y , which is denoted by X = Y , if the claim is true.

Example 9. Let us prove that A = B if and only if A ⊆ B and B ⊆ A.

Proof. By definition, we have A = B if and only if . But

Example 10. Let us prove that the empty set is a subset of any given set, i.e. that ∅ ⊆ X for every set X.

Proof. According to the definition of being a subset, ∅ ⊆ X means that the claim holds. Now, for each x, the implication “” is true, because “x ∈ ∅” is false.

Let A = {x ∈ U/P(x)} and B = {x ∈ U/Q(x)} be two sets given by comprehension. It can be seen that A ⊆ B if and only if in the context U; and A = B if and only if in the context U.

Example 11. Let us prove the first claim of the previous paragraph, i.e., that if A = {x ∈ U/P(x)} and B = {x ∈ U/Q(x)}, then A ⊆ B if and only if in the context U.

Proof. By definition, A ⊆ B if and only if . But x ∈ A if and only if x ∈ U and P(x); and x ∈ B if and only if x ∈ U and Q(x). So if and only if in the context U. We conclude that A ⊆ B if and only if in the context U.

Exercise 1. The following exercises are good for clarifying certain fine points of the definitions and notations we have discussed.

1. Let A = {{1, {2}}, {3}}. List separately all the elements of the set A, and all subsets of the set A.

2. Answer each one of the questions, and justify your answer:

(a) {1, 3, 3, 3, 5, 5, 5, 5} = {5, 3, 1}?

(b) {{1}} = {1, {1}}?

(c) ∅ = {∅}?

3. In each case decide if the claim is true or false, and justify your answer:

(a) x ∈ {x}

(b) {x, y} ⊆ {x, y}

(c) {x} ∈ {x, y}

(d) x ∈ {{x}}

(e) ∅ ∈ {}

(f) ∅ ⊆ {}

(g) ∅ ∈ {1, 2, 3}

(h) ∅ ∈ {{}}

(i) ∅ ⊆ {{}}

(j) ∅ ⊆ {1, 2, 3, 4}

4. Determine the cardinality of the following sets:

(a) {1,{1,1,1},{1},1}

(b) {∅, 3}

(c) {}

(d) {{}, ∅}

5. Prove that for all set X, X ⊆ X.

6. Prove that if A ⊆ B y B ⊆ C, then A ⊆ C.