Math 103: Introduction to Abstract Mathematics, Fall 2018

Topics Covered in the Lectures

Lecture Number	Date	Content	Corresponding Reading material
1	Sep. 18	General structure of mathematical theories: Definition of object of study, axioms, theorems (lemmas, propositions, corollaries, fundamental theorems), conjectures, undecidable statements & Gödel’s incompleteness theorem; Euclid’s axioms and the discovery of non-Euclidean geometries; General structure of scientific theories: Description of objects of study, postulates (laws of nature), predictions, experimental tests & differences with mathematical theories; Fermat’s last theorem, the solution of the 4-color problem, and the need for a precise mathematical language	Textbook 1 (A First Course in Abstract Mathematics): Pages 1-6
2	Sep. 20	Statements, their truth value, some basic mathematical symbols, predicates, qualifiers, negation of a statement, truth tables, negation of a qualified predicate, compound statements: disjunctions, conjunctions, and implications	Textbook 1: Pages 6-17
3	Sep. 25	Basic properties of disjunctions, conjunctions, implications, and logical equivalence, negation of basic compound statements, tautologies and contradictions, propositional calculus	Textbook 1: Pages 17-31
4	Sep. 27	Theorem types and proof methods: Existence, uniqueness, and classification theorems; proving implications: Trivial, direct, contrapositive, and deductive proofs; Proof by cases	Textbook 1: pages 35-41 & 45-46; Textbook 2 (Mathematical Proofs): Pages 87-110
-	Oct. 02	Quiz 1
5	Oct. 04	Proof by contradiction, great common divisor (g.c.d.) of two integers, well-ordering principle and the proof of existence of g.c.d., relatively prime integers, Lemma: Rational numbers are ratios of relatively prime integers, Theorem: Square root of 2 is not rational. Proof by induction: Basic idea	Textbook 1: Pages 41-45 & 47; Textbook 2: Pages 319-320
6	Oct. 05	Induction axiom, principle of mathematical induction, examples, complete induction, recursive definitions	Textbook 1: Pages 47-57; Textbook 2: Pages 164-177
7	Oct. 09	Characterization theorems, counterexamples; Set Theory: General introduction, axioms of extensionality, specification, and existence, equal sets, empty set, subsets, power set axiom, Russel’s paradox	Textbook 1: Pages 65-71 Textbook 2: Pages 60-66
8	Oct. 11	Universal sets, intersection of two sets, basic properties of intersection of sets, disjoint sets, difference of two sets, intersection of more than two sets, intersection of an arbitrary collection of sets	Textbook 1: Pages 71-79; Textbook 2: Pages 67-73
-	Oct. 12	Quiz 2
9	Oct. 16	Union Axiom, union of a collection of sets, and its basic properties, intersection and union of the complement of sets having a universal set, unordered pairs, Paring Axiom, and ordered pairs	Textbook 1: Pages 80-85; Textbook 2: Pages 70-73
10	Oct. 18	Ordered pairs (a,b) with a ϵ A and b ϵ B as elements of the power set of power set of , the Cartesian product of two or more sets; Natural numbers: Inductive sets, Axiom of Infinity, the construction of natural numbers, the definition of the set of natural numbers, the proof that natural numbers are the only elements of this set, definition of the addition and multiplication of natural numbers, the definition of inequality of natural numbers	Textbook 1: Pages 86-90
11	Oct. 23	Relations, the image and inverse image of subsets under a relation, the domain and range of a relation, equality two relations, restriction and extensions of a relation	Textbook 1: Pages 95-101
12	Oct. 25	Image and inverse image of the intersection and union of a collection of subsets under a relation, reflexive, symmetric, antisymmetric, and transitive relations, the identity relation, inverse of a relation, composition of two relations and its domain, noncommutativity of composition of relations	Textbook 1: Pages 101-107
-	Oct. 26	Quiz 3
13	Oct. 30	Associativity of composition of relations, inverse of the composition of two relations, composing a relation with its inverse (whenever it is possible), Equivalence relations, congruence relation, equivalence classes and the quotient of a set by an equivalence relation, partitions of a set, parallelism for lines in plane as an equivalence relation and its equivalence classes	Textbook 1: Pages 107-113; Textbook 2: Pages 224-230 & 234-239
14	Nov. 01	The one-to-one correspondence between equivalence relations on a nonempty set and its partitions, finding all possible equivalence relations on the set {1,2,3} using its partitions, Partial ordering relations, total ordering, partially ordered sets (posets)	Textbook 1: Pages 113-121
15	Nov. 06	Graphical representations of partial ordering relations; maximal, minimal, greatest, and least elements of a poset, uniqueness of the greatest, and least elements; upper and lower bounds, supremum, and infimum of a subset of a poset, uniqueness of the supremum and infimum, supremum property, chains of a poset, statement of Zorn’s lemma.	Textbook 1: Pages 121-127
16	Nov. 08	Well-ordered posets and Well-Ordering Principle, proof of well-ordering of natural numbers, application to division algorithm; Functions: Well-defined relations, notation, everywhere-defined relations and functions.	Textbook 1: Pages 127-139
	Nov. 09	Quiz 4
17	Nov. 13	Image and inverse image of sets under functions, domain and range of a function, identity function, equal functions, one-to-one and onto functions, bijections, examples. Restriction and extensions of functions, inclusion maps, construction of a bijection mapping disjoint union of two sets to the disjoint union of two sets.	Textbook 1: Pages 140-146
18	Nov. 15	Image and inverse image of intersection of a collection of sets and the complement of a set under a function, composition of and inverse of functions, invertible functions	Textbook 1: Pages 146-155
	Nov. 17	Midterm Exam
19	Nov. 20	Properties of the inverse of an invertible function; Transpositions and permutations of In:={1,2,…,n}, Theorem: A function f: In -> In is a bijection if and only if it is a permutation of In.	Textbook 1: Pages 155-158
20	Nov. 22	Non-existence of everywhere-defined and 1-to-1 functions f: In -> A and onto functions f: A -> In when A is a proper subset of In, n=m as the necessary and sufficient condition for the existence of bijections f: In -> Im; Sequences, sequences with distinct terms; Equivalent sets	Textbook 1: Pages 158-163 & 177-179
21	Nov. 27	Finite sets, order of a finite sets, finiteness of subsets of finite sets, finiteness of the union of two finite sets	Textbook 1: Pages 179-183
22	Nov. 29	Order of the union of two finite sets, Cartesian product of two finite sets and its order, characterization of finite sets with different different order, power set of finite sets and its order	Textbook 1: Pages 183-187
	Nov. 30	Quiz 5
23	Dec. 04	Infinite sets: Definition, examples, characterization theorems, Cartesian product of finite and infinite sets; Countably infinite sets: Definition, examples, a characterization theorem	Textbook 1: Pages 187-192
24	Dec. 06	Characterization theorems for countably infinite sets, subsets of countably infinite sets, Q is countable	Textbook 1: Pages 192-195
25	Dec. 11	Union and cross product of countable sets are countable, injecting finite sets into countably infinite sets and countably infinite sets into infinite sets; Uncountable set, decimal expansion of real numbers, and Cantor’s theorem on unaccountability of the set of real numbers	Textbook 1: Pages 195-200
26	Dec. 13	Uncountability of the union and cross product of a nonempty set and an uncountable set, Cardinality of a set, Cantor-Schroder-Bernstain theorem (without proof) and partial ordering of cardinality of sets, Cantor’s theorem: Cardinality of a set is strictly smaller than its power set’s, sum and product of cardinal numbers	Textbook 1: Pages 200-209
	Dec. 14	Quiz 6
27	Dec. 18	Theorem: Card(A) ≤ Card(B) implies Card(P(A)) ≤ Card(P(B)), Corollary: Card(A) = Card(B) implies Card(P(A)) = Card(P(B)); Cardinality of the set of real numbers R; Theorem: Cardinality of the Cartesian product of disjoint sets equals to that of their union; Cardinality of R^n; The continuum and generalized continuum hypotheses.	Textbook 1: Pages 209-214
28	Dec. 20	Cartesian product of members of an arbitrary family sets, the Axiom of Choice, Theorem: If there is an onto function f:A->B, Card(B) ≤ Card(A).	Textbook 1: Pages 214-217

Note: The pages from the textbook listed above may not include some of the material covered in the lectures. Quizzes are 30-50 minutes-long mini exams.