Sets, Functions & Relations
Open in the Padhaiko app1.0 Introduction to Theory of Computation
The theory of computation is the branch of computer science and mathematics that investigates what problems can be solved on a formal model of computation using an algorithm, how efficiently they can be solved, and to what degree. Its central goal is to develop formal mathematical models of computation that reflect real-world computers.
The field is divided into three major pillars:
- Complexity Theory: Classifies computational problems as easy or hard according to the computational resources (time and memory) required to solve them. For example, sorting a million numbers is an easy problem that even a modest computer performs rapidly, whereas university-wide class scheduling—assigning a thousand courses to classrooms and time slots with no conflicts—is a computationally hard problem where finding the optimal schedule by brute force could take a supercomputer centuries.
- Computability Theory: Investigates which problems are algorithmically solvable (decidable) and which are fundamentally unsolvable (undecidable). For instance, no computer algorithm can decide in general whether an arbitrary mathematical statement is true or false, or whether an arbitrary program will eventually halt.
- Automata Theory: Studies the definitions and mathematical properties of abstract models of computation:
- Finite Automata: Used in text processing, lexical analyzers of compilers, network protocol verification, and hardware circuit design.
- Context-Free Grammars & Pushdown Automata: Used in programming language syntax, parsers, and artificial intelligence.
- Turing Machines: The universal mathematical model of general-purpose computation.
| Aspect | Complexity Theory | Computability Theory |
|---|---|---|
| Core Question | What makes some problems computationally hard and others easy? | Which problems can be solved by a computer algorithm and which cannot? |
| Classification | Easy (tractable, e.g. class ) vs. Hard (intractable, e.g. -hard) | Solvable (decidable / recursive) vs. Unsolvable (undecidable) |
| Representative Examples | Sorting numbers (easy) vs. Optimal university timetable scheduling (hard) | Halting problem, deciding truth of arbitrary mathematical statements |
1.1 Brief Review of Set Theory
Set and Elements
A set is a collection of well-defined objects. Sets may contain any kind of object—numbers, symbols, strings, or even other sets. The objects belonging to a set are called its elements or members.
Usually, sets are denoted by uppercase English letters () and their elements by lowercase letters (). If is a member of , we write ; otherwise, .
For a collection to qualify as a set, its membership criterion must be well-defined—objective and unambiguous rather than subjective:
| Not a Set (Subjective / Ambiguous) | Valid Set (Well-Defined Property) |
|---|---|
| i. Collection of tall students in our school. | i. Collection of students in our school whose height is more than . |
| ii. Collection of honest persons in our colony. | ii. Collection of people in our colony never found involved in any theft case. |
| iii. Collection of interesting books in the school library. | iii. Collection of mathematics books in the school library. |
| iv. Collection of intelligent students in our school. | iv. Collection of students in our school who secured more than marks in the annual examination. |
Representation of Sets
There are two standard methods to represent a set:
- Roster Method (Tabular Form): All elements of the set are listed explicitly, separated by commas, and enclosed within curly braces .
- Example: The set of natural numbers less than is written in roster form as:
- Set-Builder Form (Rule Method): Elements are not listed individually; instead, they are specified by a common characterizing property .
- Example: The same set of natural numbers less than is written in set-builder form as:
1.1.2 Types of Sets
Fundamental Types of Sets
- Singleton Set: A set containing exactly one element. For example, is a singleton set.
- Equal Sets (): Two sets and are equal if and only if they contain the exact same elements (order and repetition do not matter). For example, and satisfy .
- Equivalent Sets ( or ): Two finite sets and are equivalent if they have the same cardinality (the same number of distinct elements), i.e., . For example, and satisfy since . Every pair of equal sets is equivalent, but equivalent sets need not be equal.
- Disjoint Sets: Two sets and are disjoint if they have no element in common (). For example, and are disjoint.
- Finite and Infinite Sets: A set is finite if its elements can be counted up to a last element (e.g., the set of students of batch 2073 in Institute of Engineering), and infinite otherwise (e.g., the set of all natural numbers ).
- Universal Set (): The overarching set containing all elements under consideration in a given context.
- Subset (): Set is a subset of set if every element of is also an element of . For example, . Every set is a subset of itself (), and the empty set is a subset of every set ().
- Empty (Void or Null) Set ( or ): A set containing no elements at all. For example, the set of male students enrolled in a women-only college.
- Power Set ( or ): The set of all possible subsets of a set . If , then . For ,
Countably Infinite and Uncountable Sets
Infinite sets are classified into two categories based on whether their elements can be placed in one-to-one correspondence (bijection) with the set of natural numbers :
- Countably Infinite (Denumerable) Set: An infinite set is countably infinite (or denumerable) if there exists a one-to-one correspondence (bijection) between the natural numbers and . Examples include the set of even integers, the set of odd integers, the set of all integers , and the set of rational numbers .
- A set that is either finite or countably infinite (denumerable) is called a countable set.
- Bijection between and : To show that the set of integers is countably infinite, we list its elements in alternating sign order and pair them with :
Formally, for even and for odd is a bijection from onto .
- Uncountably Infinite (Non-Denumerable / Uncountable) Set: An infinite set is uncountably infinite (or simply uncountable) if there is no one-to-one correspondence between its elements and the natural numbers . Examples include the set of all real numbers , the interval , and the power set (the set of all languages over a non-empty alphabet ).
1.1.3 Operations on Sets
Fundamental Set Operations
Let and be subsets of a universal set :
- Set Difference ( or ): The set of elements that belong to but not to :
For example, if and , then .
- Complement ( or ): The set of all elements in the universal set that do not belong to :
For example, if and , then (and if with , then ).
- Intersection (): The set of elements common to both and :
For example, if and , then . If , then and are disjoint.
- Union (): The set of elements that belong to , or to , or to both:
For example, if and , then .
- Ordered Pair and Cartesian Product ():
- An ordered pair consists of two objects in a fixed order, where unless .
- The Cartesian product of two non-empty sets and is the set of all ordered pairs with and :
For example, if and , then
In general, , and .
1.1.4 Properties of Set Operations
Algebraic Laws of Set Operations
For any sets , , and :
- Idempotence Laws:
- Commutative Laws:
- Associative Laws:
- Distributive Laws:
- De Morgan's Laws:
(When , these take the complement form and .)
- Absorption Laws:
1.2 Relations and Functions
1.2.1 Relations
Binary Relation, Domain, and Range
A binary relation from a set to a set is a subset of the Cartesian product :
If , we say that is related to by (often written ).
- The domain of is the set of all first components of the ordered pairs in :
- The range of is the set of all second components of the ordered pairs in :
When , is called a relation on the set .
For example, let and , and consider the relation
Then:
Properties and Types of Relations on a Set A
Let be a binary relation on a set :
- Reflexive Relation: is reflexive if for every .
- Example: On , is reflexive because .
- Symmetric Relation: is symmetric if whenever , we also have , for all .
- Example: On , is symmetric because are paired with respectively.
- Antisymmetric Relation: is antisymmetric if whenever and , we must have , for all . Equivalently, for distinct elements , and cannot both belong to .
- Transitive Relation: is transitive if whenever and , we also have , for all .
- Example: On , is transitive.
- Equivalence Relation: is an equivalence relation on if it is reflexive, symmetric, and transitive.
- Example: On , the universal relation is an equivalence relation.
- Partial Order Relation: is a partial order relation on if it is reflexive, antisymmetric, and transitive. A set equipped with a partial order is called a partially ordered set (poset).
- Example: On , (the standard relation) is a partial order relation.
Equivalence Class and Quotient Set
Let be an equivalence relation on a set .
- For any element , the equivalence class of , denoted , is the set of all elements in that are related to under :
- The quotient set of by , denoted , is the collection of all distinct equivalence classes of under :
The distinct equivalence classes in form a partition of into pairwise disjoint non-empty subsets whose union is .
For example, let and . Then:
- Quotient set: .
1.2.2 Functions (Mappings)
Function (Mapping) and Types of Functions
Let and be two non-empty sets. A function (or mapping) from to , written , is a relation from to with the property that for every element , there is a unique element such that (written ).
- is the domain of , and is the codomain of .
- Every element of the domain must be mapped to some element in , and no element of may be mapped to two or more elements in .
Functions are classified by how they map elements of into :
- One-to-One Function (Injective): is one-to-one (or an injection) if distinct elements of always map to distinct elements of :
- Book Example: , with .
- Onto Function (Surjective): is onto (or a surjection) if every element of is the image of at least one element of :
- Book Example: , with .
- One-to-One and Onto Function (Bijective): is bijective (a bijection or one-to-one correspondence) if it is both injective (one-to-one) and surjective (onto).
- Book Example: , with .
Worked Out Examples
1.1
Let be the set of positive integers, i.e., , and let be the relation defined as "" on the set . Test whether the relation is a partial order or not.
Listing the ordered pairs of : The relation consists of the pairs:
Checking reflexivity, antisymmetry, and transitivity:
- Reflexive: For every , holds, so .
- Antisymmetric: For any , if () and (), then .
- Transitive: For any , if and , then , so .
Since is reflexive, antisymmetric, and transitive on , the relation "" is a partial order relation.
1.2
Let be the set of positive integers and let be the relation defined on by
Construct the equivalence classes and find the quotient set .
Listing the pairs of the equivalence relation : Two positive integers and have an even sum ( divisible by ) if and only if they have the same parity (both are odd or both are even):
Constructing the equivalence classes :
- For odd elements ():
- For even elements ():
Forming the quotient set : Collecting the distinct equivalence classes gives the quotient set:
Equivalence classes: (odd positive integers) and (even positive integers). Quotient set: .
1.3
Check whether each of the following sets of ordered pairs represents a function or not:
Testing relation : Construct the mapping table for :
Every first element () is mapped to a unique output value. (Multiple inputs may share the same output without violating the definition of a function.) Therefore, is a function.
Testing relation : Construct the mapping table for :
Here, the domain element branches to two distinct values ( and ). Therefore, is not a function.
represents a function, whereas does not represent a function (since the input is mapped to both and ).
Exercises
Exercise — Sets, Relations & Functions
Define countably infinite set with example. [2082 Kartik, 2081 Bhadra]
Formal definition of countably infinite set: An infinite set is called countably infinite (or denumerable) if and only if there exists a one-to-one correspondence (a bijective function) between and the set of natural numbers :
The cardinality of any countably infinite set is denoted by ("aleph-null"):
A set is called countable if it is either finite or countably infinite.
Listing property and enumeration: A set is countably infinite if and only if its elements can be arranged in an infinite sequence without repetition:
where for each . Every element of appears at a definite finite index in the list.
Concrete example (the set of all integers ): Consider the set of all integers . Define the function by:
Evaluating for consecutive natural numbers:
Every integer appears exactly once in the sequence . Since is a bijection, is countably infinite.
An infinite set is countably infinite (or denumerable) if there exists a one-to-one correspondence (bijection) between the elements of and the set of natural numbers . For example, the set of integers is countably infinite via the bijection
Define uncountable set with example. [2082 Kartik]
Formal definition of uncountable set: An infinite set is called uncountable (or uncountably infinite / non-denumerable) if it cannot be placed in a one-to-one correspondence with the set of natural numbers . That is, there exists no surjective function , meaning any infinite list of elements from must omit at least one element of . Its cardinality is strictly greater than :
Cantor's power set theorem: By Cantor's Theorem, for any set , the cardinality of its power set is strictly greater than the cardinality of :
When (countably infinite), the power set (or equivalently the set of all infinite binary sequences ) has cardinality (the cardinality of the continuum), which is strictly uncountable.
Concrete example (the real interval via Cantor's diagonal argument): The set of real numbers (and any open interval ) is uncountable. Suppose for contradiction that were countable. Then all real numbers in could be enumerated in an infinite decimal list:
where each . Construct a real number by setting the diagonal digits:
The number differs from the -th number in the -th decimal position for every . Hence is not in the list, contradicting the assumption that all elements of were listed. Therefore, and are uncountable.
An infinite set is uncountable (or uncountably infinite / non-denumerable) if its elements cannot be placed in one-to-one correspondence with the set of natural numbers . For example, the set of all real numbers (or the real interval ) is uncountable.
Explain partial order relation with example. [2082 Baishakh, 2078 Kartik]
Definition and axioms of a partial order relation: A binary relation on a set (denoted ) is a partial order relation if and only if it satisfies the following three properties for all elements :
- Reflexivity: For all , (every element is related to itself).
- Antisymmetry: For all , if and , then .
- Transitivity: For all , if and , then .
A set equipped with a partial order relation is called a partially ordered set or poset, written or .
Why it is called "partial": It is called partial because not every pair of elements in needs to be comparable. Two distinct elements are incomparable if neither nor . If every pair of elements is comparable, the relation is a total order (or linear order).
Concrete example on a finite set: Let and define the relation by the standard numerical order "":
- Reflexive: .
- Antisymmetric: but ; but ; but . The only time and is when .
- Transitive: and .
Thus, is a poset.
Classic non-total example (subset inclusion ): Let and let . The subset inclusion relation on is a partial order:
- for all (reflexive).
- If and , then (antisymmetric).
- If and , then (transitive).
Here, and , so and are incomparable, demonstrating a strictly partial order.
A binary relation on a set is a partial order relation if it is:
- Reflexive: for all ,
- Antisymmetric: and , and
- Transitive: and .
For example, on , the relation "" given by is a partial order relation.
Explain equivalence relations with example. [2078 Kartik]
Definition and axioms of an equivalence relation: A binary relation on a set is an equivalence relation if and only if it satisfies three axioms for all elements :
- Reflexivity: for every .
- Symmetry: If , then .
- Transitivity: If and , then .
When , we often write or and say is equivalent to .
Equivalence classes and partitioning of a set: The fundamental property of any equivalence relation is that it partitions the underlying set into mutually disjoint, non-empty subsets called equivalence classes:
Two equivalence classes and are either completely identical (if ) or completely disjoint (if ):
The set of all equivalence classes forms the quotient set, denoted .
Concrete example (congruence modulo 3 on ): Let and define relation by :
- Reflexive: For any , , so .
- Symmetric: If , then for some . Then , so .
- Transitive: If and , then and . Adding the two gives , so .
This equivalence relation partitions into exactly three equivalence classes:
Thus, is an equivalence relation.
A binary relation on a set is an equivalence relation if it is simultaneously reflexive ( for all ), symmetric (), and transitive (). For example, on , (or congruence modulo on ) is an equivalence relation.