SET Theroy

Set Theory

 

Definition

A set is a well-defined collection of distinct objects, which are called the 'elements or members' of the set. 

            · Capital letters A, B, C, ..... are  generally  used to denote sets  

            ·    Lower case letters a, b, c, ......  are used to denote elements  

            · A pair of braces} are used to enclose the elements of a set  

            ·  If an element x is a member of any set S, it is denoted by  x ∈ S  

            ·  If an element x is not a member of set S, it is denoted by  x ∉ S

 

Special sets and its notation

·       ∅ - The  empty set  is the set which contains no elements

·       U - The  universe set  is the set of all elements

·       N = {0, 1, 2, 3, ......}, t he set of natural numbers

·       Z =…, -2, -1, 0, 1, 2, 3, .....}, t he set of integers

·       Z + = {1, 2, 3, ...., the set of positive integers

·       Q =  The set of rational numbers

·       R = The set of real numbers

·       P (A) = The  power set  of any set  A  is the set of all subsets of  A

 

Representation of a Set

Sets can be represented in two ways

  1. Roster or Tabular Form
  2. 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.     The set of all vowels in English alphabet,  V = {a, e, i, o, u

2.     The set A of odd numbers less than 10, A = = 1, 3, 4, 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 V ={a, e, i, o, u}  is written as - V = {x | x is a vowel in English alphabet

2.     The set A = {1, 3, 5, 7, 9} is written as - A = {x | 1≤x <10 and (x% 2) ≠ 0


Various Types of Set

There are many types of set which are described as  

Empty set / Null set

A set which contains no elements at all is called the empty set or null set, and is denoted by {} or ∅

 

Universal set

The universal set is the set that contains all elements of all sets needed to solve a problem, denoted by  U

Example

Let A = {1, 2, 3  }

       B = {2, 4, 6, 8} then we can take

       U = {1, 2, 3, 4, 6, 8} as universal set

 

Singleton set

If a set contains only one element it is called a singleton set.

Example

1.  1. A = {1}   

2.  2. B = {A}     

 

Finite Set

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

Example 

1. S = {x | x ∈ N  and 100> x> of 200

2.   2. A = {5, 7, 9, 11

3.   3. B = {4, 8, 16, 32, 64, 128   

 

Infinite set

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

Example

S = {x | x ∈ N  and x> 10

2.     A = {2, 4, 6, 8, 10,. . . . . .}

3.     B = {4, 8, 16, 32, 64, 128, ......

 

Cardinality or Size of a set

Let A be any finite set, the cardinality of a set A is the number of elements in the set A. The cardinality of a set A is denoted by | A | 

Example

B = {4, 8, 16, 32, 64, 128

| B | = 6


Subset

Let A, B be sets, A  is a subset of  B  if and only if all members of A are member of B

The notation for A is a subset of B is A ⊆ B

 

Proper Subset

If A ⊆ B and A ≠ B, then we say that A is the  proper  subset of B,

The notation for A is a proper subset of B is A ⊂ B

 

Example

1.     If set A = {1, 3, 5 then

Number of subsets: ∅ , {1}, {3}, {5}, {1,3}, {1,5}, {3,5}, {1,3,5

Proper subsets: {1}, {3}, {5}, {1,3, {1,5}, {3,5

 

2.     If A = {1, 2}, B = {1, 2, 3} and C = {3, 1, 2} then A and B are subset of C, But A is a proper subset of C, while B is not , since B = C

 

Equal set

If two sets A and B are said to be equal, then these two sets are called equal set

            B = A, if A ⊆ B and B ⊆A

Example

        A = {1, 2, 3 and B = {3, 1, 2

 

Power set

The power set of a set is the set of all subsets of the set.

The power set of S is denoted by  P ( S )

Example

S = {1,2,3

P (S) = ∅ , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3

 

Cardinality of a power set

If | A  | =  n  then | P ( A ) | = 2 ^ n

where the size of the power set is equal to 2 ^ n  where n is the number of elements in the set.

 

Venn diagrams

A Venn diagram is a pictorial representation of the logical relationships between sets. 
In a Venn diagram, the sets are represented by shapes; usually rectangle and  circles.

The universal set is represented by the interior of a rectangle and other sets are represented by the interiors of circles that lie inside the rectangle.

The elements of a set are labeled within the circle.


Set Operations / Set Algebra

Union

Let A and B be sets. The union of two sets A  and  B  is the set that contains all elements in  A  or B , or both. It is denoted by  A ∪ B   

A ∪ B  = {  x  

| x ∈ A  or  x ∈ B  }    

Example

            A = {a, e, i, o, u

            B = {a, b, c, d, e

            A ∪ B = {a, b, c, d, e, i, o, u  }  


Intersection

Let A , and B be sets. The intersection of two sets A  and  B  is the set that contains all elements that are elements of both A and B. It is denoted by A  ∩  B   

A  ∩  B  = {  x

| x ∈ A  and  x ∈ B  }    

Example

            A = {a, e, i, o, u

            B = {a, b, c, d, e

            A  ∩  B = {a, e }

 

Disjoint sets

Two sets are said to be disjoint if their intersection is the empty set (ie, they have no elements in common) and it is r epresented by   A  ∩  B =  ∅

Example

            A = {a, e, i, o, u

            B = {1, 2, 3, 4, 5

            A  ∩  B =∅


Set Difference

The difference of  A  and  B , denoted by A  -  B , is the set containing elements in  A  but not in  B .

A  -  B = {x | x  ∈ A and x ∉ B

Example

            A = {a, e, i, o, u

            B = {a, b, c, d, e

            A  -  B = {i, o, u  }

Note: A  -  B  is ≠ the  B  -  A  

          A  ∩  B c  = A - B

 

Set Complement

If  U  is the universal set and A is the any set, then the set of elements which belong to U but which do not belong to A is called t he complement of A, and is denoted by A c  .T he complement of a set is represented by A A c  =  U  -  A .     

A c  = {  x

| x ∈ U  and  x ∉ A  }    

Example

            U = {a, b, c, d, e, f, g, h, I, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x , y, z

V = {a, e, i, o, u

            V c= {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z}

Note

            A ∩ A c  =  ∅

            A ∪Ac  = U

 

Cartesian product

Let A and B are sets. The Cartesian product of A and B, denoted as A x B, is defined as 

A  x  B = {(x, y) | x  ∈ A and y ∈ B

Example

            A = {a, e, i, o, u

            B = {1, 2, 3

            A x B = {(a, 1), (e, 1), (i, 1), (o, 1), (u, 1),

   (a, 2), (e, 2), (i, 2), (o, 2), (u, 2),

   (a, 3), (e, 3), (i, 3), (o, 3), (u, 3)

 

Duality Principal

The property of  duality  ('dual') means that you can

and swap   ∪

swap ∪ and ∩

swap ∅ and  U

swap U and  d 

 

Set Identities or Laws of set algebra

                             

  1. Identity Laws:    A ∪ ∅ = A and  A ∩  U  = A
  1. Laws Domination: A  ∪ U  =  U and  A ∩ ∅ = ∅ 
  1. Idempotent laws: A ∪ A = A and  A ∩ A = A
  2. Complement Laws: A ∩ A c= ∅ and  A ∪ A c =  U 

  1. Involution or Double complement laws:         (A c ) c  = A      
  2. Commutative laws: A ∪ B = B ∪ A and A ∩ B = B∩A

  1. Associative Laws: A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
  2. Distribute laws: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

  1. Absorption laws: A ∪ (A ∩ B) = A and  A ∩ (A ∪ B) = A

  1. De Morgan's laws: (A ∪ B) c  = A c  ∩ B c  and(A ∩ B)c  = Ac∪Bc   


Set Theory – Assignment Problems

https://deepanotes.blogspot.com/2020/08/assignment-problem.html





Comments

Post a Comment

Popular posts from this blog

Backtracking - N-Queens Problem, Sum of Subsets, Graph Colouring, Hamiltonian Cycle

Image
UNIT - V : BACKTRACKING General Method – 8-Queens Problem – Sum Of Subsets – Graph Coloring –  Hamiltonian Cycles General Method Backtracking is a problem-solving technique used in algorithms to find solutions by exploring all possible options. In backtracking, a state-space tree is a tree-like structure that represents all possible states (solutions or non-solutions) of a problem. Backtracking algorithms explore this tree using a depth-first search approach, systematically checking each path until a solution is found or all possibilities have been exhausted.  Here’s how it works, step-by-step: Start with a choice : Make a decision and move forward. Check feasibility : If this choice leads to a solution or partial solution, continue. If not, stop exploring this path. Go back and try a different path : If you reach a dead end, go back to the last point where you made a choice. Try a different path from there. Repeat until you find a solution ...
Read more

Divide and Conquer Technique - Binary Search, Quick Sort, Merge Sort

Image
  UNIT II - DIVIDE AND CONQUER TECHNIQUE General Method – Binary Search – Merge Sort – Quick Sort.  GENERAL METHOD The divide and conquer technique is a problem-solving approach that works in three main steps: 1.       Divide : Break down a large problem into smaller, simpler sub-problems. 2.       Conquer : Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large. 3.     Combine : Combine the solutions of the sub-problems to get the solution to the original, larger problem. This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.   BINARY SEARCH Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works: Start in the Middle : Look at the middle element of the list. Compare : ...
Read more

GRAPH THEORY

Image
  GRAPH THEORY DEFINITION A graph G = (V, E) consists of a non-empty set V, called the set of vertices (points, nodes) and a set  of ordered or unordered pairs of elements of V, called the edges E set (links), such that there is a mapping from the set E to the set of ordered or unordered pairs of elements of V. Example In the first graph, V = { A , B , C , D } E = {(A,B) , (A,C) , (A,D), (B,C), (B,D) , (C,D)} In the second graph, V = { E, F, G } E = {(F,E) , (E,G) , (G,F)} If an edge e ∈ E is associated with an ordered pair (u,v) or an unordered pair (u,v), where u,v ∈ V, then e is said to connect or join the nodes u and v.  The edge e that connects the nodes u and v is said to be incident on each of the nodes.  The pair of each node that is connected by an edge is called adjacent nodes . Isolated Nodes If any node has no edges connected with any other node then its degree will be zero(0) and it will be called as isolated node. Adjacent Nodes Her...
Read more