SetTheory

SET 13 · Flashcards

Setup

Uses the Spaced Repetition plugin, like the other decks. Review through the plugin so answers stay hidden until you click.

Basics

What is a set?::A well-defined collection of distinct objects. What makes a collection well-defined?::Membership of any object can be decided objectively, not by opinion. Is “the set of beautiful songs” a set?::No — “beautiful” is subjective, so it’s not well-defined. {1, 2, 2, 3} = ?::{1, 2, 3} — duplicates are ignored. Three ways to represent a set?::List (roster), predicate (set-builder), missing-element (ellipsis). What is {x | P(x)}?::The set of all x for which P(x) is true.

Subsets & equality

Definition of A ⊆ B in logic?::∀x (x ∈ A → x ∈ B) Definition of A = B?::A ⊆ B and B ⊆ A (equivalently ∀x (x ∈ A ↔ x ∈ B)). Definition of A ⊂ B (proper)?::A ⊆ B and A ≠ B. Is ⊆ reflexive? Is ⊂ reflexive?::⊆ yes (A ⊆ A); ⊂ no. Is {{1,2},3} = {1,2,3}?::No — {1,2} is a single element of the first set.

∈ vs ⊆

Is 1 ∈ {{1,2},3}?::No — 1 is inside the inner set, not a direct element. How do you check X ⊆ A?::Check every element of X is an element of A. X ∈ A is equivalent to which subset statement?::{X} ⊆ A Is {1,2} ⊆ {{1,2},3}?::No — 1 and 2 are not elements of it. Is {{1,2}} ⊆ {{1,2},3}?::Yes — its only element {1,2} is in the set.

Special sets

Is ϕ ⊆ A for every set A?::Yes — vacuously true, since x ∈ ϕ is always false. Is ϕ ∈ A for every set A?::No — only if ϕ is listed as an element. |ϕ| and |{ϕ}|?::0 and 1 Is ϕ = {ϕ}?::No — {ϕ} contains one element (ϕ); ϕ contains none. Minimum number of subsets of a non-empty set?::2 — ϕ and the set itself. Universal set in predicate form?::{x | P(x) ∨ ¬P(x)} Empty set in predicate form?::{x | P(x) ∧ ¬P(x)}

Power set & cardinality

Definition of P(A)?::The set of all subsets of A: {x | x ⊆ A}. |A| = n ⇒ |P(A)| = ?::2ⁿ P(ϕ) = ?::{ϕ} P({ϕ}) = ?::{ϕ, {ϕ}} |P(P(P(ϕ)))| = ?::4 Is ϕ ∈ P(A)?::Always yes. X ∈ 2ᴬ is equivalent to…?::X ⊆ A Cardinality of P({0, 1, …, 10})?::2¹¹ = 2048 (11 elements — count the 0!) |P({{ϕ}, 1, {2,3}})| = ?::8 (3 top-level elements)

Cartesian product

Definition of A × B?::{(a, b) | a ∈ A and b ∈ B} |A × B| = ?::|A|·|B| ϕ × A = ?::ϕ Is A × B = B × A in general?::No — only if A = B or one of them is empty. Is A×B×C = (A×B)×C?::No — triples (a,b,c) vs nested pairs ((a,b),c). Number of relations from A (size n) to B (size m)?::2^(nm)

Operations

A − B in terms of ∩?::A ∩ B’ A ∪ B in logic?::x ∈ A ∨ x ∈ B A ∩ B in logic?::x ∈ A ∧ x ∈ B Complement A’ in logic?::x ∉ A (relative to U) (A − B) ∪ (B − A) ∪ (A ∩ B) = ?::A ∪ B A − (A − B) = ?::A ∩ B How many regions in a 3-set Venn diagram?::8

Identities

De Morgan for sets?::(A ∪ B)’ = A’ ∩ B’ and (A ∩ B)’ = A’ ∪ B’ Absorption laws?::A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A Domination laws?::A ∪ U = U and A ∩ ϕ = ϕ Identity laws?::A ∪ ϕ = A and A ∩ U = A Complement laws?::A ∪ A’ = U and A ∩ A’ = ϕ A ⊆ B is equivalent to…?::A ∪ B = B, A ∩ B = A, A − B = ϕ, or B’ ⊆ A’

Symmetric difference

Definition of A ⊕ B?::Elements in A or B but not both. Two formulas for A ⊕ B?::(A ∪ B) − (A ∩ B) and (A − B) ∪ (B − A) A ⊕ A = ?::ϕ A ⊕ ϕ = ?::A A ⊕ U = ?::A’ A ⊕ A’ = ?::U |A ⊕ B| = ?::|A| + |B| − 2|A ∩ B| Does A ⊕ B = A ⊕ C imply B = C?::Yes (cancellation).

Extras

|A ∪ B| = ?::|A| + |B| − |A ∩ B| |A ∪ B ∪ C| = ?::Sum of singles − sum of pairs + triple. Proper subsets of an n-element set?::2ⁿ − 1 Subsets of size k?::C(n, k) Pairs (X, Y) with X ⊆ Y ⊆ A, |A| = n?::3ⁿ Is P(A ∪ B) = P(A) ∪ P(B)?::No — only P(A) ∪ P(B) ⊆ P(A ∪ B). Is P(A ∩ B) = P(A) ∩ P(B)?::Yes. Is P(ℕ) countable?::No — uncountable (Cantor’s theorem). Cantor’s theorem?::|A| < |P(A)| for every set A.


Prev ← SET 12 Practice Problems · Next → SET 14 Memory Tricks and Traps