Introduction

Sets are collections of “things”
For example, a set could contain the numbers:

2, 4, 5, 8, 25

Sets We Work with

Almost all of our sets will either be:

  • A subset of all natural numbers ($\mathbb{N}$) (All positive whole numbers - including zero)
  • A subset of all integers ($\mathbb{Z}$) (All integers, including negative numbers)
  • A subset of all real numbers ($\mathbb{R}$) (All rational and irrational numbers)
  • The empty set: $\emptyset$ (which contains no elements)
  • Sets containing lowercase letters representing “abstract” objects: $ \{a, b, c, x, y \} $
  • Sets containing any of the above sets as elements

Note that many of the above sets are infinite

Defining Sets

Sets can be defined in many ways:

  • Enumeration
    • $ \{ 1, 2, 3, 4, 5, 6 \} $
    • Note that order isn’t important
    • $ \{ 1, 2, 3, 4, 5, 6 \} = \{ 6, 5, 4, 3, 2, 1 \} $
  • Descriptively
    • “The set of all people who accessed this website”
    • More robust mathematical descriptions also exist

Defining Sets Descriptively Using Mathematical Notation

$ P(x) $ means that the mathematical object $x$ satisfies the property $P$
We can define a set of all elements that satisfy $P$ as such:

$ A = \{ x | P(x) \} $

Examples of sets

\[ S_n = \{ x | x \in \mathbb{N} \textrm{ and } 1 \leq x \leq n \}\\ S_n = \{1,2,3,4,...,n\}\\ \\ B = \{ x | x = 3n+2, n \in \mathbb{N} \textrm{ and } 1 \leq n \leq 4 \}\\ B = \{ 5,8,11,14 \}\\ \\ \mathbb{N}^+ = \{ x | x \in \mathbb{Z} \textrm{ and } x \gt 0 \}\\ \mathbb{N}^+ \textrm{ is the set of all positive numbers}\\ \\ \mathbb{Q} = \left\{ \frac{x}{y} | x \in \mathbb{Z} \textrm{ and } y \in \mathbb{N}^+ \right\}\\ \mathbb{Q} \textrm{ is the set of all positive numbers (fractions)} \]

Computational Features Of Sets

  • Sets are abstract data structures
  • Data structures are interesting due to the queries and operations they support
    • Membership
    • Containment/Subset
    • Equality
    • Cardinality
    • Power Set
    • Union
    • Intersection
    • Complement
    • Cartesian Product