Discrete Structures Workbook

(a) ⋃_n=2^∞ Aₙ = {2, 3, 4, …} = ℕ ∖ {1}. If m ≥ 2, then m is divisible by itself, so m ∈ A_m and m is in the union. The number 1 is divisible by no n ≥ 2, so it is in none of the sets.

(b) ⋂_n=2^∞ Aₙ = ∅. Suppose m is in every Aₙ. Then m ∈ A_m+1, so m + 1 divides m; but 0 < m < m + 1, a contradiction.

This is Exercise 2.9 of Lecture 1. Compare Exercise 1.6(c), where the union runs over the primes and gives the same answer.

Let A₁ = A ∖ M. Then M ∪ A = M ∪ A₁ and M ∩ A₁ = ∅. As a subset of the countable set A, A₁ is finite or countable (Theorem 10). If A₁ = ∅, then M ∪ A = M and the identity map is a bijection. So assume A₁ ≠ ∅.

Since M is infinite, it contains a countable subset B = {b₁, b₂, b₃, …} (Theorem 12). The set B ∪ A₁ is countable (Theorem 11: a union of a countable and a finite or countable set). List it without repetition as c₁, c₂, c₃, …; then g(bₙ) = cₙ is a bijection g: B → B ∪ A₁.

Define f: M → M ∪ A by f(x) = g(x) for x ∈ B and f(x) = x for x ∈ M ∖ B. We have the disjoint unions

M = (M ∖ B) ∪ B and M ∪ A = (M ∖ B) ∪ (B ∪ A₁).

f maps M ∖ B onto itself by the identity and B onto B ∪ A₁ by the bijection g, and the pieces do not overlap. So f is one-to-one and onto, and M ~ M ∪ A. ∎

Explicit version of g (Hilbert's hotel). If A₁ = {α₁, …, α_k} is finite: g(bₙ) = αₙ for n ≤ k and g(bₙ) = b_n−k for n > k. If A₁ = {α₁, α₂, …} is countable: g(b_2n−1) = bₙ and g(b_2n) = αₙ.

• Did you use A ∖ M, so that elements of A already in M are not counted twice?
• Did you cover the case where A ∖ M is finite (or empty), not only the countable case?
• Did you find a countable subset of M and say why it exists?
• Did you define an actual bijection and check both one-to-one and onto?
• “Both sets are infinite, so they are equivalent” is not a proof: ℕ and ℝ are both infinite and not equivalent.

(1) Let p = “The teacher is present” and q = “All the students completed their homework”. Then ¬p = “The teacher is absent” and ¬q = “Some students did not complete their homework”.

Notice that (b) and (c) are negations of each other, which is a good check. Choosing p = “the teacher is absent” and q = “some students did not complete their homework” also works: the formulas change (for example (a) becomes p → q, negated to p ∧ ¬q), but the English answers are the same.

x + 1 > 2x ⟺ x < 1, so over the integers the truth set is T_Q = {…, −2, −1, 0}. It is neither empty nor all of ℤ, which settles (d)–(g) at once.

(a) (∀x ∈ A)(x + 3 ≠ 10), true. (b) (∃x ∈ A)(x + 3 ≥ 10), false. (c) (∀x ∈ A)(x + 3 ≥ 5), false. (d) (∃x ∈ A)(x + 3 > 7), true.

Flip the quantifier and negate the condition (= becomes ≠, < becomes ≥, ≤ becomes >). Each negation has the opposite truth value of the original.

(a) P(−5) ∨ P(−3) ∨ P(−1) ∨ P(1) ∨ P(3) ∨ P(5)

(b) P(−5) ∧ P(−3) ∧ P(−1) ∧ P(1) ∧ P(3) ∧ P(5)

(c) P(−5) ∧ P(−3) ∧ P(−1) ∧ P(3) ∧ P(5)

(d) P(1) ∨ P(3) ∨ P(5)

(e) (¬P(−5) ∨ ¬P(−3) ∨ ¬P(−1) ∨ ¬P(1) ∨ ¬P(3) ∨ ¬P(5)) ∧ (P(−5) ∧ P(−3) ∧ P(−1)). Since the second part makes P(−5), P(−3), P(−1) true, this simplifies to P(−5) ∧ P(−3) ∧ P(−1) ∧ (¬P(1) ∨ ¬P(3) ∨ ¬P(5)).

(P(1) ∧ ¬P(2) ∧ ¬P(3)) ∨ (¬P(1) ∧ P(2) ∧ ¬P(3)) ∨ (¬P(1) ∧ ¬P(2) ∧ P(3))

(a) xxy′y′z = xy′z (b) 0, because it contains y and y′ (c) xxy′y′z′t = xy′z′t (d) 0, because of y and y′. Laws used: commutative, xx = x, xx′ = 0.

(a) xxy′ + xx′y + xy′z = xy′ + 0 + xy′z = xy′ (absorption). CSoP: xy′(z + z′) = xy′z + xy′z′.

(b) xy + xz′ + y′zy + y′zz′ = xy + xz′. CSoP: xy(z + z′) + x(y + y′)z′ = xyz + xyz′ + xy′z′.

(c) (x′ + y)′ = xy′, so E = xy′ + y′z. CSoP: xy′z + xy′z′ + x′y′z (the product xy′z appears twice and is kept once).

(d) (x′y)′ = x + y′, so E = (x + y′)(x′ + xyz′) = xx′ + xyz′ + x′y′ + xyy′z′ = xyz′ + x′y′. CSoP: xyz′ + x′y′z + x′y′z′.

(e) (x + y)′ = x′y′ and (xy′)′ = x′ + y, so E = x′y′(x′ + y) = x′y′ + x′yy′ = x′y′. CSoP: x′y′z + x′y′z′.

(f) (x + yz)′ = x′(yz)′ = x′(y′ + z′), so E = yx′y′ + yx′z′ = x′yz′, which is already a minterm.

(a) E₁ = x′y + y′z′. The squares are xy′z′, x′yz, x′yz′, x′y′z′; the prime implicants are x′y, x′z′, y′z′, of which x′y and y′z′ are essential and already cover everything.

(b) E₂ = xy′ + xzt′ + x′z′t + y′zt′, unique (4 products, 11 literals). All four are essential.

(c) Two minimal sums: E₃ = xyzt + xz′t′ + x′z′t + y′z′t′ and E₃ = xyzt + xz′t′ + x′z′t + x′y′z′. The square xyzt is isolated, so it stays a 4-literal product; xz′t′ and x′z′t are essential; the square x′y′z′t′ can go with either neighbour.

(a) The AND gates receive (A′, B, C), (A′, C′) and (B, C′), so Y = A′BC + A′C′ + BC′.

(b) The AND gates receive (A, B, C), (A′, B, C) and (A, B′, C′), so Y = ABC + A′BC + AB′C′.

Not asked, but useful practice: (a) simplifies to A′B + A′C′ + BC′, and (b) to BC + AB′C′.

(a) Three AND gates (3, 2 and 2 inputs) into a three-input OR gate:

(b) Three three-input AND gates into a three-input OR gate:

Your drawing can be arranged differently; what matters is which inputs, complemented or not, reach each AND gate.

(a) 100001 (positions 1 and 6 are all ones) (b) 00111000 (positions 3, 4, 5) (c) 00110000 (positions 3, 4).

(a) 100111 (all zeros only in positions 2 and 3) (b) 10100111 (positions 2, 4, 5) (c) 11111101 (position 7).

(a) 00011000 (b) 01110111 (c) 00000111

(a) xy = 00001111 · 00110011 = 00000011; x′z = 11110000 · 01010101 = 01010000; sum 01010011.

(b) A sum of minterms, so read the positions from Table 5: xyz′ → 7, xy′z′ → 5, x′y′z′ → 1, giving 10001010.

(a) Positions 1, 5, 7: E = x′y′z′ + xy′z′ + xyz′, which simplifies to y′z′ + xz′. This is the same function as 2.9(b).

(b) Positions 4, 8: E = x′yz + xyz = yz.

(c) Positions 3, 4: E = x′yz′ + x′yz = x′y.

(a) Three minimal sums, each with 4 products and 10 literals:

zt′ + x′y + yz′t + xy′t
zt′ + x′y + xz′t + xy′t
zt′ + x′y + xz′t + xy′z

The zt′ column and the x′y row are essential. The squares xyz′t, xy′zt and xy′z′t remain: xyz′t pairs with its neighbour below (xz′t) or with the bottom row across the edge (yz′t), and xy′zt pairs to its right (xy′z) or across the side edge (xy′t).

(b) One minimal sum: zt′ + yt′ + yz + xy′z′ (4 products, 9 literals). The prime implicant xt′ is not needed.

(a) E = y′ + z′t. The two middle rows (y′) are full, an 8-square rectangle, and z′t covers the rest of the last column.

(b) E = xy′ + y′zt + xzt′. The row xy′ is full; x′y′zt needs y′zt; xyzt′ needs xzt′.

(a) The circuit computes Y = AB′C + ABC′ + AB′C′. On the map, AB′C + AB′C′ = AB′ and ABC′ + AB′C′ = AC′, so Y = AB′ + AC′:

(b) The circuit computes Y = ABC + A′BC′ + ABC′. Then ABC + ABC′ = AB and A′BC′ + ABC′ = BC′, so Y = AB + BC′:

(a) The inputs in order are 000, 001, 010, 011, 100, 101, 110, 111, with 0, 1, 1, 2, 1, 2, 2, 3 ones. The odd counts are in positions 2, 3, 5, 8, which is exactly where 01101001 has its 1s. Changing any one switch changes the count by one and so flips the parity, which toggles the light; so each switch controls the light from any state.

(b) L = A′B′C + A′BC′ + AB′C′ + ABC. On the map the four squares form a checkerboard: no two are adjacent, so every square is its own prime implicant and this CSoP is already minimal (this is A ⊕ B ⊕ C).

Step 1: L = x′y′z′ + x′yz + xy′z′ + xyz′ + xyz.

Steps 2–3: x′y′z′ + xy′z′ = y′z′ and x′yz + xyz = yz are essential. The square xyz′ is left; it pairs with xyz (xy) or with xy′z′ (xz′). Two minimal sums, 3 products and 6 literals each:

L = y′z′ + yz + xy or L = y′z′ + yz + xz′

(xy′ + z′)′(x + yz′) = (x′ + y)z(x + yz′) = x′zx + x′zyz′ + yzx + yzyz′ = xyz

(x′z + y)(y′z)′ = (x′z + y)(y + z′) = x′yz + x′zz′ + y + yz′ = x′yz + y

So E = xyz + x′yz + y + x′z + xy′z′ = y + x′z + xy′z′ (absorption).

CSoP: y(x + x′)(z + z′) + x′(y + y′)z + xy′z′ = xyz + xyz′ + x′yz + x′yz′ + x′y′z + xy′z′.

T(E): the minterms sit in positions 8, 7, 4, 3, 2, 5, so T(E) = 01111011.

Not asked, but the map shrinks it further to y + x′z + xz′.

Positions 1, 2, 4, 5, 8: CSoP(E) = x′y′z′ + x′y′z + x′yz + xy′z′ + xyz.

yz and y′z′ are essential; x′y′z is left and goes with x′y′ or x′z:

E = yz + y′z′ + x′y′ or E = yz + y′z′ + x′z

(A) Two minimal sums, 5 products and 14 literals each:

yz′ + x′yt + xy′z + y′zt′ + xz′t′
yz′ + x′yt + xy′z + y′zt′ + xy′t′

(B) One minimal sum: E = z′t′ + yt + xy′.

For every x ∈ S:

x ∈ (A ∪ B)′ ⟺ x ∉ A ∪ B ⟺ ¬(x ∈ A ∨ x ∈ B) ⟺ x ∉ A ∧ x ∉ B ⟺ x ∈ A′ ∧ x ∈ B′ ⟺ x ∈ A′ ∩ B′.

The third step is De Morgan's law for propositions. Both sets have the same elements, so they are equal. ∎

The sheet writes U − (A ∪ B) in the second step; here the universal set is called S.

Let Aₙ be the set of polynomials of degree exactly n (put the constants, including 0, in A₀). Then P = A₀ ∪ A₁ ∪ A₂ ∪ ⋯, a countable union, so it is enough to show each Aₙ is countable.

Let Bₙ = A₀ ∪ ⋯ ∪ Aₙ be the polynomials of degree at most n. B₀ = A₀ = ℚ is countable. Suppose Bₙ₋₁ is countable. For each a ∈ ℚ, the set {a xⁿ + q : q ∈ Bₙ₋₁} is in bijection with Bₙ₋₁, hence countable. Then Bₙ = ⋃_a∈ℚ {a xⁿ + q : q ∈ Bₙ₋₁} is a countable union of countable sets, so it is countable. By induction every Bₙ is countable, and Aₙ ⊆ Bₙ is infinite (it contains xⁿ + q for every q ∈ ℚ), so it is countable too. ∎

The sheet's proof fixes aₙ, …, a₁, lets a₀ run through ℚ, then frees a₁, and so on: the same induction, written out step by step. It writes P = ∑ Aₙ for the disjoint union ⋃ Aₙ. Another route: aₙxⁿ + ⋯ + a₀ ↦ (aₙ, …, a₀) is a bijection from Aₙ onto a subset of ℚⁿ⁺¹, which is countable.

Step 1: positions 2, 4, 6, 7, 8 give L = x′y′z + x′yz + xy′z + xyz′ + xyz.

Steps 2–3: the four squares with z form a block, and xyz′ pairs with xyz: L = z + xy.

(x + y′z′)′ = x′(y + z), so (xy + z′)x′(y + z) = xyx′y + xyx′z + x′yz′ + x′zz′ = x′yz′.

(xy′ + z)′ = (x′ + y)z′ and (yz′)′ = y′ + z, so (x′ + y)z′(y′ + z) = x′y′z′ + x′z′z + yy′z′ + yz′z = x′y′z′.

So E = x′yz′ + x′y′z′ + x′y + x′yz′ = x′y′z′ + x′y. CSoP: x′y′z′ + x′yz + x′yz′, positions 1, 4, 3, so T(E) = 10110000.

Positions 1, 3, 4, 7, 8: CSoP(E) = x′y′z′ + x′yz′ + x′yz + xyz′ + xyz. The four y squares form a block, and x′y′z′ pairs with x′yz′: E = y + x′z′.

(A) One minimal sum: E = xt′ + xz′ + yz′ + x′yt + y′zt′ (5 products, 12 literals).

(B) Three minimal sums, 4 products and 10 literals each, all containing z′t′ + xy′:

z′t′ + xy′ + x′yz′ + x′zt
z′t′ + xy′ + x′yt + x′zt
z′t′ + xy′ + x′yt + y′zt

For every x ∈ S:

x ∈ (A ∩ B)′ ⟺ x ∉ A ∩ B ⟺ ¬(x ∈ A ∧ x ∈ B) ⟺ x ∉ A ∨ x ∉ B ⟺ x ∈ A′ ∨ x ∈ B′ ⟺ x ∈ A′ ∪ B′.

So the two sets have the same elements. ∎

The set is A = ℚ × ℚ. For each a ∈ ℚ let Bₐ = {(a, y) : y ∈ ℚ}. The map y ↦ (a, y) is a bijection ℚ → Bₐ, so each Bₐ is countable. Every point (x, y) lies in exactly one of them, Bₓ, so A = ⋃_a∈ℚ Bₐ, a union of countably many countable sets. Hence A is countable; it is infinite, since it contains B₀. ∎

Step 1: positions 1, 4, 5, 7, 8 give L = x′y′z′ + x′yz + xy′z′ + xyz′ + xyz.

Steps 2–3: y′z′ and yz are essential; xyz′ goes with xy or xz′:

L = y′z′ + yz + xy or L = y′z′ + yz + xz′

(x + y′)z′(x′ + y′z) = xz′x′ + xz′y′z + y′z′x′ + y′z′y′z = x′y′z′

(x′z + y)(y + z′) = x′yz + x′zz′ + y + yz′ = x′yz + y

So E = x′y′z′ + x′yz + y + xz′ + x′y′z = x′y′ + xz′ + y.

CSoP: every minterm except xy′z: x′y′z′ + x′y′z + x′yz′ + x′yz + xy′z′ + xyz′ + xyz. Only position 6 is 0, so T(E) = 11111011.

Not asked, but since E′ = xy′z, the shortest form is E = x′ + y + z′.

This is the truth table of Task 1, so the answers are the same: E = yz + y′z′ + xy or E = yz + y′z′ + xz′.

(A) One minimal sum: E = y + zt′ + xt′.

(B) One minimal sum: E = yz′ + z′t′ + x′zt + xy′t′ (4 products, 10 literals).

Let M be infinite. It contains a countable subset A = {a₁, a₂, a₃, …} with all aₙ distinct. Split it as A₁ = {a₁, a₃, a₅, …} and A₂ = {a₂, a₄, a₆, …}.

Define f : M → M ∖ A₂ by f(aₙ) = a₂ₙ₋₁ on A and f(x) = x for x ∈ M ∖ A. It maps A one-to-one onto A₁ and fixes M ∖ A, so it is a bijection from A ∪ (M ∖ A) = M onto A₁ ∪ (M ∖ A) = M ∖ A₂.

So M ∼ M ∖ A₂, and M ∖ A₂ is a proper subset of M because a₂ ∉ M ∖ A₂. ∎

For every x ∈ S:

x ∈ (A ∪ B)′ ⟺ x ∉ A ∪ B ⟺ ¬(x ∈ A ∨ x ∈ B) ⟺ x ∉ A ∧ x ∉ B ⟺ x ∈ A′ ∧ x ∈ B′ ⟺ x ∈ A′ ∩ B′.

So the two sets have the same elements. ∎

Step 1: L = x′y′z + x′yz + xy′z′ + xyz′ + xyz.

Steps 2–3: x′z (x′y′z + x′yz) and xz′ (xy′z′ + xyz′) are essential. xyz is left; it pairs with xyz′ (xy) or with x′yz (yz):

L = xz′ + x′z + xy or L = xz′ + x′z + yz

((x + y)′ + z)′ = (x + y)z′ and (x′ + yz′)′ = x(y′ + z), so (xz′ + yz′)(xy′ + xz) = xy′z′ + xzz′ + xyy′z′ + xyzz′ = xy′z′.

(xy + z′)′ = (x′ + y′)z, and (x′ + y′)z · yz′ = 0 because of zz′.

So E = xy′z′ + x′z + x′yz′. CSoP: xy′z′ + x′yz + x′y′z + x′yz′, positions 5, 4, 2, 3, so T(E) = 01111000.

This is the truth table of Task 1: E = xz′ + x′z + xy or E = xz′ + x′z + yz.

(A) One minimal sum: E = xz′ + yz′ + y′t + xyt′ + x′y′z (5 products, 12 literals).

The solution sheet gives xz′ + yz′ + z′t + y′t + x′y′z + xyt′. That sum is equivalent, but z′t is redundant: its four squares are already covered by y′t, yz′ and xz′. Drop it to get the minimal sum.

(B) One minimal sum: E = xy′ + yz′ + yt.

An interval is determined by its end points, so the set is A = {(r₁, r₂) : r₁, r₂ ∈ ℚ, r₁ < r₂}.

For each r₁ ∈ ℚ let A(r₁) = {(r₁, r₂) : r₂ ∈ ℚ, r₂ > r₁}. The map (r₁, r₂) ↦ r₂ is a bijection from A(r₁) onto {q ∈ ℚ : q > r₁}, an infinite subset of the countable set ℚ. So each A(r₁) is countable.

Every interval lies in exactly one family, so A = ⋃_r₁∈ℚ A(r₁): a union of countably many countable sets. Hence A is countable. ∎

The same argument works for closed or half-open intervals: each kind is countable, and a union of four countable sets is countable.

For every x ∈ S:

x ∈ (A ∩ B)′ ⟺ x ∉ A ∩ B ⟺ ¬(x ∈ A ∧ x ∈ B) ⟺ x ∉ A ∨ x ∉ B ⟺ x ∈ A′ ∨ x ∈ B′ ⟺ x ∈ A′ ∪ B′.

So the two sets have the same elements. ∎

Step 1: positions 1, 2, 4, 5, 8 give L = x′y′z′ + x′y′z + x′yz + xy′z′ + xyz.

Steps 2–3: yz and y′z′ are essential; x′y′z goes with x′y′ or x′z:

L = yz + y′z′ + x′y′ or L = yz + y′z′ + x′z

(x′ + y)z(x + yz′) = x′zx + x′zyz′ + xyz + yzyz′ = xyz

(x + z′)y′ · y′z = xy′z + z′y′z = xy′z

So E = xyz + xy′z + x′z + xy′z′. CSoP: xyz + xy′z + x′yz + x′y′z + xy′z′, positions 8, 6, 4, 2, 5, so T(E) = 01011101.

Not asked, but xyz + xy′z + x′z = z, so E = z + xy′.

The truth table of Task 1 again: E = yz + y′z′ + x′y′ or E = yz + y′z′ + x′z.

(A) Two minimal sums, 5 products and 14 literals each:

yz′ + x′yt + xy′z + y′zt′ + xz′t′
yz′ + x′yt + xy′z + y′zt′ + xy′t′

(B) One minimal sum: E = yt + xy′ + z′t′.

The sheet's order, starting from {e, f}:

Total weight 18. At step 6 the tree is {a, b, e, f, i, j} and both {f, g} and {j, k} leave it with weight 3. Either choice gives a minimum spanning tree of weight 18.

This is the same task as Fall 2025, Variant 1, Task 7; the model proof is there. In short: let Bₙ be the polynomials of degree at most n. B₀ = ℚ is countable, and Bₙ = ⋃_a∈ℚ {a xⁿ + q : q ∈ Bₙ₋₁} is a countable union of countable sets. So every Bₙ is countable, and the set of all polynomials, ⋃ₙ Bₙ, is countable too. ∎

Step 1: positions 2, 4, 5, 6, 7, 8 give L = x′y′z + x′yz + xy′z′ + xy′z + xyz′ + xyz.

Steps 2–3: the whole x row and the four z squares are two 4-square blocks, so L = x + z. The circuit is a single OR gate with inputs x and z; no AND gates are needed.

(x + y)z′ · yz′ = xyz′ + yz′ = yz′

(xy′ + y′z′)(y′z + x) = xy′z + xy′ + y′z′y′z + xy′z′ = xy′

So E = yz′ + xy′ + x′z + xy′z′ = yz′ + xy′ + x′z.

CSoP: xyz′ + x′yz′ + xy′z + xy′z′ + x′yz + x′y′z: every minterm except x′y′z′ and xyz. So T(E) = 01111110.

Positions 1, 2, 4, 5, 6: CSoP(E) = x′y′z′ + x′y′z + x′yz + xy′z′ + xy′z.

The four y′ squares form a block, and x′yz pairs with x′y′z: E = y′ + x′z.

The sheet's order, starting from {b, f}:

Total weight 24. From step 4 on there are several edges of weight 3 to choose from, so other orders (and other trees) are possible, all of weight 24.

(A) One minimal sum: E = x′y + x′z + yz + yt + xy′z′ (5 products, 11 literals).

(B) One minimal sum: E = x′z + y′z′ + y′t′ + xyt (4 products, 9 literals).

The sheet counts 12 literals for (A); the sum it gives has 11.

Let x ∈ A ∩ B. Then x ∈ A and x ∈ B; in particular x ∈ A. So A ∩ B ⊆ A.

Let x ∈ A. Then the statement “x ∈ A or x ∈ B” is true, so x ∈ A ∪ B. So A ⊆ A ∪ B. ∎

x ∈ B ∖ A ⟺ x ∈ B ∧ x ∉ A ⟺ x ∈ B ∧ x ∈ A′ ⟺ x ∈ B ∩ A′.

The steps use the definitions of difference, complement and intersection. Both sets have the same elements. ∎

This identity is the most useful tool for differences: it turns every ∖ into ∩ and ′, so the laws of Table 1 apply.

⊆: let x ∈ A ∪ (A ∩ B). Then x ∈ A or x ∈ A ∩ B. In the second case also x ∈ A. So x ∈ A either way.

⊇: A ⊆ A ∪ (A ∩ B) by P1. So A ∪ (A ∩ B) = A.

Second law: A ∩ (A ∪ B) ⊆ A by P1. If x ∈ A, then x ∈ A ∪ B (P1), so x ∈ A ∩ (A ∪ B). ∎

(a) ¬(p → q) ≡ ¬(¬p ∨ q) ≡ ¬¬p ∧ ¬q ≡ p ∧ ¬q (conditional law, De Morgan, double negation).

(b) (p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q) ≡ (¬p ∨ ¬q) ∨ (p ∨ q) ≡ (¬p ∨ p) ∨ (¬q ∨ q) ≡ T ∨ T ≡ T (conditional law, De Morgan, associative and commutative laws, negation law, domination). ∎

(1) ⟹ (2). A ∩ B ⊆ A always (P1). If x ∈ A, then x ∈ B by (1), so x ∈ A ∩ B. Hence A ∩ B = A.

(2) ⟹ (3). B ⊆ A ∪ B always. If x ∈ A ∪ B, then either x ∈ B, or x ∈ A = A ∩ B, and then x ∈ B too. Hence A ∪ B = B.

(3) ⟹ (1). If x ∈ A, then x ∈ A ∪ B = B. Hence A ⊆ B. ∎

B ⊆ A ∪ B = A, and A = A ∩ B ⊆ B (both by P1). So A ⊆ B and B ⊆ A, that is, A = B. ∎

(A ∪ B) ∖ (A ∩ B) = (A ∪ B) ∩ (A ∩ B)′ = (A ∪ B) ∩ (A′ ∪ B′)

= (A ∩ A′) ∪ (A ∩ B′) ∪ (B ∩ A′) ∪ (B ∩ B′) = ∅ ∪ (A ∩ B′) ∪ (B ∩ A′) ∪ ∅

= (A ∩ B′) ∪ (B ∩ A′) = (A ∖ B) ∪ (B ∖ A).

Laws used: P2, De Morgan, distributive (twice), complement, identity, P2 again. ∎

x ∈ (A − C) − (B − C) ⟺ (x ∈ A ∧ x ∉ C) ∧ ¬(x ∈ B ∧ x ∉ C)

⟺ (x ∈ A ∧ x ∉ C) ∧ (x ∉ B ∨ x ∈ C)

⟺ (x ∈ A ∧ x ∉ C ∧ x ∉ B) ∨ (x ∈ A ∧ x ∉ C ∧ x ∈ C)

⟺ (x ∈ A ∧ x ∉ B ∧ x ∉ C) ∨ F ⟺ x ∈ (A − B) − C.

Definitions, De Morgan, distributive law, negation and identity laws. ∎

(a) Counterexample: A = {1}, B = {2}. Then (A − B) ∪ B = {1} ∪ {2} = {1, 2} ≠ A.

(b) (A − B) ∪ B = (A ∩ B′) ∪ B = (A ∪ B) ∩ (B′ ∪ B) = (A ∪ B) ∩ U = A ∪ B (P2, distributive, complement, identity).

(c) By (b), (A − B) ∪ B = A ⟺ A ∪ B = A ⟺ B ⊆ A, by P6 with the roles of A and B swapped. ∎

x ∈ A ∩ (B ∪ C) ⟺ x ∈ A ∧ (x ∈ B ∨ x ∈ C) ⟺ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) ⟺ x ∈ (A ∩ B) ∨ x ∈ (A ∩ C) ⟺ x ∈ (A ∩ B) ∪ (A ∩ C).

The second step is the distributive law of propositions; the others are definitions. ∎

Notice the pattern: every law of sets is the matching law of logic applied to the statements “x ∈ A”, “x ∈ B”, “x ∈ C”.

Fix any domain and any predicate P. ¬∀x P(x) is true ⟺ ∀x P(x) is false ⟺ there is an a in the domain with P(a) false ⟺ there is an a with ¬P(a) true ⟺ ∃x ¬P(x) is true. Both sides always have the same truth value.

For the second law, apply the first to the predicate ¬P: ¬∀x ¬P(x) ≡ ∃x ¬¬P(x) ≡ ∃x P(x). Negating both sides gives ∀x ¬P(x) ≡ ¬∃x P(x). ∎

(⟹) Suppose ∀x(P(x) ∧ Q(x)) is true. Let a be any element of the domain. Then P(a) ∧ Q(a) is true, so P(a) is true and Q(a) is true. As a was arbitrary, ∀x P(x) and ∀x Q(x) are both true.

(⟸) Suppose ∀x P(x) and ∀x Q(x) are true. For any a, P(a) and Q(a) are true, so P(a) ∧ Q(a) is true. Hence ∀x(P(x) ∧ Q(x)). ∎

Domain ℤ, P(x): “x is even”, Q(x): “x is odd”.

(a) ∀x(P(x) ∨ Q(x)) is true: every integer is even or odd. But ∀x P(x) is false (x = 1) and ∀x Q(x) is false (x = 2), so ∀x P(x) ∨ ∀x Q(x) is false.

(b) ∃x P(x) (take 2) and ∃x Q(x) (take 1) are true, so the left side is true. No integer is both even and odd, so ∃x(P(x) ∧ Q(x)) is false. ∎

One direction does hold in each case: ∀x P ∨ ∀x Q ⟹ ∀x(P ∨ Q) and ∃x(P ∧ Q) ⟹ ∃x P ∧ ∃x Q.

¬∀x(P(x) → Q(x)) ≡ ∃x ¬(P(x) → Q(x)) ≡ ∃x(P(x) ∧ ¬Q(x)).

The first step is P14; the second is P4(a) applied inside the quantifier. ∎

In words: “not every P is a Q” means “some P is not a Q”.

Suppose that for some truth values the proposition is false. Then its premise (p → q) ∧ (q → r) is true and its conclusion p → r is false. From the conclusion, p is true and r is false. Since p is true and p → q is true, q is true. Since q is true and q → r is true, r is true. That contradicts “r is false”. So the proposition is never false: it is a tautology. ∎

(a) Let (g ∘ f)(x₁) = (g ∘ f)(x₂), i.e. g(f(x₁)) = g(f(x₂)). Since g is injective, f(x₁) = f(x₂); since f is injective, x₁ = x₂.

(b) Let z ∈ Z. Since g is onto, z = g(y) for some y ∈ Y; since f is onto, y = f(x) for some x ∈ X. Then (g ∘ f)(x) = z.

If f : X → Y and g : Y → Z are bijections, then by (a) and (b) g ∘ f : X → Z is a bijection, so X ∼ Z. ∎

(a) For x ∈ X: x ∈ f⁻¹(Y − B) ⟺ f(x) ∈ Y − B ⟺ f(x) ∉ B ⟺ x ∉ f⁻¹(B) ⟺ x ∈ X − f⁻¹(B). ∎

(b) No. Let X = {1, 2}, Y = {a, b}, f(1) = f(2) = a, A = {1}. Then f(X − A) = f({2}) = {a}, but Y − f(A) = {a, b} − {a} = {b}.

The equality does hold when f is a bijection: injectivity gives f(X − A) ⊆ Y − f(A) and surjectivity gives ⊇.

y ∈ f(A ∪ B) ⟺ ∃x ∈ A ∪ B with f(x) = y ⟺ (∃x ∈ A with f(x) = y) ∨ (∃x ∈ B with f(x) = y) ⟺ y ∈ f(A) ∪ f(B). The middle step is “∃ distributes over ∨”.

If y ∈ f(A ∩ B), then y = f(x) with x ∈ A and x ∈ B, so y ∈ f(A) and y ∈ f(B).

Strict: f(x) = x² on ℝ, A = {−1}, B = {1}. Then f(A ∩ B) = f(∅) = ∅ but f(A) ∩ f(B) = {1}. ∎

(a) a0 = a0 + 0 = a0 + aa′ = a(0 + a′) = a(a′ + 0) = aa′ = 0 [B3a, B4b, B2b, B1, B3a, B4b].

(b) a(a + b) = (a + 0)(a + b) = a + 0b = a + b0 = a + 0 = a [B3a, B2a, B1, (a), B3a].

Duals: a + 1 = 1 (B6a) and a + ab = a (B7a). ∎

a + a′b = (a + a′)(a + b) = 1 · (a + b) = (a + b) · 1 = a + b [B2a, B4a, B1, B3b].

Dual: a(a′ + b) = ab. ∎

This is the step behind many K-map simplifications, e.g. x + x′y = x + y.

x = x + 0 = x + aa′ = (x + a)(x + a′) = (a + x)(x + a′) = 1 · (x + a′) = x + a′ [B3a, B4b, B2a, B1, hypothesis, B1 + B3b]

a′ = a′ + 0 = a′ + ax = (a′ + a)(a′ + x) = 1 · (a′ + x) = a′ + x = x + a′ [B3a, hypothesis, B2a, B1 + B4a, B1 + B3b, B1]

Both equal x + a′, so x = a′. ∎

By [B4] and [B1], a′ + a = 1 and a′a = 0. So a satisfies the two conditions of a complement of a′, and by P27, a = (a′)′.

0 + 1 = 1 + 0 = 1 [B1, B3a] and 0 · 1 = 0 [B3b]. So 1 is a complement of 0: 0′ = 1 by P27. By duality, 1′ = 0. ∎

Sum: (a + b) + a′b′ = ((a + b) + a′)((a + b) + b′) [B2a]. Here (a + b) + a′ = (a + a′) + b = 1 + b = 1 [B1, B8a, B4a, B6a], and (a + b) + b′ = a + (b + b′) = a + 1 = 1 [B8a, B4a, B6a]. So the sum is 1 · 1 = 1.

Product: (a + b)(a′b′) = a(a′b′) + b(a′b′) = (aa′)b′ + a′(bb′) = 0 · b′ + a′ · 0 = 0 + 0 = 0 [B2b, B1 + B8b, B4b, B1 + B6b, B3a].

By P27, a′b′ is the complement of a + b. By duality, (ab)′ = a′ + b′. ∎

(1) ⟹ (2): ab = a(a + b) = a (substitute (1), then absorption B7b).

(2) ⟹ (4): ab′ = (ab)b′ = a(bb′) = a0 = 0 (substitute (2), B8b, B4b, B6b).

(4) ⟹ (3): a′ + b = a′ + b″ = (ab′)′ = 0′ = 1 (B10, De Morgan P29, substitute (4), B11).

(3) ⟹ (1): a + b = (a + b) · 1 = (b + a)(b + a′) = b + aa′ = b + 0 = b (B3b, substitute (3) and B1, B2a, B4b, B3a). ∎

In the algebra of sets these say: A ∪ B = B, A ∩ B = A, A′ ∪ B = U, A − B = ∅, i.e. A ⊆ B (compare P6).

Well defined: for n ≥ 0, 2n + 1 ≥ 1 is odd; for n < 0, 2|n| ≥ 2 is even. So f(n) ∈ ℤ⁺.

Injective: an odd value never equals an even value, so if f(n) = f(m) then n, m have the same sign. If both are ≥ 0, 2n + 1 = 2m + 1 gives n = m; if both are negative, 2|n| = 2|m| gives n = m.

Surjective: an odd k is f((k − 1)/2) with (k − 1)/2 ≥ 0; an even k is f(−k/2) with −k/2 < 0. ∎

Both are subsets of the countable set ℤ⁺, so each is finite or countable. Neither is finite. For the squares, n ↦ n² is injective on ℤ⁺. For the primes, suppose there were only finitely many, p₁, …, pₖ. Then N = p₁p₂⋯pₖ + 1 leaves remainder 1 when divided by every pᵢ, so any prime factor of N is a new prime, a contradiction (Euclid). Hence both sets are countable. ∎

Surjective: let k ∈ ℤ⁺. Divide k by 2 as often as possible: k = 2ᵃ · q with a ≥ 0 and q odd. Put m = a + 1 and n = (q + 1)/2; then g(m, n) = k.

Injective: if 2ᵐ⁻¹(2n − 1) = 2ᵐ′⁻¹(2n′ − 1) and, say, m > m′, divide by 2ᵐ′⁻¹: the left side is even and the right side is odd, which is impossible. So m = m′, and then 2n − 1 = 2n′ − 1 gives n = n′. ∎

This replaces the diagonal picture (4.2) in the proof of Theorem 11 with a formula.

For each q ∈ ℤ⁺ let Q_q = {p/q : p ∈ ℤ}. The map p ↦ p/q is a bijection ℤ → Q_q, so each Q_q is countable (P31 and transitivity, P19). Every rational can be written with a positive denominator, so ℚ = ⋃_q∈ℤ⁺ Q_q: a countable union of countable sets. By Theorem 11, ℚ is countable. ∎

The sets Q_q overlap (1/1 = 2/2); Theorem 11 allows that, as its proof first makes the sets disjoint.

Let 𝒫 be the set of nonzero polynomials with rational coefficients; it is countable (a subset of a countable set, infinite). For P ∈ 𝒫 let R(P) be its set of roots; it is finite (at most deg P elements). The set of algebraic numbers is 𝔸 = ⋃_P∈𝒫 R(P), a countable union of finite sets, so it is finite or countable: list the polynomials as P₁, P₂, …, then list the roots of P₁, then those of P₂, and so on, skipping repeats. It is infinite, because every rational r is the root of t − r. Hence 𝔸 is countable. ∎

Let A₀ = A − M; then M ∪ A = M ∪ A₀ with M ∩ A₀ = ∅, and A₀ is finite or countable (Theorem 10). If A₀ = ∅ there is nothing to prove.

By Theorem 12, M has a countable subset C. Then C ∪ A₀ is countable (Theorem 11; a finite set can be listed first). So there is a bijection g : C ∪ A₀ → C, since both are countable.

Define h : M ∪ A₀ → M by h(x) = g(x) for x ∈ C ∪ A₀ and h(x) = x for x ∈ M − C. The two parts C ∪ A₀ and M − C partition M ∪ A₀, their images C and M − C partition M, and h is a bijection on each part. So h is a bijection and M ∪ A ∼ M. ∎

Let B ⊆ M with B uncountable, and suppose M is not uncountable, i.e. M is finite or countable. If M is finite, so is its subset B. If M is countable, B is finite or countable by Theorem 10. Either way B is not uncountable, a contradiction. ∎

(a) f(x) = c + (d − c)(x − a)/(b − a) maps a ↦ c and b ↦ d, and is increasing, so it maps [a, b] into [c, d]. Its inverse g(y) = a + (b − a)(y − c)/(d − c) maps [c, d] into [a, b], and g(f(x)) = x, f(g(y)) = y. A function with a two-sided inverse is a bijection.

(b) h(x) = tan(π(x − ½)): as x runs over (0, 1), π(x − ½) runs over (−π/2, π/2), and tan is a bijection from there onto ℝ (Example 4). A composition of bijections is a bijection (P19). ∎

With P38: [0, 1] is uncountable (P40), so ℝ and every interval [c, d] are uncountable.

Let 𝔸_ℝ be the real algebraic numbers and T = ℝ − 𝔸_ℝ. 𝔸_ℝ is countable (an infinite subset of the countable set in P35). Suppose T were finite or countable. Then ℝ = 𝔸_ℝ ∪ T would be countable by Theorem 11. But ℝ is uncountable (P39 with P38). So T is uncountable; in particular it is not empty. ∎

The proof shows that transcendental numbers exist without exhibiting a single one. Proving that a specific number such as π or e is transcendental is much harder.

Define h : [0, 1] → (0, 1): h(0) = ½, h(1) = ⅓, h(1/n) = 1/(n + 2) for n ≥ 2, and h(x) = x for every other x.

Let E = {1/n : n ≥ 2}. h maps {0, 1} ∪ E one-to-one onto E: 0, 1, ½, ⅓, … go to ½, ⅓, ¼, ⅕, …, which is all of E without repetition. It maps the rest, (0, 1) − E, identically onto itself. These two pieces partition [0, 1] and their images partition (0, 1), so h is a bijection. ∎

The same idea gives a general fact (from IIT Kharagpur CS60005 tutorial solutions): if A is uncountable and B ⊆ A is countable, then A − B ∼ A. Take a countable C = {c₁, c₂, …} ⊆ A − B and send bₙ ↦ c₂ₙ₋₁, cₙ ↦ c₂ₙ, everything else to itself.

The map x ↦ {x} is injective, so |M| ≤ |P(M)|.

Let f : M → P(M) be any function and D = {x ∈ M : x ∉ f(x)} ∈ P(M). Suppose D = f(d) for some d ∈ M. If d ∈ D, then by the definition of D, d ∉ f(d) = D. If d ∉ D = f(d), then by the definition of D, d ∈ D. Both cases are impossible, so D is not in the image of f: no f is onto. Hence there is no bijection and |M| < |P(M)|. ∎

Exercise 2.18 follows: a function M → {0, 1} is the same as a subset of M (the set where it equals 1), so the set of all such functions has cardinality |P(M)| > |M|. Note that this is the diagonal argument again: D differs from f(x) at the element x.

Let C₀ = A − g(B), Cₙ₊₁ = g(f(Cₙ)), and C = C₀ ∪ C₁ ∪ C₂ ∪ ⋯. Define h : A → B by h(x) = f(x) for x ∈ C and h(x) = g⁻¹(x) for x ∉ C. The second case makes sense: x ∉ C₀ means x ∈ g(B), and g⁻¹(x) is unique because g is injective.

Injective. On C, h = f is injective; off C, h = g⁻¹ is injective. Suppose f(x) = g⁻¹(x′) with x ∈ Cₙ and x′ ∉ C. Then x′ = g(f(x)) ∈ Cₙ₊₁ ⊆ C, a contradiction.

Surjective. Let y ∈ B. If g(y) ∉ C, then h(g(y)) = g⁻¹(g(y)) = y. If g(y) ∈ C, then g(y) ∉ C₀ (it lies in g(B)), so g(y) ∈ Cₙ₊₁ = g(f(Cₙ)) for some n. That is, g(y) = g(f(x)) with x ∈ Cₙ, and since g is injective, y = f(x) = h(x). So h is a bijection. ∎

Application. The inclusion (a, b) → [a, b] is injective. So is x ↦ m + (x − m)/2 from [a, b] to (a, b), where m = (a + b)/2: it shrinks [a, b] to the middle half, [(3a + b)/4, (a + 3b)/4] ⊂ (a, b). By Cantor–Bernstein, [a, b] ∼ (a, b), without building the bijection by hand as in P42.