ARCHIVE PAGE

This page is not updated any more.

Study guide for the midterm
(MATH 6100-090, Fall 2018)
This document will be continuously updated until we review for the midterm on September 26
Last update: Wednesday, September 26, 2018 (no more updates will occur)

  1. Definitions and notions to remember:
    conjunction, disjunction, negation, conditional, biconditional, tautology, contradiction (Section 1.1); P implies Q, P is logically equivalent to Q (Section 1.2), bound variable, existential quantifier, universal quantifier, even and odd integers (Definition 2.1.2), divisibility (Definition 2.2.1), partial order (from your notes), proofs by contrapositive and by contradiction (Section 2.3), rational and irrational numbers (Definition 2.3.3), prime and composite numbers (Definition 2.3.6), subset (Definition 3.2.2), proper subset and equality of sets (Definition 3.2.5), power set (Definition 3.2.8), union and intersection (Definition 3.3.1), disjoint sets (Definition 3.3.4), set difference (Definition 3.3.5), Cartesian product (Definition 3.3.9), families of sets (Definition 3.4.2), infinite unions and intersections (Definition 3.4.3), functions (Definition 4.1.1), special maps, restriction and extension (Definition 4.1.3), image and inverse image (Definition 4.2.1), composing functions (Definition 4.3.1), left and right inverses (Definition 4.3.6), injections, surjections and bijections (Definition 4.4.2), Relations (Definition 5.1.1), reflexive, symmetric and transitive relations (Definition 5.1.5), equivalence relation (Definition 5.3.1), equivalence classes (Definition 5.3.3), cardinality (Definition 6.5.1), finite, countable and infinite sets (Definition 6.5.4), smaller or equal sets (Definition 6.5.9), cardinality of a finite set as a natural number (Definition 6.6.1).

  2. Exercises you should be able to perform:
    Translate a statement into a formula, build a truth table, prove or disprove it using truth tables. Write a set in set notation, using a defining property, or by listing its elements.

  3. Statements you should be able to prove:
    Any of the logical implications listed in Fact 1.3.1 and any logical equivalence listed in Fact 1.3.2 (I will provide the lists, you have to work out the truth table), facts about even and odd integers (Theorem 2.1.3), divisibility on nonnegative integers is a partial order (Theorem 2.2.2 and your notes), any integer divides zero (Theorem 2.2.3), an integer has the same parity as its square (Theorem 2.3.1 and Exercise 2.2.4), the square root of 2 is irrational (Theorem 2.3.5), n2+n is even (Theorem 2.4.1), properties of the subset relation (Lemma 3.2.4), laws on union and intersection (Theorem 3.3.3), no set has the same cardinality as its power set (Theorem 6.5.7), the set of real numbers is uncountable (Theorem 6.7.3)

  4. Statements whose proof techniques you should be able to reproduce to prove similar statements:
    If xy is irrational then x or y is irrational (Theorem 2.4.2), a divides b and b divides a if and only if a=b or a=-b (Theorem 2.4.3), mn is odd iff both m and n are odd (Theorem 2.4.4), solving radical equations (Section 2.5), for all a there is a b such that a2-b2+4=0 (Proposition 2.5.3), there is an x such that (3-x)(y2+1)>0 for all y (Proposition 2.5.4), summation formula for an arithmetic sequence (Proposition 6.3.3), Proposition 6.3.7, every positive integer is one, a prime, or a product of finitely many primes (Theorem 6.3.10), closed form formula for the Fibonacci numbers (formula (6.4.1), I would provide it, you would need to prove it by induction).

  5. Statements you should be able to state (without proof):
    Completeness theorem (from your notes), analogues of De Morgan's laws for quantifiers (Fact 1.5.1), implications and equivalences listed in Fig. 1.5.1, properties of image and inverse image (Theorem 4.2.4), associative and identity laws for composing functions (Lemma 4.3.5), every left inverse equals every right inverse (Lemma 4.3.7), composing injections and surjections (Lemma 4.4.4), one sided inverses, injectivity and surjectivity (Theorem 4.4.5), having the same cardinality is an equivalence (Lemma 6.5.2), the set of natural numbers is infinite (Lemma 6.5.5), a subset of a countable set is countable (Theorem 6.6.7), every infinite set has a countably infinite subset (Theorem 6.6.11), the set of rational numbers is countably infinite (Theorem 6.7.1).

  6. What to expect
    The exam will be closed book. I will provide a list of logical implications and equivalences listed in Fact 1.3.1 and 1.3.2. You will have 80 minutes to answer about 10 questions. Some questions may ask you to state and prove a theorem from the list above, others may be like the exercises from your homework assignments. Even if a statement is listed "without proof" above, you must remember the proof of those parts of it that were on a homework assignment!