Set Theory

Last Updated on: 15th February 2024, 12:46 pm

Set Theory

Set theory is the mathematical theory of well-determined collections, called sets, of objects that are called members, or elements, of the set.

Set

A set is a well-defined collection of distinct objects. Each object is said to be an element (or member) of the set.

The symbol Î is used to indicate ‘is an element of ‘ or ‘is a member of ‘ or ‘belongs to’ . Thus x $\displaystyle \in$ A, should be read as x is an element of A, or x belongs to A. Again for denoting ‘not an element of ‘ or ‘does not belong to, we use a symbol $\displaystyle \notin$ . So, y $\displaystyle \notin$ A should be read as y does not belong to’ A

Ex.: If V is the set of all vowels, we can say a $\displaystyle \notin$ V and g $\displaystyle \notin$ V.

Forms of describing a set

Roaster or Braces Method : In this form, the list of elements belonging to the set are shown within braces { …}

Ex. A = {a, e, i, o, u}, B = {6, 8, 10, 12, 14}, C = {pqr, prq, qrp, rqp, qpr, rpq}, D = {5, 7, 9} etc

Rule or Builder method

Under this method, a variable is written which represents all elements of the set followed by properties common to all elements of the set.

Ex. A = {x : x = 2n – 1, n $\displaystyle \in$ N and n $\displaystyle \le$ 7}, B = { x : x = 2n + 1, n $\displaystyle \in$ N and n $\displaystyle \le$ 6 }

Relationship of elements in Set

The members of a set are usually termed as elements, In A = {a, e, i, o, u}, a is an element and we write a $\displaystyle \in$ A i.e. a belongs to A . But 3 is not an element of M = {2, 14, 6, 8, 10} and we write 3 $\displaystyle \notin$ M. i.e 3 does not belong to M.
If every element of a set M is also an element of set N we say that M is a subset of N . We write M $\displaystyle \in$ N. N is said to be a superset of M. For example {a, b} $\displaystyle \in$ {a, b, c}, {2, 4, 6, 8, 10} $\displaystyle \in$ N. If there exists even a single element in A , which is not in B then A is not a subset of B.
If M is subset of N but M is not equal to N then M is called a proper subset of N.
$\displaystyle \phi$ has no proper subset.

Types of Sets

Sets may be classified in several types.

Finite Set

Finite set is a set containing of finite number of elements.

Ex: P = {6, 7, 8, 9, 10}, Q = {2, 4, 6, ……, 50}, R = {x : x is number of students in a class}

Infinite Set

A set that contains infinite or uncountable number of different elements is called an infinite set. A set of natural numbers is an infinites set. A set of Integers is an infinites set.

Ex. : S = { x:x >1, x is any number}

Null or Empty or Void Set

It is a set containing no element in it. Null or Empty set is usually indicated by $\displaystyle \phi$ (read as phi) or { }.

Ex: A= {x: x ispositive numbers less than zero}, A = { x : x is a perfect square of an integer 11 < x < 15}, B = { x : x is a negative integer whose square is -3}.

{{}} or { $\displaystyle \phi$ } are not empty sets, because each contain one element, namely the empty set Φ itself.

Note: (i) $\displaystyle \phi$ $\displaystyle \ne$ { $\displaystyle \phi$ } (ii) $\displaystyle \phi$ ¹ $\displaystyle \ne$ {0}.

Universal Set

A Universal set, denoted by U, is the collection of all objects in a particular context or theory. All other sets in that framework constitute subsets of the universal set. A Universal set may be finite or infinite.

Ex: 1. A pack of cards may be taken as Universal set for a set of diamond or spade. 2. A set of integers is a Universal set for the set of even or odd numbers.

Equal Sets

Two sets are called equal if any only if they have the same element.

Ex : For A = { 4, 8, 9, 3} & B = { 9, 3, 8, 4}, then the sets A and B are said to be equal. This is denoted by A = B (the order of elements does not matter)

A = {x : x is a letter in the word AMIT} ; B = {x : x is a letter in the word MITA}, then A = B

In Equal set, each set is sub set of the other. If A=B, then A $\displaystyle \in$ B and B $\displaystyle \in$ A

Singleton Set

A set containing only one element is called a singleton set.

Ex : A={2}

Ex : X = {x: x is neither positive nor negative}. Here, X = {0}, because it’s only 0 which is neither positive nor negative. Therefore, X is a singleton set

Equivalent Set

Two sets are equivalent If the total number of elements of both sets are equal, and is denoted as A ≅ B. It is not essential that the elements of the two sets should be same.

Example: A = {3, 4, 5, 6} , B = {a, i, o, u}, In both the sets A & B, there are 4 elements. So, A & B are equivalent sets

Disjoint Sets

Two sets are called disjoint or non-overlapping if and only if they have no element in common.

Ex. : A = { 2, 4, 7, 6, 8, 10} B = { 1, 5, 9, 3}. A & B are disjoint sets there is no common between them

Subset and Super Set

For any 2 sets A & B, A is called a subset of B if every member of A is also a member of B. It is denoted by A $\displaystyle \subseteq$ B (read as A is a subset of B), and B is superset of A (denoted by B⊇A).

Ex : A { 1, 2, 3, 4, } B= { 1, 2, 3, …….. 10}, A $\displaystyle \subseteq$ B and B⊇A)

Proper Sub-set

If each and every element of a set A are the elements of B and there exists at least one element of B that does not belong to A, Then the set A is said to be a proper sub-set of B (or B is called super set of A ). This is denoted by A $\displaystyle \subset$ B (read as A is proper sub-set of B), and B $\displaystyle \supset$ A (means A is a super set of B)

Ex. If B = {a, b, c}, then the sets {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, $\displaystyle \phi$ . are all proper sub-sets of B.

Note: 1. A set is not a proper subset of itself. 2. Number of proper subsets of a set A, containing n elements is 2ⁿ – 1, (taking f as a proper subset). (iii) $\displaystyle \phi$ is not a proper subset of itself.

Complement of Set

Let U be the Universal set and A be its sub-set. Then the complement set of A in relation

to U is that set whose elements belong to U but does not belong to A. This is denoted by A’,

A^c or A ( = U ~ A )

In symbols, A’ = {x : x e U and x $\displaystyle \in$ A}. We may also write A’ = {x : x $\displaystyle \notin$ A}.

Ex. U = { 1, 2, 3, ….., 10}, A = {2, 3, 6}, then A’ {1, 3, 5, 6, 8, 9, 10}

Properties of Complement set

The union of any set A and its complement A’ is the universal set, ί.e., A $\displaystyle \cup$ A’ = U.
The intersection of any set and its complement A’ is the null set, ί.e., A $\displaystyle \cap$ A’ = $\displaystyle \phi$ .
U’ = $\displaystyle \phi$ (ί.e., complement of a universal set is empty).
Complement of an empty set is a universal set,(ί.e., $\displaystyle \phi$ ’ = U)

Power Set

The family of all sub-sets of a given set A is known as power set and is denoted by P(A).

Ex: (i) If A = {b}, then P(A) = {b}, $\displaystyle \phi$ . (ii) If A = {c, d}, then P(A) = {c}, {d}, {c, d}, $\displaystyle \phi$ .

(iii) If A = {a, b, c}, P(A) = {a}, {b}, {c}, {a,b}, {b, c}, {a, c}, {a, b, c}, $\displaystyle \phi$ .

Thus when the number of elements of A is 1, then the number of sub-sets is 2, when the

number of elements of A is 2, then the number of sub-sets is 2² =4 and when it is 3, the number of sub-sets is 2³ =8. So, if A has n elements, P(A) will have 2ⁿ sub-sets.

Set Operations

Set Operations include Set Union, Set Intersection, Set Difference, Complement of Set, and Cartesian Product.

Union

If A and B are two given sets then their union is the set of those elements that belong either

to A or to B (or to both).

The union of A and B is denoted symbolically as A $\displaystyle \cup$ B ( read as A union B or A cup B). In symbols,

A $\displaystyle \cup$ B = {x : x $\displaystyle \in$ A or x $\displaystyle \in$ B}

Ex: (i) P = {1, 2, 3, 4, 5, }, Q = {2, 3, 5, 6, 7}, R = { 2, 4, 7, 8, 9}. Then P $\displaystyle \cup$ Q = {1, 2, 3, 4, 5, 6, 7}, and Q $\displaystyle \cup$ P = {1, 2, 3, 4, 5, 6, 7}, So, P $\displaystyle \cup$ Q = Q $\displaystyle \cup$ P (commutative law)

Again ( P $\displaystyle \cup$ Q) $\displaystyle \cup$ R = {1, 2, 3, 4, 5, 6, 7, 8, 9}, ( Q $\displaystyle \cup$ R) = { 2, 3, 4, 5, 6, 7, 8, 9}

P $\displaystyle \cup$ ( Q $\displaystyle \cup$ R) = { 1, 2, 3, 4, 5, 6, 7, 8, 9}, So, (P $\displaystyle \cup$ Q) $\displaystyle \cup$ R = P $\displaystyle \cup$ (Q $\displaystyle \cup$ R) (associative law)

Intersection

Intersection of 2 sets is the set consisting of all such elements of the given set which are common in both.

It is denoted by A $\displaystyle \cap$ B = { read as A intersection B}

Thus, A $\displaystyle \cap$ B = { x : x $\displaystyle \in$ A and x $\displaystyle \in$ B }

Ex. A = { 3, 4, 5, 6}, B = { 1,2,3,4,9,8}. Then A $\displaystyle \cap$ B = {3,4}

Difference

Given set P and set Q, the set difference of set P from set Q is the set of all element in P, but not in Q.

It is denoted by P – Q = { x : x $\displaystyle \notin$ Q, x $\displaystyle \notin$ P}

Ex. P = { 3, 4, 15, 16 } , Q = { 15, 16, 7, 8}, Then P – Q = { 3, 4}, Q – P = {7, 8}

Laws of Set operations

Set operations Laws

Idempotent Laws : For any set A. we have

(a) A $\displaystyle \cup$ A = A, (b) A $\displaystyle \cap$ A = A

Identity Laws: For any set A, we have

(a) A $\displaystyle \cup$ $\displaystyle \phi$ = A, (b) A $\displaystyle \cap$ $\displaystyle \phi$ = $\displaystyle \phi$ , (c ) A $\displaystyle \cup$ U = U, (d) A $\displaystyle \cap$ U = A

Commutative Laws : For any two sets A and B,

(a) A $\displaystyle \cup$ B = B $\displaystyle \cup$ A , (b) A $\displaystyle \cap$ B = B $\displaystyle \cap$ A

Associative Laws : For any three sets A, B and C,

(a) A $\displaystyle \cup$ (B $\displaystyle \cup$ C) = (A $\displaystyle \cup$ B) $\displaystyle \cup$ C, (b) A $\displaystyle \cap$ (B $\displaystyle \cap$ C) = (A $\displaystyle \cap$ B) $\displaystyle \cap$ C

Distributive Laws : For any three sets A, B and C,

(a) A $\displaystyle \cup$ (B $\displaystyle \cap$ C) = (A $\displaystyle \cup$ B) $\displaystyle \cap$ (A $\displaystyle \cup$ C) , (b) A Ç (B $\displaystyle \cup$ C) = (A $\displaystyle \cap$ B) $\displaystyle \cup$ (A $\displaystyle \cap$ C)

For any two sets A and B,

(a) P(A) $\displaystyle \cap$ P(B) = P(A $\displaystyle \cap$ B) , (b) P(A) $\displaystyle \cup$ P(B) $\displaystyle \subseteq$ P (A $\displaystyle \cup$ B), where P(A) is the power set of A.

If A is any set, we have (A’)’ = A (complement of complement of a set, is the set itself)

Demorgan’s Laws: For any three sets A, B and C, we have

(a) ( A $\displaystyle \cup$ B)’ = A’ $\displaystyle \cap$ B’, (b) (A $\displaystyle \cap$ B)’ = A’ $\displaystyle \cup$ B’, ( c ) A – (B $\displaystyle \cup$ C) = (A – B) $\displaystyle \cap$ (A – C)

(d) A – (B $\displaystyle \cap$ C) = (A – B) $\displaystyle \cup$ (A – C)

Venn Diagram

Venn Diagram is diagrammatical representation of mathematical relationships or logical sets, as circles or closed curves within an enclosing rectangle (the universal set), common elements of the sets being represented by intersections of the circles

Venn Diagram – Problems

Practical Applications of Venn Diagram

Ex. In a survey of 300 students, it was found that 80 students studied Physics, 120 students studied Chemistry, 100 Students studied Mathematics. 30 students studied all the three subjects, 54 students studied Physics and Chemistry, 70 students studied Chemistry and Mathematics and 50 students Physics and Mathematics.

Find the number who studied only Physics and the number who studied none of these subjects

Let P, C and M represent Physics, Chemistry and Mathematics respectively

The figure shows the Venn Diagram of the relationships :

P $\displaystyle \cap$ C $\displaystyle \cap$ M = 30 ( Students who studied all the 3 subjects)

P $\displaystyle \cap$ C= 54 ( Students who studied Physics & Chemistry)

C $\displaystyle \cap$ M = 70 ( Students who studied Chemistry and Mathematics)

P $\displaystyle \cap$ M = 50 (Students who studied Physics and Mathematics)

So, number of Students studying Physics only = 80 – (24 + 30 + 20) = 6

Number of students who studied one more subjects = 30 + 24 + 20 + 40 + 6 + 26 + 10 = 156

Number of students who studied none = 300 – 156 = 144.

Venn Diagram : Problems

Practical Applications of Venn Diagram

Ex. Out of a certain set of 400 students, 80 read German, 152 read French and 164 read Spanish. 72 readexactly two of these languages, but none read all the three. 68 read German but not Spanish and 20 read both German and French.

Find how many of the original set fail to read any of the three languages, and how many read German only.

Total number of students reading one or more of the subjects = 80 + 152 + 164 = 396.

Here, there is no student reading all the three languages together, so there will be no common region between the three circles, which means three circles will meet at a point. Now 72 students read exactly two subjects, ί.e., German and French, French and Spanish, German and Spanish

Let x₁ denote number of students reading both German & Spanish, and let x₂ denote number of students reading both French & Spanish

20 students read German and French. So, x₁ + x ₂= 72 – 20 = 52.

68 students read German but not Spanish. So, x₁ = 80 – 68 = 12 . So, x₂ = 52 – 12 = 40.

Number of students read German only = 80 – 20 – 12 = 48.

Total number of students reading German only, French only, Spanish only = 396 – 72 = 324.

Students fail to read either of the three languages = 400 – 324 = 76.

Ordered Pairs

An ordered pair (x, y) is a pair of mathematical objects. The order in which the objects appear in the pair is significant.

Given the two related values x and y, ordered pair is written as (x, y). The set of all possible ordered pairs of real numbers is written as {(x, y) | x $\displaystyle \in$ R, y $\displaystyle \in$ R}

Ordered pair (2, 3) is different from the ordered pair (3, 2).
(2, 3) is an ordered pair {2, -4} is a set (but not ordered pair as it uses brace {}).
(1,3,-2) is not ordered pair as it contain 3 elements (instead of 2),
{(1,5), (2,7)} is set of ordered pairs,
2,5 is not ordered pair (it is a simple list of numbers, as it is not paired in parenthesis)

Cartesian Product

If A and B are two non-empty sets, then the set of all ordered pairs (a,b) such that ‘a’ belongs to A and ‘b’ belongs to B, is called the Cartesian product of A and B, denoted by A $\displaystyle \times$ B.

Thus, A $\displaystyle \times$ B = { (a, b) : a $\displaystyle \in$ A and b $\displaystyle \in$ B}

If A = $\displaystyle \phi$ or B = $\displaystyle \phi$ , we define A $\displaystyle \times$ B = $\displaystyle \phi$

Ex: A = {1, 2, 3}, B = {4, 5}. Cartesian Product set A ´ B = {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}

Ex. If A $\displaystyle \times$ B = {(3, 2), (3, 4), (5, 2), (5, 4)}, find A and B.

A is the set of all first co-ordinates of A $\displaystyle \times$ B, while B is the set of all second co-ordinates of elements of A $\displaystyle \times$ B. So, A = {3, 5} and B = {2, 4}

Number of elements in Product Set

n(P $\displaystyle \times$ Q) = n(P) $\displaystyle \times$ n(Q), where n(P) & n(Q) represents the number of elements in the respective set P & Q. n(P $\displaystyle \times$ Q) represents the number of elements in the Cartesian product set (P $\displaystyle \times$ Q)

So n (P $\displaystyle \times$ Q) = n(Q $\displaystyle \times$ P).

Ex. P = {1, 3, 6} Q = {3, 5}

The product set P $\displaystyle \times$ Q = {(1, 3), (1,5), (3, 3), (3, 5), (6, 3), (6, 5)}.

The product set Q $\displaystyle \times$ P = {(3, 1) (3, 3) (3, 6), (5, 1), (5, 3), (5, 6)}

Here n(P) = 3 and n (Q) = 2, n(P $\displaystyle \times$ Q) = 6

Hence n(P $\displaystyle \times$ Q) = n(P) $\displaystyle \times$ n(Q). and n(P $\displaystyle \times$ Q) = n (Q $\displaystyle \times$ P) = 6.

Relation

A Relation is a set of Ordered Pairs,

Let A, B be any two non- empty sets, then every subset of A $\displaystyle \times$ B defines a relation from A to B and every relation from A to B is a subset of A $\displaystyle \times$ B.

Types of Relations

Void relation : Since $\displaystyle \phi$ $\displaystyle \subset$ A $\displaystyle \times$ A, it follows that $\displaystyle \phi$ is a relation on A, called empty or void relation.
Universal relation : Since A $\displaystyle \times$ A $\displaystyle \subseteq$ A $\displaystyle \times$ B, it follows. That A $\displaystyle \times$ A is a relation on A, called the Universal relation.
Inverse relation : If R is a relation on A, then the relation R^–¹ on A is defined by

R^-1 = { (b, a) : (a, b) $\displaystyle \in$ R } is called an inverse relation on A.

Domain & Range of a Relation

If R is a relation from A to B, then the set of all first co-ordinates of elements of R is called the Domain of R, while the set of all second co–ordinates of elements of R is called the range of R. Only the elements used by the relation constitute the range.

Dom (R) = {a: (a, b) $\displaystyle \in$ R } & Range (R) = { b : ( a, b) $\displaystyle \in$ R }

So, dom (R ^–¹) = range ( R) & Range (R^–¹ ) = dom (R)

Ex. 1: R={(2, –3), (4, 6), (3, –1), (6, 6), (2, 3)}. It is a relation between certain x‘s and certain y‘s The domain is all the x-values, and the range is all the y-values. To give the domain and the range, just list the values without duplication: domain: {2, 3, 4, 6}, range: {–3, –1, 3, 6}

Ex.2: In the Relation (1,2), (3,2), (5,7), (9,8), The domain is the set {1, 3, 5, 9} and the range is the set {2, 7, 8}.

Ex. 3: Let R = { (1, 2), (1, 4), (3, 2), (3, 4) }, then Dom ( R ) = {1, 3} and Range ( R) = { 2, 4 }.

Let N be the set of all natural numbers and let R = { (a, b) : a Î N, b Î N and 2a + b =10}

Find the Domain, range and Inverse Relation

R $\displaystyle \subseteq$ N $\displaystyle \times$ N . So it is a binary relation on A.

R = { (1, 8), (2, 6), (3, 4), (4, 2)}, Dom ( R ) = { 1, 2, 3, 4 }, Range ( R ) = { 8, 6, 4, 2 }

R^–¹ = { (8, 1), (6, 2), (4, 3), (2, 4)}.

Function

A function is a set of ordered pair, in which each x element has only ONE element associated with it.

A function is defined a type of relation which has only one output value with respect any permissible input value. The argument and the value may be real numbers, but they can also be elements from any given sets. The domain, the co-domain of the function and all the assigned values are in the Range of the function.

Let A and B be two non empty sets. A function ƒ : A $\displaystyle \to$ B is a rule that corresponds each a $\displaystyle \in$ A to unique b $\displaystyle \in$ B. A is called domain and B is called co-domain.

It is denoted as b = ƒ (a), b is called image of ‘a’. Range of ‘ƒ is the set of images of members of ‘A’.

Thus range of ƒ = ƒ(A) = { ƒ(a) : a $\displaystyle \in$ A } $\displaystyle \subseteq$ B.

Note : ƒ(A) is always a subset of B.

Domain & Range of Function

Domain : Domain of each function is determined by looking for those values of the independent variable (usually x) which we are allowed to use. (avoid 0 on the bottom of a fraction, or negative values under the square root sign).
Range : The Range of a function is the complete set of all possible resulting values of the dependent variable (y, usually), after we have substituted the domain.

In simple term, domain is all the values that go into a function, and the range is all the values that come out. Co-domain is what can possibly come out of the function

Set “A” is the Domain, {1, 2, 3, 4}
Set “B” is the Codomain, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Set of elements that get pointed to in B (the actual values produced by the function) are the Range (also called the Image), {3, 5, 7, 9}

Click here to see PDF

Set Theory – Definition, Types, Examples