Welcome to Edukum.com

# Set Theory

Set Operations
A set is basically a collection of dissimilar objects of same type. The objects of set are known as elements and members of the set. Objects can be a number or a alphabets or a name respectively.
For example:
A = {1, 2, 3, 4}
This is a set of numbers as an element (1, 2, 3, and 4). ‘A’ is the name of set.

A set can be formed either in tabular form or in builder form.

• Tabular Form
Listing of members in set formation is known as tabular form. If a set named ‘P’ having elements a, b, c, d.
For example:
P = {a, b, c, d}
• Builder Form
Builder form is a set is defined by its properties which their elements must gratify.
For example:
P = {x: x € N is a multiple of 3}
R = {x: x is even less than 9}

Standard notations

1. x $\in$ A: x belongs to A.
2. x $\in$ A: x does not belong to A
3. $\phi$ : empty set
4. U: universal set
5. N: Set of natural numbers
6. I: Set of all integers
7. I0: set of non-zero integers
8. I+: Set of all positive integers
9. C, C0: set of complex and non-complex integers
10. Q, Q0: set of rational number

Set Operations
There are several operations on set:

1. Union of Sets
If we have two sets A and B then, union is basically a combinations of elements of both A and B.
For example: A= {1, 2, 3}, B= {3, 4, 5, 6}
A Ụ B= {1, 2, 3, 4, 5, 6}
2. Intersection of Sets
If we have two sets A and B then, the common elements are selected.
For example: A= {a, b, c, d}, B= {d, b, e, f, g}
A ∩ B is {b, d}
3. Difference of Sets
The difference of two elements A and B are the element which belongs to A but not to B.
For example: A= {a, b, c, d}, B= {d, e, f, g}
A-B= {a, b, c}
4. Complement of a Set w.r.t a Universal Set
The complement of a set A is a set of element which doesn’t belong to A and is denoted by Ac.
5. Symmetric Difference of Sets
Symmetric difference is a difference in which if we have two sets A and B then, it is the combination of A and B and ignore the common elements.
For example:
A= {a, b, c, d}
B= {c, d, l, m}
Then it is = {a, b, l, m}

Algebra of Sets
A set is basically originated from a set formula by replacing the variable by definite sets. When the set of variables are replaced by sets and the set formulas are equal as set. The equality of sets are called identifiers.

• Idempotent Laws
In idempotent law, both the intersection and union of two sets A and A are equal to A.
A U A= A
A ∩ A= A
• Associative Laws
(A U B) U C= A U (B U C)
(A ∩ B) ∩ C= A ∩ (B ∩ C)
• Commutative Laws
(A U B)= B U A
A ∩ B= B ∩ A
• Distributive Laws
A U (B ∩ C) = (A U B) ∩ (A U C)
A ∩ (B U C) = (A ∩ B) U (A ∩ C)
• Identity Laws
A U $\phi$ = A
A ∩ B = A
A U Q = Q
A ∩ $\phi$ = $\phi$
• Complement Laws
A U Ac = U
A ∩ Ac = $\phi$
• De Morgan’s Laws
(A U B)c = Ac ∩ Bc
(A ∩ B)c= Ac U Bc

Finite and Infinite Sets

• If a set contains specific numbers of different elements, this set is known as Finite set.
P= {2, 4, 6, 8}
Q= {months in a year}
• Infinite set is a set that consists of infinite number of elements. If the counting of different elements of the sets does not come at the end are infinite sets.
I = {the set of all integers}
E = {x: x $\in$ N, x is a multiple of 2}

Power Set
The power set is defined as a given set A is the set of all subsets of A. it is denoted by P (A). if A has an n elements then P (A) has 2n elements.
If A= {r, s} then its subsets are Φ, {r}, {s}, {r, s}
P (A) = {Φ, {r}, {s}, {r, s} which has 2= 4 elements.

Duality
Duality is basically a expression which is obtained by putting (AND) in place of (OR) or vice versa. It is a one-to-one fashion. If the dual of S is Q, then the dual of Q is S. The duality principle holds the intersection and union of sets. If we change each and every symbol then we have dual results.

Multisets
It is basically an unordered collection of elements. The multiplicity of an element may be one or more than zero or one. The number of times a number is repeated is Multiset.
For example: A = {l, l, m, m, m, m, q, q, q, q}
Z = {g, g, g, g, a}

Cartesian Product
The Cartesian product of set named as A and B is in the order so that all the ordered pairs whose first member belongs to A and second belong to B. The Cartesian product is denoted by A×B.
For example

• Let P= {a, b, c} and Q= {k, l, m, n}. Find out its Cartesian product.
Solution:
P $\times$ Q = {(a, k), (a, l), (a, m), (a, n), (b, k), (b, l), (b, m), (b, n), (c, k), (c, l), (c, m), (c, n)}
• Let D= {1, 2, 3} and V= {4, 5, 6}. Find out the Cartesian product.
Solution:
D $\times$ V = {(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)}

Representation of Relation
Relation can be represented as:

1. Relation as Matrix
Relation of matrix can be represented as m × n matrix where M= [Mij]. Suppose we have two sets P= {a1, a2, a3….am} and Q= {b1, b2, b3….bn} are finite numbers that contains m and n number of elements.
Mij = {0 if (ai, bj) not belongs to R
1 if (ai, bj) belongs to R}
For example:
Problem: Let P= {1, 2, 3, 4}, Q= {a, b, c, d}
R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}
M=
 PQ a b c d 1 1 1 1 1 2 0 1 1 1 3 0 0 0 0 4 0 0 0 0
2. Relation as Directed Graph
If D is a finite set and R is a relation on P, where R is a relation which can be represented by directed graph.
3. Relation as an Arrow Diagram
If we have two set and a relation R is from X to Y. The relation can be represented by using arrow.
4. Relation as a Table
Relation can be represented in tabular form too. Where X and Y are two finite sets and R is a relation form X to Y.
 x y -3 0 0 3 3 6 6 9

Types of Relation

1. Reflexive Relation
A relation R on the set A is said to be reflexive when (a, a) € R. R can hold every elements a € A i.e. if A= {a, b} then R= {(a, a), (b, b)} is reflexive.
2. Symmetric Relation
A relation is said to be symmetric when it holds for all ‘a’ and ‘b’ in X. so, that a is related to b and b is related to a.
Symmetric if x R y $\Rightarrow$ y R x, where x, y $\in$ x
3. Transitive Relation
Transitive relation is a relation in which a related to b, b related to c, and c related to a.
Transitive if x R y, y R z $\Rightarrow$ R z, where x, y, z $\in$ x

Equivalence Relation and Partitions

• Equivalence Relation
It is a combination of symmetric, reflexive, and transitive. An equivalence relation is a relation when it satisfies all the three conditions.
For example:
Problem: Let A = {1, 2, 3, 4} and R= {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}. Prove that it is equivalence.
Solution:
Relation R is Reflexive as (1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)
Transitive: Relation R is transitive because (a, b), (b, c) belongs to R and (c, a) also belongs to R, hence proved it is transitive.
Symmetric relation is a relation where (a, b) $\in$ R, (b, a) belongs to R.
Hence it is an equivalence relation.
• Partition
A partition (A1, A2…, and Ai) of non-empty set can be defined as a collection of non-empty subset of A.
• Every elements of A belongs to one of Ai.
• If Ai and Aj are different then Ai ∩ Aj = $\phi$.
For example
Problem: Let A= {7, 8, 9}. Determine its partitions.
Solution:
We have three elements in a set.
1. [{7}, {8}, {9}]
2. [{7}, {8, 9}]
3. [{8}, {7, 9}]
4. [{9}, {7, 8}]
5. [{7, 8, 9}]

Partial Ordering
A relation is said to be partial when it satisfies their three conditions are as follows:

1. The relation must be reflexive.
2. The relation must be antisymmetric.
3. The relation must be transitive too.

For example:
Problem: Show that relation (x, y) € R, when x and y defined on +ve end of the partial order.
Solution:
Consider A = {1, 2, 3, 4} and relation R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3), (1, 1), (2, 2), (3, 3), (4, 4)}
for every a $\in$ A(a, a) $\in$ R i.e. (1, 1), (2, 2), (3, 3) and (4, 4) is reflexive.
whenever (a, b) and (b, a) $\in$ R then (a, c) $\in$ R, then we have a = b then it is antisymmetric.
when (a, b) and (b, c) belongs to R and (c, a) also belongs to R, then it is transitive.

Composition of Function and Relations
Suppose a function f: A→B and g: B→C, then the composition of f with g is the function from A into C and is defined as (gof) (x) = g [f(x)]. Composition of relation can be defined as relation R1 from A to B and another relation R2 from B to C. the composition of R1 and R2 are denoted by R1 o R2.

Cardinality and Inverse Functions
The number of elements in a set can be the cardinality of sets. The number is also known as cardinal number. If a sat has finite number of sets then it is cardinality. The inverse function is also known as invertible function. A function is invertible only when it is bijective function. If we have f: X→Y, then each element of X corresponds to different elements on Y.
For example: consider we have X= {1, 3, 4}, Y= {4, 6, 0 } and f= {(1, 4), (1, 6), (1, 0), (3, 4), (3, 6), (3, 0), (4, 4), (4, 6), (4, 0)}.
Solution: