CAT Quant: Set Theory: Formulas and Important Concepts
Sets
A set is a well defined collection of objects.
Elements – The objects contained within a set are termed as its elements.
Basic notation – Sets are usually denoted by capital letters (e.g.- A, B, C) and the elements of the set are denoted by lower case letters (e.g.- a, b, c).
If an element x belongs to set A, it is denoted by “x \( \in \) A”. If x is not an element of A, it is denoted by “x \( \notin \) A”.
A set, in general is represented in two forms —
Roster Form – In this form a set is described by actually listing out its elements inside curly braces. For example the set of all prime numbers less than 12 is represented by A = {2,3, 5, 7, 11}.
Set Builder Form – In this form a set is described by charactering the properties of the elements of the set. For example the set of all prime numbers less than 12 is represented by A = {x | x is a prime number < 12}
Types of Set
Null Set – A set with no elements is known as a Null Set. Also called an Empty set or a Void Set and denoted by \( \{ \} \ or \ \phi \). For Example A = {x | x is an integer, 1< x <2} = {}.
Singleton Set – A set with only one element is known as a Singleton Set. For Example A = {x | x is an even prime number} = {2}.
Finite and Infinite Sets – A set is said to be finite if it is either an empty set or contains a finite number of elements. Otherwise it is said to be an Infinite Set. For Example, Finite Set: A = {x | x ∈ vowels in English}. Infinite Set: B = {x | x ∈ Natural numbers.}
Cardinality of a Set – The number of distinct elements in a set is called the cardinality(or order) of the set. It is denoted by O(A) or n(A) where n is the number of distinct elements in a set. For Example, Cardinality of A = {x, y, z, k} = 4.
Equal Set – Two sets A and B are said to be equal if they have the same elements i.e. if every element of A is an element of B and vise-versa. Example A = {x | x is an even prime number} and B = {x | x ∈ Even natural numbers, x < 3}.
Subsets
Subset – a set “A” is a subset of set “B” if every element of A is also an element of B. Denoted by A ⊆ B.
Every set is a subset of itself.
The empty set is a subset of every set.
If A is a finite set of cardinality “n”, then the total number of subsets of A is “2n“.
Proper Subset – a subset that is not equal to the original set. A is a subset of B and there is at least one element in B that is not there in A , A is said to be a proper subset of B, denoted by A ⊂ B.
Superset – If A is a subset of B (A ⊆ B), then we say that B contains A or “B is a Superset of A”. Denoted by A ⊇ B.
Power Set – If A is any set, then the set of all subsets of A is called the power set of A and is denoted by P(A) i.e. P{A} = {S | S ⊆ A}
For a set A , \( \phi \) ∈ P(A).
If A is a finite set having n elements, then the cardinality of P(A) is “2n“.
Universal Set – The set that contains all the elements under consideration in a given context is called the Universal Set. Denoted by “\( \mu \) or U”. For Example: In plane geometry, the set of all points in the plane is a Universal Set.
Set Operations
Union of Sets – Combining elements from two or more sets.. For two sets A and B, the union is the set of all those elements which belong to either A or B or to both of them. Denoted by A \( \cup \) B.
If A ⊆ B, then A \( \cup \) B = B.
A \( \cup \) \( \phi \) = A
A \( \cup \) \( \mu \) = \( \mu \)
Intersection of Sets – Finding common elements between two or more sets. For two sets A and B , the intersection of A and B is the set of all those elements that belong to both A and B. Denoted by A \( \cap \) B.
If A ⊆ B, then A \( \cap \) B = A.
A \( \cup \) \( \phi \) = \( \phi \).
A \( \cup \) \( \mu \) = A
Disjoint Sets – Two sets A and B are said to be disjoint if they have no element in common. Thus, A \( \cap \) B = \( \phi \).
Difference of Sets – Subtracting elements of one set from another. For two sets A and B, the difference is the set of all those elements of A which do not belong to B. Denoted by A – B. For Example A = {1, 2, 3} B = {3, 4, 5} then, A – B = {1, 2}.
Complement of a Set – The complement of set A is the set of all those elements that do not belong to set A. Denoted by A’ or Ac. For Example, U = {x | x ∈ to Natural Numbers} and A = {x | x is an even natural number} then complement of A or A’ = {x | x is an odd natural number}.
Symmetric Difference of two Sets – Let A and B be two sets. The symmetric difference of set A and B is the set (A – B) \( \cup \) (B – A) and is denoted by A \( \delta \) B. For Example A = {1, 2, 3, 4} B = {3, 4, 5, 6} then A \( \delta \) B = {1, 2, 5, 6}.
Cartesian Product of Two Sets – Let A and B be two sets. Then the Cartesian Product of A and B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. The product is denoted by (A x B). Thus (A x B) = {(a, b) | a ∈ A, b ∈ B}.
If A and B are two sets such that O(A)=m and O(B)=n, then the number of ordered pairs in A \( \times \) B is “mn”.
A \( \times \) B \( \neq \) B \( \times \) A
n (A \( \times \) B) = n (B \( \times \) A)
Relation
A relation between two sets A and B is a collection of ordered pairs, where the first element belongs to set A, and the second element belongs to set B. Any subset of A \( \times \) B is a relation from A to B.
If (a, b) is an ordered pair in the relation R, it indicates that element ‘a’ is related to element ‘b’ under relation R.
For Example A = {1, 2, 3} B = {a, b} then R = {(1, a), (3, b)} is a possible relation.
Domain of a Relation – The set of all first elements of the ordered pairs in a relation is called the Domain. Denoted by Dom R.
Range of a Relation – The set of all second elements of the ordered pairs in a relation is called the Range. Denoted by Range R.
Inverse of a Relation – Let A and B be two sets and let R be a relation from A to B. Then the inverse of R denoted by R-1 is a relation from B to A and is defined by – $$R^-1 = \{ (b, a) | (a, b) ∈ R \} $$
