Math 103: Introduction to Abstract Mathematics, Fall 2023
Topics Covered in the Lectures
|
Lecture Number |
Date |
Content |
Corresponding Reading material |
|
1 |
Oct. 03 |
General structure of
mathematical theories: Definition of object of study, axioms, theorems (lemmas,
propositions, corollaries, fundamental theorems), Fermat’s last theorem,
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 |
Textbook
1 (A First Course in Abstract Mathematics): Pages 1-6 |
|
2 |
Oct. 05 |
The 4-color problem and the
need for a precise mathematical language, Statements, their truth value, some basic
mathematical symbols, predicates, qualifiers, negation of a statement, truth
tables, negation of a qualified predicate, compound statements: disjunctions
and conjunctions |
Textbook
1: Pages 6-17 |
|
3 |
Oct. 10 |
Implications, 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 |
Oct. 12 |
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 |
|
5 |
Oct. 17 |
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,
induction axiom, principle of mathematical induction |
Textbook
1: Pages
41-45 & 47-49; Textbook
2: Pages
319-320 |
|
6 |
Oct. 19 |
Examples of applications of induction, complete induction, recursive
definitions |
Textbook
1: Pages 48-57; Textbook 2: Pages
164-177 |
|
7 |
Oct. 24 |
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. 26 |
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 |
|
9 |
Oct. 31 |
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 |
Nov. 02 |
Ordered pairs (a,b) with a ϵ
A and b ϵ B as elements of the
power set of power set of |
Textbook
1: Pages 86-90 |
|
Midterm Exam 1 |
|
||
|
11 |
Nov. 07 |
Relations, the image and inverse image of subsets under a
relation, the domain and range of a relation, equality of two relations,
restriction of a relation, identity relation |
Textbook
1: Pages 95-101 |
|
12 |
Nov. 09 |
Extension of a relation, image and inverse image of the
intersection and union of a collection of sets under a relation, reflexive,
symmetric, antisymmetric, and transitive relations, the inverse of a
relation, composition of two relations and its domain |
Textbook
1: Pages 101-106 |
|
- |
Winter Break |
|
|
|
13 |
Nov. 21 |
Non-commutativity and associativity of composition of
relations, inverse of the composition of two relations, composing a relation
with its inverse (whenever it is possible), Equivalence relations,
equivalence classes and the quotient of a set by an equivalence relation,
partitions of a set |
Textbook 1: Pages 107-113; Textbook
2: Pages 224-230 & 234-239 |
|
14 |
Nov. 23 |
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 |
Textbook
1: Pages 113-119 |
|
15 |
Nov. 28 |
Partially ordered sets (posets), 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 |
Textbook
1: Pages 120-126 |
|
16 |
Nov. 30 |
Supremum property, chains
of a poset, statement of Zorn’s lemma, Well-ordered
posets and Well-Ordering Principle, proof of
well-ordering of natural numbers, application to division algorithm |
Textbook
1: Pages 127-136 |
|
17 |
Dec. 05 |
Functions: Well-defined
relations, notation, everywhere-defined relations and functions, 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 137-146 |
|
18 |
Dec. 07 |
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-154 |
|
Midterm Exam 2 |
|
||
|
19 |
Dec. 12 |
Properties of the inverse
of an invertible function; Transpositions of In:={1,2,…,n}.
Theorem: Transpositions of In are bijections. |
Textbook
1: Pages 155-157 |
|
20 |
Dec. 14 |
Inverse of every
Transpositions of In is itself. Trivial extensions
of Transpositions of In , 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, Non-existence of
everywhere-defined and 1-to-1 functions f: In -> A for proper
subsets of In. |
Textbook
1: Pages 157-160 |
|
21 |
Dec. 19 |
Non-existence of 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 |
|
22 |
Dec. 21 |
Finite sets, order of a
finite sets, finiteness of subsets of finite sets, finiteness and order of
the union of two finite sets |
Textbook
1: Pages 179-184 |
|
23 |
Dec. 26 |
Cartesian product of two finite
sets and its order, characterization of finite sets with different order,
power set of finite sets and its order, Infinite sets: Definition, examples,
characterization theorems, Cartesian product of finite and infinite sets |
Textbook
1: Pages 184-190 |
|
24 |
Dec. 28 |
Countably infinite sets:
Definition, examples, characterization theorems for countably infinite sets,
subsets of countably infinite sets, Q is countable, Union
and cross product of countable sets are countable |
Textbook
1: Pages 190-196 |
|
25 |
Jan. 02 |
Existence of everywhere-defined 1-to-1 functions from
finite sets to countably infinite sets and from to countably infinite sets to
infinite sets; Uncountable sets, decimal expansion of real numbers, Cantor’s
proof of uncountability
of the set of real numbers Uncountability of the
union and cross product of a nonempty set and an uncountable set |
Textbook
1: Pages 197-201 |
|
26 |
Jan. 04 |
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 201-209 |
|
|
Midterm Exam 3 |
|
|
|
27 |
Jan. 09 |
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 Rn ; The
continuum and generalized continuum hypotheses. |
Textbook
1: Pages 209-214 |
|
28 |
Jan. 11 |
Cartesian product of
members of an arbitrary collection of sets, 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.