Set Theory

Set Theory is a fundamental branch of mathematics that deals with the study of collections of objects. These collections are called sets. Set theory forms the foundation of many areas in computer science such as data structures, databases, discrete mathematics, logic, automata theory, and programming languages.

Definition of a Set

A set is a well-defined collection of distinct objects, called elements or members.

Example:

A = {1, 2, 3, 4}
B = {a, e, i, o, u}

Representation of Sets

Roster (Tabular) Form: Elements are listed explicitly.
- A = {2, 4, 6, 8}
Set-Builder Form: Describes elements using a property.
- A = {x | x is an even natural number less than 10}

Types of Sets

Empty (Null) Set (Ø): A set with no elements.
Finite Set: Limited number of elements.
Infinite Set: Unlimited number of elements.
Singleton Set: Contains only one element.
Universal Set (U): Contains all objects under consideration.
Subset (⊆): A ⊆ B if every element of A is also in B.
Proper Subset (⊂): A ⊂ B and A ≠ B.

Size of Sets and Cardinals

Cardinality of a Set

The cardinality of a set refers to the number of elements present in the set. It is denoted by |A|.

Examples:

A = {1, 3, 5, 7} → |A| = 4
Ø → |Ø| = 0

Cardinal Numbers

Cardinal numbers represent the size of a set.

Types of Cardinalities

Finite Cardinality – Countable elements
Infinite Cardinality – Uncountable or countable infinite sets

Set of natural numbers (N) is countably infinite
Set of real numbers (R) is uncountable

Equality of Sets Based on Cardinality

Two sets A and B are said to be equal in cardinality if there exists a one-to-one correspondence (bijection) between them.

Venn Diagrams

A Venn diagram is a pictorial representation of sets using closed curves, usually circles, inside a universal set.

Uses of Venn Diagrams

To show relationships between sets
To solve problems involving union, intersection, and complement

Common Operations Shown Using Venn Diagrams

Union (A ∪ B): All elements in A or B or both
Intersection (A ∩ B): Common elements in A and B
Difference (A − B): Elements in A but not in B
Complement (A′): Elements not in A but in U

Exam Tip: Venn diagrams are frequently used in problem-solving questions.

Combination of Sets

Union of Sets (A ∪ B)

The union of two sets contains all elements that are in A or B or both.

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

Intersection of Sets (A ∩ B)

The intersection contains only the common elements.

A ∩ B = {3}

Difference of Sets (A − B)

Contains elements present in A but not in B.

A − B = {1, 2}

Complement of a Set (A′)

Contains elements not in A but present in the universal set.

Laws Related to Combination of Sets

Commutative Law
Associative Law
Distributive Law

Multisets

A multiset is a collection in which repetition of elements is allowed.

Difference Between Set and Multiset

Feature	Set	Multiset
Repetition	Not allowed	Allowed
Example	{1,2,3}	{1,1,2,3}

Applications of Multisets

Database systems
Counting problems
Bag data structures

Cardinality of Multiset

The cardinality of a multiset is the total count of all elements including repetitions.

Ordered Pairs

An ordered pair is a pair of elements written in a specific order.

Representation

Ordered pair is written as (a, b), where:

a is the first element
b is the second element

Equality of Ordered Pairs

(a, b) = (c, d) if and only if:

a = c
b = d

Cartesian Product

The Cartesian product of two sets A and B is denoted by A × B.

Definition: A × B = {(a, b) | a ∈ A and b ∈ B}

Example: A = {1,2}, B = {x,y} A × B = {(1,x), (1,y), (2,x), (2,y)}

Cardinality of Cartesian Product

|A × B| = |A| × |B|

Set Identities

Set identities are laws that are always true for all sets.

Important Set Identities

Identity Laws

A ∪ Ø = A
A ∩ U = A

Domination Laws

A ∪ U = U
A ∩ Ø = Ø

Idempotent Laws

A ∪ A = A
A ∩ A = A

Complement Laws

A ∪ A′ = U
A ∩ A′ = Ø
(A′)′ = A

Commutative Laws

A ∪ B = B ∪ A
A ∩ B = B ∩ A

Associative Laws

(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive Laws

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

De Morgan’s Laws (Very Important for Exams)

(A ∪ B)′ = A′ ∩ B′
(A ∩ B)′ = A′ ∪ B′

Exam-Oriented Important Points

Learn definitions clearly for theory questions
Practice Venn diagram-based numerical problems
Memorize set identities and De Morgan’s laws
Cartesian product questions are frequently asked
Difference between set and multiset is important for short notes

Conclusion

Set theory provides the mathematical language required to understand and design computer-based systems. For MCA students, a strong grasp of these concepts is essential for higher-level subjects like algorithms, database theory, and artificial intelligence.

Relations

In set theory, a relation describes a relationship between elements of two sets.

Let A and B be two non-empty sets. A relation R from A to B is a subset of the Cartesian product A × B.

R ⊆ A × B

If (a, b) ∈ R, then we say a is related to b.

Example

Let A = {1, 2, 3} and B = {a, b}

A × B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

If R = {(1,a), (2,b)}, then R is a relation from A to B.

Types of Relations (Based on Sets)

Empty relation: R = Ø
Universal relation: R = A × B
Identity relation: R = {(a, a) | a ∈ A}

Operations on Relations

Operations on relations are similar to set operations because relations are subsets of Cartesian products.

Let R and S be two relations from A to B.

(a) Union of Relations

R ∪ S = {(a, b) | (a, b) ∈ R or (a, b) ∈ S}

(b) Intersection of Relations

R ∩ S = {(a, b) | (a, b) ∈ R and (a, b) ∈ S}

(c) Difference of Relations

R − S = {(a, b) | (a, b) ∈ R and (a, b) ∉ S}

(d) Complement of a Relation

R′ = (A × B) − R

Composite Relations

Definition of Composition of Relations

Let R ⊆ A × B and S ⊆ B × C be two relations.

The composition of R and S, denoted by S ∘ R, is defined as:

S ∘ R = {(a, c) | ∃ b ∈ B such that (a, b) ∈ R and (b, c) ∈ S}

Explanation

An element a in A is related to c in C if there exists an intermediate element b such that:

a is related to b by R
b is related to c by S

Example

Let: R = {(1,2), (2,3)} S = {(2,4), (3,5)}

Then: S ∘ R = {(1,4), (2,5)}

Important Points (Exam-Oriented)

Composition is not commutative
S ∘ R ≠ R ∘ S in general

Properties of Relations

Let R be a relation on a set A.

(a) Reflexive Relation

R is reflexive if: (a, a) ∈ R for all a ∈ A

Example: ≤ on natural numbers

(b) Irreflexive Relation

R is irreflexive if: (a, a) ∉ R for all a ∈ A

(c) Symmetric Relation

R is symmetric if: (a, b) ∈ R ⇒ (b, a) ∈ R

(d) Asymmetric Relation

R is asymmetric if: (a, b) ∈ R ⇒ (b, a) ∉ R

(e) Antisymmetric Relation

R is antisymmetric if: (a, b) ∈ R and (b, a) ∈ R ⇒ a = b

(f) Transitive Relation

R is transitive if: (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R

Equality of Relations

Two relations R and S are said to be equal if they contain exactly the same ordered pairs.

R = S if and only if:

R ⊆ S and
S ⊆ R

Example

R = {(1,2), (2,3)} S = {(2,3), (1,2)}

Then R = S

Exam Note

Order of elements does not matter in relations, but ordered pairs must match exactly.

Partial Order Relation

A relation R on a set A is called a partial order relation if it satisfies:

Reflexive
Antisymmetric
Transitive

Such a relation is denoted as (A, R) and is called a Partially Ordered Set (Poset).

Example of Partial Order Relations

≤ (less than or equal to)
⊆ (subset relation)
Divisibility relation on integers

Example

Let A = {1, 2, 3, 6} Define R as: aRb if a divides b

R is reflexive, antisymmetric, and transitive → hence a partial order relation

Hasse Diagram (Conceptual)

A Hasse diagram is a graphical representation of a poset where:

Reflexive edges are removed
Transitive edges are removed
Only cover relations are shown

Difference Between Equivalence Relation and Partial Order

Basis	Equivalence Relation	Partial Order Relation
Reflexive	Yes	Yes
Symmetric	Yes	No
Antisymmetric	No	Yes
Transitive	Yes	Yes

Exam-Oriented Important Points

Definition of relation is frequently asked (2–3 marks)
Properties of relations are important for short notes
Composition of relations often appears as numerical problems
Partial order relation is a long-answer topic
Difference questions are commonly asked

Conclusion

Relations are an essential concept in discrete mathematics and computer science. Understanding relations helps MCA students in database theory, graph theory, automata, and algorithm design

Functions

In mathematics and computer science, a function represents a special type of relation that associates each element of one set with exactly one element of another set.

Let A and B be two non-empty sets. A function f from A to B is a relation such that for every element a ∈ A, there exists one and only one element b ∈ B for which:

f(a) = b

It is written as: f : A → B

Where:

A is called the domain
B is called the codomain
Set of all actual outputs is called the range

Example

Let A = {1, 2, 3} and B = {a, b, c}

f = {(1,a), (2,b), (3,b)} → This is a valid function

Classification of Functions

Functions can be classified on different bases. This topic is very important from an exam point of view.

(a) One-to-One Function (Injective Function)

A function f : A → B is said to be one-to-one if:

f(a₁) = f(a₂) ⇒ a₁ = a₂

Different elements of A have different images in B.

Example: f(x) = 2x

(b) Many-to-One Function

A function f : A → B is many-to-one if:

Two or more elements of A are mapped to the same element of B.

Example: f(x) = x²

f(2) = f(-2) = 4

(c) Onto Function (Surjective Function)

A function f : A → B is onto if:

For every element b ∈ B, there exists at least one a ∈ A such that:

f(a) = b

Range = Codomain

(d) Into Function

A function f : A → B is into if:

At least one element of B has no pre-image in A.

Range ⊂ Codomain

(e) One-to-One and Onto Function (Bijective Function)

A function is bijective if it is both:

One-to-one
Onto

Bijective functions have inverse functions.

(f) Constant Function

A function f : A → B is constant if:

f(a) = c for all a ∈ A, where c ∈ B

(g) Identity Function

The identity function maps every element to itself.

f(a) = a for all a ∈ A

Operations on Functions

Let f : A → B and g : B → C be two functions.

(a) Addition of Functions

(f + g)(x) = f(x) + g(x)

(b) Subtraction of Functions

(f − g)(x) = f(x) − g(x)

(c) Multiplication of Functions

(f · g)(x) = f(x) × g(x)

(d) Division of Functions

(f / g)(x) = f(x) / g(x), where g(x) ≠ 0

(e) Composition of Functions

The composition of functions f and g is denoted by g ∘ f.

(g ∘ f)(x) = g(f(x))

Important Notes:

Composition is not commutative
g ∘ f ≠ f ∘ g in general

(f) Inverse of a Function

A function f has an inverse f⁻¹ if and only if f is bijective.

f⁻¹(f(a)) = a

Recursively Defined Functions

A recursively defined function is a function that is defined:

By one or more initial (base) values
By a recurrence relation that defines the function in terms of its previous values

This concept is very important in computer programming and algorithms.

General Form

f(n) is defined as:

Base case: f(0) = c
Recursive case: f(n) = expression involving f(n−1)

Example 1: Factorial Function

f(n) = n!

Defined recursively as:

f(0) = 1
f(n) = n × f(n−1), for n ≥ 1

Example 2: Fibonacci Sequence

F(0) = 0 F(1) = 1 F(n) = F(n−1) + F(n−2), for n ≥ 2

Characteristics of Recursive Functions

Must have a base condition
Must progress towards the base condition
Without a base case, recursion leads to infinite loop

Difference Between Relation and Function

Basis	Relation	Function
Mapping	May or may not be unique	Exactly one output
Domain	Optional mapping	Mandatory mapping
Example	(a, b), (a, c) allowed	Only one of them allowed

Exam-Oriented Important Points

Definition of function is frequently asked
Classification of functions is a high-weight topic
Composition and inverse questions appear in numericals
Recursive functions are important for theory + examples
Bijective functions always have inverse

Conclusion

Functions are the backbone of mathematics and computer science. For MCA students, understanding functions is essential for programming, data structures, algorithms, and database systems.