M13:  INTRODUCTION TO ABSTRACT MATHEMATICS

LECTURE:  M-W-F  3:00 -- 3:50 SH 134   (MAP:BLDG #502)
DISCUSSION:
Tu-Th  5:00 -- 5:50  SST 220B   (MAP:BLDG # 201)

INSTRUCTOR: Martin Zeman, RH 410E
OFFICE HOURS:  Wednesday 10am - 12noon (I may be few minutes late)   and by appointment

TA:  Katie Evans, RH 540M
OFFICE HOURS:   Tue 3:00 - 4:30 and Thr 10:30 -- 12:00

BOOK   By Alessandra Pantano and Neil Donaldson will be used as the text for this class.

HOMEWORK ASSIGNMENTS    HW1   HW2   HW3   HW4   HW5   HW6

COURSE PROGRESS       PREVIOUS WEEKS

WEEK 10
M: Equinumerosity. Finite sets, infinite sets, countable sets (the book uses the obsolete term denumerable" instead), uncountable sets. Cardinality. Examples: Countability of sets N u {0}, 2N, kN, Z, kZ. Theorem: There is no bijection between {1,...,m} and {1,...n} for distinct numbers m,n\in N. There is no bijection between {1,...,n} and N for any n\in N. Theorem: If A is an infinite subset of N then A is countable. Example: If A,B are countable sets then so is their union. Read Section 8.1 in the book. Recommended practice problems
W: Calculating that given sets are countable. Countability of NxN and of Q: typical enumerations. Rules that can be applied to verify countability. R1: If there is a surjection f:N-->A and A is ininite then A is countable. R2: Sets N,Z,Q,NxN,ZxZ,QxQ are countable. R3: If there is a bijection f:A-->A' and a bijection g:B-->B' then there is a bijection h:AxB-->A'xB' R4: If A_1,A_2,...,A_n,... are such that each set A_n is either finite or countable. Denote by A the union of all A_n. Thus, A=A_1 u A_2 u ... u A_n u ... We conclude: A is infinite then A is countable. In particular, if at least one of the sets A_n is countable then A is countable.

WEEK 9
M: Proposition: Assume n,a,b are nonzero integers. If gcd(n,a)=1 and n|ab then n|b. (With proof.) Corollary: If p,q are primes and n is distinct from pq,-pq then n|pq ==> (n|p or n|q). Properties of relations: reflexivity, symmetricity, antisymmetricity, transitivity. Equivalence relations. Ordering relations. Examples: Equality, Congruence modulon n, Divisibility. Read Section 7.3 in the book. Recommended practice problems
W: Example of equivalence relation: E on R^2 defined by (x,y)E(x',y') iff distance((x,y),(0,0))=distance((x',y'),(0,0)). Equivalence class of an element with respect of an equivalence relation. Examples of equivalence classes for equivalence relations Identiy, Congruence mod n, and the distance relation E above. Partition of a set with respect to an equivalence relation E, denoted by P_E. Theorem: If E is an equivalence relation on A then (1) each element of A is an element of some [a]_E, and (2) if [a]_E is distinct from [b]_E then the intersection [a]_E n [b]_E is empty (with proof). Read Section 7.4 in the book. Recommended practice problems
F: Reconstructing the equivalence relation E from its partition P_E. Quotient map. Notation ~ for equivalence relations, A/~ for the corresponding partion. P_E=A/~ is also called the quotient. Abstract definition of a partition of a set $A$. Equivalence relation ~_P induced by a partition P. Conversions ~ --> A/~ --> ~_{A/~} = ~ and P --> ~_P --> A/~_P = P. Geometric examples: Equivalence relation on a rectangle giving a cylinder and a torus. Read Section 7.4 in the book. Recommended practice problems

WEEK 8
M: Division algorithm and its proof using the well-ordering principle.
W: Division algorithm: completion of the proof. Congruence. Theorem: a,b are congruent mod n iff n|(a-b). Modular arithmetic. Calculation of remainders mod n for large numbers. Read Section 3.1 in the book. Recommended practice problems
F: Greatest common divisor. Proof of the existence of greatest common divisors using the well-ordering principle. Euclid's algorithm. Read Section 3.2 in the book. Recommended practice problems

WEEK 7
M: Holiday.
W: Finite tuples. Examples of induction: Counting the number of functions s:{1,...,k} --> {1,...,n}. Theorem A: If A is a nonempty subset of {1,...,n} then A has a smallest element. Read Definition 5.12, Theorem 5.13 and Theorem 5.14 and Section 5.2 in the book. Recommended practice problems
F: Well-ordering principle for N. Theorem: if n>1 is an integer then n is a prime or a product of primes. Proof: Using the well-ordering principle. The division algorithm: statement and an outline of the proof. Read Definition in the book. Recommended practice problems

WEEK 6     ADDITIONAL PRACTICE PROBLEMS FOR WEEK6
M: Practice.
W: Practice.
F: Proof by induction. Examples of induction: The sum of the k^2 for k from 1 to n; the difference 13^n-8^n is divisible by 5, Book Theorem 5.8. Strong induction. Example of strong induction: Book, thoerem 5.16.