Welcome to Edukum.com

Set Theory and Propositional Calculus

Technique of Counting

Recursion and Recurrence Relation

Algebraic Structure

Graphs and Trees

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}
    Union of sets
  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}
    Intersection of Sets
  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}
    Difference of Sets
  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.
    Complement of a set
  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}
    Symmetric Difference of set

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 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.

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.
    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.
    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)}
    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.
    Relation as 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.
    Relation as an Arrow Diagram
  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.
    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.
    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.
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.

Composite of Function and Relations

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)}.

Cardinality and Inverse Function


#Things To Remember