Definition D1
For a finite set A, |A| = m means that there is a bijection from A to {1, 2, …, m}.
Proof.
(1)A bijection is a correspondence that sends distinct elements to distinct values and omits no value.convention
(2)Hence counting a set is the act of constructing one bijection.(1)
(3)For m = 0, {1, …, 0} is the empty set, and |A| = 0 means A = ∅.(1)
∎
Definition D2
When A ∩ B = ∅, the two sets are called disjoint.
Proof.
If disjoint, no element belongs to both sets at once.convention
∎
Theorem T1
If |A| = m and |B| = n, then |A × B| = mn.
Proof.
(1)Suppose m ≥ 1, n ≥ 1, and choose bijections f : A → {1,…,m} and g : B → {1,…,n}.assumption, D1
(2)To an element (a, b) of A × B, assign h(a,b) = (f(a) − 1)n + g(b).(1)
(3)f(a) ≥ 1 and g(b) ≥ 1, so h(a,b) ≥ 1(1), N
(4)f(a) ≤ m and g(b) ≤ n, so h(a,b) ≤ (m−1)n + n = mn(1), N
(5)Hence h is a correspondence from A × B to {1, …, mn}.(3), (4)
(6)Suppose h(a,b) = h(a′,b′). Both values are of the form (i−1)n + j with j between 1 and n.(1), (2)
(7)That representation is unique, so f(a) = f(a′) and g(b) = g(b′)(6), A1
(8)f and g are bijections, so a = a′ and b = b′. h is injective.(7), (1), D1
(9)Suppose 1 ≤ k ≤ mn. There exist unique i ≥ 1 and j with k = (i−1)n + j and 1 ≤ j ≤ n.A1
(10)j ≥ 1 gives (i−1)n < mn, and n > 0 gives i − 1 < m, that is, i ≤ m.(9), A2, N
(11)f and g are surjective, so there are a with f(a) = i and b with g(b) = j, and for that (a,b), h(a,b) = k. h is surjective.(9), (10), (1), D1
(12)h is a bijection, so |A × B| = mn(5), (8), (11), D1
(13)If m = 0 or n = 0, then A × B is empty and mn = 0, so the equation holds as it stands.D1, N
∎
Theorem T2
If A and B are disjoint and |A| = m, |B| = n, then |A ∪ B| = m + n.
Proof.
(1)Choose bijections f : A → {1,…,m} and g : B → {1,…,n}.assumption, D1
(2)Define h(x) = f(x) for x ∈ A, and h(x) = m + g(x) for x ∈ B.(1)
(3)A and B are disjoint, so each x falls under exactly one of the two cases. h takes a single value.assumption, D2, (2)
(4)If 1 ≤ k ≤ m+n, then k ≤ m or k = m + j (1 ≤ j ≤ n), and the two cases never hold at once.A3
(5)The values of h are at most m or of the form m + j, hence lie in {1, …, m+n}.(2), (1), A3
(6)Suppose h(x) = h(y). By (4) the two values fall in the same case, so x and y are together in A or together in B.(4), (2)
(7)f and g are injective, so x = y. h is injective.(6), (1), D1
(8)If k ≤ m, there is x ∈ A with f(x) = k; if k = m + j, there is x ∈ B with g(x) = j. h is surjective.(4), (1), D1
(9)h is a bijection, so |A ∪ B| = m + n(3), (5), (7), (8), D1
∎
Corollary C1
For two finite sets that need not be disjoint, |A ∪ B| = |A| + |B| − |A ∩ B|
Proof.
(1)A ∪ B = A ∪ (B∖A), and the two sets are disjoint.A4, D2
(2)|A ∪ B| = |A| + |B∖A|(1), T2
(3)B = (A∩B) ∪ (B∖A), and the two sets are disjoint.A5, D2
(4)|B| = |A∩B| + |B∖A|(3), T2
(5)|B∖A| = |B| − |A∩B|(4), A6
(6)|A ∪ B| = |A| + |B| − |A∩B|(2), (5)
(7)If A ∩ B = ∅, then |A∩B| = 0 and (6) reduces to T2.(6), D2, D1
(8)If A ∩ B ≠ ∅, then |A| + |B| counts the elements of A ∩ B twice. That excess is exactly |A∩B|.(6), N
∎