## Discrete Mathematics for Computer Science

As we saw in Section 3.6, if (p(n)) is a proposition over a universe (U ext<,>) its truth set (T_p) is equal to a subset of U. In many cases, such as when (p(n)) is an equation, we are most concerned with whether (T_p) is empty or not. In other cases, we might be interested in whether (T_p=U ext<>) that is, whether (p(n)) is a tautology. Since the conditions (T_p eq emptyset) and (T_p=U) are so often an issue, we have a special system of notation for them.

### Subsection 3.8.1 The Existential Quantifier

###### Definition 3.8.1 . The Existential Quantifier.

If (p(n)) is a proposition over (U) with (T_p eq emptyset ext<,>) we commonly say “There exists an (n) in (U) such that (p(n)) (is true).” We abbreviate this with the symbols ((exists n)_U(p(n)) ext<.>) The symbol (exists) is called the existential quantifier. If the context is clear, the mention of (U) is dropped: ((exists n)(p(n)) ext<.>)

###### Example 3.8.2 . Some examples of existential quantifiers.

((exists k)_

((exists k)_

((exists x)_

There are a wide variety of ways that you can write a proposition with an existential quantifier. Table 3.8.5 contains a list of different variations that could be used for both the existential and universal quantifiers.

### Subsection 3.8.2 The Universal Quantifier

###### Definition 3.8.3 . The Universal Quantifier.

If (p(n)) is a proposition over (U) with (T_p=U ext<,>) we commonly say “For all (n) in (U ext<,>) (p(n)) (is true).” We abbreviate this with the symbols ((forall n)_U(p(n)) ext<.>) The symbol (forall) is called the universal quantifier. If the context is clear, the mention of (U) is dropped: ((forall n)(p(n)) ext<.>)

###### Example 3.8.4 . Some Universal Quantifiers.

- We can say that the square of every real number is non-negative symbolically with a universal quantifier: ((forall x) _
>(x ^2 geq 0) ext<.>) - ((forall n) _
> (n + 0 = 0 + n =n)) says that the sum of zero and any integer (n) is (n ext<.>) This fact is called the identity property of zero for addition.

Universal Quantifier | Existential Quantifier |

((forall n)_U(p(n))) | ((exists n)_U(p(n))) |

((forall nin U)(p(n))) | ((exists nin U)(p(n))) |

(forall nin U, p(n)) | (exists nin U extrm |

(p(n), forall n in U) | (p(n)) is true for some (n in U) |

(p(n)) is true for all (n in U) |

### Subsection 3.8.3 The Negation of Quantified Propositions

When you negate a quantified proposition, the existential and universal quantifiers complement one another.

###### Example 3.8.6 . Negation of an Existential Quantifier.

Over the universe of animals, define (F(x) ext<:>) (x) is a fish and (W(x) ext<:>) (x) lives in the water. We know that the proposition (W(x) ightarrow F(x)) is not always true. In other words, ((forall x)(W(x) ightarrow F(x))) is false. Another way of stating this fact is that there exists an animal that lives in the water and is not a fish that is,

Note that the negation of a universally quantified proposition is an existentially quantified proposition. In addition, when you negate an existentially quantified proposition, you get a universally quantified proposition. Symbolically,

( eg ((forall n)_U(p(n)) )Leftrightarrow (exists n)_U ( eg p(n))) |

( eg ((exists n)_U(p(n)) )Leftrightarrow (forall n)_U ( eg p(n))) |

###### Example 3.8.8 . More Negations of Quantified Expressions.

- The ancient Greeks first discovered that (sqrt<2>) is an irrational number that is, (sqrt<2>) is not a rational number. (
eg ((exists r)_
>(r^2 = 2))) and ((forall r)_ > (r^2 eq 2)) both state this fact symbolically. - (
eg ((forall n)_
>(n ^2- n + 41 extrm< is prime>))) is equivalent to ((exists n)_ > (n^2 - n + 41 extrm< is composite>) ext<.>) They are either both true or both false.

### Subsection 3.8.4 Multiple Quantifiers

If a proposition has more than one variable, then you can quantify it more than once. For example, (p(x, y):x^2 - y^2 = (x + y)(x - y)) is a tautology over the set of all pairs of real numbers because it is true for each pair ((x, y)) in (mathbb

In general, multiple universal quantifiers can be arranged in any order without logically changing the meaning of the resulting proposition. The same is true for multiple existential quantifiers. For example, (p(x, y) : x + y = 4 extrm < and >x - y = 2) is a proposition over (mathbb

When existential and universal quantifiers are mixed, the order cannot be exchanged without possibly changing the meaning of the proposition. For example, let (mathbb

*Tips on Reading Multiply-Quantified Propositions.* It is understandable that you would find propositions such as (x) difficult to read. The trick to deciphering these expressions is to “peel” one quantifier off the proposition just as you would peel off the layers of an onion (but quantifiers shouldn't make you cry!). Since the outermost quantifier in (x) is universal, (x) says that (z(a) : (exists b)_

Now consider (y ext<.>) To see that (y) is false, we peel off the outer quantifier. Since it is an existential quantifier, all that (y) says is that some positive real number makes (w(b)) : ((forall a) _

Another way of convincing yourself that (y) is false is to convince yourself that ( eg y) is true:

In words, for each value of (b ext<,>) there is a value for (a) that makes (a b
eq 1 ext<.>) One such value is (a=frac<1>**+1 ext<.>) Therefore, (
eg y) is true.**

** **

**Subsection 3.8.5 Proofs With Quantifiers**

Proving quantified statements often requires invoking one or more the following inference rules.

Existential Instantiation | ((exists x)(p(x)) Rightarrow p(c)) | (c in U) |

Existential Generalization | (p(c) Rightarrow (exists x)(p(x)) ) | (c in U) |

Universal Instantiation | ((forall x)(p(x)) Rightarrow p(c) ) | (c) is any arbitrary element of (U) |

Universal Generalization | (p(c) Rightarrow (forall x)(p(x)) ) | (c) is any arbitrary element of (U) |

The instantiation rules are used to fix a variable in a proposition over a universe to a single (but perhaps unspecified) value in order to apply the rules of propositional logic. The generalization rules are used to expand results from a fixed variable to the entire universe. Commonly in less formal proofs, such as those in mathematics, these are implied but not directly stated in the proof.

Formal proofs of quantified expressions can use all the techniques presented in sections Section 3.5 - Section 3.7 , plus these specialized forms:

###### Definition 3.8.10 . Constructive Proof.

Constructive proofs are used to prove theorems of the form: ((exists n)(p(n)) ext<.>) All that is needed is to find one value (c) for which (p(c)) is true and then invoke the Existential Generalization Rule.

###### Example 3.8.11 . A constructive proof.

Show that there is a positive integer that can be written as the sum of cubes of positive integers in two different ways:

Therefore by Existential Generalization it is true, there is a positive integer that can be written as the sum of cubes of positive integers in two different ways.

###### Definition 3.8.12 . Non-Constructive Proof.

Non-constructive proofs are also used to prove theorems of the form: ((exists n)(p(n)) ext<.>) Assume no (c) exists for which (p(c)) is true and show this leads to a contradiction.

###### Example 3.8.13 . A non-constructive proof.

Show that there exist irrational numbers (x) and (y) such that (x^y) is rational.

Take the negation of the conclusion: no such (x, y) exist.

We know that (sqrt<2>) is irrational.

There are two possibilities, (sqrt<2>^

If it is rational, we have two irrational numbers (x) and (y) with (x^y) rational.

In either case, we have a rational result, which contradicts our negated conclusion.(square)

###### Definition 3.8.14 . Proof of Non-Existence.

Non-Existence proofs are used to prove theorems of the form: ( eg (exists n)(p(n)) ext<.>) Using the equivalent form ((forall n) eg(p(n)) )) show that ((p(n))) is never true.

###### Example 3.8.15 . A non-existence proof..

Show that there is no number (x) such that (x^2 + 1 lt 0 ext<.>)

Then the whole statement can be written as: ( eg (exists x)(p(x)))

Equivalently: ((forall x) ( eg(p(x))))

Case 1: (x lt 0 ext<.>) Since multiplying two negatives, gives a positive, (x^2) is positive. Thus, (x^2 + 1) is also positive. Hence ( eg(p(x))) holds.

Case 2: (x = 0 ext<.>) Here (x^2 = 0 ext<.>) Thus, (x^2 + 1 = 1) is also positive. Hence ( eg(p(x))) holds.

Case 3: (x gt 0 ext<.>) Since multiplying two positives, gives a positive, (x^2) is positive.. Thus, (x^2 + 1) is also positive. Hence ( eg(p(x))) holds.

Therefore, by Universal Instantiation ((forall x) eg(p(x)) )square)

###### Definition 3.8.16 . Proof by Counterexample.

Counterexamples are used to show theorems of the form ((forall n)(p(n))) are false. All that is needed is to find one value (c) for which (p(c)) is false. That value is called a counterexample. ((forall n)(p(n))) is then false by Universal Instantiation. Counterexamples can also be used to prove statements with a negated universal quantifier ( eg (forall n)(p(n))) are true. This is done using the counterexample in a proof by contradiction on ((forall n)(p(n)))

###### Example 3.8.17 . A counterexample proof..

Show that every positive integer is the sum of the squares of 3 integers.

This can be rewritten as ((forall x)(p(x)) ext<,>) where (p(x)) is the statement "(x) is the sum of the squares of 3 integers" and (x in mathbb

ext<.>)

## A spiral workbook for discrete mathematics

This is a text that covers the standard topics in a sophomore-level course in discrete mathematics: logic, sets, proof techniques, basic number theory, functions, relations, and elementary combinatorics, with an emphasis on motivation. It explains and clarifies the unwritten conventions in mathematics, and guides the students through a detailed discussion on how a proof is revised from its draft to a final polished form. Hands-on exercises help students understand a concept soon after learning it. The text adopts a spiral approach: many topics are revisited multiple times, sometimes from a different perspective or at a higher level of complexity. The goal is to slowly develop students’ problem-solving and writing skills.

Open SUNY Textbooks is an open access textbook publishing initiative established by State University of New York libraries and supported by SUNY Innovative Instruction Technology Grants. This initiative publishes high-quality, cost-effective course resources by engaging faculty as authors and peer-reviewers, and libraries as publishing service and infrastructure. The pilot launched in 2012, providing an editorial framework and service to authors, students and faculty, and establishing a community of practice among libraries. Participating libraries in the 2012- 2013 pilot include SUNY Geneseo, College at Brockport, College of Environmental Science and Forestry, SUNY Fredonia, Upstate Medical University, and University at Buffalo, with support from other SUNY libraries and SUNY Press. More information can be found at http://textbooks.opensuny.org.

1.2 Suggestions to Students

1.3 How to Read and Write Mathematics

2.2 Conjunctions and Disjunctions

2.4 Biconditional Statements

3.1 An Introduction to Proof Techniques

3.4 Mathematical Induction: An Introduction

3.5 More on Mathematical Induction

3.6 Mathematical Induction: The Strong Form

4.2 Subsets and Power Sets

4.3 Unions and Intersections

5.1 The Principle of Well-Ordering

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.--title page verso

"This is a text that covers the standard topics in a sophomore-level course in discrete mathematics: logic, sets, proof techniques, basic number theory, functions, relations, and elementary combinatorics, with an emphasis on motivation. It explains and clarifies the unwritten conventions in mathematics, and guides the students through a detailed discussion on how a proof is revised from its draft to a final polished form. Hands-on exercises help students understand a concept soon after learning it. The text adopts a spiral approach: many topics are revisited multiple times, sometimes from a different perspective or at a higher level of complexity. The goal is to slowly develop students problem-solving and writing skills."--Open Textbook Library

Mode of access: World Wide Web

This bibliographic record is available under the Creative Commons CC0 "No Rights Reserved" license

Description based on online version, 2015 edition Title from PDF (viewed on July 26, 2016)

## Discrete Mathematics - Lecture 1.5 Nested Quantifiers

Nested quantifiers - Nested quantifiers are often necessary to express the meaning of sentences in English as well as important concepts in computer science and mathematics.

Example: “Every real number has an additive inverse” is ∀푥푥 ∃푦푦(푥푥 + 푦푦 = 0), where the domains of 푥푥 and 푦푦 are the real numbers.

Example: Translate into English the statement ∀푥푥∀푦푦((푥푥&lt 0)∧(푦푦&lt 0)→(푥푥푦푦&gt 0))

where the domains of 푥푥 and 푦푦 are the real numbers.

Examples: 1. Let 푃푃(푥푥,푦푦) be the statement “푥푥 + 푦푦 = 푦푦 + 푥푥” Assume that 푈푈 is the real numbers. Determine the truth value of ∀푥푥∀푦푦 푃푃(푥푥,푦푦) and ∀푥푥∀푦푦 푃푃(푥푥,푦푦).

- Let 푄푄(푥푥,푦푦) be the statement “푥푥 + 푦푦 = 0” Assume that 푈푈 is the real numbers. Determine the truth value of ∀푥푥∃푦푦푄푄(푥푥,푦푦) and ∃푦푦∀ 푥푥푄푄(푥푥,푦푦).

Example: L et U be the real numbers. Define P(x,y) : x · y = 0

What is the truth value of the following? 1. ∀x∀yP(x,y)

Example: Let U be the real numbers. Define P(x,y) : x / y = 1

What is the truth value of the following? 1. ∀x∀yP(x,y)

Study Table 1 on page 60 from 1.5!

Translating Mathematical Statements into Statements with Nested Quantifiers

Example: Express the following statement using mathematical and logical operators, predicates, and quantifiers. The domain consists of all integers.

The sum of two negative integers is negative.

The difference of two positive integers is not necessarily positive.

Translating Nested Quantifiers into English

Example: Translate the statement ∀x (C(x )∨ ∃y (C(y ) ∧ F(x, y)))

where C(x) is “x has a computer,” and F(x,y) is “x and y are friends,” and the domain for both x and y consists of all students in your school.

Example: Translate the statement ∃x∀y ∀z ((F(x, y)∧ F(x,z) ∧ (y ≠z))→¬F(y,z))

More Practice with Nested Quantifiers

Suppose the variable 푥푥 represents students, 푦푦 represents courses, and 퐶퐶(푥푥,푦푦) means “푥푥 is taking 푦푦”. Match each sentence to one or more logical statements. 1. Every course is being taken by at least one student. 2. Some student is taking every course. 3. No student is taking all courses. 4. There is a course that all students are taking. 5. Every student is taking at least one course.

## 1.5. Standard axiom systems and models

- The natural numbers ℕ. These are defined using the Peano axioms, and if all you want to do is count, add, and multiply, you don't need much else. (If you want to subtract, things get messy.)
- The integers ℤ. Like the naturals, only now we can subtract. Division is still a problem.
- The rational numbers ℚ. Now we can divide. But what about √2?
- The real numbers ℝ. Now we have √2. But what about √(-1)?
- The complex numbers ℂ. Now we are pretty much done. But what if we want to talk about more than one complex number at a time?

In practice, the usual way to do things is to start with sets and then define everything else in terms of sets: e.g., 0 is the empty set, 1 is a particular set with 1 element, 2 a set with 2 elements, etc., and from here we work our way up to the fancier numbers. The idea is that if we trust our axioms for sets to be consistent, then the things we construct on top of them should also be consistent (although if we are not careful in our definitions they may not be exactly the things we think they are).

## Grouping ¶ &uarr

Parentheses also *group* the terms they enclose, allowing them to be quantified as one *atomic* whole.

The pattern below matches a vowel followed by 2 word characters:

Whereas the following pattern matches a vowel followed by a word character, twice, i.e. [aeiou]w[aeiou]w : 'enor'.

The (?: … ) construct provides grouping without capturing. That is, it combines the terms it contains into an atomic whole without creating a backreference. This benefits performance at the slight expense of readability.

The first group of parentheses captures 'n' and the second 'ti'. The second group is referred to later with the backreference 2 :

The first group of parentheses is now made non-capturing with '?:', so it still matches 'n', but doesn't create the backreference. Thus, the backreference 1 now refers to 'ti'.

### Atomic Grouping ¶ &uarr

Grouping can be made *atomic* with (?> *pat* ) . This causes the subexpression *pat* to be matched independently of the rest of the expression such that what it matches becomes fixed for the remainder of the match, unless the entire subexpression must be abandoned and subsequently revisited. In this way *pat* is treated as a non-divisible whole. Atomic grouping is typically used to optimise patterns so as to prevent the regular expression engine from backtracking needlessly.

The " in the pattern below matches the first character of the string, then .* matches *Quote“*. This causes the overall match to fail, so the text matched by .* is backtracked by one position, which leaves the final character of the string available to match "

If .* is grouped atomically, it refuses to backtrack *Quote“*, even though this means that the overall match fails

## Math 135 Course Notes - Shane Bauman

These course notes are meant to accompany the lectures of MATH 135 at the University of Waterloo. A number of faculty members in Mathematics have contributed to the writing and preparation over a number of years.

This version is a revision for first use in Fall 2018.

is true, we would need to prove that the inequality holds for every possible choice ofn. Verifying the inequality for values ofnone at a time is not an effective way to proceed. The methods of proof that we will learn in this course will allow us tolearn how to handle situations of this type, and avoid simply verifying that some fact is true for every element of a given set. In Example 2, we are saying that the inequalitya 2 + 29a+ 209≤0 holds for at least one choice of the integera. For example, whena= 0, we havea 2 +29a+209 = 209, and clearly 209 >0, so the inequality does not hold in this case. Trying again witha= 5, we have a 2 + 29a+ 209 = 379, and clearly 379>0, so the inequality does not hold in this case either. Trying once more witha=−5, we havea 2 + 29a+ 209 = 89, and 89>0, so again the inequality does not hold in this case. How long should we try valuesofaat random? In order to prove that this result is true, we would only need to find onevalue ofafor which the inequality holds. However, as for Example 1 above, checking the inequality for values ofaone at a time is not in general an effective way to proceed. The methodsof proof that we will learn in this course will also allow us to precisely handle situations of this slightly different type.

#### 1.2 Sets

The mathematical results in Examples 1 and 2 involve the integers, which collectively form aset. Sets are fundamental in mathematics, and the way in which we refer to them forms an important part of the language of mathematics.

Asetis a well-defined, unordered collection of distinct objects. Each object that appears in this collection is called anelement(ormember) of the set.

Sets can contain any type of object. Since this is a mathematics course,we frequently use sets of numbers. But sets could contain letters, the letters of thealphabet for example, or books, such as those in a library collection. The simplest way to describe a set is to explicitly list all of its elements between a pair of brace brackets,

Example 3 The following are examples of sets:

< 2 , 4 , 6 , 8 >contains all the positive even numbers less that 10.

< 1 , 2 ,< 1 , 2 , 3 >>is a set that contains three elements: 1, 2 and the set< 1 , 2 , 3 >. Note that the set< 1 , 2 , 3 >is considered a single element of< 1 , 2 ,< 1 , 2 , 3 >>, even though < 1 , 2 , 3 >contains three elements itself.

<♣,♦,♥,♠>contains the symbols of the four suits in a deck of playing cards.

The set ofnatural numbers, denoted byN, lists all the positive integers. That is,

Note that this notation is not used consistently - in some parts of Mathematics and Computer Science the symbolNmeans the set of non-negative integers< 0 , 1 , 2 , 3 . .>.

8 Chapter 1 Introduction to the Language of Mathematics

The set ofintegers, denoted byZ, lists all integers, whether they are negative, zero, or positive. That is,

The set ofrational numbers, denoted byQ, contains all numbers of the formab, whereais an integer andbis a non-zero integer.

The set ofreal numbers, denoted byR, contains all numbers in decimal form.

Many of the mathematical results that we will encounter in this courseconcern the specially designated setsN,Z,QandRdescribed above. Except for these specially designated sets, usually we will use uppercase letters (S, T, U, etc.) to represent sets and lowercase letters (x, y, z, etc.) to represent elements of those sets. Ifxis anelement ofthe setS, we write x∈S. Ifxis not an element of the setS, we writex6∈S.

Example 4 The following examples show how this notation is used:

LetT=< 1 , 2 ,< 1 , 2 , 3 >>. In this case, 1∈T, 2∈Tand< 1 , 2 , 3 >∈T, but 3∈/T.

We have 3∈Nand 8∈N, but− 3 ∈/Nand 83 ∈/N.

#### 1.3 Mathematical Statements and Negation

The mathematical results in Examples 1 and 2 are written as sentencesasserting that some mathematical facts hold. We say that these results are mathematicalstatements.

Astatementis a sentence that has a definite state of being either true or false.

Example 5 Here are some examples of sentences that are statements of a particularlysimple type.

2 + 3 = 6. (A false statement.)

2 is a rational number. (A false statement.)

The mathematical results that we will encounter in this course are assertions that some statement is true. When reading such a statement, we should realize that what is being said has to be either true or false (but cannot be both), even if we do notknow the truth value of that statement.

10 Chapter 1 Introduction to the Language of Mathematics

#### 1.4 Quantifiers and Quantified Statements

1.4.1 Universal and Existential Quantifiers

Having seen some of the simplest types of statements in the previoussection, we now turn to the more complicated types of statements that we will typically encounter in this course. Recall the mathematical results given in Examples 1 and 2.

For all integersn≥5, 2 n> n 2.

There exists at least one integerasuch that

The above sentences are examples of quantified statements. Both statements involve a variable, “n” in the first example, and “a” in the second example. Both sentences involve a set, called thedomainof the quantified statement, which is the set< 5 , 6 , 7 . .>for the first sentence, and the set of all integersZfor the second. The domain specifies the possible choices for the variable in each case. Both sentences contain an inequality involving the variable. These inequalities are

2 n> n 2 and a 2 + 29a+ 209≤ 0 ,

respectively. Neither of these inequalities is a statement by itself whether 2n> n 2 is true or false cannot possibly be determined, sincenis avariable. However, once we specify a value for the variablen, then the inequality is definitely true or false. For example, when n= 6 we have 2n= 2 6 = 64, andn 2 = 6 2 = 36, so the inequality is true forn= 6 since 64 >36. Similarly, the inequalitya 2 + 29a+ 209≤0 is not a statement by itself because whether it is true or false cannot be determined, sinceais a variable. But whena=−1 we havea 2 + 29a+ 209 = 181, so the inequality is false fora=−1 since 181>0. Each of the inequalities above is called anopen sentence – a sentence that contains a variable, where the truth of the sentence is determined by the value of the variable chosen from the domain of the variable (and, technically, the question of truthhas no meaning unless a value for the variable is specified). Finally, the variablesnandaabove have been introduced through the phrases “for all” and “there exists”, respectively. Such phrases are calledquantifiers, and they describe “how many” elements of the domain are claimed to make the open sentence true. In this course, we will only consider these two types of quantifiers: theuniversal quantifier(“for all”), and theexistential quantifier(“there exists”).

REMARK To summarize the above discussion, aquantified statementcontains four parts:

aquantifier(universal, or existential)

avariable(any symbol representing a quantity or mathematical object)

Section 1.4 Quantifiers and Quantified Statements 11

anopen sentenceinvolving the variable (that is either true or false whenever a value of the variable chosen from the domain is specified).

To help us to be completely precise when dealing with quantified statements, as well as to be compact when it is helpful, we now introduce some new mathematical symbols and notation: the symbol ∀is used to denote the universal quantifier, and the symbol∃is used to denote the existential quantifier. We letP(x) denote an open sentence involving the variablex. The way in which these symbols are used, together with set notation,is described in the following definition.

Definition 1.4. quantified statement

We consider two types of quantified statements.

We read the above quantified statement as “For allxinS,P(x) is true” or simply as “For allxinS,P(x)”. This quantified statement is true whenP(x) is true for every elementxin the set S, and this quantified statement is false otherwise. In terms of the terminology above, for this quantified statement, thequantifier is universal, thevariableisx, thedomainisS, and theopen sentenceisP(x).

We read the above quantified statement as “There exists at least one valueofxinS for whichP(x) is true” or simply as “There exists anxinSsuch thatP(x)”. This quantified statement is true whenP(x) is true for at least one elementxin the set S, and this quantified statement is false otherwise. In terms of the terminology above, for this quantified statement, thequantifier is existential, thevariableisx, thedomainisS, and theopen sentenceisP(x).

The use of the capital letter “P” for the open sentenceP(x) is because we often think of the truth ofP(x) as representing the fact thatxhas “property”P.

Example 8 Using this notation, the mathematical results in Examples 1 and 2 discussed above can be written as the following quantified statements.

Section 1.4 Quantifiers and Quantified Statements 13

For all integersx≥5, 2x> x 2.

For each positive integertin< 5 , 6 , 7 . .>, 2t> t 2.

For any integern≥5, 2n> n 2.

Letmbe a positive integer that is at least 5. Then 2mis greater thanm 2.

2 x> x 2 for all integersx≥5.

Note that in the last statement above, we even changed the order of the sentence so that the open sentenceP(x) came first. Similarly, the following statements all have the same meaning as theexistentially quantified statement “∃x∈Z, x 2 + 29x+ 209≤0” in Example 8 above.

There exists an integerxfor whichx 2 + 29x+ 209≤0.

There is an integernsuch thatn 2 + 29n+ 209≤0.

For some integery,y 2 + 29y+ 209≤0.

For at least onea∈Z,a 2 + 29a+ 209≤0.

x 2 + 29x+ 209≤0 for some integerx.

In this course, the way in which quantified statements are writtenwill vary, so students will get a lot of practice in translating the English sentences used in this text into their precise mathematical meaning.

1.4.3 Negation of Quantifiers

In the table below, we summarize what we learned about when quantifiedstatements are true or false in Definition 1.4.1.

Quantified Statement True False ∀x∈S, P(x) whenP(x) is true whenP(x) is false for for everyx∈S at least onex∈S ∃x∈S, P(x) whenP(x) is true for whenP(x) is false at least onex∈S for everyx∈S

Recall that the negation of any statement is true exactly when the statement itself is false. To apply this point of view to quantified statements, look at the rightmost column in the Table above. Then we immediately obtain the following rules fornegationof quantified statements.

“There exists somex∈Sfor whichP(x) is false.”

14 Chapter 1 Introduction to the Language of Mathematics

Similarly to (1.1), we can write this symbolically as the logical equivalence

noting that the statements on both sides of the “≡” sign have the same truth values for all possible choices of domainsS, and open sentencesP(x).

Again similarly to (1.1), we can write this symbolically as the logical equivalence

once again noting that the statements on both sides of the “≡” sign have the same truth values for all possible choices of domainsS, and open sentencesP(x).

#### 1.5 Nested Quantifiers

Most of the statements that we will see in this course are quantified statements with more than one quantifier, each quantifier associated with a variable and a domain. The quantifiers in a statement containing more than one quantifier are callednested quantifiers. It is crucial to note the order in which nested quantifiers appear, and to understand how different orders can radically change the mathematical meaning of these statements. For example, consider the statement with two nested quantifiers

A statement like this is read from left to right: “For all real numberss, there exists a real numbertsuch thatt > s.” To see how the order matters, we can think about this as playing a game with two players, one for each variable, say player “S” for variables, and player “T” for variablet. PlayerSgoes first, and announces their value for the real numbers. Then playerTgoes second, and responds by choosing a value for the real numbert. Hence playerTknows playerS’s value forsbefore they make their choice, and can take advantage of that knowledge when choosing a value fort. For the statement (1.4) to be true, player T must be able to make a choice oftsuch thatt > sis true, for every values∈Rthat could be chosen by playerS. Of course playerT can always choose a real numbertsuch thatt > sis true, since they know the value ofsbefore they make their choice (for example, playerT could chooset=s+ 1), no matter what that real numbersis. This means that statement (1.4) is true. Now consider the related statement with two nested quantifiers

This is almost identical to statement (1.4), except that the order of the two quantifiers has been switched. Statement (1.5) says: “There exists a real numbert, such that for all real numberss, we havet > s.” In terms of a game with two players, here playerT goes first,

16 Chapter 1 Introduction to the Language of Mathematics

Again, we read statement (1.6) from left to right, beginning with the leftmost quantified variablex. We then regard the rest of the statement as an open sentence depending on the choice ofx, and proceed through the rest of the statement in a similar manner, parsing it in layers, like an onion. The following parenthesized version of (1.6)might be helpful in identifying the “layers”:

For instance, the quantified statement in (1.6) above can be written as follows. ∃x∈X, P(x), where P(x) is ∀y∈Y, Q(x, y), where Q(x, y) is ∃z∈Z, R(x, y, z).

Here, we think of the quantifier∀y∈Y as being “nested” within the open sentenceP(x), and the quantifier∃z∈Zas being “nested” within the open sentenceQ(x, y). This is why we refer to the quantifiers in a statement with more than one quantifier as beingnested (like the parentheses are nested in (1.7)). A useful way to think about nested quantifiers is in terms of the nested loops that are used in computer programming.

REMARK One very important setting in which nested quantifiers appear in mathematics is the study of limits in calculus. For example, consider the following definition of the limit: Letf be a function and leta∈ R. We say thatf haslimitLasx approachesa, or thatLis the limit off atx=a, if for any positive toleranceǫ > 0 , we can find a cutoff distanceδ > 0 such that if the distance fromxtoais less thanδ, and ifx 6 =a, thenf(x) approximatesLwith an error less thanǫ. That is, if 0 <|x−a|< δ, then|f(x)−L|< ǫ. We won’t say anything further about limits themselves here, but will note how to write the above definition in the notation of this section. First, letR+denote the set of all positive real numbers. The definition above says that thelimitoff approachingais equal toLexactly when the following quantified statement is true:

whereQ(ǫ, δ, x)is the open sentence: If 0 <|x−a|< δ, then|f(x)−L|< ǫ. The open sentenceQis a special type of sentence called animplication, that we will study in Chapter 2. Here we’ll consider only the left to right order of the nested quantifiers in (1.9), particularly for variablesǫandδ. In terms of the two player game we have used to discuss nested quantifiers, the definition says that the arbitrary value for the universally quantified variableǫis knownbeforea value for the existentially quantified variableδis chosen. Hence the value ofδcan depend on the value ofǫ. Indeed, finding an appropriate choice ofδin terms ofǫis a key part in typical proofs of limits using theǫ−δdefinition in calculus.

1.5.3 Negation of Nested Quantifiers

So far, we have learned how to negate quantified statements with a single quantifier (and single variable). We have also learned how to interpret quantified statements with nested

Section 1.5 Nested Quantifiers 17

quantifiers - more than one quantifier (and more than one variable) in a givenleft to right order. Negating a statement with nested quantifiers needs to be done with care - the order of the quantifiers is very important. However, it is straightforward ifwe simply negate each quantifier layer-by-layer starting from the left. For example, consider the statement in (1.6), which was written in layers in (1.8). Using the rules (1.2) and (1.3) for negating quantified statements, logically equivalent expressions for the negations of these three layers are easily obtained, given below.

## Passage to Abstract Mathematics

Here’s a quote from the preface of a book that was published in 1967:

At the present time, the average undergraduate mathematics major finds mathematics heavily compartmentalized. After calculus, he takes a course in analysis and a course in algebra. Depending on his interests (or those of his department), he takes courses in special topics…The exciting revelations that that there is some unity in mathematics, that fields overlap, that techniques of one field have applications in another, are denied the undergraduate.

And the following passage is contained in the preface of the book under review:

Too often in an undergraduate mathematics curriculum, each course or sequence is taught as a discrete entity, as though the intersection of its content with the content of other courses or sequence were empty.

So, after a period of 44 years, it seems that the problem of the compartmentalized mathematics curriculum is still a cause of concern for at least a few of those involved in the teaching of the subject. The authors of this book clearly belong to this minority.

But the contents of this book are very different to that written by Singer and Thorpe — although the underlying philosophy is the same. Here, the foundations are provided for the later study of topics such as algebra, analysis and topology, and readers are simultaneously led to see mathematics as a way of knowing. In other words, there is a good balance between process and content.

The content is centred upon logic, proof, sets, relations and functions. Methods of proof are explored, and deeper ideas such as cardinality and infinity introduced. The book concludes with a short chapter called ‘Algebraic Systems’, with the notion of binary operation being introduced by means of examples previously discussed. These include logical connectives, set operations, function composition and the number operations. The text is nicely balanced between expository narrative, examples, illustrations and exercises, and the book as a whole is not overloaded with content. Consequently, it makes for pleasurable and informative reading.

In general, I think that this book provides a very useful first step into ‘abstract mathematics’, because many essential concepts, and the vocabulary and notation that represent them (e.g., quantifiers), are systematically developed. The exercises are of varying degrees of difficulty, but the authors have deliberately provided no solutions or hints.

In conclusion, I would like to make two minor observations regarding the contents. Firstly, as with many books that introduce symbolic logic, I could find no explicit discussion of the validity of an argument. That is to say, an argument is valid if the conjunction of the premises implies the conclusion, which is a very useful framework in which to embed ideas of mathematical proof. Secondly, the concepts of binary operation and algebraic systems require a wider range of examples than is possible to provide in a book of this size. However, when students subsequently encounter topics like geometric transformations, matrices and vector spaces etc, they will have a much wider range of examples to draw upon.

Overall, I feel that this book is highly suited to the purpose referred to in its title.

As an undergraduate student in 1962, **Peter Ruane** greatly benefitted from a book with a similar aim to this one. It was *Finite Mathematical Structures*, by Mirkil, Kemeny, Snell and Thompson — possibly the first ever text written for foundation course.

## Instructor: Anatolii Grinshpan Office hours: MWF 10-10:50, Korman 247, or by appointment, Korman 253.

Apr 1. Introduction to the course. The logical framework. Truth tables.

Reading and exercises: 1.1-1.3, 3.1-3.3. Homework 1 (due Monday, April 8).

Apr 3. Tautology and contradiction. Logical equivalences. Converse and contrapositive.

Reading and exercises: 3.4, 3.5.

Apr 5. Sets. Operations on sets. Empty set. Existential and universal quantifiers.

Reading and exercises: 1.4-1.7, 2.1-2.4, 3.6, 3.7. Modus ponens.

Apr 8. Natural numbers: axioms. The principle of induction.

Reading and exercises: 4.1-4.3. Homework 2 (due Monday , April 15).

Apr 10. Examples of inductive proofs. Reading and exercises: 4.4.

Apr 12. Quiz 1 (4.1 - 4.3). Strong induction. QED .

Apr 15. Recursive definitions and relations. Reading and exercises: 4.5-4.9.

Apr 17. Functions. Composition. Reading and exercises: 5.1-5.5. Homework 3 (due Monday , April 22).

Apr 19. Quiz 2 (5.1 - 5.4). The identity function. The inverse function.

Apr 22. Pigeonhole principle. Examples. Reading and exercises: 6.1, 6.2, 6.4. Homework 4 (due Monday, April 29).

Apr 24. Monotone sublists. Size of a set. Reading and exercises: 6.2, 6.3.

Apr 26. Quiz 3 (6.1 – 6.4). Infinite sets. Reading and exercises: 6.5-6.7.

Apr 29. Midterm 1 (Chapters 1 - 6). Homework 5: none.

May 3. Relations on a set. Equivalence relations. Reading and exercises: 7.1-7.3.

May 6. Equivalence classes. Homework 6 (due Monday , May 13).

May 8. The construction of integers. Reading and exercises: 7.4, 7.5. Question.

May 10. Quiz 4 (7.1 - 7.3). Least and greatest members. Reading and exercises: 7.6, 7.7.

May 13. Quotient and remainder. Reading and exercises: 8.1, 8.2. Homework 7 (due Monday, May 20).

May 15. The Euclidean algorithm. Reading and exercises: 8.3, 8.4.

May 17. Quiz 5 (8.1 – 8.4). A property of the greatest common divisor.

May 20. The fundamental theorem of arithmetic . Reading and exercises: 8.5-8.7. Homework 8: none.

May 22. Rational numbers. Enumeration . Reading and exercises: 9.1, 9.2, 9.7.

May 24. Quiz 6 (8.4 – 8.6). Decimal expansions. Reading and exercises: 9.3.

May 28. *Questions session: 8:30-9:30AM, Korman 245* .

May 29. Midterm 2 (6.5 – 9.3 and Theorem 9.7.1)

May 31. Cantor’s theorem . Reading and exercises: 9.7. Homework 9 (due Friday, June 7).

June 3. Real numbers and sets of natural numbers as binary strings. Reading and exercises: 9.4.

June 5. Sperner’s lemma. Rational approximation to square roots. Reading and exercises: 9.5, 9.6, 9.8

## Math 299 – Spring 2021: Training Workouts

Below are all of the Training Workouts for Math 299 – Spring 2020 to date. For the most recent Training Workout and additional information see the Math 299 Home Page.

Welcome to Math 299. I will post assignments and announcements here throughout the semester. Check back frequently. Below are links to some resources we will be using in the course.

- on your laptop and send me the email address you used for your Dropbox account if you haven’t done so already.
- Read the course syllabus (see below). Let me know if you have any questions.
- Read Problem #1 on the 2021 Prove it! admissions test and then play the Scrambler! Product Catalog game until you figure out how to reliably beat any goal on all three machines (Juggler, Frogger, Whirligig). You do not have to answer parts (a)-(f) of the question or hand in anything, but you should try figure out a strategy that is guaranteed to beat all three machines no matter what goal comes up when you select “New Goal”. I will ask you in class how to solve each machine. Virtual prize cookies may be awarded.

**0.**For each assignment that you hand in in Dropbox, make a folder called “Assignement #n”, where n is the Assignment number I have posted here. So for this assignment, put it in a subfolder of our shared Dropbox folder called “Assignment #1” and put your documents in there. All assignments must be handed in prior to class on the day they are due. Be sure to name your files as explained in the syllabus below.**1.**Answer Problem #5 at the end of Chapter 1 in the lecture notes. Type up your answer (you can use any editor for this assignment) and save your file to Dropbox as described above.**2.**Try to figure out how to consistently beat Trix Game. This is another example of a Toy Proof system. I’ll ask for volunteers in class. Cookies may be awarded.

- Reminder: For each assignment that you hand in in Dropbox, make a folder called “Assignement #n”, where n is the Assignment number I have posted here. So for this assignment, put it in a subfolder of our shared Dropbox folder called “Assignment #2” and put your documents in there. All assignments must be handed in prior to class on the day they are due. Be sure to name your files as explained in the syllabus below.
**1.**Prove each of the following Circle-Dot theorems. You must use the Toy Proof software to ensure that your proofs are correct. Prove them using the software, and then print that web page to a PDF document and place that pdf document in your Dropbox homework folder with the appropriate file name. If you put one pdf for each problem below, name the files so I know which one is which.**Thm H**$ulletigcircullet$**Thm J**$igcircigcircigcirc$**Thm M**$igcircigcirculletulletullet$**Thm R**$ulletigcirculletigcirculletigcirc$

**1.**Answer questions 2.1, 2.2, and 2.3 in the lecture notes. You can type up your answers using any editor or write them by hand on paper. Either way scan or print your document to a pdf and put it in the appropriate folder in Dropbox.

**0. Memorize the rules inference for Propositional Logic**in Section 4.2 of the lecture notes (in your Dropbox folder). We will have a quiz in class on Tuesday where you will be asked to recall them entirely from memory. (Memorize the template forms in the second table.)**1. Type up a Formal proof of each of the following statements.**You can only use the rules of Propositional Logic discussed in class. To do that, start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document . For each theorem, first state the theorem, then give a proof of it directly below it as I did in the examples in class. Number each statement in the proof, and give a reason for every statement (except Assumptions, which need no reason). Use the auto-numbered list in the Lurch to number the lines – don’t type the line numbers by hand. Be sure to give the line numbers for the statements used as the premises (i.e. inputs) immediately after the reason. Use the TAB key to indent your assumptions, and also to line up your reasons in a separate column. Do all of your work in Lurch. You do not have to use Lurch to check your work on this assignment, but you can if you want to. If you have questions, just let me know. Put your assignment in Dropbox in a folder for Assignment 4. Save it as a .lurch file (not a pdf) so I can type in it and leave comments and grades.**a.**$Q Rightarrow Q ext < and >Q$**b.**$Q Rightarrow Q ext < or >P$**c.**$Q Rightarrow (P Rightarrow Q)$**d.**$P Leftrightarrow eg eg P$**e.**$ eg ( eg P ext < and >P )$

**0.**Memorize the rules inference for Propositional Logic in Section 4.2 of the lecture notes (in your Dropbox folder). We may have a quiz in class on Thusday where you will be asked to recall them entirely from memory. (Memorize the template forms in the second table.)Type up your formal proofs in Lurch. Use the formal style we used in class – numbered lines, one statement per line, and a reason and premises stated for each line that needs one. You can only use the rules of propositional logic and the copy rule. Start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document . No other rules and no other theorems. Put your files in your Dropbox folder in a subfolder named “Assignment 5” and name your files “Assignment 5 – firstname.lurch”.**1. Prove each of the following tautologies**.**a. Easy warm up:**$R Rightarrow (Q Rightarrow (P ext < or >Q))$**b. Anything follows from a contradiction:**$ ightarrowleftarrow Rightarrow P$**c.****Associativity of ‘or’:**$(P ext < or >Q) ext < or >R Leftrightarrow P ext < or >(Q ext < or >R)$**d.****DeMorgan’s Law 2:**$ eg (P ext < and >Q) Rightarrow eg P ext < or > eg Q$

**1. Prove each of the following tautologies.**Type up your formal proofs in Lurch. Use the formal style we used in class – numbered lines, one statement per line, and a reason and premises stated for each line that needs one. You can only use the rules of propositional logic and the copy rule. Start your new document by using the Lurch menu File > Choose Topic.. > Logic > Propositional Logic > Blank Document . No other rules and no other theorems. Put your files in your Dropbox folder in a subfolder named “Assignment 6” and name your files “Assignment 6 – firstname.lurch”. Since Lurch may bog down if you ask it to check this many proofs in one document, you can make more than one Lurch document, with the filename indicating which problem(s) it contains and put them all in the Assignment 6 folder.**a. Easy peasy:**$P ext < and >Q Leftrightarrow Q ext < and >P $**b. An or- warm up:**$P ext < or >Q Rightarrow Q ext < or >P $**c. Excluded middle:**$P ext < or > eg P$**d. Alternate definition of implies:**$P Rightarrow Q Leftrightarrow eg P ext < or >Q $**e. Distributivity of ‘or’ over ‘and’:**$P ext < or >(Q ext < and >R) Leftrightarrow (P ext < or >Q) ext < and >(P ext < or >R) $**f. Alternate OR- rule:**$(P ext < or >Q) ext < and > eg P Rightarrow Q$

**1. Memorize the rules**for quantifiers ($forall$, $exists$) in Template form from the lecture notes for a possible quiz in class on Thursday.**2. Prove each of the following theorems.**Type up your formal proofs in Lurch. Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one. You can only use the rules of propositional logic and predicate logic (no other rules and no other theorems even if they are available in Lurch). You should use the rules from Logic > Predicate Logic > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). Put your files in your Dropbox folder in a subfolder called ‘Assignment 7’.**a. Existence warmup:**$(exists x,Q(x))Rightarrow (exists x,P(x)Rightarrow Q(x)).$**b. Mini-DeMorgan’s Law:**$(forall x, eg P(x)) Rightarrow ( eg exists y, P(y))$

**Midterm Exam Fun!**In your Dropbox folder there is a new subfolder named, ‘midterm’ and in that subfolder there is a file named Midterm Exam.lurch . Make a backup copy of that file to start, and name that copy Firstname midterm.lurch where you replace Firstname with your first name.

Open that file in Lurch and answer all of the questions. You should type all of your answers in Lurch. You do not have to bubble anything, but you can if you want to. If your Lurch file starts to get too large you can make several copies of the file and put one or more proofs in each file. Clearly name the files so I know which problems are in which files. You should only use the rules from Logic > Predicate Logic with Equality > Blank Document topic in your lurch file (select it from the File> Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button) if you make a new file. Put all of your files in your Dropbox folder in the ‘midterm’ subfolder.

The exam is due in Dropbox on Thursday, March 11, 2021 at 6:00pm Eastern (i.e., at the start of class). You can (and should) do all of your work in the Dropbox folder as drafts. I won’t grade anything before it is due.

As this is a take-home midterm, no collaboration is allowed on this assignment. You must all complete it individually without discussing it with anyone else (including each other, tutors, and other instructors). You cannot use any internet resources, discuss the problems online on Discord servers, chat rooms, Stack Exchange, email, text, Facebook, or any other form of communication. You cannot look up proofs or definitions or other math facts online, or use any resources other than those in our course. Any cheating on the midterm will result in failing the entire course, not just the midterm exam itself.

You can use our lecture notes, my handwritten lecture notes from class, Lurch, and any previous examples and homework assignments from this semester that are in the Dropbox folder that you are currently sharing with me. You can also ask me anything you want, and I will decide if I want to answer it.

It is a long exam, so I suggest you start working on it now. Enjoy!

**1. Answer Problems 5.23 parts j, k, and l**from the lecture notes in a lurch document in your Assignment #8 folder in Dropbox (it can be in the same document as the other problems below).**2. Prove each of the following theorems.**Type up your formal proofs in Lurch. Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one. You can only use the rules of propositional logic and predicate logic with equality (no other rules and no other theorems even if they are available in Lurch). You should use the rules from Logic > Predicate Logic and Equality > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). Put your files in your Dropbox folder in a subfolder called ‘Assignment 8’.**a. If everyone loves everyone else then everyone loves themself:**$(forall x,forall y, L(x,y)) Rightarrow forall z, L(z,z)$**b. Equivalent Predicates:**$(forall x,P(x) Leftrightarrow Q(x)) Rightarrow ((exists x,P(x))Rightarrow (exists x,Q(x)))$**c. Excluded Middle:**$(forall x,P(x)) ext < or >(exists x, eg P(x))$**d. If not the one, the other:**$(forall x, P(x) ext < or >Q(x)) ext < and >(exists y, eg P(y)) Rightarrow (exists z, Q(z))$

**Prove each of the following theorems.**Type up your formal proofs in Lurch. Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one. You can only use the rules of propositional logic and predicate logic with equality (no other rules and no other theorems even if they are available in Lurch). You should use the rules from Logic > Predicate Logic and Equality > Blank Document topic in your lurch file (select it from the File>Choose Topic menu and check the both boxes at the bottom of the dialog before clicking the OK button). Put your files in your Dropbox folder in a subfolder called ‘Assignment 9’.**1. Not if and only if:**$ig(exists y,forall x,L(x,y)ig)Rightarrow ig(forall x,exists y,L(x,y)ig)$**2. Easier than it looks:**eginBig(forall x,ig(exists y,L(x,y)ig) Rightarrow ig(exists z,L(z,x)ig)Big) Rightarrow qquad Big(forall x,ig(forall z, eg L(z,x)ig) Rightarrow ig(forall y, eg L(x,y)ig)Big) end

**Prove each of the following theorems.**Type up your formal proofs in Lurch. Use the formal style we have been using – numbered lines, one statement per line, and a reason and premises stated for each line that needs one. Unfortunately, Lurch does not have the Peano Axioms built-in, so you can’t use it to check your proofs (but you can use it to check the logic steps). Put your files in your Dropbox folder in a subfolder called ‘Assignment 10’.**1. not quite as cool, but close:**+1=1$**2. alternate definition of sigma:**$forall n,sigma(n)=n+1$**3. no number is it’s own successor:**$forall n,n eq sigma(n)$**4. left additive identity:**$forall n,0+n=n$

**Prove each of the following theorems.**Type up your semiformal proofs in Lurch. Use the semiformal style illustrated in class – unnumbered lines, one statement per line, and a reason for each line that needs one. Use the shortcut versions of the Peano Axioms in the table in section 7.3 of the lecture notes, rather than the formal versions in section 7.1. You can (and should) use the shortcut of using rules derived from previously proven theorems. When proving theorems in the problem set at end of chapter 7 you can use any earlier numbered theorem as a rule of inference to help you prove a later numbered theorem (but not the other way around, unless you prove it first). You can also prove any theorems we proved in class or that were assigned in a previous homework assignment as a rule of inference (or rules derived from them) in your proofs. For induction proofs, use the version of the induction templat (N4) that has you show $P(sigma(k))$ rather than the one that has you show $P(k+1)$ because the latter one needs parentheses that will only confuse you. Unfortunately, Lurch cannot check a semi-formal proof because it doesn’t know how to handle the shortcuts. Put your file in your Dropbox folder in a subfolder called ‘Assignment 11’.**7.5 (**$forall m,forall n,forall p, m+(n+p)=(m+n)+p$*associativity of addition*)

(Hint: try $forall+$ for $m$ and $n$ but induction for $p$.)**7.12 (**$forall n,1cdot n=n ext < and >ncdot 1=n$ (Hint: try induction on $n$ and remember you can use previous problems as rules [7.1-7.11].)*multiplicative identity*)

**Prove each of the following theorems.**Type up your semiformal proofs in Lurch. Use the semiformal style illustrated in class. When proving theorems in the problem set at end of chapter 7 you can use any earlier numbered theorem as a rule of inference to help you prove a later numbered theorem (but not the other way around, unless you prove it first). You can also prove any theorems we proved in class or that were assigned in a previous homework assignment as a rule of inference (or rules derived from them) in your proofs. Put your file in your Dropbox folder in a subfolder called ‘Assignment 12’.**7.23 (**$forall n,nleq n$*reflexivity of $leq$*)**7.35 (**$forall m,1mid m ext< and >mmid m$*every number divides itself*)**7.8 (**$forall m,forall n, m+n=n+m$*commutativity of addition*)**7.38 (**$forall m,forall n,forall p,pmid m ext < and >pmid nRightarrow pmid (m+n)$*common divisors divide sums*)**7.22 (**$forall m,forall n, mlt n Leftrightarrow sigma(m)leq n$*minimum difference*)**7.31 (**$forall b,b eq 0Rightarrow forall m,forall n,forall r, bcdot m=bcdot n+r Rightarrow exists p, r=bcdot p$*divisibility of differences*)

**Prove each of the following theorems.**Type up your semiformal proofs in Lurch. Use the semiformal style illustrated in class. When proving theorems from the lecture notes, you can use earlier theorems as a rule of inference to help you prove a later theorems (but not the other way around). You can also use any theorems we proved in class or that were assigned in a previous homework assignment as a rule of inference (or rules derived from them) in your proofs. Put your file in your Dropbox folder in a subfolder called ‘Assignment 13’. Notice that we are starting to use the ‘Given’ style of stating the theorems (compare the wording of the theorems below from chapter 7 to what is in the lecture notes).**1. Theorem 8.2(a) (**If $z$ is a natural number then $z^1=z$.*Power law*)**2. Theorem 7.10 (**For all natural numbers $m$, $n$, and $p$, if $m+p=n+p$ then $m=n$.*cancellation law for addition*)**3. Theorem 7.17 (**For all natural numbers $m$ and $n$, if $m eq 0$ and $mcdot n=0$ then $n=0$.*zero divisors*)**4. Theorem 7.24 (**For all natural numbers $m$ and $n$, if $mleq n$ and $nleq m$ then $m=n$.*antisymmetry of $leq$*)**5. Theorem 7.40 (**For all natural numbers $m$, $n$, and $p$, if $mmid n$ and $nmid p$ then $mmid p$.*divisibility is transitive*)**6. Theorem 8.2(c) (**If $m$, $n$, and $z$ are natural numbers, then $(z^m)^n=z^*Power Law*)$.

**1. Do over.**Choose any homework problem that was assigned after the midterm exam and write up its proof in Overleaf using the semiformal proof style illustrated in class. You can choose any problem, even one we went over in class which has a solution in the handwritten notes.**2. Prove the following theorem**in the same Overleaf project as the previous problem. Download the pdf from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #14”.**Factorials are positive**The natural number $k!$ is always positive.

**Let’s get real.**Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #15”. You can only use the Axioms of Real numbers, and anything prior to Chapter 9 (or any theorems that you prove yourself using those Axioms, but not theorems in the problem sets in Chapter 9 of the lecture notes). You do not need, and should not use, anything at all from Chapter 7 of the lecture notes. All constants in the following questions are real numbers.**0. Zero is its own additive inverse**$vphantom<0>^-0=0$**1. Alternate definition of multiplicative inverse**Let $x$ be a real number. If $x eq 0$ then $x^-=frac<1>$. **2. Uniqueness of predecessors**Let $x$ and $y$ be real numbers. If $x+1=y+1$ then $x=y$.**3. Not both**There do not exist any real numbers $x$ and $y$ such that $xlt y$ and $ylt x$.**4. Nostalgia for M1**Let $x$ and $y$ be real numbers. Then $xcdot(y+1)=x+xcdot y$.**5. Multiplication by zero**Let $x$ be a real number. Then $xcdot 0=0$ and cdot x=0$.**6. Yah, not as easy as you might expect**$0lt 1$ (where 0 and 1 are the real number constants, not the natural number constants) .

**Let’s get real.**Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #16”. You can only use the Axioms of Real numbers, the theorems we proved on Assignment #15, and anything from Logic (or any theorems that you prove yourself using those), but not theorems in the problem sets in Chapter 9 or anything from section 9.4. You do not need, and should not use, anything at all from Chapter 7 of the lecture notes. All constants and variables in the following questions are real numbers. You cannot use the definition of ’ from section 9.4 (or from Chapter 7), but you can always use $1+1$ (i.e., $1_mathbb+1_mathbb $) if you feel need to use ’ in your proof for some reason (you might). You do not need to use the completeness axiom, so I’ll save you time by telling you there is no need to even try to go down that path. **0. idempotency of inverses****a.**If $x$ is any real number then $vphantom^-(vphantom ^-x)=x$. **b.**If $x$ is any nonzero real number then $(x^-)vphantom^-=x$.

**Mixed bag.**Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #17”. The proof of each theorem can only use results from earlier chapters and the axioms, definitions, and previously proven results from the same chapter that the theorem is from. In particular, theorems from Chapter 8 cannot use any facts about real numbers. For theorems from Chapter 9 you can only use theorems we proved already and the axioms and dedinitions, not other problems in Chapter 9.- a.
**Thm 9.2d (**$(vphantom<1>^-1)cdot(vphantom<1>^-1)=1$.*Double negative*) - b.
**Thm 8.5 (**Let $n$ be a natural number. Then $F_*Fib Fun*)+F_n=2cdot F_ $ - c.
**Thm 9.10 (**If $x$ is a real number then $vphantom*Alternate additive inverse*)^-x=vphantom<1>^-1cdot x$. - d.
**Thm 9.33 (**Let $r$ be a rational number. Then there exist integers $m$ and $n$ with $n eq 0$ such that, $r=frac*Alternate Definition of Rational*)$ - e.
**Thm 8.3 (**For all natural numbers $ngeq 5$, $n^2lt 2^n$*Exponentiation isn’t commutative*) - f.
**Thm 9.29(part) (**For any rational numbers $r,s$, their sum $r+s$ is also rational number.*Closure of addition for rationals*)

(You can use theorem 9.28 if needed.)

**Let’s get real.**Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #18”. You can use the ‘by arithmetic’ shortcut for only those things I explained in class.**0. Not an odd result**The integer $4$ is even.**1. Easy Warm Up (**If $xin <,a,>$ and $yin <,a,>$ then $x=y$*Thm 10.1*)**2. A set of sets (**$<,1,2,>in<,A : <,1,>subseteq A,>$*Thm 10.4*)

**Mixed bag.**Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #19”. In these problems $A , B, C$ and $D$ are sets.- a.
**Thm 10.6 (**$Asubseteq A$.*Subset is reflexive*) - b.
**Thm 10.2 (**$<,a,b,>=<,b,a,>$*Order doesn’t matter*) - c.
**Thm 10.14 (**$Acap B=Bcap A$*Commutativity of $cap$*) - d.
**Thm 10.9 (**$A-(B-A)=A$*Double Negative*) - e.
**Thm 10.35 (**$mathcal*Powerset and Union*)(A)cupmathcal

(B) subseteq mathcal

(Acup B)$

- f.
**Thm 10.32 (**If $Asubseteq C$ and $Bsubseteq D$ then $A imes Bsubseteq C imes D$.*Subsets are contagious*) - g.
**Thm 8.6 (**For any natural numbers $m$ and $n$, $inom*Symmetry of Binomial Coefficients*)=inom $

- Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #20”. In these problems $A$, $B$, $C$, and $D$ are all subsets of a single universal set $mathcal
__$.__**0. Contravariance of complement**$A subseteq B Leftrightarrow B’ subseteq A’$**1. Composition is associative**If $hcolon A o B$, $gcolon B o C$, and $fcolon C o D$ then $fcirc (gcirc h)=(fcirc g)circ h$ Hint: Use the Function Equality+ recipe and the recipes for Composition.

Prove each of the following theorems and write up your semiformal proof in a single LaTeX file project. When you are done, download the pdf file from Overleaf and put it in your Dropbox folder in a subfolder named “Assignment #21”. In these problems $A , B, S$ and $T$ are sets.

- a.
**Thm 10.3 (**$(a,b)=(b,a)$ if and only if $a=b$.*order does matter*) - b.
**Thm 10.21 (**$(Acap B)’=A’cup B’$.*DeMorgan*) - c.
**Thm 10.38 (**Suppose $fcolon mathbb*a real bijection*)omathbb $ and $f(x)=3x+1$ for all $xinmathbb $. Then $f$ is bijective.

You can use the ‘by arithmetic’ and ‘by algebra’ rule shortcuts here. - d.
**Thm 10.53 (**Suppose $sim$ is the set $sim = Set< (1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)>$ Then $sim$ is not an equivalence relation on the set $Set<1,2,3>$.*not an equivalence relation*) - e.
**Thm 10.41 (**If $fcolon A o B$ and $Ssubseteq T$ and $Tsubseteq A$ then $f(S)subseteq f(T)$.*image of subsets*)

**1. Start working on your Take Home Final Exam.**To help keep you on track, put a draft of your Take Home Final Exam pdf in Dropbox before class on Thursday. It should use the Homework Template – Article style linked to below, not the usual Homework Template – Handout style. Create all of the necessary sections and pieces (Title, Abstract, Introduction section, Proof section, Summary section, bibliography) and you can start to fill in the commentary. You can clone the Sample Document linked to below to get started. Put your pdf in a Final Exam subfolder of your Dropbox folder, and call it ‘Final Exam Draft 1.pdf’.You can start to pick out which of the six theorems you would like to prove in accordance with the instructions in your Dropbox folder, and you can include the theorem statements and even the proofs if you find some you like. You can always change your mind about which problems you want to answer at any time before the exam is due. So one good strategy would be to try to prove six easy one point proofs first, and then try to increase your score from there by upgrading some to two points or three points, or collect some of the bonus points for induction, or proof by cases, writing style, or diagrams. See the instructions for details.

## Watch the video: Quantifiers (January 2022).