Sets Theory: Best Answers 007EH

Welcome to Lecture Note Three- Set Theory – Discrete Mathematics.

You can also join the Discrete Mathematics Forum to interact and share ideas, also you can navigate to any session using the Table of Content

Don’t forget to leave your comment, suggestions regarding the previous, and current lecture to help us improve.

Introduction of Sets Theory

A set is defined as a collection of distinct objects of the same type or class of objects. The purposes of a set are called elements or members of the set. An object can be numbers, alphabets, names, etc.

Examples of sets are:

  1. A set of rivers in Nigeria.
  2. A set of vowels.

We broadly denote a set by the capital letter A, B, C, etc. while the fundamentals of the set by small letter a, b, x, y, etc.

If A is a set, and a is one of the elements of A, then we denote it as a ∈ A. Here the symbol ∈ means -“Element of.”

Sets Representation:

Sets are represented in two forms:-

a) Roster or tabular form: In this form of representation we list all the elements of the set within braces { } and separate them by commas.

Example: If A= set of all odd numbers less then 10 then in the roster from it can be expressed as A={ 1,3,5,7,9}.

b) Set Builder form: In this form of representation we list the properties fulfilled by all the elements of the set. We note as {x: x satisfies properties P}. and read as ‘the set of those entire x such that each x has properties P.’

Example: If B= {2, 4, 8, 16, 32}, then the set builder representation will be: B={x: x=2n, where n ∈ N and 1≤ n ≥5}

Standard Notations:

x ∈ Ax belongs to A or x is an element of set A.
x ∉ Ax does not belong to set A.
Empty Set.
UUniversal Set.
NThe set of all natural numbers.
IThe set of all integers.
I0The set of all non- zero integers.
I+The set of all + ve integers.
C, C0The set of all complex, non-zero complex numbers respectively.
Q, Q0, Q+The sets of rational, non- zero rational, +ve rational numbers respectively.
R, R0, R+The set of real, non-zero real, +ve real number respectively.
Standard Notations

Cardinality of a Sets:

The total number of unique elements in the set is called the cardinality of the set. The cardinality of the countably infinite set is countably infinite.

Examples:

1. Let P = {k, l, m, n}
The cardinality of the set P is 4.

2. Let A is the set of all non-negative even integers, i.e.
A = {0, 2, 4, 6, 8, 10……}.

As A is countably infinite set hence the cardinality.


Types of Sets

Sets can be classified into many categories. Some of which are finite, infinite, subset, universal, proper, power, singleton set, etc.

1. Finite Sets: A set is said to be finite if it contains exactly n distinct element where n is a non-negative integer. Here, n is said to be “cardinality of sets.” The cardinality of sets is denoted by|A|, # A, card (A) or n (A).

Example:

  1. Cardinality of empty set θ is 0 and is denoted by |θ| = 0
  2. Sets of even positive integer is not a finite set.

A set is called a finite set if there is one to one correspondence between the elements in the set and the element in some set n, where n is a natural number and n is the cardinality of the set. Finite Sets are also called numerable sets. n is termed as the cardinality of sets or a cardinal number of sets.

2. Infinite Sets: A set which is not finite is called as Infinite Sets.

Countable Infinite: If there is one to one correspondence between the elements in set and element in N. A countably infinite set is also known as Denumerable. A set that is either finite or denumerable is known as countable. A set which is not countable is known as Uncountable. The set of a non-negative even integer is countable Infinite.

Uncountable Infinite: A set which is not countable is called Uncountable Infinite Set or non-denumerable set or simply Uncountable.

Example: Set R of all +ve real numbers less than 1 that can be represented by the decimal form 0. a1,a2,a3….. Where a1 is an integer such that 0 ≤ ai ≤ 9.

3. Subsets: If every element in a set A is also an element of a set B, then A is called a subset of B. It can be denoted as A ⊆ B. Here B is called Superset of A.

Example: If A= {1, 2} and B= {4, 2, 1} the A is the subset of B or A ⊆ B.

Properties of Subsets:

  1. Every set is a subset of itself.
  2. The Null Set i.e.∅ is a subset of every set.
  3. If A is a subset of B and B is a subset of C, then A will be the subset of C. If A⊂B and B⊂ C ⟹ A ⊂ C
  4. A finite set having n elements has 2n subsets.

4. Proper Subset: If A is a subset of B and A ≠ B then A is said to be a proper subset of B. If A is a proper subset of B then B is not a subset of A, i.e., there is at least one element in B which is not in A.

Example:

(i) Let A = {2, 3, 4}
B = {2, 3, 4, 5}

A is a proper subset of B.

(ii) The null ∅ is a proper subset of every set.

5. Improper Subset: If A is a subset of B and A = B, then A is said to be an improper subset of B.

Example

(i) A = {2, 3, 4}, B = {2, 3, 4}

A is an improper subset of B.

(ii) Every set is an improper subset of itself.

6. Universal Set: If all the sets under investigations are subsets of a fixed set U, then the set U is called Universal Set.

Example: In the human population studies the universal set consists of all the people in the world.

7. Null Set or Empty Set: A set having no elements is called a Null set or void set. It is denoted by∅.

8. Singleton Set: It contains only one element. It is denoted by {s}.

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

9. Equal Sets: Two sets A and B are said to be equal and written as A = B if both have the same elements. Therefore, every element which belongs to A is also an element of the set B and every element which belongs to the set B is also an element of the set A.

  1. A = B ⟺ {x ϵ A  ⟺  x ϵ B}.  

If there is some element in set A that does not belong to set B or vice versa then A ≠ B, i.e., A is not equal to B.

10. Equivalent Sets: If the cardinalities of two sets are equal, they are called equivalent sets.

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

11. Disjoint Sets: Two sets A and B are said to be disjoint if no element of A is in B and no element of B is in A.

Example:

R = {a, b, c}
S = {k, p, m}

R and S are disjoint sets.

12. Power Sets: The power of any given set A is the set of all subsets of A and is denoted by P (A). If A has n elements, then P (A) has 2n elements.

Example: A = {1, 2, 3}
P (A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Partitions of a Set:

Let S be a nonempty set. A partition of S is a subdivision of S into nonoverlapping, nonempty subsets. Speceficially, a partition of S is a collection {Ai} of nonempty subsets of S such that:

  • Each a in S belongs to one of the Ai.
  • The sets of {Ai} are mutually disjoint; that is,
Aj≠ Ak Then Aj ∩ Ak= ∅

The subsets in a partition are called cells.

Fig: Venn diagram of a partition of the rectangular set S of points into five cells,A1,A2,A3,A4,A5

Partitions of a Set:
Partitions of a Set:

Venn Diagrams:

Venn diagram is a pictorial representation of sets in which an enclosed area in the plane represents sets.

Examples:

Venn Diagrams:


Operations on Sets

The basic set operations are:

1. Union of Sets: Union of Sets A and B is defined to be the set of all those elements which belong to A or B or both and is denoted by A∪B.

  1. A∪B = {x: x ∈ A or x ∈ B}  

Example: Let A = {1, 2, 3},       B= {3, 4, 5, 6}
A∪B = {1, 2, 3, 4, 5, 6}.

Operations on Sets

2. Intersection of Sets: Intersection of two sets A and B is the set of all those elements which belong to both A and B and is denoted by A ∩ B.

  1. A ∩ B = {x: x ∈ A and x ∈ B}  

Example: Let A = {11, 12, 13},       B = {13, 14, 15}
A ∩ B = {13}.

Sets Operations

3. Difference of Sets: The difference of two sets A and B is a set of all those elements which belongs to A but do not belong to B and is denoted by A – B.

  1. A – B = {x: x ∈ A and x ∉ B}  

Example: Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6} then A – B = {3, 4} and B – A = {5, 6}

Operations of Sets

4. Complement of a Set: The Complement of a Set A is a set of all those elements of the universal set which do not belong to A and is denoted by Ac.

Ac = U - A = {x: x ∈ U and x ∉ A} = {x: x ∉ A}

Example: Let U is the set of all natural numbers.
A = {1, 2, 3}
Ac = {all natural numbers except 1, 2, and 3}.

Operations on Sets

5. Symmetric Difference of Sets: The symmetric difference of two sets A and B is the set containing all the elements that are in A or B but not in both and is denoted by A ⨁ B i.e.

  1. A ⨁ B = (A ∪ B) – (A ∩ B)  

Example: Let A = {a, b, c, d}
B = {a, b, l, m}
A ⨁ B = {c, d, l, m}

Operations on Sets


Algebra of Sets

Sets under the operations of union, intersection, and complement satisfy various laws (identities) which are listed in Table 1.

Table: Law of Algebra of Sets

Idempotent Laws(a) A ∪ A = A(b) A ∩ A = A
Associative Laws(a) (A ∪ B) ∪ C = A ∪ (B ∪ C)(b) (A ∩ B) ∩ C = A ∩ (B ∩ C)
Commutative Laws(a) A ∪ B = B ∪ A(b) A ∩ B = B ∩ A
Distributive Laws(a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)(b) A ∩ (B ∪ C) =(A ∩ B) ∪ (A ∩ C)
De Morgan’s Laws(a) (A ∪B)c=Ac∩ Bc(b) (A ∩B)c=Ac∪ Bc
Identity Laws(a) A ∪ ∅ = A
(b) A ∪ U = U
(c) A ∩ U =A
(d) A ∩ ∅ = ∅
Complement Laws(a) A ∪ Ac= U
(b) A ∩ Ac= ∅
(c) Uc= ∅
(d) ∅c = U
Involution Law(a) (Ac)c = A
Law of Algebra of Sets

Table 1 shows the law of algebra of sets.

Example 1: Prove Idempotent Laws:

  1. (a) A ∪ A = A    

Solution:

Since, B ⊂ A ∪ B, therefore A ⊂ A ∪ A
Let   x ∈ A ∪ A ⇒ x ∈ A  or   x ∈ A ⇒  x ∈ A
∴ A ∪ A ⊂ A
As  A ∪ A ⊂ A and  A ⊂ A ∪ A ⇒ A =A ∪ A. Hence Proved.
  1. (b) A ∩ A = A  

Solution:

Since, A ∩ B ⊂ B, therefore A ∩ A ⊂ A
Let x ∈ A ⇒ x ∈ A  and x ∈ A  
⇒ x ∈ A ∩ A         ∴ A ⊂ A ∩ A
As A ∩ A ⊂ A and A ⊂ A ∩ A ⇒ A = A ∩ A. Hence Proved.

Example 2: Prove Associative Laws:

  1. (a) (A ∪ B) ∪ C = A ∪ (B ∪ C)  

Solution:

Let some x ∈ (A'∪ B) ∪ C
   ⇒  (x ∈ A   or   x ∈ B)    or   x ∈ C
   ⇒   x ∈ A   or   x ∈ B     or  x ∈ C
  ⇒    x ∈ A   or   (x ∈ B    or  x ∈ C)
  ⇒   x ∈ A   or   x ∈ B ∪ C 
  ⇒   x ∈ A ∪ (B ∪ C).
Similarly, if some   x ∈ A ∪ (B ∪ C), then  x ∈ (A ∪ B) ∪ C.
Thus, any 	         x ∈ A ∪ (B ∪ C) ⇔  x ∈ (A ∪ B) ∪ C. Hence Proved.
  1. (b) (A ∩ B) ∩ C = A ∩ (B ∩ C)  

Solution:

Let some x ∈ A ∩ (B ∩ C) ⇒   x ∈ A and x ∈ B ∩ C 
   ⇒   x ∈ A  and (x ∈ B and x ∈ C)  ⇒   x ∈ A  and x ∈ B and x ∈ C
  ⇒   (x ∈ A  and x ∈ B) and x ∈ C)  ⇒   x ∈ A ∩ B and x ∈ C
  ⇒   x ∈ (A ∩ B) ∩ C.
Similarly, if some   x ∈ A ∩ (B ∩ C), then x ∈ (A ∩ B) ∩ C
Thus, any 	         x ∈ (A ∩ B) ∩ C  ⇔  x ∈ A ∩ (B ∩ C). Hence Proved.

Example3: Prove Commutative Laws

  1. (a)  A ∪ B = B ∪ A  

Solution:

To Prove 
      A ∪ B = B ∪ A
      A ∪ B = {x: x ∈ A or x ∈ B}
            = {x: x ∈ B or x ∈ A}   (∵ Order is not preserved in case of sets)
      A ∪ B = B ∪ A. Hence Proved.
  1. (b) A ∩ B = B ∩ A   

Solution:

To Prove 
      A ∩ B = B ∩ A
      A ∩ B = {x: x ∈ A and x ∈ B}
            = {x: x ∈ B and x ∈ A}   (∵ Order is not preserved in case of sets)
      A ∩ B = B ∩ A. Hence Proved.

Example 4: Prove Distributive Laws

  1. (a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)  

Solution:

To Prove 
	     Let x ∈ A ∪ (B ∩ C)  ⇒ x ∈ A or  x ∈ B ∩ C 
      ⇒   (x ∈ A  or x ∈ A) or (x ∈ B and   x ∈ C)
      ⇒   (x ∈ A  or x ∈ B) and (x ∈ A  or x ∈ C)
      ⇒   x ∈ A ∪ B and   x ∈ A ∪ C
      ⇒   x ∈ (A ∪ B) ∩ (A ∪ C)
	  
Therefore, A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C)............(i)
Again, Let y ∈ (A ∪ B)  ∩ (A ∪ C) ⇒   y ∈ A ∪ B and y ∈ A ∪ C
      ⇒   (y ∈ A or y ∈ B) and (y ∈ A or y ∈ C)
      ⇒   (y ∈ A and y ∈ A) or (y ∈ B and y ∈ C)
      ⇒   y ∈ A    or    y ∈ B ∩ C
      ⇒   y ∈ A  ∪ (B ∩ C)
Therefore, (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C)............(ii)

Combining (i) and (ii), we get A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Hence Proved
  1. (b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)  

Solution:

To Prove 
      Let x ∈ A ∩ (B ∪ C)   ⇒   x ∈ A and x ∈ B ∪ C
	⇒  (x ∈ A and x ∈ A) and (x ∈ B  or x ∈ C)
         ⇒  (x ∈ A and x ∈ B) or  (x ∈ A and x ∈ C)
         ⇒   x ∈ A ∩ B or  x ∈ A ∩ C
         ⇒   x ∈ (A ∩ B) ∪ (A ∪ C)
		 
Therefore, A ∩ (B ∪ C) ⊂ (A ∩ B) ∪ (A ∪ C)............ (i)
Again, Let  y ∈ (A ∩ B) ∪ (A ∪ C) ⇒ y ∈ A ∩ B or y ∈ A ∩ C
	  ⇒  (y ∈ A and y ∈ B) or (y ∈ A and y ∈ C)
	  ⇒  (y ∈ A or y ∈ A) and (y ∈ B or y ∈ C)
	  ⇒ y ∈ A and  y ∈ B ∪ C
           ⇒ y ∈ A ∩ (B ∪ C)
Therefore, (A ∩ B) ∪ (A ∪ C) ⊂ A ∩ (B ∪ C)............ (ii)

Combining (i) and (ii), we get A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∪ C). Hence Proved

Example 5: Prove De Morgan’s Laws

(a) (A ∪B)c=Ac∩ Bc

Solution:

To Prove (A ∪B)c=Ac∩ Bc
Let x ∈ (A ∪B)c  ⇒  x ∉  A ∪ B			(∵ a ∈ A ⇔ a ∉ Ac)
           ⇒  x ∉  A and x ∉ B
           ⇒  x ∉  Ac and x ∉ Bc
           ⇒  x ∉  Ac∩ Bc
Therefore,  (A ∪B)c ⊂ Ac∩ Bc............. (i)
Again, let x ∈ Ac∩ Bc ⇒ x ∈ Ac and x ∈ Bc
            ⇒ x ∉  A and x ∉ B
            ⇒  x ∉  A ∪ B
            ⇒ x ∈ (A ∪B)c
Therefore, Ac∩ Bc  ⊂ (A ∪B)c............. (ii)
Combining (i) and (ii), we get Ac∩ Bc =(A ∪B)c. Hence Proved.
(b) (A ∩B)c = Ac∪ Bc

Solution:

Let x ∈ (A ∩B)c ⇒ x ∉  A ∩ B    (∵ a ∈ A ⇔ a ∉ Ac)
           ⇒ x ∉  A or x ∉ B
           ⇒ x ∈ Ac and x ∈ Bc
           ⇒ x ∈ Ac∪ Bc
∴ (A ∩B)c⊂ (A ∪B)c.................. (i)
Again, Let x ∈ Ac∪ Bc   ⇒ x ∈ Ac or x ∈ Bc
            ⇒ x ∉  A or x ∉ B
            ⇒ x ∉  A ∩ B
            ⇒ x ∈ (A ∩B)c
∴ Ac∪ Bc⊂ (A ∩B)c.................... (ii)
Combining (i) and (ii), we get(A ∩B)c=Ac∪ Bc. Hence Proved.

Example 6: Prove Identity Laws.

  1. (a) A ∪ ∅ = A  

Solution:

To Prove A ∪ ∅ = A
	         Let  x ∈ A ∪ ∅ ⇒ x ∈ A   or  x ∈ ∅
              ⇒ x ∈ A        (∵x ∈ ∅, as ∅ is the null set )
        Therefore, x ∈ A ∪ ∅ ⇒ x ∈ A   
  Hence,     A ∪ ∅ ⊂ A.
We know that A ⊂ A ∪ B for any set B.
 But for B = ∅, we have A ⊂ A ∪ ∅ 
From above, A ⊂ A ∪ ∅ , A ∪ ∅ ⊂ A ⇒ A = A ∪ ∅. Hence Proved.
  1. (b) A ∩ ∅ = ∅  

Solution:

To Prove A ∩ ∅ = ∅
If  x ∈ A, then x ∉  ∅             (∵∅ is a null set)
Therefore, x ∈ A, x ∉  ∅ ⇒ A ∩ ∅ = ∅. Hence Proved.
  1. (c) A ∪ U = U  

Solution:

To Prove A ∪ U = U
Every set is a subset of a universal set.
   ∴   A ∪ U ⊆ U
    Also,   U ⊆ A ∪ U
Therefore, A ∪ U = U. Hence Proved.
  1. (d) A ∩ U = A  

Solution:

To Prove A ∩ U = A
We know   A ∩ U ⊂ A................. (i)
So we have to show that A ⊂ A ∩ U
Let  x ∈ A ⇒ x ∈ A and x ∈ U        (∵ A ⊂ U so x ∈ A ⇒ x ∈ U )         
   ∴     x ∈ A ⇒ x ∈ A ∩ U
   ∴     A ⊂ A ∩ U................. (ii)
From (i) and (ii), we get A ∩ U = A. Hence Proved.

Example7: Prove Complement Laws

(a) A ∪ Ac= U

Solution:

To Prove A ∪ Ac= U
  Every set is a subset of U
    ∴  A ∪ Ac ⊂ U.................. (i)
We have to show that U ⊆ A ∪ Ac
  Let x ∈ U  ⇒  x ∈ A    or    x ∉  A     
      ⇒  x ∈ A    or   x ∈ Ac    ⇒ x ∈ A ∪ Ac
    ∴ U ⊆ A ∪ Ac................... (ii)
From (i) and (ii), we get A ∪ Ac= U. Hence Proved.
(b) A ∩ Ac=∅

Solution:

As ∅ is the subset of every set
     ∴     ∅ ⊆ A ∩ Ac..................... (i)
We have to show that A ∩ Ac ⊆ ∅
Let x ∈ A ∩ Ac  ⇒ x ∈ A and x ∈  Ac       
     ⇒ x ∈ A  and x ∉  A
      ⇒ x ∈ ∅
    ∴      A ∩ Ac ⊂∅..................... (ii)

From (i) and (ii), we get A∩ Ac=∅. Hence Proved.
(c) Uc= ∅

Solution:

Let x ∈ Uc   ⇔ x ∉ U ⇔ x ∈ ∅
    ∴ Uc= ∅. Hence Proved.     (As U is the Universal Set).
(d) ∅c = U

Solution:

Let x ∈ ∅c ⇔ x ∉ ∅  ⇔ x ∈ U       (As ∅ is an empty set)
	∴ ∅c = U.  Hence Proved.	

Example8: Prove Involution Law

(a) (Ac )c A.

Solution:

Let x ∈ (Ac )c ⇔ x ∉ Ac⇔  x ∈ a
     ∴ (Ac )c =A. Hence Proved.

Duality:

The dual E∗ of E is the equation obtained by replacing every occurrence of ∪, ∩, U and ∅ in E by ∩, ∪, ∅, and U, respectively. For example, the dual of

  1. (U ∩ A) ∪ (B ∩ A) = A is (∅ ∪ A) ∩ (B ∪ A) = A  

It is noted as the principle of duality, that if any equation E is an identity, then its dual E∗ is also an identity.

Principle of Extension:

According to the Principle of Extension two sets, A and B are the same if and only if they have the same members. We denote equal sets by A=B.

  1. If A= {1, 3, 5} and B= {3, 1, 5}, then A=B i.e., A and B are equal sets.  
  2. If A= {1, 4, 7} and B= {5, 4, 8}, then A≠ B i.e.., A and B are unequal sets.  

Cartesian product of two sets:

The Cartesian Product of two sets P and Q in that order is the set of all ordered pairs whose first member belongs to the set P and second member belong to set Q and is denoted by P x Q, i.e.,

  1. P x Q = {(x, y): x ∈ P, y ∈ Q}.  

Example: Let P = {a, b, c} and Q = {k, l, m, n}. Determine the Cartesian product of P and Q.

Solution: The Cartesian product of P and Q is

Algebra of Sets


Multisets

A multiset is an unordered collection of elements, in which the multiplicity of an element may be one or more than one or zero. The multiplicity of an element is the number of times the element repeated in the multiset. In other words, we can say that an element can appear any number of times in a set.

Example:

  1. A = {l, l, m, m, n, n, n, n}  
  2. B = {a, a, a, a, a, c}  

Operations on Multisets

1. Union of Multisets: The Union of two multisets A and B is a multiset such that the multiplicity of an element is equal to the maximum of the multiplicity of an element in A and B and is denoted by A ∪ B.

Example:

  1. Let A = {l, l, m, m, n, n, n, n}  
  2.     B = {l, m, m, m, n},   
  3. A ∪ B = {l, l, m, m, m, n, n, n, n}  

2. Intersections of Multisets: The intersection of two multisets A and B, is a multiset such that the multiplicity of an element is equal to the minimum of the multiplicity of an element in A and B and is denoted by A ∩ B.

Example:

  1. Let A = {l, l, m, n, p, q, q, r}  
  2.     B = {l, m, m, p, q, r, r, r, r}  
  3. A ∩ B = {l, m, p, q, r}.  

3. Difference of Multisets: The difference of two multisets A and B, is a multiset such that the multiplicity of an element is equal to the multiplicity of the element in A minus the multiplicity of the element in B if the difference is +ve, and is equal to 0 if the difference is 0 or negative

Example:

  1. Let A = {l, m, m, m, n, n, n, p, p, p}  
  2.     B = {l, m, m, m, n, r, r, r}  
  3. A – B = {n, n, p, p, p}  

4. Sum of Multisets: The sum of two multisets A and B, is a multiset such that the multiplicity of an element is equal to the sum of the multiplicity of an element in A and B

Example:

  1. Let A = {l, m, n, p, r}  
  2.     B = {l, l, m, n, n, n, p, r, r}  
  3. A + B = {l, l, l, m, m, n, n, n, n, p, p, r, r, r}  

5. Cardinality of Sets: The cardinality of a multiset is the number of distinct elements in a multiset without considering the multiplicity of an element

Example:

  1. A = {l, l, m, m, n, n, n, p, p, p, p, q, q, q}  

The cardinality of the multiset A is 5.

Ordered Set

It is defined as the ordered collection of distinct objects.

Example:

  1. Roll no {3, 6, 7, 8, 9}  
  2. Week Days {S, M, T, W, W, TH, F, S, S}  

Ordered Pairs

An Ordered Pair consists of two elements such that one of them is designated as the first member and other as the second member.

(a, b) and (b, a) are two different ordered pair. An ordered triple can also be written regarding an ordered pair as {(a, b) c}

An ordered Quadrable is an ordered pair {(((a, b), c) d)} with the first element as ordered triple.

An ordered n-tuple is an ordered pair where the first component is an ordered (n – 1) tuples, and the nth element is the second component.

  1. {(n -1), n}  

Example:

Multisets


Inclusion-Exclusion Principle

Let A, B be any two finite sets. Then n (A ∪ B) = n (A) + n (B) – n (A ∩ B)

Here “include” n (A) and n (B) and we “exclude” n (A ∩ B)

Example 1:

Suppose A, B, C are finite sets. Then A ∪ B ∪ C is finite and n (A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(A ∩ C) – n(BC) + n(A ∩ B ∩ C)

Example 2:

In a town of 10000 families it was found that 40% of families buy newspaper A, 20% family buy newspaper B, 10% family buy newspaper C, 5% family buy newspaper A and B, 3% family buy newspaper B and C and 4% family buy newspaper A and C. If 2% family buy all the newspaper. Find the number of families which buy

  1. Number of families which buy all three newspapers.
  2. Number of families which buy newspaper A only
  3. Number of families which buy newspaper B only
  4. Number of families which buy newspaper C only
  5. Number of families which buy None of A, B, C
  6. Number of families which buy exactly only one newspaper
  7. Number of families which buy newspaper A and B only
  8. Number of families which buy newspaper B and C only
  9. Number of families which buy newspaper C and A only
  10. Number of families which buy at least two newspapers
  11. Number of families which buy at most two newspapers
  12. Number of families which buy exactly two newspapers

Solution:

Inclusion-Exclusion Principle

1. Number of families which buy all three newspapers:

  1. n (A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(A ∩ C) – n(B ∩ C) + n(A ∩ B ∩ C)  
  2. n (A ∪ B ∪ C) = 40 + 20 + 10 – 5 – 3 – 4 + 2 = 60%  

2. Number of families which buy newspaper A only

  1. = 40 – 7 = 33%  

3. Number of families which buy newspaper B only

  1. = 20 – 6 = 14%  

4. Number of families which buy newspaper C only

  1. = 10 – 5 = 5%  

5. Number of families which buy None of A, B, and C

n (A ∪B ∪C)c = 100 - n (A ∪ B ∪ C)
n (A ∪B ∪C)c = 100 - [40 + 20 + 10 - 5- 3- 4 + 2]
n (A ∪B ∪C)c = 100 - 60 = 40 %

6. Number of families which buy exactly only one newspaper

  1. = 33 + 14 + 5 = 52%  

7. Number of families which buy newspaper A and B only

  1. = 3%  

8. Number of families which buy newspaper B and C only

  1. = 1%  

9. Number of families which buy newspaper C and A only

  1. = 2%  

10. Number of families which buy at least two newspapers

  1. = 8%  

11. Number of families which buy at most two newspapers

  1. = 98%  

12. Number of families which buy exactly two newspapers

  1. = 6%  

Mathematical Induction

The process to establish the validity of an ordinary result involving natural numbers is the principle of mathematical induction.

Rules of Mathematical Induction

Let n0 be a fixed integer. Suppose P (n) is a statement involving the natural number n and we wish to prove that P (n) is true for all n ≥n0.

1. Basic of Induction: P (n0) is true i.e. P (n) is true for n = n0.

2. Induction Step: Assume that the P (k) is true for n = k.
Then P (K+1) must also be true.
Then P (n) is true for all n ≥n0.

Example 1:

Prove the follo2wing by Mathematical Induction:

1 + 3 + 5 +.... + 2n - 1 = n2.

Solution: let us assume that.

P (n) = 1 + 3 + 5 +..... + 2n - 1 = n2.
For n = 1, 	P (1) = 1 = 12 = 1
It is true for n = 1................ (i)

Induction Step: For n = r,

P (r) = 1 + 3 + 5 +..... +2r-1 = r2 is true......................... (ii)
Adding 2r + 1 in both sides
       P (r + 1) = 1 + 3 + 5 +..... +2r-1 + 2r +1
                = r2 + (2r + 1) = r2 + 2r +1 = (r+1)2..................... (iii)
As P(r) is true. Hence P (r+1) is also true.
From (i), (ii) and (iii) we conclude that.
        1 + 3 + 5 +..... + 2n - 1 =n2 is true for n = 1, 2, 3, 4, 5 ....Hence Proved.

Example 2:
12 + 22 + 32 +…….+ n2 = Mathematical Induction

Solution: For n = 1,
P (1) = 12 =Mathematical Induction= 1

It is true for n = 1.

Induction Step: For n = r,………………. (i)
P (r) = 12 + 22 + 32 +…….. + r2 =Mathematical Inductionis true……….. (ii)

Adding (r+1)2 on both sides, we get
P (r+1) = 12 + 22 + 32 +…….+ r2+ (r+1)2 =Mathematical Induction+ (r+1)2

Mathematical Induction

As P (r) is true, hence P (r+1) is true.
From (i), (ii) and (iii) we conclude that

12 + 22 + 32 +……+ n2=Mathematical Induction is true for n = 1, 2, 3, 4, 5 ….. Hence Proved.

Example3: Show that for any integer n
11n+2 + 122n+1 is divisible by 133.

Solution:

Let P (n) = 11n+2+122n+1
    For n = 1,
    P (1) = 113+123=3059=133 x 23
So, 133 divide P (1).................. (i)

Induction Step: For n = r,

P (r) = 11r+2+122r+1=133 x s............ (ii)
 Now, for n = r + 1,
P (r+1) = 11r+2+1+122(r)+3=11[133s-122r+1] + 144. 122r+1
        = 11 x 133s + 122r+1.133=133[11s+122r+1]=133 x t........... (iii)
As (i), (ii), and (iii) all are true, hence P (n) is divisible by 133.


Discrete Mathematics Forum

https://eduraryhub.com/forums/forum/discrete-mathematics-forum/

Related Articles

Responses