Kitabı oku: «A course of plane geometry», sayfa 3

Yazı tipi:

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

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.

(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.