Sets Solutions

SET

The concept of set is fundamental in all branches of mathematics. A set is a well defined collection or ensemble of distinct objects. Well defined collection means that there exists a rule with the help of which it is possible to tell whether a given object belongs or does not belong to given collection. Generally sets are denoted by capital letters A, B, C, X, Y, Z etc.

Representation of set

The set may be described by listing the objects/elements belonging to it, each element being separated by comma. This method is called tabular form of the set. The set also may be described by stating the property which its elements must satisfy. A = {x: P(x)} means A is the set consisting of the elements x such that x satisfies the property P(x). This method is called Set Builder form of the set.

For example
A = {1, 2, 3, 4, 5}  Tabular form; A = {x | x ≤ 5, x ∈ N}  Set Builder form

Union of Sets

Union of two or more sets is the set of all elements that belong to any of these sets. The symbol used for union of sets is '∪' i.e. A ∪ B = Union of set A and set B = {x: x ∈ in A or x ∈ in B (or both)}
e.g. A = {1, 2, 3, 4} and B = {2, 4, 5, 6} and C = {1, 2, 6, 8}, then A ∪ B ∪ C = {1, 2, 3, 4, 5, 6, 8}

Intersection of Sets

It is the set of all the elements, which are common to all the sets. The symbol used for intersection of sets is ‘∩’ i.e. A ∩ B = {x: x ∈ in A and x ∈ B}

Difference of two sets

The difference of set A to B denoted as A − B is the set of those elements that are in the set A but not in the set B i.e. A − B = {x: x ∈ A and x ∉ B}
Similarly B − A = {x: x ∈ B and x ∉ A} In general A − B ≠ B − A

Symmetric Difference of Two Sets

For two sets A and B, symmetric difference of A and B is given by (A − B) ∪ (B − A) and is denoted by A Δ B.

Subset of a Set

A set A is said to be a subset of the set B if each element of the set A is also the element of the set B. The symbol used is ‘⊆’ i.e. A ⊆ B ⇔ (x ∈ A ⇒ x ∈ B).
Each set is a subset of its own set. Also a void set is a subset of any set. If there is at least one element in B which does not belong to the set A, then A is a proper subset of set B and is denoted as A ⊂ B.
Total number of subsets of a finite set containing n elements is 2ⁿ.

Cardinality of set

If A is a set, then number of elements in set A is known as cardinality of set A denoted by n(A).
e.g., A = {1, 2, 3}, n(A) = 3

Some More Results Regarding the Order of Finite Sets

Let A, B and C be finite sets and U be the finite universal set, then

(i) n(A ∪ B) = n(A) + n(B) – n(A ∩ B)
(ii) n(A – B) = n(A) – n(A ∩ B)
(iii) n(A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ C)

Ex.:
If A and B be two sets containing 3 and 6 elements respectively, then minimum number of elements in A ∪ B is
(A) 3

(B) 4

(C) 6

(D) 12

Solution:
(C). We have, n(A ∪ B) = n(A) + n(B) – n(A ∩ B)

This shows that n(A ∪ B) is minimum according as n(A ∩ B) is maximum. When n(A ∩ B) is maximum;

This is possible only when A ⊆ B; In this case n(A ∩ B) = 3

∴ n(A ∪ B) = n(A) + n(B) – n(A ∩ B) = (3 + 6 – 3) = 6; n(A ∪ B)_min = 6.

Universal Set
A non-empty set of which all the sets under consideration are subsets is called the universal set. It is usually denoted by ‘U’.

Complementary Set
The complement of a set A with respect to the Universal Set U is difference of U and A. Complement of set A is denoted by A (or A^c) (or A′).

A = U − A = {x : x ∈ U and x ∉ A}

we can say that A ∪ A = U (Universal Set) and A ∩ A = ϕ (Void Set)

Some of the useful properties/operations on sets are as follows

1. A ∪ U = U
2. A ∩ ϕ = ϕ
3. ϕ^c = U
4. U^c = ϕ
5. (A ∪ B)′ = A′ ∩ B′
6. (A ∩ B)′ = A′ ∪ B′

Power Set
The set of all subsets of a set is called the power set, denoted by P(A).

P(A) = {S : S ⊆ A}

It follows that P (A) contains 2ⁿ elements.

VENN DIAGRAMS

The diagram drawn to represent sets are called Venn diagrams or Eule–Venn diagrams. Here we represent the universal set U by points within rectangle and the subset A of the set U represented by the interior of a circle. If a set A is a subset of a set B then the circle representing A is drawn inside the circle representing B. If A and B are no equal but they have some common elements, then to represent A and B by two intersecting circles.

CARTESIAN PRODUCT OF SETS

Order pair: If a, b ∈ R, then (a, b) is known as order pair. i.e., pair of elements in which their order of existence is important. (a, b) ≠ (b, a).

Cartesian product: If A and B are any two sets, then the set of all order pairs from set A to set B is known as Cartesian Product and denoted by A × B and is defined as A × B = {(x, y) / x ∈ A and y ∈ B} e.g., A = {1, 2, 3}, B = {a, b}

A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}

A × B ≠ B × A.

CARTESIAN PRODUCT OF SETS

Order pair: If a, b ∈ R, then (a, b) is known as order pair. i.e., pair of elements in which their order of existence is important. (a, b) ≠ (b, a).

Cartesian product: If A and B are any two sets, then the set of all order pairs from set A to set B is known as Cartesian Product and denoted by A × B and is defined as A × B = {(x, y) / x ∈ A and y ∈ B} e.g., A = {1, 2, 3}, B = {a, b}

A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}

A × B ≠ B × A.

RELATIONSDefinition

Let A and B be two non-empty sets then every subset of A × B defines a relation from A to B and every relation from A to B is subset of A × B.

Let R ⊆ A × B and (a, b) ∈ R. Then we say that a is related to b by the relation R and write it as a R b. If (a, b) ∉ R, we write it as a ∃(a, b) ∉ R, a ∤R b.

Example
Let A = {1, 2, 3, 4, 5}, B = {1, 3}
We set a relation from A to B as: a R b iff a ≤ b; a ∈ A, b ∈ B. Then
R = {(1, 1), (1, 3), (2, 3), (3, 3)} ⊆ A × B

Domain and Range of a Relation

Let R be a relation from A to B, that is, let R ⊆ A × B. Then
Domain R = {a: a ∈ A, (a, b) ∈ R for some b ∈ B}
Also Range R = {b: b ∈ B, (a, b) ∈ R for some a ∈ A},
Thus Dom. R ⊆ A, Range R ⊆ B.

Total Number of Distinct Relations from A to B

Suppose the set A has m elements and the set B has n elements. Then A × B has 2^mn different subsets which are different relations from A to B.

Inverse Relation

Let R ⊆ A × B be a relation from A to B. Then inverse relation R⁻¹ ⊆ B × A is defined by
R⁻¹ = {(b, a): (a, b) ∈ R, a ∈ A, b ∈ B}. It is clear that

1. a R b ⇔ b R⁻¹ a
2. dom R⁻¹ = range R and range R⁻¹ = dom R
3. (R⁻¹)⁻¹ = R

Example: Let A = {1, 2, 3, 4}, B = {a, b, c} and R = {(1, a), (1, c), (2, a)}. Then
(i) dom R = {1, 2}, range R = {a, c}
(ii) R⁻¹ = {(a, 1), (c, 1), (a, 2)}

Compositions of Relations

Let R ⊆ A × B, S ⊆ B × C be two relations. Then compositions of the relations R and S denoted by S∘R ⊆ A × C and is defined by (a, c) ∈ (S∘R) iff ∃ b ∈ B such that (a, b) ∈ R, (b, c) ∈ S.

Reflexive Relation

R is a reflexive relation if (a, a) ∈ R, ∀ a ∈ A. It should be noted if there is at least one element a ∈ A such that (a, a) ∉ R, then R is not reflexive.

Example:
Let A = {1, 2, 3, 4, 5}
R = {(1, 1), (3, 2), (4, 2), (4, 4), (5, 2), (5, 5)} is not reflexive because 3 ∈ A and (3, 3) ∉ R.

Symmetric Relation

R is called a symmetric relation on A if (x, y) ∈ R ⇒ (y, x) ∈ R. That is, y R x whenever x R y.
It should be noted that R is symmetric iff R⁻¹ = R. Let A = {1, 2, 3}, then R = {(1, 1), (1, 3), (3, 1)} is symmetric.

Anti-symmetric Relation

R is called an anti-symmetric relation if (a, b) ∈ R and (b, a) ∈ R ⇒ a = b. Thus, if a ≠ b then a may be related to b or b may be related to a, but never both. Or, we have never both a R b and b R a except when a = b.

Example: Let ℕ be the set of natural numbers. A relation R ⊆ ℕ × ℕ is defined by x R y iff x divides y (i.e. x/y).
Then x R y, y R x ⇒ x divides y, y divides x ⇒ x = y.

Transitive Relation

R is called a transitive relation if (a, b) ∈ R, (b, c) ∈ R ⇒ (a, c) ∈ R.
In other words, if a is related to b, b is related to c, then a is related to c.
Transitivity fails only when there exists a, b, c such that a R b, b R c but a not R c.

Equivalence Relation

A relation R in a set A is called an equivalence relation if
(i) R is reflexive i.e., (a, a) ∈ R, ∀ a ∈ A
(ii) R is symmetric i.e., (a, b) ∈ R ⇒ (b, a) ∈ R
(iii) R is transitive i.e., (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R
The equivalence relation is usually denoted by the symbol ~.

Formulae and Concepts

1. A set is a collection of well defined objects which are distinct from each other.

2. Let A be any set. The set of all subsets of A is called power set of A and is denoted by P(A).

3. Power set of a given set is always non empty.

4. If A has n elements, then P(A) has 2ⁿ elements.

5. Equal sets are always equivalent but equivalent sets may not be equal.

6. n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(B ∩ C) − n(A ∩ C) + n(A ∩ B ∩ C).

7. n(A − B) = n(A) − n(A ∩ B).

8. (A ∪ B)’ = A’ ∩ B’.

9. (A ∩ B)’ = A’ ∪ B’.

10. R is a reflexive relation if (a, a) ∈ R, ∀ a ∈ A.

11. R is called symmetric relation on A if (x, y) ∈ R ⇒ (y, x) ∈ R.

12. R is called anti-symmetric relation if (a, b) ∈ R and (b, a) ∈ R ⇒ a = b.

13. R is called transitive relation if (a, b) ∈ R, (b, c) ∈ R ⇒ (a, c) ∈ R.