# 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 “2
^{n}“.

**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 “2
^{n}“.

**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 A^{c}. 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 \} $$