# CS代考 Introduction to mathematical arguments – cscodehelp代写

Introduction to mathematical arguments
(background handout for courses requiring proofs) by
A mathematical proof is an argument which convinces other people that something is true. Math isn’t a court of law, so a “preponderance of the evidence” or “beyond any reasonable doubt” isn’t good enough. In principle we try to prove things beyond any doubt at all — although in real life people make mistakes, and total rigor can be impractical for large projects. (There are also some subtleties in the foundations of mathematics, such as G ̈odel’s theorem, but never mind.)
Anyway, there is a certain vocabulary and grammar that underlies all mathematical proofs. The vocabulary includes logical words such as ‘or’, ‘if’, etc. These words have very precise meanings in mathematics which can differ slightly from everyday usage. By “grammar”, I mean that there are certain common-sense principles of logic, or proof techniques, which you can use to start with statements which you know and deduce statements which you didn’t know before.
These notes give a very basic introduction to the above. One could easily write a whole book on this topic; see for example How to read and do proofs: an introduction to mathematical thought process by D. Solow). There are many more beautiful examples of proofs that I would like to show you; but this might then turn into an introduction to all the math I know. So I have tried to keep this introduction brief and I hope it will be a useful guide.
In §1 we introduce the basic vocabulary for mathematical statements. In §2 and §3 we introduce the basic principles for proving statements. We provide a handy chart which summarizes the meaning and basic ways to prove any type of statement. This chart does not include uniqueness proofs and proof by induction, which are explained in §3.3 and §4. Apendix A reviews some terminology from set theory which we will use and gives some more (not terribly interesting) examples of proofs.
1

The following was selected and cobbled together from piles of old notes, so it is a bit uneven; and the figures are missing, sorry. If you find any mistakes or have any suggestions for improvement please let me know.
1 Statements and logical operations
In mathematics, we study statements, sentences that are either true or false
but not both. For example, 6 is an even integer
and
4 is an odd integer
are statements. (The first one is true, and the second is false.) We will use letters such as ‘p’ and ‘q’ to denote statements.
1.1 Logical operations
In arithmetic, we can combine or modify numbers with operations such as ‘+’, ‘×’, etc. Likewise, in logic, we have certain operations for combining or modifying statements; some of these operations are ‘and’, ‘or’, ‘not’, and ‘if…then’. In mathematics, these words have precise meanings, which are given below. In some cases, the mathematical meanings of these words differ slightly from, or are more precise than, common English usage.
Not. The simplest logical operation is ‘not’. If p is a statement, then ‘not p’ is defined to be
• true, when p is false; • false, when p is true.
The statement ‘not p’ is called the negation of p.
And. If p and q are two statements, then the statement ‘p and q’ is defined
to be
• true, when p and q are both true;
• false, when p is false or q is false or both p and q are false. 2

Or. If p and q are two statements, then the statement ‘p or q’ is defined to be
• true,whenpistrueorqistrueorbothpandqaretrue;
• false, when both p and q are false.
In English, sometimes “p or q” means that p is true or q is true, but not both. However, this is never the case in mathematics. We always allow for the possibility that both p and q are true, unless we explicitly say otherwise.
If. . . then. If p and q are statements, then the statement ‘if p then q’ is defined to be
• true, when p and q are both true or p is false;
• false, when p is true and q is false.
We sometimes abbreviate the statement ‘if p then q’ by ‘p implies q’, or
‘p ⇒ q’. If p is false, then we say that p ⇒ q is vacuously true.
If and only if. If p and q are statements, then the statement ‘p if and only
if q’ is defined to be
• true, when p and q are both true or both false;
• false, when one of p, q is true and the other is false.
Thesymbolfor‘ifandonlyif’is‘⇐⇒’. Whenp ⇐⇒ qistrue,wesay that p and q are equivalent.
1.2 Quantifiers
Consider the sentence x is even.
This is not what we have been calling a statement; we can’t say whether it is true or false, because we don’t know what x is.
There are three basic ways to turn this sentence into a statement. The first is to say exactly what x is:
3

When x = 6, x is even.
The following are two more interesting ways of turning the sentence into a
statement:
For every integer x, x is even.
There exists an integer x such that x is even.
The phrases ‘for every’ and ‘there exists’ are called quantifiers.
As an example of the use of quantifiers, we can give precise definitions of
the terms ‘even’ and ‘odd’.
Definition. An integer x is even if there exists an integer y such that
x = 2y.
(The ‘if’ in this definition is really an ‘if and only if’. Mathematical literature tends to misuse the word ‘if’ this way when making definitions, and we will do this too.)
Definition. An integer x is odd if there exists an integer y such that x = 2y + 1.
Notation for quantifiers. We will call a sentence such as ‘x is even’ that depends on the value of x a “statement about x”. We can denote the sentence ‘x is even’ by ‘P(x)’; then P(5) is the statement ‘5 is even’, P(72) is the statement ‘72 is even’, and so forth.
If S is a set and P(x) is a statement about x, then the notation (∀x ∈ S) P(x)
means that P(x) is true for every x in the set S. (See Appendix A for a discussion of sets.) The notation
(∃x ∈ S) P(x)
means that there exists at least one element x of S for which P (x) is true. We denote the set of integers by ‘Z’. Using the above notation, the
definition of ‘x is even’ given previously becomes (∃y ∈ Z) x = 2y.
4

Of course, this is still a statement about x. We can turn this into a statement by using a quantifier to say what x is. For instance, the statement
(∀x ∈ Z) (∃y ∈ Z) x = 2y
says that all integers are even. (This is false.) The statement
(∃x ∈ Z) (∃y ∈ Z) x = 2y
says that there exists at least one even integer. (This is true.)
The sentence
means that x is odd. The statement
(∃y ∈ Z) x = 2y + 1 (∀x∈Z)􏰁(∃y∈Z)x=2y􏰂 or 􏰁(∃y∈Z)x=2y+1􏰂
says that every integer is even or odd.
The order of quantifiers is very important; changing the order of the
quantifiers in a statement will often change the meaning of a statement. For example, the statement
But we said before that b is as small as possible, so this is a contradiction.

2 cannot be rational. P scent, which is used to prove various theorems in classical number theory. If
Therefore
This particular type of proof by contradiction is known as infinite de-

there exist positive integers a and b such that a/b =
shows that we can find smaller positive integers a and b with the same prop- erty, and repeating this process, we will get an infinite descending sequence of positive integers, which is impossible.
Recall that in the above proof, we said
We can assume that b is positive, since otherwise we can simply
change the signs of both a and b. Another way to write this would be
Without loss of generality, b > 0.
“Without loss of generality” means that there are two or more cases (in this proof the cases when b > 0 and b < 0), but considering just one particular case is enough to prove the theorem, because the proof for the other case or cases works the same way. 3.3 Uniqueness proofs Suppose we want to prove that the object x satisfying a certain property, if it exists, is unique. There is a standard strategy for doing this. We let x 14 2, then the above proof and y be two objects both satisfying the given property, and we then try to deduce that x = y. A classic example of a uniqueness proof comes from group theory. Recall that a group is a set G together with a rule for multiplying any two elements of G to obtain another element of G. The definition of a group requires that this multiplication is associative (though not necessarily commutative), and that there is an identity element e ∈ G such that (∀x∈G) ex=xe=x. (1) (Also any element x has an inverse x−1 such that xx−1 = x−1x = e.) Example. Prove that the identity element e ∈ G satisfying (1) is unique. Let e1,e2 be elements of G satisfying e1x = xe1 = x and e2x = xe2 = x for all x ∈ G. We will show that e1 = e2. The trick is to multiply e1 and e2 together in order to obtain an “identity crisis”. Since e1 is an identity element, we have e1e2 = e2. But since e2 is an identity element, we have e1e2 =e1. Thuse1 =e2. P Exercise. Prove that the inverse of a given element x ∈ G is unique. 4 Proof by induction Mathematical induction is a useful technique for proving statements about natural numbers. 4.1 The principle of mathematical induction Let P(n) be a statement about the positive integer n. For example, perhaps P(n) = “n is a multiple of 5.” or P (n) = “If n is even, then n2 is divisible by 4.” Suppose we want to show that P (n) is true for every positive integer n. How can we do this? One way is to prove the following two statements: 15 (a) P(1) is true. (b) For every n ∈ Z+, if P(n) is true, then P(n + 1) is true. Why is this sufficient? Well, suppose we have proved (a) and (b) above. Then we know that P(1) is true. Since P(1) ⇒ P(2), we know that P(2) is true. Since P(2) ⇒ P(3), we know that P(3) is true. Since P(3) ⇒ P(4), we know that P (4) is true. We can continue this indefinitely, so we see that P(n) is true for every positive integer n. By analogy, suppose we have a chain of dominoes standing on end. If we push over the first domino, and if each domino knocks over the next domino as it falls, then eventually every domino will fall. This reasoning is called the principle of mathematical induction. In fact this principle can be regarded as one of the axioms defining the natural numbers. Let us state it precisely. Principle of Mathematical Induction (PMI). Let P (n) be a statement about the positive integer n. If the following are true: 1. P (1), 2. (∀n ∈ Z+) P(n) ⇒ P(n + 1), then (∀n ∈ Z+) P(n). A proof by induction consists of two parts. In the first part, called the base case, we show that P(1) is true. In the second part, called the inductive step, we assume that n is a positive integer such that P (n) is true, (although we don’t know what n is), and we deduce that P (n + 1) is true. The assumption that P (n) is true is called the inductive hypothesis. (This may look like circular reasoning, but it is not! Think about the dominoes again.) Example. For every positive integer n, 1 + 2 + · · · + n = n(n + 1) . Proof. We will use induction on n. 16 2 Base case: When n = 1, we have1+···+n = 1, and n(n+1)/2 = 1 · 2/2 = 1. Inductive step: Suppose that for a given n ∈ Z+, 1 + 2 + · · · + n = n(n + 1) . (inductive hypothesis) Our goal is to show that 2 i.e., 1+2+···+n+(n+1)= [n+1]([n+1]+1), 2 1+2+···+n+(n+1)= (n+1)(n+2). 2 Adding (n + 1) to both sides of the inductive hypothesis, we get 1+2+···+n+(n+1) = n(n+1) +(n+1) 2 = n(n+1) + 2(n+1) 22 = (n+2)(n+1). 2 Recall that if a and b are real numbers and ab = 0, then a = 0 or b = 0. Using induction, we can extend this to the following: Example. If a1,a2,...,an are real numbers and a1a2 ···an = 0, then ai = 0 for some i with 1 ≤ i ≤ n. Proof. We will use induction on n. Base case: For n = 1, this is trivial. Inductive step: Suppose the statement is true for n. We wish to show that the statement is true for n+1. Suppose a1, . . . , an, an+1 are real numbers such that a1a2 · · · anan+1 = 0. Since (a1 · · · an)an+1 = 0, it follows that a1···an =0oran+1 =0. 17 P If a1 ···an = 0, then by inductive hypothesis, ai = 0 for some i with 1≤i≤n,andwearedone. Ifan+1 =0,wearealsodone. P In mathematical writing, simple induction proofs like this are often omit- ted. For example, one might write “since the product of two nonzero real numbers is nonzero, it follows by induction that the product of n nonzero real numbers is nonzero”. However induction is an essential tool for breaking down more complicated arguments into simple steps. There are many (equivalent) variants of the principle of induction. For example, one can start at 0 instead of 1, to prove that some statement is true for all nonnegative integers. One can also prove a statement about several positive integers by doing induction on one variable at a time. Another important variant is the following: Strong induction. Let P(n) be a statement about the positive integer n. Suppose that for every positive integer n, (*) If P(n′) is true for all positive integers n′ < n, then P(n) is true. Then P(n) is true for all positive integers n. Note that no base case is needed. To see this, suppose we have proved (*) for all positive integers n. Putting n = 1 into (*), we deduce that P(1) is true, since the statement “P(n′) is true for all positive integers n′ < 1” is vacuously true. Putting n = 2 into (*) we deduce that P(2) is true. Thus P(1) and P(2) are true, so putting n = 3 into (*) we deduce that P(3) is true. And so on. To give an example of proof by strong induction, recall that an integer p > 1 is prime if it has no integer divisors other than 1 and p.
Theorem. Any integer n > 1 can be expressed as a product of prime numbers.
Proof. We use strong induction on n (starting at 2 instead of 1). Let n > 1 be an integer and suppose that every integer n′ with 2 ≤ n′ < n is a product of primes. We need to show that n is a product of primes. If n is prime then n is the product of one prime number (itself) and we are done. If n is not prime then n is divisible by an integer a with 1 < a < n, so n = ab where a and b are integers with 1 < a, b < n. By inductive hypothesis, a and b are 18 both products of primes, and since n = ab, it follows that n is a product of primes. P 4.2 The Well-Ordering Principle If S is a set of integers, then a least element of S is an element x ∈ S such that x ≤ y for all y ∈ S. The following may seem obvious. Well-Ordering Principle (WOP). Any nonempty set of positive inte- gers has a least element. However, it is not true for negative integers, rational numbers, or real numbers. For example, {x ∈ R | x > 0} has no least element.
The well-ordering principle is equivalent to the principle of mathematical induction. To see this, we will first prove that the principle of induction implies the well-ordering principle. In other words, we will prove WOP by induction.
PMI⇒WOP. Suppose PMI is true. We will prove WOP. Let S be a set of positive integers with no least element. We will show that S is empty. To do this, we will prove by induction on n that for every positive integer n, S does not contain any numbers less than n.
Base case: S cannot contain any numbers smaller than 1, since S is a set of positive integers.
Inductive step: Suppose S does not contain any numbers smaller than n. We wish to show that S does not contain any numbers smaller than n+1. Itisenoughtoshowthatn∈/S. Ifn∈S,thennisaleastelementofS, since S contains no numbers less than n. But we assumed that S has no least element, so this is a contradiction. P
WOP⇒PMI. Suppose WOP is true. We will prove PMI. Let P(n) be a statement about the positive integer n. Suppose that P(1) is true, and suppose for all n, P(n) ⇒ P(n + 1). We must show that for all n, P(n) is true. Suppose to the contrary that P(n) is false for some n. Let
S:={n∈Z+ |P(n)isfalse}. 19

By assumption this set is nonempty, so it contains a least element n0. Now n0 ̸=1,becauseweknowthatP(1)istrue. Son0 >1. Thenn0−1isa positive integer, and since it is smaller than n0, it is not in the set S. Thus P(n0 − 1) is true. But P(n0 − 1) implies P(n0), so P(n0) is true. Thus n0 ∈/ S, a contradiction. P
There are some variants of the well-ordering principle which are easily seen to be equivalent to it. For example any nonempty set of integers (possibly negative) with a lower bound has a least element, and any nonempty set of integers with an upper bound has a largest element. (A lower bound on SisanumberLsuchthatx≥Lforallx∈S. AnupperboundonSis a number U such that x ≤ U for all x ∈ S. A largest element of S is an element x ∈ S such that x ≥ y for all y ∈ S.)
A useful application of the well-ordering principle is the following:
Division theorem. If a and b are integers with b > 0, then there exist unique integers q and r such that a = qb + r and 0 ≤ r < b. (The integer q is the “quotient” when a is divided by b, and r is the remainder. In elementary school you learned an algorithm for finding q and r. But let’s now prove that they exist and are unique.) Proof. The idea is that we want q to be the largest integer such that a ≥ qb. So let S := {q ∈ Z | a − qb ≥ 0}. This set is nonempty; for example −|a| ∈ S since b > 0. It also has an upper bound, since a − qb ≥ 0 implies q ≤ |a|. So by the well ordering principle, S contains a largest element q. Let r = a − qb. Then r ≥ 0 by definition of S. Alsor0 and x<4} thesetofevenintegers = {x∈Z|(∃y∈Z)x=2y}. If A and B are sets, and if every element of A is also an element of B, we saythatAisasubsetofB,andwewriteA⊂B. Insymbols, A⊂B ⇐⇒ (∀x)x∈A⇒x∈B 22 For example, Z is a subset of R, but R is not a subset of Z. Every set is a subset of itself. Also, the empty set is a subset of every set; for any set A, the statement (∀x) x ∈ ∅ ⇒ x ∈ A is vacuously true, since the statement “x ∈ ∅” is always false. On the other hand, the empty set is the only set that is a subset of the empty set. Two sets are equal if and only if they have the same elements; in terms of subsets, For example, but A=B ⇐⇒ A⊂B and B⊂A {1,2,3} = {2,3,1}, {1, {2}} ≠ {1, 2}. A.2 Unions and intersections The union of two sets A and B, denoted by A ∪ B, is the set of all objects that are in A or B (or both): A∪B:={x|x∈A or x∈B}. The intersection of A and B is the set of all objects that are in both A and B: For example, A∩B:={x|x∈A and x∈B}. {1,2,3}∪{2,3,4} = {1,2,3,4}, {1,2,3}∩{2,3,4} = {2,3}. Venn diagrams provide a nice way to visualize these and other set- theoretic concepts. In Figure ??(a), the inside of the circle on the left repre- sents the contents of A, while the inside of the circle on the right represents B. The shaded region is A ∪ B. In Figure ??(b), the shaded region is A ∩ B. How would you demonstrate the meaning of “A ⊂ B” with a Venn diagram? The following are some basic properties of the union and intersection operations. We will leave the proofs of most of these facts as exercises. 23 Commutative properties. A∪B=B∪A A∩B=B∩A Associative properties. A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C Distributive properties. Other facts. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∪ C) = (A ∪ B) ∪ (A ∪ C) A ∩ (B ∩ C) = (A ∩ B) ∩ (A ∩ C) A∪A=A=A∩A A∪∅=A A∩∅=∅ A∩B⊂A⊂A∪B A∩B⊂B⊂A∪B A proof that two sets are equal usually consists of two parts: in the first part, labeled ‘(⊂)’, we show that the first set is a subset of the second; in the second part of the proof, labeled ‘(⊃)’, we show that the second set is a subset of the first. 24 Example. ProvethatA∪(B∩C)=(A∪B)∩(A∪C). (⊂) Suppose x ∈ A∪(B∩C). We wish to show that x ∈ (A∪B)∩(A∪C). By definition of union, x ∈ A or x ∈ B ∩ C. Case1: Supposex∈A. Thenx∈Aorx∈B,sox∈A∪B. Likewise, x ∈ A ∪ C. Thus x ∈ A ∪ B and x ∈ A ∪ C, so x ∈ (A ∪ B) ∩ (A ∪ C). Case2: Supposex∈B∩C. Thenx∈Bandx∈C. Sincex∈B, it follows that x ∈ A∪B. Since x ∈ C, it follows that x ∈ A∪C. Thus x ∈ (A ∪ B) ∩ (A ∪ C). (⊃) Suppose x ∈ (A∪B)∩(A∪C). Then x ∈ A∪B and x ∈ A∪C. Wewishtoshowthatx∈A∪(B∩C),i.e.,x∈Aorx∈B∩C. Suppose x ∈/ A. It is enough to show that x ∈ B ∩ C. Since x ∈ A ∪ B and x ∈/ A, it followsthatx∈B. Likewise,sincex∈A∪C,x∈C. Thusx∈B∩C. P In this example we have written down a lot of the details, but not every single one. For example, at the bottom of the proof, we write Since x ∈ A∪B and x ∈/ A, it follows that x ∈ B. Likewise, since x∈A∪C,x∈C. Thusx∈B∩C. If we wanted to include every single detail, we would write Sincex∈A∪B,x∈Aorx∈B. Sincex∈/A,itfollowsthat x∈B. Sincex∈A∪C,x∈Aorx∈C. Sincex∈/A,itfollows thatx∈C. Thusx∈Aandx∈C,sox∈B∩C. However, we prefer to be concise and omit obvious steps, provided that the reader can easily follow the argument. Usually a proof is centered around a few simple ideas, and excessive writing will tend to obscure them. We would like to mention one more thing about the union and intersection operations. These are binary operations, which means that they can only operate on two sets at once. If we want to take the union of three sets A, B, and C, there are two different ways we might do this: either or A ∪ (B ∪ C) (A∪B)∪C. But the associative property says that these two expressions are equal. So when we write A ∪ B ∪ C, 25 we mean either of the two expressions above. Also, the commutative property implies that we can change the order in which A, B, and C appear. Likewise for intersection. Similarly, if n is any positive integer and A1, A2, . . . , An are sets, then there is no ambiguity in the expressions and A1 ∪A2 ∪...∪An A1 ∩A2 ∩...∩An. The union of A1,A2,...,An is the set of all things which are in at least one of these n sets; the intersection of A1, A2, . . . , An is the set of all things which are in all n sets. A.3 Set difference The difference between two sets A and B, denoted by A − B, is defined as follows: A−B:={x|x∈A and x∈/B}. Figure ?? gives a Venn diagram illustrating this operation. For example, ZN is the set of negative integers. Some literature uses the notation ‘AB’ instead of A − B. The following are some basic properties of the set difference operation which you should remember. De Morgan’s laws. Other facts. A − (B ∪ C) = (A − B) ∩ (A − C) A − (B ∩ C) = (A − B) ∪ (A − C) A − B ⊂ A B ∩ (A − B) = ∅ A−B=∅ ⇐⇒ A⊂B A−B=A ⇐⇒ A∩B=∅ 26 Example. ProvethatA−(B∪C)=(A−B)∩(A−C). (⊂) Suppose x ∈ A−(B∪C). Then x ∈ A, and x ∈/ B∪C. Since it isnottruethatx∈Borx∈C,weknowthatx∈/Bandx∈/C. Since x∈Aandx∈/B,wehavex∈(A−B). Likewise,x∈(A−C). Thus x ∈ (A − B) ∩ (A − C). (⊃)Supposex∈(A−B)∩(A−C). Thenx∈A,x∈/B,andx∈/C. It isnottruethatx∈Borx∈C,sox∈/(B∪C).Thusx∈A−(B∪C). P There are many more set-theoretic identities which we have not listed. However, instead of memorizing a huge list of identities, it is better to figure out and prove identities as they are needed. In mathematical writing, one usually omits proofs of simple set identities. (But don’t do that for the exercises in this chapter.) Exercises. 1. List separately the elements and the subsets of {{1, {2}}, {3}}. (There are 2 elements and 4 subsets.) 2. ExplainwhyifA⊂BandB⊂C,thenA⊂C. 3. If a set has exactly n elements, how many subsets does it have? Why? 4. We have repeatedly used the words, ‘the empty set’. Is this justified? If A and B are both sets that contain no elements, then is A necessarily equal to B? 5. Which of the following statements are true, and which are false? Why? (a) {{∅}}∪∅={∅,{∅}} (b) {{∅}}∪{∅}={∅,{∅}} (c) {∅,{∅}}∩{{∅},{{∅}}}={∅} (d) {∅,{∅}}∩{{∅},{{∅}}}={{∅}} 6. Prove the all the properties of union, intersection, and set difference that we stated without proof in the text. 7. Show that A∩(B−C) = (A∩B)−(A∩C). Is it always true that A∪(B−C) = (A∪B)−(A∪C)? 8. Find some more set theoretic identities and prove them. 27