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