# Basic Concepts of Sets

German mathematician **G. Cantor** introduced the concept of sets. He had defined a set as a collection of definite and distinguishable objects selected by the means of certain rules or description.

**Set** theory forms the basis of several other fields of study like counting theory, relations, graph theory and finite state machines. In this chapter, we will cover the different aspects of **Set Theory**.

Contents

## Set – Definition

A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any changes in the set.

### Some Example of Sets

- A set of all positive integers
- A set of all the planets in the solar system
- A set of all the states in India
- A set of all the lowercase letters of the alphabet

## Representation of a Set

Sets can be represented in two ways −

- Roster or Tabular Form
- Set Builder Notation

### Roster or Tabular Form

The set is represented by listing all the elements comprising it. The elements are enclosed within braces and separated by commas.

**Example 1** − Set of vowels in English alphabet, A = {a,e,i,o,u}

**Example 2** − Set of odd numbers less than 10, B = {1,3,5,7,9}

### Set Builder Notation

The set is defined by specifying a property that elements of the set have in common. The set is described as A = { x : p(x)}

**Example 1** − The set {a,e,i,o,u} is written as −

A = { x : x is a vowel in English alphabet}

**Example 2** − The set {1,3,5,7,9} is written as −

B = { x : 1≤x<10 and (x%2) = 0}

If an element x is a member of any set S, it is denoted by x ∈ S and if an element y is not a member of set S, it is denoted by y ∉ S.

**Example** − If S = {1, 1.2, 1.7, 2}, 1 ∈ S but 1.5 ∉ S

**Some Important Sets**

**N** − the set of all natural numbers = {1, 2, 3, 4, …..}

**Z** − the set of all integers = {….., −3, −2, −1, 0, 1, 2, 3, …..}

**Z ^{+}** − the set of all positive integers

**Q** − the set of all rational numbers

**R** − the set of all real numbers

**W** − the set of all whole numbers

## Cardinality of a Set

Cardinality of a set S, denoted by |S|, is the number of elements of the set. If a set has an infinite number of elements, its cardinality is ∞.

**Example** − |{1, 4, 3, 5}| = 4, |{1, 2, 3, 4, 5,…}| = ∞

If there are two sets X and Y,

- |X| = |Y| represents two sets X and Y that have the same cardinality, if there exists a bijective function ‘f’ from X to Y.
- |X| ≤ |Y| represents set X has cardinality less than or equal to the cardinality of Y, if there exists an injective function ‘f’ from X to Y.
- |X| < |Y| represents set X has cardinality less than the cardinality of Y, if there is an injective function f, but no bijective function ‘f’ from X to Y.
- If |X| ≤ |Y| and |X| ≤ |Y| then |X| = |Y|

## Types of Sets

Sets can be classified into many types. Some of which are finite, infinite, subset, universal, proper, singleton set, etc.

### Finite Set

A set which contains a definite number of elements is called a finite set.

**Example** − S = {x | x ∈ N and 70 > x > 50}

### Infinite Set

A set which contains infinite number of elements is called an infinite set.

**Example** − S = {x | x ∈ N and x > 10}

### Subset

A set Y is a subset of set X (Written as X ⊆ Y) if every element of X is an element of set Y.

**Example 1** − Let, X = { 1, 2, 3, 4, 5, 6 } and Y = { 1, 2 }. Here set X is a subset of set Y as all the elements of set X is in set Y. Hence, we can write X ⊆ Y.

**Example 2** − Let, X = {1, 2, 3} and Y = {1, 2, 3}. Here set X is a subset (Not a proper subset) of set Y as all the elements of set X is in set Y. Hence, we can write X ⊆ Y.

### Proper Subset

The term “proper subset” can be defined as “subset of but not equal to”. A Set X is a proper subset of set Y (Written as X ⊂ Y) if every element of X is an element of set Y and |X| < |Y|.

**Example** − Let, X = {1, 2, 3, 4, 5, 6} and Y = {1, 2}. Here set X is a proper subset of set Y as at least one element is more in set Y. Hence, we can write X ⊂ Y.

### Universal Set

It is a collection of all elements in a particular context or application. All the sets in that context or application are essentially subsets of this universal set. Universal sets are represented as U.

**Example** − We may define U as the set of all animals on earth. In this case, set of all mammals is a subset of U, set of all fishes is a subset of U, set of all insects is a subset of U, and so on.

### Empty Set or Null Set

An empty set contains no elements. It is denoted by ∅. As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero.

**Example** − ∅ = {x | x ∈ N and 7 < x < 8}

### Singleton Set or Unit Set

Singleton set or unit set contains only one element. A singleton set is denoted by {s}.

**Example** − S = {x | x ∈ N, 7 < x < 9}

### Equal Set

If two sets contain the same elements they are said to be equal.

**Example** − If A = {1, 2, 6} and B = {6, 1, 2}, they are equal as every element of set A is an element of set B and every element of set B is an element of set A.

### Equivalent Set

If the cardinalities of two sets are same, they are called equivalent sets.

**Example** − If A = {1, 2, 6} and B = {16, 17, 22}, they are equivalent as cardinality of A is equal to the cardinality of B. i.e. |A| = |B| = 3

### Overlapping Set

Two sets that have at least one common element are called overlapping sets.

In case of overlapping sets −

- n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
- n(A ∪ B) = n(A − B) + n(B − A) + n(A ∩ B)
- n(A) = n(A − B) + n(A ∩ B)
- n(B) = n(B − A) + n(A ∩ B)

**Example** − Let, A = {1, 2, 6} and B = {6, 12, 42}. There is a common element ‘6’, hence these sets are overlapping sets.

### Disjoint Set

If two sets C and D are disjoint sets as they do not have even one element in common. Therefore, n(A ∪ B) = n(A) + n(B)

**Example** − Let, A = {1, 2, 6} and B = {7, 9, 14}, there is no common element, hence these sets are overlapping sets.

## Venn Diagrams

Venn diagram, invented in 1880 by John Venn, is a schematic diagram that shows all possible logical relations between different mathematical sets.

### Examples

## Set Operations

Set Operations include Set Union, Set Intersection, Set Difference, Complement of Set, and Cartesian Product.

### Set Union

The union of sets A and B (denoted by A ∪ B) is the set of elements which are in A, in B, or in both A and B. Hence, A ∪ B = {x | x ∈ A OR x ∈ B}.

**Example** − If A = {10, 11, 12, 13} and B = {13, 14, 15}, then A ∪ B = {10, 11, 12, 13, 14, 15}. (The common element occurs only once)

### Set Intersection

The union of sets A and B (denoted by A ∩ B) is the set of elements which are in both A and B. Hence, A ∩ B = {x | x ∈ A AND x ∈ B}.

**Example** − If A = {11, 12, 13} and B = {13, 14, 15}, then A ∩ B = {13}.

### Set Difference/ Relative Complement

The set difference of sets A and B (denoted by A − B) is the set of elements which are only in A but not in B. Hence, A − B = {x | x ∈ A AND x ∉ B}.

**Example** − If A = {10, 11, 12, 13} and B = {13, 14, 15}, then (A− B) = {10, 11, 12} and (B − A) = {14, 15}. Here, we can see (A − B) ≠ (B − A)

### Complement of a Set

The complement of a set A (denoted by A’) is the set of elements which are not in set A. Hence, A’ = {x | x ∉ A}.

More specifically, A’= (U − A) where U is a universal set which contains all objects.

**Example** − If A = {x | x belongs to set of odd integers} then A’ = {y | y does not belong to set of odd integers}

### Cartesian Product / Cross Product

The Cartesian product of n number of sets A_{1,} A_{2} …..A_{n,} defined as A_{1} × A_{2} ×….. × A_{n,} are the ordered pair (x_{1,} x_{2,}….x_{n}) where x_{1} ∈ A_{1}, x_{2} ∈ A_{2,} …… x_{n} ∈ A_{n}

**Example** − If we take two sets A = {a, b} and B = {1, 2},

The Cartesian product of A and B is written as − A × B = {(a, 1), (a, 2), (b, 1), (b, 2)}

The Cartesian product of B and A is written as − B × A = {(1, a), (1, b), (2, a), (2, b)}

## Power Set

Power set of a set S is the set of all subsets of S including the empty set. The cardinality of a power set of a set S of cardinality n is 2^{n}. Power set is denoted as P(S).

### Example −

For a set S = {a, b, c, d} let us calculate the subsets −

- Subsets with 0 elements − {∅} (the empty set)
- Subsets with 1 element − {a}, {b}, {c}, {d}
- Subsets with 2 elements − {a,b}, {a,c}, {a,d}, {b,c}, {b,d},{c,d}
- Subsets with 3 elements − {a,b,c},{a,b,d},{a,c,d},{b,c,d}
- Subsets with 4 elements − {a,b,c,d}

Hence, P(S) = { {∅}, {a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}}

| P(S) | = 2^{4} = 16

**Note** − The power set of an empty set is also an empty set.

| P ({∅}) | = 2^{0} = 1

## Partitioning of a Set

Partition of a set, say *S*, is a collection of *n* disjoint subsets, say*P _{1,} P_{2,}…… P_{n,}* that satisfies the following three conditions −

- P
_{i}does not contain the empty set.[ P

_{i}≠ {∅} for all 0 < i ≤ n] - The union of the subsets must equal the entire original set.
[P

_{1}∪ P_{2}∪ …..∪ P_{n}= S] - The intersection of any two distinct sets is empty.
[P

_{a}∩ P_{b}= {∅}, for a ≠ b where n ≥ a, b ≥ 0 ]

The number of partitions of the set is called a Bell number denoted as B_{n}.

### Example

Let S = {a, b, c, d, e, f, g, h}

One probable partitioning is {a}, {b, c, d}, {e, f, g, h}

Another probable partitioning is {a, b}, { c, d}, {e, f, g, h}

In this way, we can find out B_{n} number of different partitions.