Sets (Discrete Math)

Sets refresher for Algorithms

Sets

Definitions

Set - is an unordered collection of objects. Usually sets are denoted by capital letters. A set contains its elements.

  • aAa \in A

In the example above, the special character \in means that the lower case letter aa is an element of the set AA. If aa is not an element of AA, we write aAa \notin A.

When two sets contain the same elements, they are said to be equal. AA = {e}, BB = {e} means that A=BA = B or A=BA = B provided that e(xA    eB)\forall e(x \in A \iff e \in B).

Describing sets

Roster method There are a few ways of describing sets. One of them is the roster method. In roster method curly braces are used to list out the elements of a set. AA = {1,2,3} is a set of positive integers between 1 and 3 inclusive. It is fundamental to note that the order inside set does not matter: {1,3,2} = {1,2,3} because xx \in {1,3,2} and xx \in {1,2,3}, that is

  • x(x\forall x(x \in {1,3,2}     x\iff x \in {1,2,3}).

Also, notice that we separate the elements with comma and we ignore the duplicates.

When the quantity of the elements is large, roster method does not fit well for the purpose. We would not want to list out all 1000 elements when we need to create a set that contains integers from 1 to 1000. One solution is to use three dots ... (which is also called ellipsis). So AA = {1,2,3 ..., 1000} would describe a set with positive integers 1 to 1000.

Set-builder notation A set can also be described as set-builder notation AA = {xp(x)x \mid p(x)} - set of all objects xx for which the predicate p(x)p(x) is true. A set SS of all even positive integers less than 5 can be written as

  • SS = {xxx \mid x is an even integer less than 5}

Or AA = {1,2,3 ..., 1000} can be written as

  • AA = {xxx \mid x is a whole number and 1 x\le x \le 1000}

Some sets appear so often that they have special notations for them.

Set Definition
N\mathbb{N} = {0,1,2,3, \mathellipsis} Natural numbers
Z\mathbb{Z} = {\mathellipsis -2,-1,0,1,2,3, \mathellipsis} Integers
Z+\mathbb{Z}^{+} = {\mathellipsis -2,-1,0,1,2,3, \mathellipsis} Positive integers
Q\mathbb{Q} = {xx=pq,px \mid x = \frac{p}{q}, p and qq are integers with q0q \neq 0} Rational Numbers
R\mathbb{R} = {xxx \mid x is a real number} Real numbers
R+\mathbb{R^{+}} = {xxx \mid x is a positive real number} Positive real numbers

Empty and Universal sets

  • \emptyset - is the notation to define an empty set (also written as { })
  • UU denotes a universal set

For example, AA = {xRx2=2x \in \mathbb{R}\mid x^2 = -2} = \emptyset

There are two traps that a lot of people fall into when dealing with sets.

  1. =0\emptyset = 0

This is incorrect because it is like comparing apples and oranges, one of them is set and the other one is a number 2. \emptyset = {\emptyset} This is incorrect as well because the left side is an empty set while the right side is a set with a single element (which is also called a singleton set)

Subsets If every element of set SS is also an element of set OO, we can say that SS is a subset of OO or SOS \subseteq O. For example,

  • SOS \subseteq O when x(xS    xO)\forall x(x \in S \implies x \in O) is true
  • {apple, banana, cherry} \subseteq {apple, banana, cherry, lemon, kiwi}
  • {4,5,6} \subseteq {7,8,4,5,6}

When an element exists in one set and not in the other, we use the \nsubseteq notation:

  • {2,3,4} \nsubseteq {3,4,5,6}

because the number 2 is not present in the second set

The empty set is a subset of every set

Proper set When every elements of set AA is also an element of set BB but there is at least one element in set AA that is not in set BB, AA is a proper subset of BB. In symbols we write ABA \subset B. For example,

  • {3,4} \subset {3,4,5,6}

Cardinality Cardinality of a set is the number of elements a set contains. For example, AA = {6,7,8,9} has four elements, therefore the cardinality of the set AA is 4, often written as |AA| = 4. The empty set has a cardinality of 0: EE = { } = \emptyset

  • E\mid E \mid = 0

A set can be finite and infinite. The cardinality symbol | | above is used to describe finite sets.

Power sets Let's say there is a set SS which contains aa and bb:

  • SS = {a,ba,b}.

If wanted to get the all subsets of set SS, they would be the followings:

  1. \emptyset (since it is a subset of any set)
  2. {aa}
  3. {bb}
  4. {a,ba,b}

Now, the power set of SS, is the set of all subsets. It is denoted by the special sign P\mathcal{P}

  • SS = {a,ba,b}
  • P(S)\mathcal{P}(S) = {\emptyset, {aa}, {bb}, {a,ba,b}}

If the size of a set is written as

  • A\mid A \mid = nn

then the size of a power set is

  • P(A)=2n\mid \mathcal{P}(A) \mid = 2^n