Stony Brook University                                                                                                        Logic, Language and Proof

Mathematics Department                                                                                                                      MAT 200, Lec 31

Julia Viro                                                                                                                                                    Spring 2021

Syllabus

Course description: The goal of the course is to introduce the student to logical rea-soning and proofs. This course serves as an introduction to rigorous mathematics used in upper-division mathematics courses. We discuss logical language and operations, and methods of proof in general. Then we focus on sets and maps between them - the foun-dational objects of mathematics. Finally, we study cardinality. We apply the rigorous language to systematically define and study some notions of number theory, elementary analysis, and Euclidean geometry. There is considerable focus on mathematical writing.

Credits: 3.

Instructor: Julia Viro

e-mail: [email protected]

MLC hours: Tu 12noon-1pm

Office hours: Th 12noon-2pm

Zoom personal meeting room: https://stonybrook.zoom.us/j/9792031214

Grader: Hang Yuan

e-mail: [email protected]

MLC hours: Tu 1pm-3pm

Office hours: Th 1pm-2pm

Zoom personal meeting room: https://stonybrook.zoom.us/j/6117091309

Textbook: Peter J. Eccles, An Introduction to Mathematical Reasoning, Cambridge University Press.

Zoom Meetings: MW 4:25pm-5:45pm

Homework: will be assigned weekly through Gradescope. The emphasis of the course is on writing proofs, so please try to write legibly and explain your reasoning clearly and fully. You are encouraged to discuss the homework problems with others, but your write-up must be your own work. Suspiciously similar papers won’t be graded.

Homework should be submitted to Gradescope according to the Gradescope rules. Incor-rect submission format will lead to a grade reduction. Late homework won’t be accepted. Homework in the form of e-mail won’t be accepted.

Quizzes will be given weekly in class Zoom meetings.

Exams: two midterms and final exam. Midterms 1 and 2 are preliminary scheduled for 3/3 and 4/14 respectively. Final exam is on Tuesday, May 18 at 2:15-5pm.

All exams will be given in proctored online format. Missing any of the exams without any serious and documented reason will result to failure in the course.

For exams, please have a microphone, webcam and reliable internet connection. No complaints about technical difficulties during the exams will be accepted.

To ensure integrity during the exams, you may be called to a private Zoom meeting with the instructor after each exam to validate (check) that you are able to reproduce your work submitted online. By the results of the meeting, the grade may be changed.

Grading system: your grade for the course will be based on: homework 10%, quizzes 10%, class active participation 5%, two midterms 20% each, final exam 35%.

Make-up policy: Make-up examinations are given only for work missed due to unfore-seen circumstances beyond the student’s control.

Student Accessibility Support Center (SASC) statement: If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact SASC (631) 632-6748 or http://studentaffairs.stonybrook.edu/dss/. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and SASC. For procedures and information go to the following website: http://www.stonybrook.edu/ehs/fifire/disabilities/asp.

Academic integrity statement: Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person’s work as your own is always wrong. Faculty are required to report any suspected instance of academic dishonesty to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary

The following will be considered as acts of academic dishonesty:

• Using problems solving websites or other internet resources to get solutions.

• Getting help in any from from other people.

• Sharing solutions and/or answers with other people.

All cases of violation of academic integrity will be reported immediately to the Academic Judiciary. Students who admitted dishonesty will face

• failure of the course,

• a dishonesty report in the transcript, and

• an obligation to take the Q course.

Critical incident management: Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, and/or inhibits students’ ability to learn.

Student Absences Statement: Students are expected to attend every class, report for examinations and submit major graded coursework as scheduled. If a student is unable to attend lecture(s), report for any exams or complete major graded coursework as scheduled due to extenuating circumstances, the student must contact the instructor as soon as possible. Students may be requested to provide documentation to support their absence and/or may be referred to the Student Support Team for assistance. Students will be provided reasonable accommodations for missed exams, assignments or projects due to significant illness, tragedy or other personal emergencies. In the instance of missed lectures or recitations, the student is responsible for insert course specific information here (examples include: review posted slides, review recorded lectures, seek notes from a classmate). Please note, all students must follow Stony Brook, local, state and Centers for Disease Control and Prevention (CDC) guidelines to reduce the risk of transmission of COVID.

Weekly Plan (tentative)

Week 1 (M 2/1, W 2/3).

Learning objectives: Introduction to logic. Propositions and predicates. Logical con-nectives. Truth tables. Compound propositions. Conjunctive and disjunctive normal forms. Conditional and biconditional sentences. Denials. Logical identities.

Reading: 1, 2.

Learning outcomes. A student should be able to

1. outline the scope of the course and list the main topics to be studied

2. identify whether a phrase is a proposition

3. distinguish a proposition and a predicate

4. manipulate correctly with five logical connectives (negation, conjunction, disjunction, implication, and equivalence).

5. understand the nature of truth tables

6. identify logical connectives given with emotional attributions (logical conjunction vs. colloquial and, but, though, nevertheless, etc.).

7. compose propositional forms and identify their truth values

8. determine equivalent propositional forms

9. identify conditional and biconditional sentences

10. use the whole range of linguistic expressions associated with conditionals and bicon-ditionals (“sufficient”, “necessary”, “sufficient and necessary”, “whenever”, “if and only if”, etc.)

11. understand the difference between implication in mathematics and causation in lan-guage/everyday life

12. list and prove at least 10 logical identities

13. define what a tautology and contradiction mean

14. formulate and prove de Morgan’s laws, the law of excluded middle and the law of consistency

15. construct useful denials of propositional forms

16. construct the contrapositive, the converse, and the inverse of a conditional statement.

17. explain what a normal form of a proposition is and how to construct disjunctive and conjunctive normal forms

Week 2 (M 2/8, W 2/10).

Learning objectives: Quantifiers and quantified sentences. Analyzing and constructing propositions involving several quantifiers.

Reading: 7.

Learning outcomes. A student should be able to

1. recognize three quantifiers (universal, existential, and unique existential) in both writ-ten and colloquial environment

2. translating propositions formulated in a colloquial English into symbolic forms and the other way around

3. analyze and construct propositions involving several quantifiers

4. identify free and dummy variables in logical structures

5. list the situations when quantifiers commute and when they don’t

6. construct useful denials of propositional forms and quantified sentences

Week 3 (M 2/15, W 2/17).

Learning objectives: Logical structure of definitions and theorems. How to read and understand mathematical texts. Structure of a mathematical theory: basic objects, ax-ioms, definitions and theorems. The role of proofs. Examples and counterexamples.

Reading: 3; Lecture notes.

Learning outcomes. A student should be able to

1. comprehend the logical structure of a definition

2. treat mathematical definitions as biconditional sentences with a single free variable

3. be aware about the agreement about conditional colloquial expressions in definitions

4. present three signs/criteria for identification of a definition

5. comprehend the logical structure of a theorem

6. explain the impossibility of free variables in formulations of theorems

7. distinguish a definition from a theorem and example using the logical criteria

8. identify definitions, theorems, and examples in an unknown mathematical text

9. put known definitions and theorems in an appropriate logical structure, both in words and symbols.

10. comprehend the structure of a mathematical theory: identify the basic objects, axioms and theorems

11. explain the role of proofs in mathematics

12. distinguishing the formulation (statement) of a theorem and its proof and see the difference between motivation and proof

13. understand the nature of examples and counterexamples

14. explain when and why examples can’t replace a proof

15. understand the structure of a mathematical text

16. list several techniques how to read and understand a mathematical text

Week 4 (M 2/22, W 2/24).

Learning objectives: Proof techniques: direct proof, proof by contraposition, proof by contradiction, proof by exhaustion. Strategies for constructing proofs.

Reading: 3, 4.

Learning outcomes. A student should be able to

1. describe four standard proof techniques: direct proof, proof by contraposition, proof by contradiction, proof by exhaustion

2. implement standard proving schemes for simplest proofs

3. evaluate pros and contra of different proof techniques

4. make comparative analysis of various proofs of the same fact

5. master symbolic writing within appropriate logical framework

6. identify three most common logical mistakes in a making a proof

Week 5 (M 3/1, W 3/3). Review and Midterm 1.

Week 6 (M 3/8, W 3/10).

Learning objectives: Principle of mathematical induction in various forms: induction, strong induction, well-ordering principle.

Reading: 5.

Learning outcomes. A student should be able to

1. describe the principle of mathematical induction in various forms (induction, strong induction, well- ordering principle)

2. identify the situations when a proof by induction is suitable and the situations when it is not

3. conduct proofs by induction of various statements from combinatorics, algebra, geom-etry and analysis.

Week 7 (M 3/15, W 3/17).

Learning objectives. Basic notions of set theory: set and its elements, empty set, subset, intersection, union, difference and complement. Families of sets. Relations be-tween logical and set-theoretical operations. Set theoretic identities. Maps: definitions and notations. Basic terminology associated with maps: domain, codomain, image and preimage. Examples of maps: functions in one variable, numerical sequences, identity map, constant map.

Reading: 6, 8

Learning outcomes. A student should be able to

1. operate freely with basic notions of set theory: set and its elements, empty set, subset,6 intersection, union, difference and complement

2. use Venn diagrams to illustrate set-theoretical events

3. explain why Venn diagram can’t serve as a proof

4. explain why Venn diagram can serve as a counterexample

5. establish relations between logical and set-theoretical operations, like negation and complement, conjunction and intersection etc.

6. explain what is a set-theoretical identity and how to prove it

7. understand the concept of families of sets and give several examples of families of sets

8. give definition of the power set and list several properties of the power set

9. define a map from one set to another, provide synonyms for the word map

10. use freely basic terminology related to maps: the domain, codomain, and range of a map; the image and preimage of a set

11. use correct symbols related to maps

12. provide examples of maps from different parts of mathematics

13. operate with special maps: identity map and constant map.

Week 8 (M 3/22 W 3/24).

Learning objectives. Composition of maps: definition and properties. Inclusion map. Restriction of a map to a subset. Submap. Characteristic function of a set. Power set and the set of all maps to a two-element set. The set of all maps X → Y .

Injections, surjections and bijections. Definition and properties of inverse map. Equiva-lence between invertibility and bijectivity.

Reading: 9.

Learning outcomes. A student should be able to

1. define a composition of maps and list its properties

2. define inclusion map, submap and restrictions of a map

3. define and list properties of the characteristic function of a set

4. work with the set of all maps from one set to another

5. establish relation between the power set and the set of all maps to a two-element set

6. provide definitions of Injections, surjections and bijections. List synonyms for these words

7. provide definitions of inverse map, left inverse,and right inverse

8. list basic examples of functions and their inverse: exponential and logarithmic, tangent and arctangent, etc.

9. state and prove equivalence of invertibility and bijectivity

Week 9 (M 3/29, W 3/31).

Learning objectives. Cartesian product of sets. Coordinate projections and fibers. Graph of a map. Relations. Functions of several variables as functions on a Cartesian product. Metric on a set. Equivalence relations and partitions. Quotient sets. Canonical factorization of a map into composition of surjection, bijection and injection. Construc-tions of integers and rational numbers. Construction of complex numbers.

Reading: 13; Lecture notes.

Learning outcomes. A student should be able to

1. give definition of the Cartesian product of sets and list several properties of the Cartesian product

2. describe coordinate projections and fibers

3. define graph os a map

4. define a metric on a set

5. provide examples of different metrics on the same sets

6. define and give example of a relation from one set to another and a relation on a set

7. list several properties of relations

8. discuss properties associated with a binary relation on a set: reflexivity, irreflexivity, symmetry, antisymmetry, transitivity

8. define strict partial order, non-strict partial order, and linear order

10. provide basic examples of sets with strict partial order, non-strict partial order, and linear order

11. define equivalence relation on a set

12. provide five examples of equivalence relations

13. define partition of a set and establish connection between equivalence relations and partitions of a set

14. describe equivalence classes, the quotient set, and the quotient map

Week 10 (M 4/5, W 4/7).

Learning objectives. Congruence classes. Modular arithmetic.

Reading: 19, 20, 21.

Learning outcomes. A student should be able to

1. define congruence modulo m and prove that this is an equivalence relation

2. define congruence classes

3. define operations of addition and multiplication on congruence classes

3. give defifinition of a ring

4. prove that Zm is a ring

5. use modular arithmetic for solving various divisibility problems and control of calcu-lations

6. define ring homomorphism and prove that the canonical projection Z → Zm is a ring homomorphism

Week 11 (M 4/12, W 4/14). Review and Midterm 2.

Week 12 (M 4/19, W 4/21).

Learning objectives. Number systems. Peano’s axioms. Integers, rational, real and complex numbers as quotient sets. Definitions of equipotent sets and cardinality of a set. Finite and infinite sets. Finite arithmetic. Pigeonhole principle.

Reading: 10, 11, 12.

Learning outcomes. A student should be able to

1. define which sets are called equipotent

2. define the cardinality of a set

3. explain what are the cardinal numbers of the empty set and a singleton

4. explain why natural numbers and integers have the same cardinality

5. defifine which sets are called finite and infinite

6. formulate and prove the pigeonhole principle

7. state and prove five corollaries for the pigeonhole principle

8. solve problems using the pigeonhole principle

9. establish one-to-one correspondence between natural numbers and cardinalities of finite sets.

Week 13 (M 4/26, W 4/28).

Learning objectives. Denumerable, countable and uncountable sets. Examples of infinite sets of the same and different cardinalities. Hilbert’s Grand Hotel. Cantor theorem about non-equipotency of a set and its power set. Denumerable arithmetic. Countable and uncountable sets.

Reading: 14.

Learning outcomes. A student should be able to

1. explain which sets are called denumerable, countable and uncountable

2. explain counting principles for finite sets (addition, multiplication, inclusion-exclusion)

3. count the number of permutations of a finite set

4. state and prove absorption theorem for denumerable sets

5. explain how to define the product of infinite cardinal numbers

6. prove that the set od rational numbers is denumerable

7. state and prove Cantor’s theorem about uncountability of R

8. prove that an open interval in uncountable

Week 14 (M 5/3, W 5/5)

Learning objectives. Cantor-Shr¨oder-Bernstein theorem. Ordering of cardinal num-bers. Cantor’s theorem about uncountability of R. Continuum hypotheses.

Reading: 14.

Learning outcomes. A student should be able to

1. define inequalities for cardinal numbers

2. state the Continuum hypothesis

3. state and prove Cantor’s theorem about cardinalities of a set and its power set

4. state Cantor-Shr¨oder-Bernstein theorem and use it for problem solving

5. prove that the power set of natural numbers is uncountable

Final exam is on Tu 5/18 at 2:15pm-5pm.