Sets, Logic and Proof
Year 1 · 7 sections · 112 concepts · 470 practice questions
What's covered
free1 · Logic and statements13 concepts
- Definition 1.1 · Statements
- Definition 1.2 · Negation, conjunction and disjunction
- Definition 1.3 · Implication
- Definition 1.4 · Converse, contrapositive and biconditional
- Proposition 1.5 · An implication is equivalent to its contrapositive
- Definition 1.6 · Tautologies and logical equivalence
- Theorem 1.7 · De Morgan's laws (logic)
- Proposition 1.8 · Distributive laws (logic)
- Proposition 1.9 · The negation of an implication
- Definition 1.10 · Quantifiers
- Proposition 1.11 · Negating quantifiers
- Remark 1.12 · The order of quantifiers matters
- Check: writing a negation
2 · Techniques of proof22 concepts
- Definition 2.1 · Even, odd, divisibility and primes
- Proposition 2.2 · Parity of sums and products (direct proof)
- Proposition 2.3 · If n² is even then n is even (proof by contrapositive)
- Theorem 2.4 · √2 is irrational (proof by contradiction)
- Lemma 2.5 · Every integer n ≥ 2 has a prime divisor
- Theorem 2.6 · There are infinitely many primes (Euclid)
- Proposition 2.7 · Squares modulo 4 (proof by cases)
- Proposition 2.8 · The triangle inequality
- Remark 2.9 · Disproof by counterexample
- Proposition 2.10 · A non-constructive existence proof
- Proposition 2.11 · Existence and uniqueness proofs
- Axiom 2.12 · The well-ordering principle
- Theorem 2.13 · The principle of mathematical induction
- Proposition 2.14 · Sums of integers and squares
- Proposition 2.15 · Bernoulli's inequality
- Theorem 2.16 · Strong induction
- Theorem 2.17 · Every integer n ≥ 2 is a product of primes
- Definition 2.18 · Factorials and binomial coefficients
- Proposition 2.19 · Pascal's rule
- Theorem 2.20 · The binomial theorem
- Proposition 2.21 · The AM–GM inequality for two numbers
- Check 2.22 · Check: choosing and writing a proof
3 · Sets15 concepts
- Definition 3.1 · Sets, elements and subsets
- Proposition 3.2 · Equality by double inclusion
- Proposition 3.3 · The empty set
- Definition 3.4 · Union, intersection, difference and complement
- Proposition 3.5 · The laws of set algebra
- Theorem 3.6 · De Morgan's laws for sets
- Definition 3.7 · The power set
- Proposition 3.8 · A set with n elements has 2ⁿ subsets
- Definition 3.9 · Ordered pairs and Cartesian products
- Proposition 3.10 · Size and distributivity of products
- Definition 3.11 · Indexed families of sets
- Proposition 3.12 · De Morgan and distributive laws for families
- Theorem 3.13 · Inclusion–exclusion
- Remark 3.14 · Russell's paradox
- Check 3.15 · Check: proving or disproving a set identity
4 · Functions18 concepts
- Definition 4.1 · Functions
- Definition 4.2 · Images and preimages
- Proposition 4.3 · How images and preimages interact with ∪, ∩ and complements
- Proposition 4.4 · Images of preimages and preimages of images
- Definition 4.5 · Injective functions
- Definition 4.6 · Surjective functions
- Definition 4.7 · Bijective functions
- Definition 4.8 · Composition and the identity
- Proposition 4.9 · Composition is associative
- Proposition 4.10 · Composites of injections, surjections and bijections
- Proposition 4.11 · What a composite tells you about its factors
- Definition 4.12 · Inverse functions
- Theorem 4.13 · A function is invertible if and only if it is bijective
- Proposition 4.14 · Properties of inverses
- Theorem 4.15 · One-sided inverses
- Proposition 4.16 · For finite sets of the same size, injective ⇔ surjective
- Definition 4.17 · Restrictions and inclusions
- Check 4.18 · Check: is this function injective, surjective, bijective?
5 · Relations16 concepts
- Definition 5.1 · Relations
- Definition 5.2 · Reflexive, symmetric, antisymmetric, transitive
- Definition 5.3 · Equivalence relations
- Definition 5.4 · Equivalence classes and the quotient set
- Lemma 5.5 · Two classes are equal or disjoint
- Theorem 5.6 · Equivalence classes partition the set
- Theorem 5.7 · Partitions give equivalence relations
- Theorem 5.8 · The division algorithm
- Proposition 5.9 · Congruence modulo n
- Proposition 5.10 · Arithmetic in ℤₙ is well defined
- Definition 5.11 · Well-defined functions on a quotient
- Proposition 5.12 · The equivalence relation of a function
- Definition 5.13 · Partial and total orders
- Definition 5.14 · Maximal, greatest, upper bounds and suprema in a poset
- Proposition 5.15 · Greatest elements are unique and maximal
- Check 5.16 · Check: verifying an equivalence relation or order
6 · Cardinality14 concepts
- Definition 6.1 · Same size, and finite sets
- Proposition 6.2 · Having the same cardinality behaves like equality
- Theorem 6.3 · The pigeonhole principle
- Theorem 6.4 · The generalised pigeonhole principle
- Definition 6.5 · Countable sets
- Proposition 6.6 · Subsets and images of countable sets
- Proposition 6.7 · ℤ and ℕ × ℕ are countable
- Theorem 6.8 · A countable union of countable sets is countable
- Corollary 6.9 · ℚ is countable
- Theorem 6.10 · ℝ is uncountable (Cantor's diagonal argument)
- Corollary 6.11 · The irrationals are uncountable
- Theorem 6.12 · Cantor's theorem
- Theorem 6.13 · The Schröder–Bernstein theorem
- Check 6.14 · Check: countable or uncountable?
7 · The number systems14 concepts
- Definition 7.1 · Recursive definitions
- Definition 7.2 · Fields and ordered fields
- Proposition 7.3 · Consequences of the field axioms
- Proposition 7.4 · Consequences of the order axioms
- Definition 7.5 · Absolute value
- Definition 7.6 · Bounds, suprema and infima
- Proposition 7.7 · The ε-characterisation of the supremum
- Axiom 7.8 · The completeness axiom
- Proposition 7.9 · Infima exist for sets bounded below
- Theorem 7.10 · The Archimedean property
- Theorem 7.11 · ℚ is dense in ℝ
- Corollary 7.12 · The irrationals are dense in ℝ
- Theorem 7.13 · √2 exists in ℝ
- Check 7.14 · Check: finding and proving sup and inf
Try it: a free card from this module
This is exactly what studying looks like inside UniMaths.
Proposition 1.5 · An implication is equivalent to its contrapositive
Contrapositive = same statement. "If it rains, the ground is wet" ≡ "if the ground is dry, it didn't rain". Proof: both fail in exactly one row: true, false. Use it when the negation of the conclusion is easier to work with than the hypothesis.
Proof
Learn all 112 concepts like this
Cards, step-by-step proofs, and 470 questions scheduled so you review right before you forget.