# 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.
A = {4x | x ∈ N } Set A is a countably infinite set. |

## Programming

editNot 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
```