Set Theory Concepts

Set

A set is an unordered collection of objects. objects in the set are called elements or members of that set. To denote that some element belongs to some we write

a ∈ A. To denote that a is not an member of the set A we write a ∉ A. Sets are named using uppercase letters. Lowercase letters are usually used to denote members of sets.

There are ways to represent or describe a set.

One way is to list all the members of a set, when this is possible. In this way all members of the set are listed between braces.

For example, the notation {1, 2, 3} represents the set with the four elements 1, 2 and 3. This method of describing a set is called as the roster method.

Example 1. The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}.

Another way to represent a set is to use set builder notation. In this method we characterize all the elements in the set by stating the property they must have to be members.

For example, the set O of all odd positive integers less than 10 can be written as

O = {x | x is an odd positive integer less than 10}

The Empty Set

There is a special set that has no elements. This set is called the empty set (or null set). Empty set is denoted by ∅. It can also be denoted by { }

A singleton set

A set with one element is known a singleton set. The set ∅ is an empty set and the set {∅} is a singleton set. The single element of the set {∅} is the empty set itself.

You can think of folders in a computer file system to remember it. The empty set can be thought of as an empty folder and the set consisting of just the empty set can be thought of as a folder with exactly one folder inside, namely, the empty folder.

Subsets

Def: The set A is a subset of B if and only if every element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of the set B.

Example:

The set of all odd positive integers less than 10 is a subset of the set of all positive integers less than 10

The Size of a Set

Sets are used extensively in counting problems, and for such applications we need the sizes of sets

Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by |S|

Example:

Let A be the set of odd positive integers less than 10. Then |A| = 5.

Infinite Set

A set is said to be infinite if it is not finite

Example:

The set of positive integers is infinite

Power Sets

Many problems involve testing all combinations of elements of a set to see if they satisfy some property. To consider all such combinations of elements of a set S, we build a new set that has as its members all the subsets of S

Def:

Given a set S, the power set of S is the set of all subsets of the set S. The power set of S is denoted by P(S).

Example: What is the power set of the set {0, 1, 2}?

The power set P({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence, P({0, 1, 2}) = {∅,{0},{1},{2},{0, 1},{0, 2},{1, 2},{0, 1, 2}}. Note that the empty set and the set itself are members of this set of subsets

What is the power set of the empty set? What is the power set of the set {∅}

The empty set has exactly one subset, namely, itself. Consequently, P(∅) = {∅}. The set {∅} has exactly two subsets, namely, ∅ and the set {∅} itself. Therefore, P({∅}) = {∅,{∅}}.

If a set has n elements, then its power set has 2ⁿelements.