Discrete Mathematics Sets - Discrete Mathematics

What is a Set?

The concept of Sets is introduced by G. Cantor. According to him, a collection of definite and distinguishable objects which are selected by means of description or certain rules is defined as a set.

The basis of many fields such as counting theory, relations, graph theory and finite state machines etc is formed by Set theory.

Set - Definition

An unordered collection of different elements is defined as a set. A set bracket is used for listing all the elements and thus set is written. The changes in the order of the set do not make any changes in the set.

Some of the examples of sets are as follows:

  • A set of all positive integers
  • A set of all the planets in the solar system
  • A set of all the states in India
  • A set of all the lowercase letters of the alphabet

How a Set is represented?

Usually there are two ways for representing sets. They are:

  • Roster or Tabular Form
  • Set Builder Notation

Roster or Tabular Form

The listing of all the elements represents sets. The elements are separated by commas and enclosed with braces.

Example 1 − Set of vowels in English alphabet, A={a,e,i,o,u}

Example 2 − Set of odd numbers less than 10, B={1,3,5,7,9}

Set Builder Notation

The common property of all the elements of the set is specified by the set. The set is described as A={x:p(x)}

Example 1 − The set {a,e,i,o,u}is written as −A={x:x is a vowel in English alphabet}

Example 2 − The set {1,3,5,7,9} is written as −B={x:1≤x<10 and (x%2)≠0}

If an element x is a member of any set S, it is denoted by x∈S and if an element y is not a member of set S, it is denoted by y∉S.

Example − If S={1,1.2,1.7,2},1∈S but 1.5∉S

Some Important Sets

N − the set of all natural numbers = {1,2,3,4,.....}

Z − the set of all integers = {.....,−3,−2,−1,0,1,2,3,.....}

Z+ − the set of all positive integers

Q − the set of all rational numbers

R − the set of all real numbers

W − the set of all whole numbers

What is cardinality of a Set?

The number of elements that belong to a set is known as cardinality of the set and is denoted as |S| and the number is referred as the cardinal number. The cardinal number for the set with infinite number of elements is ∞.

Example − |{1,4,3,5}|=4,|{1,2,3,4,5,…}|=∞|

If there are two sets X and Y,

  • |X|=|Y| denotes two sets X and Y having same cardinality. It occurs when the number of elements in X is exactly equal to the number of elements in Y. In this case, there exists a bijective function ‘f’ from X to Y.
  • |X|≤|Y||X|≤|Y| denotes that set X’s cardinality is less than or equal to set Y’s cardinality. It occurs when number of elements in X is less than or equal to that of Y. Here, there exists an injective function ‘f’ from X to Y.
  • |X|<|Y||X|<|Y| denotes that set X’s cardinality is less than set Y’s cardinality. It occurs when number of elements in X is less than that of Y. Here, the function ‘f’ from X to Y is injective function but not bijective.
  • If |X|≤|Y|If |X|≤|Y| and |X|≥|Y||X|≥|Y| then |X|=|Y||X|=|Y|. The sets X and Y are commonly referred as equivalent sets.

What are the different types of Sets?

There are different types of sets such as finite, infinite, subset, universal, proper, singleton set, etc.

Finite Set

In a finite set, there are a definite number of elements.

Example − S={x|x∈N and 70>x>50}

Infinite Set

In an infinite set, there are a infinite number of elements

Example − S={x|x∈NS and x>10}

Subset

If every element of X is an element of Y, then a set X is a subset of set Y which is written as X⊆Y.

Example 1 − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y is a subset of set X as all the elements of set Y is in set X. Hence, it is written as Y⊆X.

Example 2 − Let, X={1,2,3} and Y={1,2,3}. Here set Y is a subset (Not a proper subset) of set X as all the elements of set Y is in set X. Hence, it is represented as Y⊆X.

Proper Subset

The subset which is not equal to is known as a proper subset. A Set X is a proper subset of set Y (Written as X⊂Y) if every element of X is an element of set Y and |X|<|Y|.

Example − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y⊂X as all elements in Y are contained in X too and X has at least one element is more than set Y.

Universal Set

A collection of elements in a particular context or application is known as Universal Set. The sets in that context or application are considered as the subsets of the universal sets. U is used for representing Universal Set.

Example – The set of all the animals on the earth can be defined as U. Set of mammals is considered as subset of U, set of fishes is also subset of U, etc.

Empty Set or Null Set

If the set does not have any elements, then such a set is known as Empty set, which is represented by ∅. The cardinality of the null set or empty set is considered as zero, as there are no elements.

Example − S={x|x∈N and 7<x<8}=∅

Singleton Set or Unit Set

When a set has only one element then such a set is known as Singleton set and is denoted by {s}.

Example − S={x|x∈N, 7<x<9} = {8}

Equal Set

When two sets have the same number of elements, then they are said to be equal sets.

Example − If A={1,2,6} and B={6,1,2}, they are equal as every element of set A is an element of set B and every element of set B is an element of set A.

Equivalent Set

Equivalent sets have same cardinalities.

Example − If A={1,2,6} and B={16,17,22} they are equivalent as cardinality of A is equal to the cardinality of B. i.e. |A|=|B|=3

Overlapping Set

When there is at least one common element in two sets, they are called as overlapping sets.

In case of overlapping sets −

  • n(A∪B)=n(A)+n(B)−n(A∩B)
  • n(A∪B)=n(A−B)+n(B−A)+n(A∩B)
  • n(A)=n(A−B)+n(A∩B)
  • n(B)=n(B−A)+n(A∩B)

Example − Let, A={1,2,6} and B={6,12,42}. Here the common element is 6 and hence the two sets are known to be overlapping.

Disjoint Set

If not even one element is common among both the sets, then the sets are known to be disjoint sets. The properties of disjoint sets are as follows:

  • n(A∩B)=∅
  • n(A∪B)=n(A)+n(B)

Example − Let, A={1,2,6} and B={7,9,14}, the two sets are disjoint sets as they do not have any common single element.

What are Venn Diagrams?

All possible logical relations between different mathematical sets are represented by Venn diagrams, which are invented by John Venn in 1880.

Examples

Some of the examples of Venn diagrams are depicted below:

Venn Diagram

What are Set Operations?

Some of the operations on sets such as Set Union, Set Interaction, Set Difference, and Set complement etc come under Set Operations.

Set Union

The union of sets A and B (denoted by A∪B) is the set of elements which are in A, in B, or in both A and B. Hence, A∪B={x|x∈A OR x∈B}

Example − If A={10,11,12,13} and B = {13,14,15} then A∪B={10,11,12,13,14,15}. Here the common element is considered only once.

Set Union

Set Intersection

The set of elements which appear in both the sets A and B is known as intersection of sets A and B and is denoted by A∩B.

Hence, A∩B={x|x∈A AND x∈B}.

Example − If A={11,12,13} and B={13,14,15}, then A∩B={13}

Set Intersection

Set Difference/ Relative Complement

The set of elements that are only in A but not in B is the difference between the Sets A and B is denoted as A–B.

Hence, A−B={x|x∈A AND x∉B}.

Example − If A={10,11,12,13} and B={13,14,15} then (A−B)={10,11,12} and (B−A)={14,15}. Here, it is to be noted that (A−B)≠(B−A)

Set Difference

Complement of a Set

All the elements that are not In set A are known as complement of set A. Hence, A′={x|x∉A}.

More specifically, A′=(U−A) where U is a universal set which contains all objects.

Example − If A={x|x belongstosetofoddintegers} then A′={y|y doesnotbelongtosetofoddintegers}

Complement Set

Cartesian Product / Cross Product

The Cartesian product of n number of sets A1,A2,…An denoted as A1×A2⋯×An can be defined as all possible ordered pairs (x1,x2,…xn)where x1∈A1,x2∈A2,…xn∈An

Example – Two sets are considered, A={a,b} and B={1,2}.

The Cartesian product of A and B is written as − A×B={(a,1),(a,2),(b,1),(b,2)}

The Cartesian product of B and A is written as − B×A={(1,a),(1,b),(2,a),(2,b)}

Power Set

The set of all the subsets of S, which are included in the empty set, is known as the power set of set S. The cardinality of a power set of a set S of cardinality n is 2n. Power set is denoted as P(S).

Example −

For a set S={a,b,c,d}, the subsets are calculated as

  • Subsets with 0 elements − {∅}(the empty set)
  • Subsets with 1 element − {a},{b},{c},{d}
  • Subsets with 2 elements − {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}
  • Subsets with 3 elements − {a,b,c},{a,b,d},{a,c,d},{b,c,d}
  • Subsets with 4 elements − {a,b,c,d}

Hence, P(S)={{∅},{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d},{a,b,c},{a,b,d},{a,c,d},{b,c,d},{a,b,c,d}

DMEQ1

20=1

Partitioning of a Set

The collection of n disjoint subsets is known as a partition of a set S. Say P1,P2,…Pn satisfy the conditions:

  • Pi does not contain the empty set.

[Pi≠{∅} for all 0<i≤n]

  • The union of the subsets must equal the entire original set.

[P1∪P2∪⋯∪Pn=S]

  • The intersection of any two distinct sets is empty.

[Pa∩Pb={∅}, for a≠b where n≥a,b≥0]

Example

Let S={a,b,c,d,e,f,g,h}

One probable partitioning is {a},{b,c,d},{e,f,g,h}

Another probable partitioning is {a,b},{c,d},{e,f,g,h}

Bell Numbers

The number of ways in which a set can be portioned, is provided by Bell Numbers, and are denoted by Bn, where n belongs to the cardinality of the set.

Example −

Let S={1,2,3}, n=|S|=3

The alternate partitions are −

  1. ∅,{1,2,3}
  2. {1},{2,3}
  3. {1,2},{3}
  4. {1,3},{2}
  5. {1},{2},{3}

Hence B3=5

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics