Explanation
Welcome to The Mapping Maze
All of mathematics is built on two ideas: collections of things, and rules that link them. In the Mapping Maze, you'll count sets with Venn diagrams, test relations, and learn to find where a function lives and what it can reach.
Every calculus question later depends on this.
A set with n elements has 2ⁿ subsets
Every element is either in a subset or out. Two choices each, so a set with n elements has two to the n subsets, including the empty set and the set itself.
A set with n elements has 2ⁿ subsets
N(A ∪ B) = n(A) + n(B) − n(A ∩ B)
To count the union, add both sets, then subtract the overlap, which you counted twice.
n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
De Morgan
De Morgan's laws: the complement of a union is the intersection of complements, and the other way round. Flip the symbol, complement each set.
De Morgan: (A ∪ B)′ = A′ ∩ B′ · (A ∩ B)′ = A′ ∪ B′
A × B = all ordered pairs (a, b) · n(A × B) =…
The Cartesian product pairs every element of A with every element of B. A relation is any subset of these pairs, so there are two to the power m n relations.
A × B = all ordered pairs (a, b) · n(A × B) = n(A)·n(B) · relations from A to B: 2^(n(A)·n(B))
Reflexive (a, a) ∈ R for all a · symmetric (a, b)
A relation is reflexive if everything is related to itself, symmetric if it works both ways, and transitive if it chains. All three together make an equivalence relation, like 'has the same remainder when divided by three'.
Reflexive (a, a) ∈ R for all a · symmetric (a, b) → (b, a) · transitive (a, b), (b, c) → (a, c) · all three = equivalence
Worked example
100 students: 60 like tea, 50 like coffee, 20 like both. Tea or coffee = 60 + 50 − 20 = 90.
Neither = 100 − 90 = 10.