Theory of Computation: Compact set notation

PAPER 1 - ⇑ Theory of computation ⇑

← Maths for regular expressions Compact set notation Regular expressions →



Compact set notation is a useful tool to describe the properties of each element of a set, rather than writing out all elements of a set.

The table below lists all of the necessary symbols for compact set notation.

Symbol Meaning
x ∈ S x is an element of S
| such that
and
or
< smaller than
smaller or equal than
> greater than
greater or equal than
A ⊆ B A is a subset of B
A ⊂ B A is a proper subset of B
C = A ∪ B C is the union of A and B
C = A ∩ B C is the intersection of A and B
C = A \ B C is the difference of A and B

Example 1:

We might want to describe a set A, which contains all natural numbers greater than 10.

This means that we are interested in a subset of ℕ, such that each of its elements is greater than the value 10.

Using set notation this set can be described as:

A = {x|x ∈ ℕ ∧ x> 10}

Example 2:

This time set A is described as natural numbers, which are multiples of 10. This can be notated as:

A = {10x|x ∈ ℕ}

Example 3:

The elements of set A are all even numbers, up to including 12. Set notation allows us to write this set as {0,2,4,6,8,10,12}, which in this example is feasible.

However, this would be very impractical, if A is described as all even numbers, up to including 1,000,000!

A = {2x | x ∈ N &and 2x ≦ 1,000,000}

The table below explains how each expression is linked to the English description of the elements of the set A.

English description... ... expressed in set notation
x must be even 2x
such that 2x |
2x must be a natural number 2x ∈ N
2x must be smaller or equal than 1,000,000 2x ≦ 1,000,000

Example 4:

Set A is described as all the natural multiples of 3, below 5,000.

A = {3x | x ∈ N ∧ 3x < 5,000}

The table below explains how each expression is linked to the English description of the elements of the set A.

English description... ... expressed in set notation
x must be a multiple of 3 3x
such that 3x |
x must be a natural number x ∈ N
3x must be smaller than 5,000 3x < 5000
Questions

Using set notation, define the set A as all the numbers divisible by 4. Which of the following terms are applicable to A: countable, uncountable, finite, infinite.

Answer:

A = {4x | x ∈ N } Set A is a countably infinite set.

Programming

edit

Not every programming language offers the ability to perform set theory calculations out of the box. In Visual Basic it has only been available since VB.NET 2008, using the LINQ libraries that you have to import to get it working:

Imports System.Linq
Imports System.Xml.Linq

Module Module1
    Sub Main()

    Dim A() As Integer = {0,2,4,6,8,10,12}
    Dim B() As Integer = {0,3,6,9,12}

    Dim unionAB = A.Union(B)
    Console.WriteLine("Union of A and B:")
    For Each n In unionAB
       Console.WriteLine(n)
    Next

    Dim differenceAB = A.Except(B) 'Except performs the same function as Difference
    Console.WriteLine("Difference of A and B:")
    For Each n In differenceAB
       Console.WriteLine(n)
    Next

    Dim intersectAB = A.Intersect(B)
    Console.WriteLine("Intersection of A and B:")
    For Each n In intersectAB
       Console.WriteLine(n)
    Next

    End Sub
End Module