Theory of Computation: Compact set notation

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

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