# Set

## What is a Set in Mathematics?

A set is a well-defined collection of distinct objects.

The theory of Set (now called the Set Theory), as a mathematical discipline, rose up with George Cantor, a German mathematician, when he was working on some problems in Trigonometric series and series of real numbers after he recognized the importance of some distinct collections and intervals.

Cantor defined the set as a 'plurality conceived as a unity' (many in one; in other words, mentally putting together a number of things and assigning them into one box).

Mathematically, a Set $S$ is 'any collection' of definite, distinguishable objects of our universe, conceived as a whole. The objects (or things) are called the elements or members of the set $S$ . Some sets which are often pronounced in real life are, words like ''bunch'', ''herd'', ''flock'' etc. The set is a different entity from any of its members.

For example, a flock of birds (set) is not just only a single bird (member of the set). 'Flock' is just a mathematical concept with no material existence but 'bird' or 'birds' are real.

## How to write and represent sets?

Sets are represented in two main ways:

### Standard Method

In this method we use to write all elements of a set in a curly bracket ( { } ).

For example:

Flock of Birds := {Bird-1, Bird-2, ..., Bird-100,...}
or, $F:= {B_1, B_2, \ldots, B_{100}, \ldots }$ is a set.

Here I have used first capital letter of each term to notate the example mathematically. We read this set as, A set F is defined by a collection of objects $B_1, B_2, \ldots$ etc..

### Characteristic Method or Formula Method

In this method, we write a representative element and define that by a characteristic property. A characteristic property of a set is a property which is satisfied by each member of that set and by nothing else.

For example, above set of Flock of birds can also be written as:
$\mathrm{ F := { B : B \ is \ a \ bird } }$ which has the same meaning at a wider extent.

We read it as: ''A set F is defined by element B such that B is a bird.''

## Examples of Useful Standard Sets

Some standard sets in Mathematics are:

### Set of Natural Numbers

It includes of the numbers, which we can count, viz. $\mathrm{ {0,1,2,3,4,5,6,7, \ldots }}$ . The set of natural numbers is denoted by $\mathbb{N}$ .

### Set of Integers

Integers includes of negatives of natural numbers and natural numbers itself. It is denoted by $\mathbb{Z}$ . $-5, -4, 1, 2, 0$ ...all are integers. The rigorous definition of integers be discussed in fourth part of the series.

### Set of Rational Numbers

Rational numbers are numbers which might be represented as $\frac{p}{q}$ , where p and q both are integers and relatively prime to each other and q not being zero. The set of rational numbers is represented by $\mathbb{Q}$ and may include elements like $\frac{2}{3}, \frac{-5}{7}, 8$ . The characteristic notation of the set of rational numbers is $\mathbb{Q} := { \dfrac{p}{q};/ p,q \in \mathbb{Z}, \ (p,q) \equiv 1 \ q \ne 0 }$ . The rigorous discussion about rational numbers will be provided in fourth part of the series.

### Empty Set

It is possible to conceive a set with no elements at all. Such a set is variously known as an empty set or a void set or a vacuous set or a null set.

An example of emptyset is the set $\{\mathrm{x:\ x \ is \ an \ integer \ and \ x^2=2} \}$ , since there exists no integer which square is 2 ---the set is empty. The unique empty set is denoted by $\emptyset$ .

### Unit Set

A set with only one element is called the unit set. {x} is a unit set or a singleton set.

### Universal Set

A set which contains every possible element in the universe, is a universal set. It is denoted by $U$ .

## The subset of a Set

Let $A$ and $B$ be two sets. We say that $A$ is a subset of $B$ (or $B$ is superset of $A$ or $A$ is contained in $B$ (or $B$ contains $A$ ) if every element of $A$ is also an element of set $B$ .

In this case we write, $A \subset B$ or $B \supset A$ respectively, having the same meaning. If every element of the set A is an element of the set B and B contains at-least one element which does not belong to A, then the set A is called a 'proper subset' of B (conversely, B is called the proper superset of A), otherwise A is an improper subset of B.

The proper subset notion is denoted by $A \subset B$ while the latter is represented by $A \subseteq B$ . Subset word might be understood using 'sub-collection' or 'sub-family' as its synonyms. Two sets are equal to each other if and only if each is a subset of the other.

## Types of sets (based on number of elements)

### Finite Set

A set is said to be finite, if it has finite number of elements. For example: A:= {a,b,c,d} is a finite set with four elements. The number of elements in a set is called the cardinality of the set.

### Infinite Set

A set is infinite, if contains infinitely many elements. The set of natural numbers, $\mathbb{N} := \mathrm{ {0,1,2,3,4,5,6,7, \ldots }}$ is an infinite set. The cardinality of an infinite set is infinite.

An empty set is a finite set with zero elements (i.e., zero cardinality).

## Power Set of a Set

Power set of a set A is defined as the family consisting of all subsets of A, but the subset itself. The power-set is denoted by $P(A):= { X: X \subset A }$ .

## Operations on Sets

### Union of Two Sets

If A and B are two sets, then their union (or join) is the set, defined by another set $S \cup T$ such that it consists of elements from either A or B or both. If we write the sets A and B using Characteristic Method as,

$\mathrm{A:= {x : x \ is \ an \ element \ of \ set \ A}}$ .

and, $\mathrm{B:= {x : x \ is \ an \ element \ of \ set \ B}}$

then the union set of A and B is defined by set J such that

$\mathrm{J := {x: x \ is \ an \ element \ of \ set \ A \ or \ set \ B \ or \ both }}$ .

For practical example, let we have two sets:

$A:= {1,2,3,r,t,y}$ and $B:={3,6,9,r,y,g,k}$ be any two sets; then their union is $A \cup B :={ 1,2,3,6,9,r,t,y,g,k }$ .

Note that it behaves like writing all the elements of each set, just caring that you are not allowed to write one element twice.

### Intersection of Two Sets

Intersection or meet of two sets A and B is similarly defined by 'and' connective. The set {x: x is an element of A and x is an element of B} or briefly $\mathrm { { x: x \in A \wedge x \in B }}$ . It is denoted by $A \cap B$ or by $A \cdot B$ or by $AB$ .

For example, and by definition, if A and B be two sets defined as,

$A:={1,2,3,r,t,y}$

$B:={3,6,9,r,g,k}$

then their intersection set, defined by $A \cap B:= {3,r}$ .

In simple words, the set formed with all common elements of two or more sets is called the intersection set of those sets.

If, again, A and B are two sets, we say that A is disjoint from B or B is disjoint from A or both A and B are mutually disjoint, if they have no common elements. Mathematically, two sets A and B are said to be disjoint iff $A \cap B := \emptyset$ .

If two sets are not disjoint, they are said to intersect each other.

For example, if ${q,w,e,r,t,y,u}$ is a set of keyboard letters, then ${ {q,w,e}, {r}, {t,y},{u}}$ is a partition of the set and each element of the set belongs to exactly one member (subset) of partition set. Note that there are many partition sets possible for a set. For example, ${{q,w}, {e,r},{t,y,u}}$ is also a partition set of set ${q,w,e,r,t,y,u}$ .

The complement set $A^c$ or $\displaystyle{\overline{A}}$ of a set $A$ is a collection of objects which do not belong to $A$ . Mathematically, $A^c := {x: x \notin A }$ .

The relative complement of set $A$ with respect to another set $X$ is $X \cap A^c$ ; i.e., intersection of set $X$ and the complement set of $A$ . This is usually shortened by $X-A$ , read X minus A. Thus, $X-A := {x : x \in X \wedge x \notin A}$ , that is, the set of members of $X$ which are not members of $A$ .

The complement set is considered as a relative complement set with respect to (w.r.t) the universal set, and is called the Absolute Complement Set.

### Symmetric Difference of two sets

The symmetric difference is another difference of sets $A$ and $B$ , symbolized $A \Delta B$ , is defined by the union of mutual complements of sets $A$ and $B$ , i.e., $A \Delta B := (A -B) \cup (B-A) = B \Delta A$ .

### Cartesian Product of sets

Let $A$ and $B$ be two sets. Then their cartesian product is defined to be the set of an ordered pair, $(a,b)$ , where $a$ and $b$ are the elements of set $A$ and set $B$, respectively. Mathematically; the product of two sets $A$ and $B$ : $A \times B := {(a,b) : a \in A, \ b \in B}$ .

Note that $A \times B \ne B \times A$ .

If $A$ has $m$ elements, $B$ has $n$ elements then $A \times B$ indeed has $mn$ elements.

We see that if we product two sets, we get an ordered pair of two objects (now we'll say them, variables). Similarly if we product more than two sets we get ordered pair of same number of variables. For example:

$X \times Y := (x,y); x \in X, y \in Y$ .

$X \times Y \times Z :=(x,y,z); x \in X, y \in Y, z \in Z$ . etc.

The sets, which are being product are called the factor sets of the ordered pair obtained. When we form products, it is not necessary the factor sets to be distinct. The product of the same set $A$ taken $n$ times is called the $n$ -th power of $A$ and is denoted by $A^n$ . Thus, $A^2$ is $A \times A$ . $A^3$ is $A \times A \times A$ . And so on.

## Important Theorems on Sets

• $A \cup (B \cup C) = (A \cup B) \cup C$
• $A \cap (B \cap C) = (A \cap B) \cap C$
• $A \cup B= B \cup A$
• $A \cap B= B \cap A$
• $A \cup (B \cap C)= (A \cup B) \cap (A \cup C)$
• $A \cap (B \cup C)= (A \cap B) \cup (A \cap C)$
• $A \cup \emptyset= A$
• $A \cap \emptyset= \emptyset$
• $A \cup U=U$
• $A \cap U=A$
• $A \cup \overline{A}=U$
• $A \cap \overline{A}=\emptyset$
• If $\forall A \ , A \cup B=A$ $\Rightarrow B=\emptyset$
• If $\forall A \ , A \cap B=A \Rightarrow B=U$
• Self-dual Property: If $A \cup B =U$ and $A \cap B=\emptyset \ \Rightarrow B=\overline{A}$
• Self Dual: $\overline{\overline{A}}=A$
• $\overline{\emptyset}=U$
• $\overline{U}= \emptyset$
• Idempotent Law: $A \cup A=A$
• Idempotent Law: $A \cap A =A$
• Absorption Law: $A \cup (A \cap B) =A$
• Absorption Law: $A \cap (A \cup B) =A$
• de Morgen Law: $\overline{A \cup B} =\overline{A} \cap \overline{B}$
• de Morgen Law: $\overline{A \cap B} =\overline{A} \cup \overline{B}$
• Another Theorem

The following statements about set A and set B are equivalent to one another

$A \subseteq B$

$A \cap B=A$

$A \cup B =B$

## Set Relations

A relation from set X to set Y is a subset of cartesian product $X \times Y$ . Similarly, a relation from set B to set A is a subset of $B \times A$ .

• 'Michelle is the wife of Barak Obama.'
• 'John is the brother of Nick.'
• 'Robert is the father of Marry.'
• 'Ram is older than Laxman.'
• 'Mac is the product of Apple Inc.'

After reading these statements, you will realize that the first 'Noun' of each sentence is related to the other.

We say that each noun is in a RELATIONSHIP to the other.

Michelle is related to Barak Obama as a wife.

John is related to Nick, as a brother. Robert is related to Marry as the father.

Ram is related to Laxman in terms of age(seniority).

Mac is related to Apple Inc. as a product.

Such relations are also used in Mathematics, but a little variations; like 'alphabets' or 'numbers' are used at place of some noun and mathematical relations are used between them. Some good examples of relations are:

is less than
is greater than
is equal to
is an element of
belongs to
divides
etc. etc.

Some examples of regular mathematical statements which we encounter daily are:

4<6 : 4 is less than 6.
5=5 : 5 is equal to 5.
6/3 : 3 divides 6.

For a general use, we can represent a statement as:

''some x is related to y''

Here 'is related to' phrase is nothing but a particular mathematical relation. For mathematical convenience, we write ''x is related to y'' as $x \rho y$.

x and y are two objects in a certain order and they can also be used as ordered pairs (x,y).

$(x,y) \in \rho$ and $x \rho y$ are the same and will be treated as the same term in further readings. If $\rho$ represents the relation motherhood, then $\mathrm {(Jane, \ John)} \in \rho$ means that Jane is the mother of John.

All the relations we discussed above, were in between two objects (x,y), thus they are called Binary Relations. $(x,y) \in \rho \Rightarrow \rho$ is a binary relation between a and b. Similarly, $(x,y,z) \in \rho \Rightarrow \rho$ is a ternary (3-nary) relation on ordered pair (x,y,z).

In general a relation working on an n-tuple $(x_1, x_2, \ldots x_n) \in \rho \Rightarrow \rho$ is an n-ary relation working on n-tuple.

Binary relations are really important to understand for further understanding. In a binary relation, $(x,y) \in \rho$ , the first object of the ordered pair is called the the domain of relation ρ and is defined by $D_{\rho} := {x| \mathrm{for \ some \ y, \ (x,y) \in \rho} }$ and the second object is called the range of the relation ρ and is defined by $R_{\rho} := {y| \mathrm{for \ some \ y, \ (x,y) \in \rho} }$ .

## Equivalence Relations on Set

A relation is equivalence if it satisfies three properties, Symmetric, Reflexive and Transitive.

A relation is symmetric: Consider three sentences:

1. "Jen is the mother of John.";
2. "John is brother of Nick." and
3. "Jen, John and Nick live in a room altogether."

In the first sentence, Jen has a relationship of motherhood with John. But can John have the same relation to Jen?

Can John be mother of Jen?

This type of relations are not symmetric.

Now consider the second statement.

John has a brotherhood relationship with Nick. But can Nick have the same relation to John? Can Nick be brother of John? The answer is simply YES!

Thus, both the sentences "John is the brother of Nick." and "Nick is the brother of John." are the same.

We may say that both are symmetric sentences.

And here the relation of 'brotherhood' is symmetric in nature.

Again LIVING WITH is also symmetric (it's your time to understand it how?).

Now try to write the above short discussion in general and mathematical forms.

Let X and Y be two objects (numbers or people or any living or non-living thing) and have a relation ρ between them.

Then we write that X is related by a relation ρ , to Y.

Or X ρ Y.

And if ρ is a symmetric relation, we might say that Y is (also) related by a relation ρ to X. Or Y ρ X.

So, in one line, $X \rho Y \iff Y \rho X$ is true.

A relation is reflexive if X is related to itself by a relation. i.e., $X \rho X$

Consider the statement "Jen, John and Nick live in a house altogether." once again. Is the relation of living reflexive?

How to check? Ask like, Jen lives with Jen, true?

Yes! Jen lives there.

If a relation is a transitive relation, means that some objects X, Y, Z are such that if X is related to Y by the relation, Y is related to Z by the relation, then X is also related to Z by the same relation.

i.e., $X \rho Y \wedge Y \rho Z \Rightarrow X \rho Z$ . For example, the relationship of brotherhood is transitive. (Why?)

Now we will define a combined relation, called equivalence relation, on sets.

We say that a relation ρ is an equivalence relation if the following properties are satisfied:

• (i) $X \rho Y \iff Y \rho X$
• (ii) $X \rho X$
• (iii) $X \rho Y \ Y \rho Z \Rightarrow X \rho Z$ .

If a set X has $n$ elements and set Y has $m$ elements, then the total number of relations from set A to B (or set B to A) is $2^{n\cdot m}$ .

## Relations on a single set

A relation on a set A is a subset of $A \times A$ . There are $2^{n^2}$ relations on set with $n$ elements out of which following are notable:

• Empty Relation: $\emptyset \subset A \times A$ is an empty relation on set A.
• Improper Relation: $A \times A$ is an improper or trivial relation on set A.
• Diagonal Relation: $\Delta := \{ (a,a) : a \in A \}$ is a diagonal relation on A.

## Composition of two relations

Let R and S be two relations on set A. Then, $R \cup S, \, R \cap S$ and $R \setminus S$ are all subsets of $A \times A$ and hence they are also relations on A.

The relation, $R \rho S := { (a_1, a_2)} \subset A \times A$ such that $(a_1, a_3) \in S$ and $(a_3, a_2) \in R$ , $\forall a_1, a_2, a_3$ is called the composition of R and S on set A.

### Properties of composite relations

Let R,S and t be relations set A. Then,

• $(R \rho S) \rho T =R\rho (S \rho T)$
• $R \rho \Delta = R = \Delta \rho R$
• $R \rho (S \cup T) = (R \rho S) \cup (R \rho T)$
• $R \rho (S \cap T) \subseteq (R \rho S) \cap (R \rho T)$

## Inverse Relation

Let R be a relation on a set defined by ordered pair $(x,y)$ , then the inverse of the relation R, $R^{-1}$ , is defined by ordered pair, $(y,x)$ . $R^{-1}$ is called the inverse relation of R on the set.

Remarks

Let R and S be the relations on A, then

• $(R^{-1})^{-1} = R$
• ${(R \rho S)}^{-1} = S^{-1} \rho R^{-1}$

## Partition of a set

A partition set of a set X is a disjoint collection of non-empty and distinct subsets of X such that each member of X is a member of exactly one member (subset) of the collection.

Let A be a set. A subset P of the power-set of A is called partition of A, if

• Union of members of P is A. i.e., $\displaystyle {\cup_{X \in P}} X =A$
• $X, \, Y \in P, \, X \neq Y \Rightarrow X \cap Y = \emptyset$ .

## Cardinally Equivalent Sets

A set $A$ is said to be cardinally equivalent or just ‘equivalent’ to another set $B$ if there exists one-one mapping (function) from A to B. This relation is denoted by the symbol ~. Therefore A~B means that set A and B are equivalent to each other.

## Denumerable, Countable and Uncountable Sets

A set A is called a denumerable (or countably infinite) set if there exists a one-one mapping from the set $\mathbb{N}$ of natural numbers onto the set A,i.e., A is denumerable, if it’s equivalent to the set of natural numbers $\mathbb{N}$ .

A set A is said to be countable set if either A is denumerable or A is finite.

A set is uncountable, if it’s infinite and not equivalent to $\mathbb{N}$ .

## Examples of Denumerable, Countable and Uncountable Sets

• The set of all natural numbers $\mathbb{N}$ is countable.
• The set of all rational numbers $\mathbb{Q}$ is countable.
• The set of all real numbers $\mathbb{R}$ is uncountable.
• The set of all irrational numbers is uncountable.
• The set $\mathbb{N} \times \mathbb{N}$ is uncountable.

## Important Theorems on Sets

1. Every subset of a finite set is finite.
2. Every superset of an infinite set is infinite.
3. If A and B are finite sets, then $A \cap B$ and $A \cup B$ are also finite sets.
4. Every subset of a countable set is countable.
5. Every infinite subset of a denumerable set is denumerable.
6. For countable sets, A & B , $A \cap B$ is also countable.
7. Every superset of an uncountable set is uncountable.
8. Every infinite set has a denumerable subset.
9. Countably infinite sets are smallest infinite sets.
10. The countable (finite) union of countable sets is countable.
11. Every infinite set is equivalent to one of its proper subsets.