LECTURE:  M-W-F  3:00 -- 3:50 SH 134   (MAP:BLDG #502) 
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

COURSE INFORMATION AND POLICIES  GRADING  UCI Academic Honesty Policy   UCI Student Resources Page    

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


HOMEWORK ASSIGNMENTS    HW1   HW2   HW3   HW4   HW5   HW6        


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

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.



Last Modified: March 15, 2017