UNIT–1 (SETS & RELATIONS)

(Set Operations, Representation of Relations, Properties of Relations, Equivalence & Partial Order Relations)

PART A — SETS

1. What is a Set? (Definition)

A set is a well-defined collection of objects (called elements) such that it is possible to clearly decide whether an element belongs to the set or not.

Key idea:
✔ “Well-defined” means no ambiguity.
✔ Sets are written using curly braces.

Examples:

A = {1,2,3,4}
B = {a, e, i, o, u}
C = {x | x is an even natural number}

Non-example:

“All beautiful flowers” → not well-defined (beauty is subjective)

2. Important Types of Sets

2.1 Empty set (Null set)

A set with no elements.
Symbol: Ø or { }
Example: Set of even prime numbers > 2.

2.2 Finite and Infinite sets

Finite: elements can be counted
Infinite: unending, e.g., natural numbers ℕ

2.3 Equal sets

Two sets A and B are equal if every element of A is in B and vice-versa.

2.4 Subset

A ⊆ B means every element of A is also in B.

Example:
A = {1,2}
B = {1,2,3,4}
→ A ⊆ B

Proper subset:
A ⊂ B if A ⊆ B and A ≠ B.

2.5 Power Set

P(A) = set of all subsets of A.
If |A| = n → |P(A)| = 2ⁿ.

Example:
A = {1,2}
P(A) = { Ø, {1}, {2}, {1,2} }

3. SET OPERATIONS

Operations on sets are exactly parallel to logical operations.

Let A and B be sets in a universal set U.

3.1 Union (A ∪ B)

Statement: Set of all elements that belong to A, or to B, or to both.

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

3.2 Intersection (A ∩ B)

Statement: Elements common to both A and B.

A={1,2}, B={2,3}
A∩B = {2}

3.3 Difference (A – B)

Statement: Elements belonging to A but not in B.

A − B = {elements in A that are not in B}

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

3.4 Symmetric Difference (A Δ B)

Statement: Elements that are in A or in B but NOT in both.
AΔB = (A−B) ∪ (B−A)

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

3.5 Complement (A′)

Everything in the universal set U that is NOT in A.

A′ = U − A

4. IMPORTANT SET IDENTITIES

These laws are vital for proofs and simplifications.

Identity Laws

A ∪ Ø = A
→ “Adding nothing changes the set.”
A ∩ U = A
→ “Intersecting with everything gives the set.”

Domination Laws

A ∪ U = U
A ∩ Ø = Ø

Statement:
“Union with universal set gives universal set; intersection with empty set gives empty set.”

Idempotent Laws

A ∪ A = 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)

Absorption Laws

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

De Morgan’s Laws

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

These correspond to logical laws for (∨, ∧, ¬).

PART B — RELATIONS

Relations form the mathematical structure for describing connections between objects.
They generalize functions, orders, equivalence, graph relations, database relations, etc.

5. RELATION — DEFINITION

A relation R from set A to set B is a subset of the Cartesian product A × B.

That is:
R ⊆ A × B

Where A × B = {(a,b) | a ∈ A, b ∈ B}

5.1 Binary Relation on a Set

A relation R on A is a subset of A × A.

Example:
A={1,2,3}
R = {(1,1),(2,2),(1,3)} is a relation on A.

6. REPRESENTATION OF RELATIONS

A relation can be represented in three ways:

6.1 (a) Set of Ordered Pairs

Direct listing of (a,b).

Example:
R = {(1,2),(2,3),(3,1)}

6.1 (b) Matrix Representation

If A = {a₁,a₂,…,aₙ}, R is represented by an n×n matrix M:

$m_{i j} = {\begin{cases} 1 & if (a_{i}, a_{j}) \in R \\ 0 & otherwise \end{cases}$

Used heavily in computing and adjacency matrices.

6.1 (c) Directed Graph (Digraph)

Each element of A is a node.
Each pair (a,b) ∈ R is a directed edge from a→b.

Graphical representation helps visualize transitivity, symmetry, closure, etc.

7. PROPERTIES OF RELATIONS

These properties define the nature of the relationship.

Let R be a relation on set A.

7.1 Reflexive Relation

Definition (Statement):

A relation R on A is reflexive if every element relates to itself.

$(a, a) \in R for every a \in A$

Example:
A = {1,2,3}
R = {(1,1),(2,2),(3,3),(1,2)} → reflexive

Non-example:
Missing even one (a,a) → not reflexive.

7.2 Symmetric Relation

Definition (Statement):

A relation R is symmetric if:

If (a,b) ∈ R then (b,a) ∈ R.

Example (symmetric):
R = {(1,2),(2,1),(2,3),(3,2)}

Non-example:
If (1,2) ∈ R but (2,1) ∉ R → not symmetric.

7.3 Antisymmetric Relation

Definition (Statement):

A relation R is antisymmetric if:

If (a,b) ∈ R and (b,a) ∈ R, then a = b.

Example (antisymmetric):
Set A = {1,2,3}
Relation: “≤”
Because if a ≤ b and b ≤ a → a = b.

Non-example:
(1,2) and (2,1) in R with 1≠2 → violates antisymmetry.

7.4 Transitive Relation

Definition (Statement):

A relation R is transitive if:

If (a,b) and (b,c) ∈ R → (a,c) must also be in R.

Example:
If a divides b and b divides c → a divides c.

Non-example:
If (a,b),(b,c) ∈ R but (a,c) ∉ R.

8. COMBINED RELATIONS — IMPORTANT TYPES

8.1 Equivalence Relation (VERY IMPORTANT)

Definition (Statement):

A relation R on A is an equivalence relation if it is:

Reflexive
Symmetric
Transitive

Meaning:
An equivalence relation groups elements into “categories” or “classes” of items that are considered equivalent.

Equivalence Class

For element a ∈ A, the equivalence class is:

$[a] = {x \in A ∣ (a, x) \in R}$

Meaning:
“All elements related to a.”

Example: Congruence modulo n

Define relation:
a ≡ b (mod n)
Meaning: “a and b leave same remainder when divided by n.”

Properties:
✔ reflexive: a≡a
✔ symmetric: if a≡b then b≡a
✔ transitive: if a≡b and b≡c then a≡c

→ So it’s an equivalence relation.

Each equivalence class contains all numbers with same remainder.

8.2 Partition of a Set

Equivalence relations partition a set into disjoint subsets (equivalence classes).

Properties of partition:

Classes are nonempty
Classes are disjoint
Union of all classes = A

Equivalence relations ↔ partitions.

These two concepts are dual to each other.

9. PARTIAL ORDER RELATIONS (POSets)

These describe ordered or hierarchical structure.

9.1 Partial Order Relation

Definition (Statement):

A relation R on A is a partial order if it is:

Reflexive
Antisymmetric
Transitive

Symbol: (A, ≤) is a poset (partially ordered set).

Example:

“Divides” relation on {1,2,4,8}
“Subset (⊆)” relation on P(S)

9.2 Total (Linear) Order

A partial order is total if every pair of elements is comparable.

That is, for any a and b:
Either a ≤ b or b ≤ a.

Example (total order):

Natural numbers with ≤
Alphabet with alphabetical order

Non-example:
Subset relation is not total.

9.3 Hasse Diagrams (Poset Representation)

Used to represent partial orders graphically:

Rules:

Draw elements as nodes
Draw edge upward if a < b and there is no c such that a < c < b
Omit loops and transitive edges

10. Reflexive–Symmetric–Transitive Closures (Advanced but important)

Sometimes a relation R does not have a property, and we want the smallest relation that includes R and satisfies the property.

Reflexive closure:

Add (a,a) for all a ∈ A missing from R.

Symmetric closure:

Add (b,a) if (a,b) is in R but (b,a) missing.

Transitive closure:

Add (a,c) whenever (a,b) and (b,c) exist.

Used in database theory (Warshall’s algorithm), graph theory, and automata.

UGC NET Computer Science Unit 1 – Sets & Relations

UNIT–1 (SETS & RELATIONS)

PART A — SETS

1. What is a Set? (Definition)

2. Important Types of Sets

2.1 Empty set (Null set)

2.2 Finite and Infinite sets

2.3 Equal sets

2.4 Subset

2.5 Power Set

3. SET OPERATIONS

3.1 Union (A ∪ B)

3.2 Intersection (A ∩ B)

3.3 Difference (A – B)

3.4 Symmetric Difference (A Δ B)

3.5 Complement (A′)

4. IMPORTANT SET IDENTITIES

Identity Laws

Domination Laws

Idempotent Laws

Commutative Laws

Associative Laws

Distributive Laws

Absorption Laws

De Morgan’s Laws

PART B — RELATIONS

5. RELATION — DEFINITION

5.1 Binary Relation on a Set

6. REPRESENTATION OF RELATIONS

6.1 (a) Set of Ordered Pairs

6.1 (b) Matrix Representation

6.1 (c) Directed Graph (Digraph)

7. PROPERTIES OF RELATIONS

7.1 Reflexive Relation

Definition (Statement):

7.2 Symmetric Relation

Definition (Statement):

7.3 Antisymmetric Relation

Definition (Statement):

7.4 Transitive Relation

Definition (Statement):

8. COMBINED RELATIONS — IMPORTANT TYPES

8.1 Equivalence Relation (VERY IMPORTANT)

Definition (Statement):

Equivalence Class

Example: Congruence modulo n

8.2 Partition of a Set

9. PARTIAL ORDER RELATIONS (POSets)

9.1 Partial Order Relation

Definition (Statement):

9.2 Total (Linear) Order

9.3 Hasse Diagrams (Poset Representation)

10. Reflexive–Symmetric–Transitive Closures (Advanced but important)

Reflexive closure:

Symmetric closure:

Transitive closure:

👋Subscribe to ProTeacher.in

Sign up to receive NewsLetters in your inbox.

👋Subscribe to
ProTeacher.in