UoL CS Notes
Menu

(Naive) Set Theory

COMP109 Lectures

Notation for Sets

A set is a collection of objects, called the elements of the set.

  • $\{7,5,3\}$

We have written down the element of each set and contained them between the braces $\{\}$.

Repetitions and orderings don’t matter in sets hence $\{7,5,3\}$ is the same as $\{5,3,3,3,7\}$.

We write $a\in A$ to denote that the object $a$ is an element of the set $a$: \(7\in\\{7,5,3\\},4\notin\\{7,5,3\\}\)

The order of elements does not matter.

Repetitions don’t count.

For a large set, especially an infinite set, we cannot write down all the elements. We use a predicate $P$ instead. \(A=\{x\in S\vert P(x)\) denotes the set of objects $x$ from $S$ fro which the predicate $P(x)$ is true.

Example

Let: \(A = \{1,3,5,7,\ldots\}\) Then: \(A=\{x\in \mathbb{Z} \vert x \text{ is odd}\}\)

More Examples

Find simpler descriptions of the following sets by listing their elements. (The set $A$ is written properly however $B$ and $C$ are written informally.

  1. $A=\{x\in\mathbb{z}\vert x^2+4x=12\}$

    $\{2,-6\}$

  2. $B=\{n^2\vert n \text{ is an integer}\}$

    $\{0,1,4,9,16,25,\ldots\}$

    $B=\{m\in\mathbb{Z}\vert m=n^2$$ \text{ for some integer } n\}$

  3. $C=\{x\vert x \text{ a day of the week,}$$\text{ not containing “u”}\}$

    $\{\text{Monday, Wednesday, Friday}\}$

Important Sets

The empty set had no elements. It is written as $\emptyset$ or as $\{\}$.

Here are some other sets:

  • $\mathbb{N}=\{0,1,2,3,\ldots\}$ The natural numbers.
  • $\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$ The integers.
  • $\mathbb{Z^+}=\{1,2,3,\ldots\}$ The positive integers.
  • $\mathbb{Q}=\{\frac{x}{y}\vert x \in\mathbb{Z},y\in\mathbb{Z},y\neq0\}$ The rationals.
  • $\mathbb{R}$ Real numbers.
    • $[a,b]=\{x\in\mathbb{R}\vert a\leq x \leq b\}$ The set of real numbers between $a$ and $b$ inclusive.

Computer Representation of Sets

Only finite sets can represented.

  • Number of elements not fixed.
    • Lists
  • All elements of $A$ are drawn from some ordered sequence $S=\langle s_1,\ldots,s_n\rangle$. The characteristic vector of $A$ is the sequence $[b_1,\ldots,b_n]$ where: \(b_i= \begin{cases} 1 & \text{if}\ S_i\in A \\ 0 & \text{if}\ S_i\notin A \end{cases}\)
  • Sequences of zeros and ones of length $n$ are called bit strings of length $n$. These are also known as bit vectors or bit arrays.

Examples

Let $S\langle 1,2,3,4,5\rangle, A = \{1,3,5\}$ and $B=\{3,4\}$

  • Characteristic vectors show how sets relate to sequences. The $1$ shows that the value is in the set.
    • The characteristic vector of $A$ is $[1,0,1,0,1]$.
    • The characteristic vector of $B$ is $[0,0,1,1,0]$.
  • You would answer a question in the opposite direction like so:
    • The set characterised by $[1,1,1,0,1]$ is $\{1,2,3,5\}$.
    • The set characterised by $[1,1,1,1,1]$ is $\{1,2,3,4,5\}$.
    • The set characterised by $[0,0,0,0,0]$ is $\emptyset$.