Sets

Set notation and comprehension, finite and countably infinite sets, cardinality, Cartesian product, subsets, union, intersection and difference.

A6.3Theory of computationA level20 min

A finite state machine sorts strings into those it accepts and those it rejects. The strings it accepts form a set, and the precise way to talk about the languages of machines, regular expressions and grammars is set notation. This lesson is the maths the next three lessons stand on. You have used lists since GCSE; a set is different in two ways that matter.

What a set is

A set is an unordered collection of values in which each value appears at most once.

• A = {1, 3, 7, 9} lists the members between braces. {9, 7, 3, 1} is the same set, because order does not matter, and {1, 1, 3} is just {1, 3}.
• 7 ∈ A means 7 is a member of A. 2 ∉ A means 2 is not.
• The empty set, with no members, is written {} or Ø.

Python has sets built in. Note that {} on its own makes an empty dictionary, so an empty set is set().

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

sightings = [3, 7, 1, 7, 9, 3]      # marker ids, in the order the camera saw them
A = set(sightings)
print(A)
print(7 in A, 2 in A)
print(len(A))

Run this in the simulator

The list had six items; the set has four, because the repeats are gone. len(A) is 4.

Set comprehension

Listing members only works for small sets. Set comprehension describes a set by a rule instead:

A = {x | x ∈ ℕ ∧ x ≥ 1 ∧ x ≤ 5}

Read | as "such that", ∈ as "is a member of" and ∧ as "and". So A is the set of every x such that x is a natural number and x is between 1 and 5: {1, 2, 3, 4, 5}. Here ℕ is the set of natural numbers {0, 1, 2, 3, ...}.

The part before the bar can be an expression: {2x | x ∈ ℕ} is the set of even natural numbers {0, 2, 4, ...}.

For strings there is a compact form that the next lessons use a lot. {0ⁿ1ⁿ | n ≥ 1} means n 0s followed by the same number n of 1s, for every n from 1 up: {01, 0011, 000111, ...}. Writing aⁿ means the symbol a repeated n times.

Python's set comprehension is written almost the same way, with for and if in place of the symbols. Python cannot build an infinite set, so it takes a finite range:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

evens = {2 * x for x in range(10)}
print(sorted(evens))
strings = {"0" * n + "1" * n for n in range(1, 4)}
print(sorted(strings, key=len))

Run this in the simulator

Finite and infinite sets, and cardinality

A finite set has a fixed number of members. The number of members is its cardinality, written |A|. For A = {1, 3, 7, 9}, |A| = 4.

An infinite set never runs out. Some infinite sets are countably infinite: their members can be counted off one by one against the natural numbers 0, 1, 2, 3, ..., so every member is reached eventually.

• ℕ itself is countably infinite.
• The integers ℤ are countably infinite too, counted as 0, 1, -1, 2, -2, 3, -3, ...
• The set of all binary strings is countably infinite: list them by length, "", 0, 1, 00, 01, 10, 11, 000, ...

The real numbers ℝ are not countable: however you try to list them, some are always missed. Every program is a finite string, so there are only countably many programs. That fact comes back in lesson A6.8.

Cartesian product

The Cartesian product A × B is the set of every ordered pair whose first item comes from A and whose second comes from B:

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

If A = {S0, S1} and B = {0, 1}, then A × B = {(S0, 0), (S0, 1), (S1, 0), (S1, 1)}. Its cardinality is |A| × |B| = 2 × 2 = 4.

That set is exactly the keys of the parity machine's transition table. A transition function takes a pair from States × Inputs and gives back a state, which is why a complete table has |States| × |Inputs| rows.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

from itertools import product

states = {"SEARCH", "APPROACH"}
inputs = {"none", "far", "near"}
pairs = set(product(states, inputs))
print(len(pairs))
print(sorted(pairs))

Run this in the simulator

Six pairs: the six rows of the controller's table in the last lesson.

Subsets and set operations

With A = {1, 3, 7, 9} and B = {2, 4, 7, 9}: A ∪ B = {1, 2, 3, 4, 7, 9}, A ∩ B = {7, 9}, A \ B = {1, 3} and B \ A = {2, 4}. Difference is not symmetric. {7, 9} ⊆ A is true, and so is {7, 9} ⊂ A, because A has members that {7, 9} does not. A ⊆ A is true but A ⊂ A is false.

Task: two robots' sightings

Two robots patrolled the same room and logged the marker ids they saw, with repeats. Let A be the set of ids robot A saw and B the set robot B saw.

• Start from the two lists in the starter. Do not type any of the answers.
• Print exactly these eight lines, in this order. A list of ids is written in ascending order separated by single spaces: 1. A: then the members of A 2. B: then the members of B 3. union: then the members of A ∪ B 4. intersection: then the members of A ∩ B 5. A minus B: then the members of A \ B 6. pairs: then the cardinality of A × B, as a whole number 7. subset: then True or False: whether {7, 9} is a proper subset of A 8. even: then the members of {x | x ∈ A ∪ B ∧ x is even}, built with a set comprehension

For example, if A were {2, 5} the first line would be A: 2 5.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

seen_by_a = [3, 7, 1, 7, 9, 3]
seen_by_b = [7, 2, 9, 9, 4]

Challenges

1. Write {x² | x ∈ ℕ ∧ x < 6} by listing its members, then check with a Python set comprehension.
2. What is |A × B × C| if |A| = 3, |B| = 2 and |C| = 4? Why?
3. Is {x | x ∈ ℤ ∧ x < 0} finite, countably infinite, or neither? Show how to count it off.