MGF 3301 - BRIDGE TO ABSTRACT MATHEMATICS
Section 001 - Spring 2020
This page is devoted to Bridge to abstract mathematics - Section 001 of Spring 2020 at USF.
Note: All the material (video lectures, homework, quizzes, tests, in-class activities, slides, notes, etc.) you will find in this page has been realized by me, unless otherwise specified. I am more than happy if you want to use part of it with your students, but in this case please give credits by sharing the URL of this webpage.
SYLLABUSSYLLABUS - SLIDESSCHEDULEGO to VIDEO LECTURES
Time and location of class:
MW: 9:30 am – 10:45 am in CMC 118
Office hours (CMC 110):
MW: 11:00 am - 12 pm
Textbook: A Transition to Advanced Mathematics, by Smith, Eggen & St. Andre, 8th edition.
Other references: An Introduction to Writing Mathematical Proofs: Shifting Gears from Calculus to Upper-Level Mathematics Classes, 4th edition (red cover), Thomas Bieske.
Contents:
The course will cover the following topics:
- Logic and Proofs, (Smith, Chapter 1);
- Set Theory, (Smith, Chapter 2);
- Relations, (Smith, Chapter 3);
- Functions, (Smith, Chapter 4).
- The tenth homework is due on Wednesday April 15 at 9:30am (submissions on Gradescope).
- The nineth homework is due on Wednesday April 8 at 9:30am (submissions on Gradescope).
- The eighth homework is due on Wednesday April 1 at 9:30am (submissions on Gradescope).
- Starting from March 23, all USF classes will be given remotely, due to the Coronavirus outbreak. Video Announcement 1, Video Announcement 2
- The second test will take place on Wednesday March 11 at 9:30 am in CMC 118. Here you can find a study guide.
- The seventh homework is due on Wednesday March 11 at the beginning of the class.
- The sixth homework is due on Wednesday March 4 at the beginning of the class.
- The fifth homework is due on Wednesday February 26 at the beginning of the class.
- The first test will take place on Wednesday February 12 at 9:30 am in CMC 118. Here you can find a study guide.
- The fourth homework is due on Wednesday February 12 at the beginning of the class.
- The third homework is due on Wednesday February 5 at the beginning of the class.
- The second homework is due on Wednesday January 29 at the beginning of the class.
- The first homework is due on Wednesday January 22 at the beginning of the class.
Logbook:
- 01/13/2020: Presentation/syllabus of the course. First day attendance. Introduction to bridge.
Slides - Introduction to bridge - 01/15/2020: Definition of definition, example, proposition. Simple/coumpound proposition. Logical connectives: conjunction, disjuction, negation. Propositional forms and well-formed formulas. Construction of truth tables. Equivalent propositions and equivalent propositional forms. De Morgan's law (example in the context of set theory).
References: Smith, Section 1.1 (pages 1-4). Bieske, Section 1 (pages 11,12).
Homework 1 - 01/22/2020: Quiz 1. Theorem about equivalent propositional forms. Definition of denial of a proposition. Examples. Definitions of tautology and contradiction with examples. Law of Excluded Middle. Truth table of the conditional sentence. Examples of true/false conditional sentences.
References: Smith, Section 1.1 (pages 4-6), Section 1.2 (pages 10,11).
Quiz 1Q1 solutionHomework 2 - 01/27/2020: Definition of conditional sentence (antecedent, consequent). Examples. The converse and the contrapositive of a conditional sentence. Theorem: a conditional sentence is equivalent to its contrapositive. Defintion of biconditional sencente. Definitions are biconditional sentences. Definition of even number.
References: Smith, Section 1.2 (pages 10-15).
- 01/29/2020: Quiz 2. Definition of open sentence and of universe of discourse. Examples of universes: $\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, $\mathbb C$. The truth set of an open sentence. Quantifiers: existential quantifier, unique existential quantifier, universal quantifier. Examples.
References: Smith, Section 1.3 (pages 18-26).
Quiz 2Q2 solutionHomework 3 - 02/03/2020: Examples of sentences with quantifiers (translation from the English to the Math language). Negation of $\forall \, x P(x)$ and $\exists \, x P(x)$. Examples. The terminology of a math paper. Undefined terms and axioms. Euclid's Postulates (in particular the 5th postulate -> non-Euclidean geometry). In-class activity (Murder Mystery).
References: Smith, Section 1.3 (pages 21-26), Section 1.4 (pages 28,29).
The Terminology of a Math PaperMurder Mystery - in-class activity - 02/05/2020: Quiz 3. Solution of the Murder Mystery. "Rules" for proving a statement. Direct proofs. Proof of the statement: If $n$ is odd, then $n+1$ is even.
References: Smith, Section 1.4 (pages 28-33).
Quiz 3Q3 solutionHomework 4Study guide - TEST 1 - 02/10/2020: Comments on HW4 (denial and truth value of a sentence containing quantifiers). More examples of direct proofs ($P\land Q \Rightarrow R$, $ P\Rightarrow Q\land R $): If $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$. If $x$ and $y$ are two real numbers such that $x<-4$ and $y>2$, then the distance from $(x,y)$ to $(1,-2)$ is greater than $6$. If $n$ is odd then $n^2+1$ is even and $n+4$ is odd.
References: Smith, Section 1.4 (pages 34,35).
- 02/12/2020: Test 1.
Test 1Test 1 - solution - 02/17/2020: Comments on Test 1. Example of proof by cases: "For all real numbers, prove that $-|x|\leq x\leq |x|$". (Definition of absolute value of a real number.) Indirect proofs: proof by contrapositive. Example: "$n$ is even if and only if $n^2$ is even." Introduction to proofs by contradiction.
References: Smith, Section 1.5 (pages 42,43).
- 02/19/2020: Proofs by contradiction. Examples: "$\sqrt{2}$ is an irrational number", "There exist no integers $a$ and $b$ such that $18a+6b=1$". Proof of "Let $a$ and $b$ be two integers. If $a+b\geq 19$ then $a\geq 10$ or $b\geq 10$." with three different methods (direct proof, proof by contrapositive, proof by contradiction).
References: Smith, Section 1.5 (pages 43-48).
Homework 5 - 02/24/2020: Techniques of proofs involving quantifiers: $\forall x, P(x)$ (direct, by contradiction), $\exists x P(x)$ (constructive, indirect, by contradiction), $\exists! x P(x)$ (existence+uniqueness). Example ($\forall x, P(x)$ - direct proof): "$\forall x$ in
$\mathbb R, x+\frac{1}{x}\geq2$". Set theory: definition of a set, Roster notation vs. set-builder notation, symbol $\in$ for membership, the empty set $\varnothing$, definition of subset of a set (examples), symbol $\subseteq$ for containment, direct proof of $A\subseteq B$ (example).
References: Smith, Section 1.6 (pages 51-60), Section 2.1 (85-87).
- 02/26/2020: Quiz 4. Comments on Quiz 4. Direct proof: "If $a\mid b$ then $b\mathbb Z \subseteq a \mathbb Z$." Proposition: for all set $A$, $A,\varnothing \subseteq A$; if $A\subseteq B$ and $B \subseteq C$ then $A \subseteq C$. Proof of $A=B$ (double inclusion). Example.
References: Smith, Section 2.1 (pages 87-88).
Quiz 4Q4 solutionHomework 6 - 03/02/2020: Definition of proper subset. Venn diagrams. Definition of the power set of a set. Examples. Proposition: "The power set of a set with $n$ elements has $2^n$ elements". Operations between sets: union, intersection, difference. Examples. Definition of disjoint sets. Theorem 2.2.1 of the textbook. Definition of the complement of a set. Examples. Theorem 2.2.2 of the textbook.
References: Smith, Section 2.1 (pages 89-91), Section 2.2 (95-98).
- 03/04/2020: Quiz 5. Comments on Quiz 5. Video. Convention: $\mathbb N=\{1,2,3,\ldots\}$. Peano's axioms. Principle of mathematical induction. Example of proof by induction: the sum of the first $n$ odd natural integers is $n^2$.
References: Smith, Section 2.4 (pages 114-117).
Quiz 5Q5 solutionHomework 7Study guide - TEST 2 - 03/09/2020: Examples of mathematical induction: the sum of the first $n$ integers is $\frac{n(n+1)}{2}$; for all $n\geq 4$ $n!>2^n$. Proofs about set theory: $A\subseteq B$ if and only if $\mathcal P(A)\subseteq \mathcal P(B)$; if $C\subseteq A$, $D\subseteq B$ and $A$ and $B$ are disjoint, then also $C$ and $D$ are disjoint.
References: Smith, Section 2.1 (page 91).
- 03/11/2020: Test 2.
Test 2Test 2 - solution - 03/23/2020 (REMOTE TEACHING): Features of MS Teams. Correction of Test 2. (Video-conference on MS Teams)
Video - Cartesian product - 03/25/2020 (REMOTE TEACHING): Definition of a relation from $A$ to $B$ and of a relation on a set $A$. Examples. Geometrical representation: Arrow diagram, graph and directed graph. Identity relation on a set and corresponding graph.
References: Smith, Section 2.2 (pages 100,101), Section 3.1 (pages 153,154).
Relations (3.1)Video - Equivalence relationHomework 8 - 03/30/2020 (REMOTE TEACHING): Definition of domain and range of a relation. Examples and geometrical interpretation in the arrow diagram and in the graph of the relation. Definition of inverse relation. Theorem 3.1.1 (with proof). The composite of two relations. Example. Some discussion about the reflexive, symmetric and transitive properties of a relation on a set.
References: Smith, Section 3.1 (pages 155-160), Section 3.2 (pages 163,164).
Relations, continue (3.1)Homework 10 - 04/01/2020 (REMOTE TEACHING): Definition of reflexive, symmetric and transitive property of a relation on a set $A$. Several examples (and Poisson d'avril). Definition of equivalence relation. Example. Given an equivalence relation $R$ on a set $A$, definition of an equivalence class of $R$, of a representative of an equivalence class and of the set $A$ modulo $R$.
References: Smith, Section 3.2 (pages 163-167).
Equivalence relations (3.2)Video - A little bit of NotationHomework 9 - 04/06/2020 (REMOTE TEACHING): Additional examples of equivalence relations (equivalence classes and $A$ modulo $R$): $R=\{(x,y)\in \mathbb Z\times \mathbb Z: x+y \textrm{ is even}\}$, $R=\{(x,y)\in \mathbb R^2: x^2=y^2\}$. Theorem 3.3.2 (with proof). Proposition: $A$ modulo $R$ is a partition of A (with proof). How to define an equivalence relation on a set $A$ starting from a partition of $A$.
References: Smith, Section 3.2 (pages 167-168), Section 3.3 (pages 175-179).
Equivalence relations (3.2), partitions (3.3) - 04/08/2020 (REMOTE TEACHING): Quiz 6. Relation congruence modulo $m$: definition, proof that it is an equivalence relation, classes of equivalence. $\mathbb Z$ modulo $m$, a clock with $m$ hands.
References: Smith, Section 3.2 (pages 168-169).
Quiz 6Q6 solution Relation congruence (3.2)Video - Functions as relationsHomework 10 - 04/15/2020 (REMOTE TEACHING): The set $\mathbb Z_m$ of all the equivalence classes of $\mathbb Z$ modulo the relation congrunce modulo $m$. Review of the Division Algorithm. Proposition 1: $a\equiv b \pmod m$ if and only if $a$ and $b$ have the same remainder when divided by $m$ (for the proof, see part (a) of Theorem 3.2.4). Examples. Proposition 2: $\mathbb Z_m=\{\overline{0},\overline{1},\ldots, \overline{m-1}\}$ (for the proof, see part (b) of Theorem 3.2.4). Operations of addition and multiplication on $\mathbb Z_m$. Corrections of the quiz about the video lecture on "Functions as relations".
References: Smith, Section 3.2 (pages 169-171), Section 3.3 (pages 182-184).
$\mathbb Z_m$ and modular arithmetic (3.2,3.4)Video - One-to-one and onto functionsThe Last Homework - 04/20/2020 (REMOTE TEACHING): Quick review on functions. Theorem 4.1.1 (without proof). Examples of functions: identity function, inclusion function, characteristic function, canonical map, infinite sequence. The inverse of a function and the composite of two functions. Examples and remarks. Additional examples on one-to-one and onto functions.
References: Smith, Section 4.1 (pages 207-209), Section 4.2 (pages 212-214), Section 4.3 (pages 222-225).
Functions (4.1, 4.2, 4.3)Study guide - TEST 3 - 04/22/2020 (REMOTE TEACHING): Test 3.
Test 3Test 3 - solution - 04/27/2020 (REMOTE TEACHING): Correction Test 3. Theorem 4.2.2: the inverse of a function $f$ is a function if and only if $f$ is one-to-one (with proof). The restriction of a function. Example.
References: Smith, Section 4.4 (pages 232-233).
Inverse functions (4.4)
Course documents:
- In-class notes (remote teaching): Relations (3.1)Relations, continue (3.1)Equivalence relations (3.2)Equivalence relations (3.2), partitions (3.3)Relation congruence (3.2)$\mathbb Z_m$ and modular arithmetic (3.2,3.4)Functions (4.1, 4.2, 4.3)Inverse functions (4.4)
- Slides: Slides - Introduction to bridgeMurder Mystery - in-class activity
- Sheets: The Terminology of a Math Paper
- Quizzes: Quiz 1Q1 solutionQuiz 2Q2 solutionQuiz 3Q3 solutionQuiz 4Q4 solutionQuiz 5Q5 solutionQuiz 6Q6 solution
- Homework: Homework 1Homework 2Homework 3Homework 4Homework 5Homework 6Homework 7Homework 8Homework 9Homework 10The Last Homework
- Review: Study guide - TEST 1Study guide - TEST 2Study guide - TEST 3
- Tests: Test 1Test 1 - solutionTest 2Test 2 - solutionTest 3Test 3 - solution
Video Lectures
Cartesian product of sets
(March 23, 2020)
Equivalence relations
(March 28, 2020)
A little bit of notation
(April 3, 2020)
Functions as Relations
(April 10, 2020)
One-to-one and onto functions
(April 17, 2020)