PadhaikoAll subjects

Sets, Functions & Relations

Theory of Computation (ENCT 203)

Open in the Padhaiko app

1.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:

  1. 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.
  2. 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.
  3. 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.
AspectComplexity TheoryComputability Theory
Core QuestionWhat makes some problems computationally hard and others easy?Which problems can be solved by a computer algorithm and which cannot?
ClassificationEasy (tractable, e.g. class ) vs. Hard (intractable, e.g. -hard)Solvable (decidable / recursive) vs. Unsolvable (undecidable)
Representative ExamplesSorting numbers (easy) vs. Optimal university timetable scheduling (hard)Halting problem, deciding truth of arbitrary mathematical statements

1.1 Brief Review of Set Theory

Definition

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:

Well-Defined vs. Non-Well-Defined Collections
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:

  1. 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:
  1. 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

Definition

Fundamental Types of Sets

Definition

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 :

  1. 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 :
One-to-One Correspondence Between N and Z

Formally, for even and for odd is a bijection from onto .

  1. 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

Definition

Fundamental Set Operations

Let and be subsets of a universal set :

  1. Set Difference ( or ): The set of elements that belong to but not to :

For example, if and , then .

  1. 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 ).

  1. Intersection (): The set of elements common to both and :

For example, if and , then . If , then and are disjoint.

  1. Union (): The set of elements that belong to , or to , or to both:

For example, if and , then .

  1. 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

Theorem

Algebraic Laws of Set Operations

For any sets , , and :

  1. Idempotence Laws:
  1. Commutative Laws:
  1. Associative Laws:
  1. Distributive Laws:
  1. De Morgan's Laws:

(When , these take the complement form and .)

  1. Absorption Laws:

1.2 Relations and Functions

1.2.1 Relations

Definition

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 ).

When , is called a relation on the set .

For example, let and , and consider the relation

Then:

Definition

Properties and Types of Relations on a Set A

Let be a binary relation on a set :

  1. Reflexive Relation: is reflexive if for every .
    • Example: On , is reflexive because .
  2. Symmetric Relation: is symmetric if whenever , we also have , for all .
    • Example: On , is symmetric because are paired with respectively.
  3. Antisymmetric Relation: is antisymmetric if whenever and , we must have , for all . Equivalently, for distinct elements , and cannot both belong to .
  4. Transitive Relation: is transitive if whenever and , we also have , for all .
    • Example: On , is transitive.
  5. Equivalence Relation: is an equivalence relation on if it is reflexive, symmetric, and transitive.
    • Example: On , the universal relation is an equivalence relation.
  6. 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.
Definition

Equivalence Class and Quotient Set

Let be an equivalence relation on a set .

The distinct equivalence classes in form a partition of into pairwise disjoint non-empty subsets whose union is .

For example, let and . Then:

1.2.2 Functions (Mappings)

Definition

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 ).

Functions are classified by how they map elements of into :

  1. One-to-One Function (Injective): is one-to-one (or an injection) if distinct elements of always map to distinct elements of :
  1. Onto Function (Surjective): is onto (or a surjection) if every element of is the image of at least one element of :
  1. 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

Example 1.1

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 .
Answer:

Since is reflexive, antisymmetric, and transitive on , the relation "" is a partial order relation.

Example 1.2

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:

Answer:

Equivalence classes: (odd positive integers) and (even positive integers). Quotient set: .

Example 1.3

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.

Answer:

represents a function, whereas does not represent a function (since the input is mapped to both and ).

Exercises

Exercise — Sets, Relations & Functions

Question 1

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.

Answer:

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

Question 2

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.

Answer:

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.

Question 4

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 :

  1. Reflexivity: For all , (every element is related to itself).
  2. Antisymmetry: For all , if and , then .
  3. 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:

  1. for all (reflexive).
  2. If and , then (antisymmetric).
  3. If and , then (transitive).

Here, and , so and are incomparable, demonstrating a strictly partial order.

Answer:

A binary relation on a set is a partial order relation if it is:

  1. Reflexive: for all ,
  2. Antisymmetric: and , and
  3. Transitive: and .

For example, on , the relation "" given by is a partial order relation.

Question 8

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 :

  1. Reflexivity: for every .
  2. Symmetry: If , then .
  3. 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.

Answer:

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.

Past exam questions for Theory of Computation

Propositional Logic, Rules of Inference & Predicate Logic →