levo

Theory of Computation

Subsets and Set Operations

  • 1 thing to know
  • Paper 1

Overview

Recall questions on the difference between a subset and a proper subset, membership tests, and the four set operations.

What you need to know

Answer each one before you reveal it.

Your recallNot started
Key term

Give the formal definition of the set difference A \ B.

Questions from this subtopic

Each one with the model answer underneath.

  1. 1

    What does A ⊆ B mean?

    Model answer

    A ⊆ B means A is a subset of B: every element of A is also an element of B. For example {4, 5, 6} ⊆ {4, 5, 6, 7}. The symbol ⊆ includes the case where the two sets are equal, so {4, 5, 6, 7} ⊆ {4, 5, 6, 7} is also true.

  2. 2

    What does A ⊂ B mean, and how does it differ from A ⊆ B?

    Model answer

    A ⊂ B means A is a proper subset of B: B contains everything in A, but there is at least one element in B that is not in A, so the two sets cannot be equal. For example {4, 5, 6} ⊂ ℕ, because ℕ contains everything in {4, 5, 6} and much else besides. The difference from ⊆ is exactly that ⊆ includes both ⊂ and equality: {4, 5, 6, 7} ⊆ {4, 5, 6, 7} is true, but {4, 5, 6, 7} ⊂ {4, 5, 6, 7} is false.

  3. 3

    Let A = {1, 2, 3, 4} and B = {3, 4, 5}. State whether each of these is true: 2 ∈ A, 5 ∈ A, B ⊆ A, {3, 4} ⊂ B.

    Model answer

    2 ∈ A is true, because 2 is one of the listed elements of A. 5 ∈ A is false; 5 ∉ A. B ⊆ A is false, because 5 is in B but not in A. {3, 4} ⊂ B is true, because B contains both 3 and 4 and also contains 5, which {3, 4} does not, so it is a proper subset.

  4. 4

    Name the four set operations and say what each does.

    Model answer

    Membership: tests whether a value is in a set, written x ∈ A, or x ∉ A if it is not. Union: A ∪ B is the set of everything that is in A or in B or in both. Intersection: A ∩ B is the set of everything that is in both A and B. Difference: A \ B, also written A − B, is the set of everything that is in A but not in B.

  5. 5

    With A = {1, 2, 3, 4} and B = {3, 4, 5}, work out A ∪ B, A ∩ B, A \ B and B \ A.

    Model answer

    A ∪ B = {1, 2, 3, 4, 5}. A ∩ B = {3, 4}. A \ B = {1, 2}. B \ A = {5}. Note that 3 and 4 appear only once in the union, because each value occurs at most once in a set, and that A \ B and B \ A are different, so difference does not work both ways round.

  6. 6

    Give the formal definition of the set difference A \ B.

    Model answer

    A \ B = {x : x ∈ A and x ∉ B} — the set of all x such that x is a member of A and x is not a member of B. It is also written A − B.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.

1Closed book
2Open book
3Closed book

The 3-step method, run for you

Answer cold, learn it, then prove it stuck. Levo tracks the jump between your first attempt and your last.

Fundamentals of Programming
Fundamentals of Data Structures
Fundamentals of Algorithms
Theory of Computation

Cram a whole paper in one sitting

Sort every topic into what you know and what you do not, then drill only the weak ones.

A driver is .
softwarehardwarestorage

Blank Blitz makes facts automatic

Rapid timed gap-fills on the terms and numbers you need to recall without thinking.

AThe integer 5 is 0101.
B0.75 is 1/2 + 1/4.
CThe fraction bits are 1100.

Build It gets the exam shape right

Assemble a full-mark answer from its marking points, in the order an examiner wants them.

Head means the first single element of a non-empty list.
TrueFalse

Test It catches misconceptions

Spot the fault in a statement. The traps are the mistakes students actually make.

721941163128510

Brain Breaks between sessions

Short focus games to reset attention, so the next set lands better than the last.

Every question in Theory of Computation, on a schedule.

Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.

Or £46 a year, about £3.83 a month. Cancel anytime.