COURSE PROGRESS ON PREVIOUS WEEKS


WEEK 5     
M: Midterm.
W: Discussion of the Midterm. Examples of binary relations and calculations of the inverse, R[X] and R^{-1}[Y] for R = divisibility (i.e. R is on Z and is defined by (a,b)\in R iff a|b) and membership (i.e. R is on A x P(A) and is defined by (x,X)\in R iff x\in X). The definition of a function as a binary relation. Read the following in the book: Page 66 and the examples on page 67 in Section 4.4 and Section 7.2, in particular the examples. Recommended practice problems
F: Injectivity, surjectivity and bijectivity (Remark: when defining bijectivity, I unintentionally wrote ''IF" in place of ``IFF". Thus, in order to avoid misunderstandings, please note that a function is bijective IFF it is both injective and surjective.) Examples: Identity function, projection, function f:R-->R defined by f(x)=x^2. Composition of binary relations. Read the following in the book: Page 66-68, Definition 4.14 and pages 71,12 in Section 4.4 and Section 7.2, in particular the examples. Compare Definition 4.14 with the definition of composition of relations from the lecture. Recommended practice problems

WEEK 4     
M: Proof of the equivalence AxB=BxA <==> A=B for non-empty sets A,B. Discussion of the cases where at least one of the sets A,B is empty. Binary relation from A to B, binary relation on A. Examples Read Section 7.1 in the book. Recommended practice problems
W: Inverse of a relation, image and inverse image of a set under a relation, domain and range of a relation. Definitions Examples: The identity relation, a randomly chosen relation from a three element set into a three element set, the relation <. Read Section 7.1 in the book. Recommended practice problems
F: Midterm review session.

WEEK 3     
M: Proving equality of two sets: direct method with help of sentential logic. Sets nZ. Subsets, inclusion. Examples. The equality of two sets is equivalent to two inclusions. The empty set. The empty set is a subset of any set. Read pages Sections 4.1, 4.2 and 4.3 in the book. Most of those is material we did in the class since the beginning of the quarter. Recommended practice problems
W: Transitivity of inclusion. Basic properties of set operations: commutativity and associativity of intersections and unions, distributivity of the intersection with respect to the union and vice versa, intersection/union of a set with iteself and with the empty set. Interaction of set operations with inclusion. The power set. Complement of a set. The Boolean algebra P(X). Recommended practice problems
F: Complement operation for Boolean algebra P(X). De Morgan laws for the complement operation. Proposition: If X is a subset of Y then P(X) is a subset of P(Y). Ordered pairs. Representation of ordered pair (x,y) as the set {{x},{x,y}}. Cartesian product. Example. Read pages Section 6.2 from the beginning up to Theorem 6.5, including (note Theorem 6.5 in the book is the same as the Proposition in today's lecture). Also read Section 6.1 but skip Theorem 6.2 for the moment. Recommended practice problems

WEEK 2     
M: Holiday
W: Examples on expressing symbolically statements involving ``there exists at most one", ``there exists exactly one", ``x is the only". Negating such statements. Hidden quantifiers. Types of proofs: direct, indirect, proof by contradiction. Examples of these proofs on the statement ``(\forall x\in Z)(x+7 is even ==> x is odd)" Recommended practice problems
Thr:Proving an equivalence. Choosing the right type of proof for a given task. The term ``WLOG". Example: ab is odd <==> both a,b are odd. Proof by cases. (P_1 v P_2) ==> Q is logically equivalent to the conjunction (P_1 ==> Q) AND (P_2 ==> Q). Example: a^2 gives remainder 0 or 2 when divided by 3. Set theory: Equality of sets. Roster notation. Recommended practice problems
F:Describing sets by naming elements (roster notation) and by separation (builder notation). Examples: Describing sets E,O,P, and divisibility using separation. Russel's paradox. Recommended practice problems

WEEK 1     
M: Sentential connectives conjunction, disjunction and negation and their truth tables. Negating of expressions built using these connections; De Morgan's laws. Sets and membership. Read the subsection on conditional and biconditional on page 11 and first half of page 12 in the book and the Section 4.1 on set notation and describing a set starting on page 52. Recommended practice problems
W: Tautology, contradiction, implication, equivalence. Liar's paradox. Quantifiers. Analogy between quantifiers and ``infinite connectives". Some examples on connectives applied to sets. Set difference and symmetric difference. Recommended practice problems
Thr: Converse and contraposition of an implication. Logically equivalent sentential (propositional) expressions. Symbols < and \le. Standard domains: Positive integers, all integers, rational numbers, irrational numbers, real numbers, complex numbers. Quantifiers and their restrictions to domains. Satements expressed by quantifiers restricted to given domains: unabbreviated and abbreviated form. Examples. Recommended practice problems
F: Negating an implication and expressing an implication in terms of disjunction and negation. Negating quantifiers. Examples. Read pages 20-25 in Subsection 2.2 in the book. Recommended practice problems


HOME   MATH 13