The worksheetDownload the PDF
Answers

A6.3 Sets

Theory of computation · A level · AQA 7517 4.4.2.2 · about 20 min

BugBotLab

What this lesson is about

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

Questions 6 marks in all

  1. [1 mark]A = {3, 5, 7} and B = {a, b, c, d}. What is |A × B|?

    Answer: 12. The Cartesian product has one pair for every member of A with every member of B: 3 x 4 = 12.

  2. [1 mark]A = {1, 2, 3, 4} and B = {3, 4, 5}. List A \ B (the difference), as numbers separated by commas in ascending order.

    Answer: 1, 2. A \ B is the members of A that are not in B.

  3. [1 mark]Which set is {2x | x ∈ ℕ ∧ x < 4}?

    1. A{0, 2, 4, 6}
    2. B{2, 4, 6, 8}
    3. C{0, 1, 2, 3}
    4. D{2, 4, 6}
    Answer: A. x takes the natural numbers 0, 1, 2 and 3, and each is doubled.

  4. [1 mark]Which of these sets are countably infinite?

    Tick every answer that is true.

    1. AThe natural numbers ℕ
    2. BThe integers ℤ
    3. C{x | x ∈ ℕ ∧ x < 1000}
    4. DThe set of all binary strings
    Answer: A, B, D. ℕ, ℤ and all binary strings can each be counted off 0, 1, 2, ... The third set is finite, with 1000 members.

  5. [1 mark]A = {1, 3, 5}. Which statement is false?

    1. A{1, 5} ⊂ A
    2. BA ⊆ A
    3. CA ⊂ A
    4. D{} ⊆ A
    Answer: C. A proper subset must be missing at least one member of the other set, so no set is a proper subset of itself.

  6. [1 mark]What does this program print?

    A = {1, 3, 7, 9}
B = {2, 3, 9}
print(sorted(A | B))
print(sorted(A & B))
print(len(A - B), len(B - A))
    Answer:
    [1, 2, 3, 7, 9]
[3, 9]
2 1

    Union has every member of either set; intersection only those in both. A - B = {1, 7} and B - A = {2}.

The 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]

The hint students can ask for: Turn each list into a set first, so the repeats disappear. Each line is then one set operation or one comparison. To print a set in the required form, put it in order and join the numbers as text. The number of pairs in a Cartesian product is the product of the two cardinalities.

A solution

# 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]

def show(s):
    return " ".join(str(x) for x in sorted(s))

A = set(seen_by_a)
B = set(seen_by_b)
print("A:", show(A))
print("B:", show(B))
print("union:", show(A | B))
print("intersection:", show(A & B))
print("A minus B:", show(A - B))
print("pairs:", len(A) * len(B))
print("subset:", {7, 9} < A)
print("even:", show({x for x in A | B if x % 2 == 0}))

Any program that meets the task's checks is marked correct in the simulator; this is one way, not the only way.