Sets and Relations are fundamental topics in Mathematics, particularly in subjects like Discrete Mathematics, Algebra, and Logic. These concepts form the basis of database theory, graph theory, and real-world applications in computing and data science. This article will provide a detailed, exam-oriented explanation of Sets and Relations, covering definitions, properties, types, and solved examples.

1. Sets

Definition of a Set

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

1. A set is usually denoted by a capital letter (e.g., A,B,C).
2. Elements of a set are enclosed within curly brackets {}.
3. Example: A={1,2,3,4,5} is a set containing five elements.

Types of Sets

1. Empty Set (Null Set) ∅:
2. A set with no elements.
3. Example: A={x∣x2+1=0,x∈R} (No real number satisfies this equation).
4. Finite and Infinite Sets:
5. A finite set has a limited number of elements. Example: A={1,2,3}.
6. An infinite set has unlimited elements. Example: B={1,2,3,4,… }.
7. Equal and Equivalent Sets:
8. Two sets are equal if they have the same elements. Example: A={1,2,3},B={3,2,1}⇒A=B.
9. Two sets are equivalent if they have the same number of elements but different values.
10. Subset and Superset:
11. If every element of set A is in set B, then A is a subset of B, denoted as A⊆B.
12. If B contains all elements of A and more, then B is a superset of A, denoted as B⊇A.
13. Power Set:
14. The set of all subsets of a set A.
15. If A={1,2}, then P(A)={∅,{1},{2},{1,2}}.
16. Universal Set:
17. The set containing all elements under consideration, usually denoted by U.
18. Example: If discussing natural numbers, U=N.

1.1 Set Operations

A set is a collection of distinct elements, and various operations can be performed on sets to analyze relationships between them.

Basic Set Operations

1. Union (A ∪ B)
2. The union of two sets A and B consists of all elements that are either in A, in B, or in both.
3. Example: If A={1,2,3} and B={3,4,5}, then: A∪B={1,2,3,4,5}.
4. Intersection (A ∩ B)
5. The intersection of two sets consists of only those elements that are present in both A and B.
6. Example: A ∩ B={3}
7. Difference (A−B)
8. The difference of two sets A and B consists of elements that are in A but not in B.
9. Example: A−B={1,2}
10. Complement (A^c)
11. The complement of a set A consists of all elements in the universal set U that are not in A.
12. Cartesian Product (A×B)
13. The Cartesian product of two sets is the set of all possible ordered pairs formed by taking an element from A and one from B.
14. Example: A×B={(1,a),(1,b),(2,a),(2,b)}.

3. Relations

Definition of a Relation

A relation is a subset of a Cartesian product. It describes a connection between elements of two sets.

1. If A and B are two sets, then a relation R from A to B is a subset of A×B.
2. Example: If A={1,2,3} and B={a,b}, a possible relation R could be: R={(1,a),(2,b)}.

Types of Relations

1. Reflexive Relation: Every element is related to itself.
2. Example: (a,a)∈R for all a∈A.
3. Symmetric Relation: If (a,b)∈R, then (b,a)∈R.
4. Example: If (1,2)∈R, then (2,1)∈R.
5. Transitive Relation: If (a,b)∈R and (b,c)∈R, then (a,c)∈R.
6. Example: If (1,2)∈R and (2,3)∈R, then (1,3)∈R.
7. Equivalence Relation: A relation that is Reflexive, Symmetric, and Transitive.

Functions as Relations

A function is a special type of relation where each element in set AAA (domain) is related to exactly one element in set BBB (codomain).

Definition

A relation f from A to B is a function if:

1. Every element in A is associated with only one element in B.
2. No element in A is mapped to multiple elements in B.

Example of a Function

1. Let A={1,2,3} and B={4,5,6} and define:
2. f={(1,4),(2,5),(3,6)} Here, every element in A has exactly one unique image in B. Hence, f is a function.

Example of a Relation That is NOT a Function

1. Let R={(1,4),(1,5),(2,5)}.
2. Here, 1 is mapped to both 4 and 5, which violates the function rule. Hence, R is a relation but not a function.

Types of Functions

Functions can be classified based on how elements in the domain and codomain are mapped.

1. One-to-One Function (Injective Function)

A function is one-to-one (injective) if no two elements in the domain map to the same element in the codomain.

1. Example: f(x)=x+1, where f:{1,2,3}→{2,3,4}
2. Mapping: 1→2,2→3,3→4
3. Unique mapping → Injective

2. Onto Function (Surjective Function)

A function is onto (surjective) if every element in the codomain has at least one pre-image in the domain.

1. Example: f(x)=x², where f:{−2,−1,0,1,2}→{0,1,4}
2. Here, every element in the codomain {0,1,4} is mapped to by at least one element in the domain.
3. Complete coverage → Surjective

3. One-to-One and Onto Function (Bijective Function)

A function is both injective and surjective if:

1. No two elements in the domain map to the same codomain element (one-to-one).
2. Every element in the codomain is mapped to (onto).
3. Example: f(x)=x+1for f:{1,2,3}→{2,3,4}.
4. Unique and complete coverage → Bijective

4. Constant Function

A function where every element in the domain maps to the same codomain value.

1. Example: f(x)=5 for all x in the domain.

5. Identity Function

A function where each element maps to itself.

1. Example: f(x)=x for all x in the domain.

Representation and Properties of Relations

A relation is a way of describing a connection between elements of two sets.

Representation of Relations

A relation R from set A to set B is a subset of the Cartesian product A×B. Relations can be represented in different ways:

1. Set Notation: Listing ordered pairs.
2. Example: R={(1,2),(2,3),(3,4)}.
3. Matrix Representation: A binary matrix where rows represent elements of A and columns represent elements of B.
4. Graph Representation: Using directed graphs (digraphs) where vertices represent elements, and edges represent relations.

Properties of Relations

A relation RRR can have the following properties:

1. Reflexive Relation: If (a,a)∈R for all a∈A, the relation is reflexive.
2. Example: R={(1,1),(2,2),(3,3)} is reflexive.
3. Symmetric Relation: If (a,b)∈R⇒(b,a)∈R, the relation is symmetric.
4. Example: If (1,2)∈R, then (2,1) must also be in R.
5. Transitive Relation: If (a,b)∈R and (b,c)∈R, then (a,c)∈R.
6. Example: If (1,2)∈R and (2,3)∈R, then (1,3) should also be in R.

Equivalence Relations

An equivalence relation is a relation that satisfies three properties:

1. Reflexive: (a,a)∈R for all a∈A.
2. Symmetric: If (a,b)∈R, then (b,a)∈R.
3. Transitive: If (a,b)∈R and (b,c)∈R, then (a,c)∈R.

Example of an Equivalence Relation

Consider the relation "is congruent modulo 3" on integers. That is, aRb if (a−b) is divisible by 3.

1. Reflexive: a−a = 0 is divisible by 3.
2. Symmetric: If a−b is divisible by 3, then b−a is also divisible by 3.
3. Transitive: If a−b and b−c are divisible by 3, then a−c is also divisible by 3.

Since all three conditions hold, this is an equivalence relation.

Equivalence Class

An equivalence class is a subset where all elements are related to each other.

Example: If we consider equivalence modulo 3:

1. The equivalence class of 0: [0]={...,−3,0,3,6,...}.
2. The equivalence class of 1: [1]={...,−2,1,4,7,...}.

4. Partially Ordered Sets (Posets)

A partially ordered set (poset) is a set equipped with a partial order relation.

Definition of Partial Order

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

1. Reflexive: aRa for all a∈A.
2. Antisymmetric: If aRb and bRa, then a=b.
3. Transitive: If aRb and bRc, then aRc.

Example of a Partially Ordered Set

Consider the set A={1,2,3,4} with the relation divisibility (a|b):

1. 1|2,1|3,1|4
2. 2|4, but 2∤3 and 3∤2.

This satisfies partial order properties but not total ordering (as not all elements are comparable).

Hasse Diagram

A Hasse diagram is a simplified directed graph that represents a partially ordered set. It removes self-loops (reflexivity) and transitive edges while preserving the order structure.

Key Features of a Hasse Diagram

1. Elements of the poset are represented as nodes (vertices).
2. A line (edge) is drawn from a to b if a ≤ b and there is no intermediate element c such that a ≤ c ≤ b.
3. No arrows are used, as it is assumed that edges go upward in the diagram.