studyhubDiscrete Structures I

Notes / Unit 1 · Module 1 · Pre-midterm

Sets

A set is an unordered collection of distinct objects, and everything later in the course — relations, functions, logic — is built on it. The exam asks you to describe sets, count them, combine them, draw them, store them as bits and pair them up.

1.1Notation and membership

A set is a collection of objects called its elements. Sets get capital letters (S), elements lowercase (s). Write u ∈ A for "u is an element of A" and u ∉ A for "u is not".

Word description
A sentence: the set of odd counting numbers between 2 and 12.
Roster method
List the elements in braces, separated by commas: {3, 5, 7, 9, 11}.
Set-builder notation
State the property: {x ∈ N | x is odd, and 2 < x < 12}. The bar | is read "such that"; the variable need not be x.

Cardinality, written n(A) or |A|, is the number of distinct elements. A set ignores order and repetition, so {1, 2, 3, 4}, {2, 3, 1, 4} and {1, 2, 2, 3, 3, 3, 4, 4} are the same set, of cardinality 4. An ellipsis continues a pattern: {1, 2, 3, …, 100}.

SymbolSet
NNatural (counting) numbers {1, 2, 3, …}
ZAll integers {…, −1, 0, 1, …}
Z⁺Positive integers
Z*Nonzero integers
2Z or EEven integers
Q, R, CRational, real, complex numbers
Empty (null) set
No elements: ∅ or { }, with n(∅) = 0.
Singleton
Exactly one element, e.g. {4}.
Finite / infinite
Limited elements ({1, 2, 3, 4, 5}) or unlimited (N = {1, 2, 3, …}).
Equal sets (A = B)
Exactly the same elements: letters of "earth" and of "heart".
Equivalent sets (A ≈ B)
Same cardinality, possibly different elements: {1, 2, 3, 4, 5} ≈ {h, e, a, r, t}.
Universal set U
Contains every element under discussion; every other set is a subset of it.

Worked example

Describe {2, 4, 6, 8, 10} in set-builder notation

  1. 1The elements are the even integers, starting at 2 and ending at 10.
  2. 2Both ends belong to the set, so the bounds are ≤, not <.
  3. 3X = {n ∈ Z | n is even, and 2 ≤ n ≤ 10}, or equally {n ∈ 2Z | 2 ≤ n ≤ 10}.

1.2Subsets and power sets

Subset A ⊆ B
Every element of A is also in B.
Proper subset A ⊂ B
A ⊆ B and B has at least one element A lacks.
Superset A ⊇ B
Every element of B is in A — the reverse of subset.
Proper superset A ⊃ B
A ⊇ B and A ≠ B.
Power set P(A)
The set of all subsets of A.

Three facts hold for every set A: A ⊆ A, ∅ ⊆ A, and A ⊆ U.

|P(A)| = 2ⁿ proper subsets = 2ⁿ − 1

n
|A|, the number of elements of A

Each element is either in a subset or not: two choices, n times. Only A itself fails to be proper.

Worked example

P(S) for S = {s, i, r}

  1. 1|S| = 3, so P(S) has 2³ = 8 elements.
  2. 2Size 3: {s, i, r}. Size 2: {s, i}, {s, r}, {i, r}. Size 1: {s}, {i}, {r}. Size 0: { }.
  3. 3P(S) = {{s, i, r}, {s, i}, {s, r}, {i, r}, {s}, {i}, {r}, ∅}; 7 of them are proper subsets of S.

1.3Set operations

OperationNotationSet-builderKeeps
UnionA ∪ B{x | x ∈ A or x ∈ B}Everything in either
IntersectionA ∩ B{x | x ∈ A and x ∈ B}Only what both share
ComplementA′{x | x ∈ U and x ∉ A}Everything in U outside A
DifferenceA − B{x | x ∈ A and x ∉ B}A with B's elements removed
Symmetric differenceA △ B (also A ⊕ B)(A − B) ∪ (B − A)In exactly one of the two
  • UAB
    A ∪ B
  • UAB
    A ∩ B
  • UAB
    A′
  • UAB
    A − B
  • UAB
    B − A
  • UAB
    A △ B

Worked example

A = {a, b, c, d}, B = {b, d, e}

  1. 1A ∪ B = {a, b, c, d, e}; A ∩ B = {b, d}.
  2. 2A − B = {a, c}, but B − A = {e}.
  3. 3A △ B = {a, c} ∪ {e} = {a, c, e}.

Sets with no common element are disjoint: A ∩ B = ∅. A collection is pairwise disjoint when every two of its sets are disjoint — {{a}, {b, d}, {e, f, g}} is, {{b, c}, {c, d}} is not.

IdentityReads
A − B = A ∩ B′Difference is intersection with a complement
(A ∪ B)′ = A′ ∩ B′De Morgan
(A ∩ B)′ = A′ ∪ B′De Morgan
A △ A = ∅, A △ ∅ = ASymmetric difference
A ∪ A′ = U, A ∩ A′ = ∅Complement
(A′)′ = ADouble complement

1.4Venn diagrams

A Venn diagram (John Venn, 1880) draws U as a rectangle and each set as a closed figure inside it. Overlaps show shared elements; a circle drawn inside another shows a subset.

RegionSet
Inside both circlesA ∩ B
Inside A, outside BA − B (= A ∩ B′)
Inside B, outside AB − A (= B ∩ A′)
Inside exactly oneA △ B
Outside both(A ∪ B)′
  • UABC
    A ∩ B ∩ C
  • UABC
    (A ∩ B) − C
  • UABC
    A ∪ (B ∩ C)
  • UABC
    A − (B ∪ C), A only

Worked example

U = {0, 1, …, 9}, A = {4, 7, 9}, B = {1, 2, 3, 4, 5}

  1. 1Overlap first: A ∩ B = {4}.
  2. 2A only: {7, 9}. B only: {1, 2, 3, 5}.
  3. 3Outside both: (A ∪ B)′ = {0, 6, 8}.
  4. 4So B ∩ A′ = {1, 2, 3, 5} and A′ ∪ B′ = (A ∩ B)′ = everything except 4.
  • UAB7, 941, 2, 3, 50, 6, 8
    The example filled in. Shaded: B ∩ A′ = {1, 2, 3, 5}

1.5Counting with inclusion–exclusion

n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

Adding n(A) and n(B) counts the overlap twice; subtract it once.

n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C)

The centre is added three times and subtracted three times, so it is added back once.

Worked example

40 students: 22 take Programming, 18 take Discrete, 7 take both

  1. 1n(P ∪ D) = 22 + 18 − 7 = 33 take at least one.
  2. 2Neither: 40 − 33 = 7.
  3. 3Programming only: 22 − 7 = 15. Discrete only: 18 − 7 = 11.
  4. 4Exactly one: 15 + 11 = 26 = n(P △ D).

1.6Computer representation

Storing a set's elements unordered makes every operation a search. Instead, fix an ordering a₁, a₂, …, aₙ of a finite universal set U, and store each subset A as an n-bit bit string: bit i is 1 if aᵢ ∈ A and 0 if not.

Set operationBit operation
A ∪ BOR, bit by bit
A ∩ BAND, bit by bit
A′NOT: flip every bit
A − BA AND (NOT B)
A △ BXOR

Worked example

U = {1, 2, …, 10} in increasing order

  1. 1Odd numbers {1, 3, 5, 7, 9}: 1010101010. Even numbers: 0101010101. Not exceeding 5: 1111100000.
  2. 2Union of {1, …, 5} and the odds: 1111100000 OR 1010101010 = 1111101010 = {1, 2, 3, 4, 5, 7, 9}.
  3. 3Intersection: 1111100000 AND 1010101010 = 1010100000 = {1, 3, 5}.
  4. 4Complement of the odds: NOT 1010101010 = 0101010101, the evens.

1.7Cartesian product

Sets ignore order, so ordered collections need ordered n-tuples (a₁, a₂, …, aₙ). A 2-tuple is an ordered pair. Two tuples are equal only when every matching position is equal: (a, b) = (c, d) iff a = c and b = d, so (1, 2) ≠ (2, 1).

A × B = {(a, b) | a ∈ A and b ∈ B} |A × B| = |A| · |B|

Likewise |A × B × C| = |A| · |B| · |C|.

Worked example

A = {1, 2}, B = {a, b, c}

  1. 1A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)} — 2 · 3 = 6 pairs.
  2. 2B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.
  3. 3Same size, different pairs: A × B ≠ B × A.

A table is a Cartesian product of rows and columns: each cell is the pair (row value, column value). In SQL, a CROSS JOIN with no WHERE clause returns that product — rows of the first table × rows of the second.

SELECT *
FROM table1
CROSS JOIN table2;
A 5-row table cross-joined with a 4-row table returns 20 rows.

Check yourself

Answer these out loud, without scrolling up. Any you can't, reread that section — then let the drill mark you.

  1. 1.Write {x ∈ N | x is even, and 3 < x ≤ 12} in roster form, and give its cardinality.
  2. 2.For S = {a, b, c, d}, how many subsets, and how many proper subsets, does S have? Is {a} ∈ S?
  3. 3.With U = {1, …, 10}, A = {1, 2, 3, 4} and B = {3, 6, 7, 8, 9}, find A − B, B − A, A △ B and (A ∪ B)′.
  4. 4.In a class of 50, 30 like coffee, 25 like tea and 12 like both. How many like neither?
  5. 5.Using U = {1, …, 10} in order, give the bit strings for {2, 3, 5, 7} and its complement.
  6. 6.If |A| = 3 and |B| = 4, how many elements do A × B and P(A × B) have?