Introduction
Sets, relations, and functions are basic concepts in discrete mathematics used to understand the organisation of information, connections between objects, and processing of values in the fields of mathematics and computer science. They are fundamental to many concepts such as database management, programming, algorithms, graph theory, and software development. A set is a collection of distinct objects; a relation is an association between objects; a function is a relationship in which every object in a set has exactly one object in another set associated with it. These concepts might seem abstract at first, but when related to real world examples like organizing student records, pairing employees with departments, or translating numbers between formats. Knowing about functions, relations and sets also helps in the understanding of more advanced mathematical concepts, as many problems in Computer science rely on these concepts. They are explained with clear explanations and examples with their definitions, properties, operation, classification and application.
In Discrete Mathematics, Sets are fundamental.Sets are basic objects of Discrete Mathematics.
What Is a Set?
A set is a clearly specified collection of specific objects called the elements or members of the set. They can be numbers, names, letters, computer files, or other things that can be identified. For instance, the set of positive integers less than or equal to 5 is A = {1, 2, 3, 4, 5} and the set of vowels in the English alphabet is V = {a, e, i, o, u}. There are no requirements on how elements in a set are arranged, and repeating an element does not make another element.
Therefore, {1, 2, 3} and {3, 2, 1} represent the same set, just as {1, 1, 2, 3} represents the same set as {1, 2, 3}. Sets are useful since they allow a precise description of collections of information. A set can consist of registered users, products available, keywords to certain programming languages, or identification numbers. Sets to group related objects together so that information is easier to analyse, compare and manipulate.
Set Notation and Representation.
Mathematical notation allows us to describe sets and their elements in a uniform manner. The elements of a set are written in curly braces and the symbol ∈ is used to indicate that an object is an element of a set. Sets can be written in two ways: by listing all the elements (called the roster method) or by using the set-builder notation to indicate a property that all elements share.
For example, A = {2, 4, 6, 8, 10} can also be expressed as A = {x ∈ N | x is even and 2 ≤ x ≤ 10}, where N represents the natural numbers. The vertical bar is used to mean “such that.” These notations are very handy for sets with a large number of elements, or when the elements in a set are specified by a mathematical rule. Similar concepts are used when programmers create collections, filter data and select values that meet certain criteria.
If A is a set, what are its subsets?
Set A is a subset of set B if all members of set A are members of set B. This relation is denoted by A ⊆ B. For example, if A = {1, 2} and B = {1, 2, 3, 4}, then A ⊆ B because both elements of A appear in B. A subset which is different from the set itself is called a proper subset, and is commonly written as A ⊂ B. Each set also has the empty set (called the null set, denoted ∅) as a subset. The empty set is an important mathematical concept, not because it has any elements but because it represents an empty collection of elements which do not satisfy the required condition.
For instance, the collection returned from searching a database for students who scored more than 100 on an exam would be empty. The concept of subsets is useful for programmers to decide if one collection is a subset of another, and the empty set can be used to indicate that no matches exist or that a result set isn’t qualified. These ideas also play an important role in probability, classification and logical reasoning.
Union and Intersection of Sets
Two simple operations that are used to compare and combine sets are Union and Intersection. A ∪ B is the set consisting of all elements in A or B (or both). A ∩ B is the intersection of sets A and B, and represents only the elements that appear in both sets. Consider A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Their union is A ∪ B = {1, 2, 3, 4, 5, 6}, while their intersection is A ∩ B = {3, 4}. They are directly applicable in databases and programming.
For example, an online shop might perform a union between two sets of customers, or an intersection between two sets of customers in which one set is in a loyalty programme and one set is a promotional mailing list. Also, set operations can be used to filter out duplicate values, to combine search criteria, and to analyse overlapping groups of values, which is helpful for search engines. The value of their use is that they offer an accurate way to merge information or find commonality amongst all the records without having to look at them individually.
The Cartesian products of sets.
The Cartesian product of two sets is a set of ordered pairs that are formed by pairing each element of the first set with the elements of the second set. It is represented as A × B and defined as A × B = {(a, b) | a ∈ A and b ∈ B}. For example, if A = {1, 2} and B = {x, y}, then A × B = {(1, x), (1, y), (2, x), (2, y)}. The position of the elements in each ordered pair remains fixed; that is, (1, x) is usually not equal to (x, 1). The Cartesian product of A and B has m × n ordered pairs.
The reason for the importance of this operation is that it is the basis for defining relations and functions. Cartesian products can be used to help describe what rows in one table can be joined to rows in another table in a database, but in real life, databases use conditions to prevent unwanted rows from being combined. Cartesian products can be used in programming to represent all possible combinations of product options, examination subjects, or scheduling options.
Relations in Discrete Mathematics
What Is a Relation?
A relation is a relation between elements of one set or more sets. In formal terms a binary relation from set A to set B is any subset of A × B. This is to say that a relation is a subset of all the pairs of elements in two sets, such that it picks out certain ordered pairs. For example, let A = {1, 2, 3} and B = {2, 3, 4}. One relation R might be: R = {(1, 2), (2, 3), (3, 4),} corresponding to the rule “the second number is one larger than the first. Relationships do not need to link all elements and one element can be related to multiple elements.
For instance, a student may take more than one course and there may be more than one student in a given course. The fact that these connections can be made is another way of showing that relations are more flexible than functions. In the world of databases, relationships are commonly used to denote associations between records; in the world of computer science, to model communications, permissions, and dependencies between entities; and in the world of graph theory, to model connections between vertices.
Properties of Relations
Relations can have various properties that dictate the way the relationship’s elements are associated. A relation R on a set A is reflexive if a is related to a for all a in A, that is if (a, a) is in R for all a in A. It is symmetric if a is related to b then b is related to a. For example, the relation has the same birthday as is symmetric, that is, if one person has the same birthday as another person, then the other person has the same birthday as the first person. A relation is called antisymmetric if aRb and bRa together does imply that a = b.
The relation “is less than or equal to” on numbers is antisymmetric, meaning that for any two numbers x and y, if x is less than or equal to y, then y is less than or equal to x. A relation R is transitive if whenever aRb and bRc, then aRc. For instance, if A is less than B and B is less than C, then A is less than C. These properties are useful to mathematicians to classify relationships and determine if they follow certain rules. They can be used in computer science to analyze ordering systems, dependency relationships, access-control structures, and the logical behavior of connected data.
Equivalence Relations
A relation that is reflexive, symmetric and transitive is called an equivalence relation. These conditions allow elements to be classified by a common attribute. For instance, integers with the same remainder on dividing with 3. In this relation, 7 is related to 4 because 7 – 4 = 3, which is divisible by 3.In this relation, 7 is related to 4 because 7 – 4 = 3, which is divisible by 3. The relation is reflexive since for any integer n, we have that n leaves the same remainder as itself, and it is symmetric since if n leaves some remainder when divided by k, then n leaves that same remainder when divided by m, the vice versa is also true, and the relation is transitive because n and m have the same remainder when divided by k, then they have the same remainder when divided by m.
Equivalence relations partition a set into equivalence classes of elements that are equivalent under the given relation. The classes of integers according to their remainder on division by three are the remainder 0, 1 and 2. This idea can be applied in computer science, such as in grouping records of the same value, simplification of mathematical expressions, comparing objects based on a given criterion, and determining states that are identical for a specific function.
What Is a Function?
A function is a relation where exactly one number in the range corresponds to each number in its domain. When a function is expressed in the form f: A → B, A is called the domain of the function and B is its codomain. The domain of a function is the set of all values for which the function is defined. For example, consider f(x) = 2x, where the domain is {1, 2, 3} and the codomain is {2, 4, 6, 8}. The outputs of the function are 2, 4 and 6, therefore the range of the function is {2, 4, 6}. The codomain for the function is 8, but the value 8 is never achieved for a value in the domain.
A function should assign each argument one and only one value; it is possible to have more than one argument with the same value, provided there are other conditions. This rule is used to differentiate functions from general relations. For instance, one student might have several course registrations, and a student ID can be used as an input to obtain one student’s record. Functions are crucial in programming as they are used to represent repeatable operations that take inputs and return outputs.
Mapping
A mapping is also known as a function or an assignment which assigns elements of one set to elements of another in some manner. One way to represent a mapping is by using arrows to connect two sets, with an arrow pointing from an element in the first set to an element in the second set showing the output that is associated with the element in the first set. Suppose A = {1, 2, 3} and B = {a, b, c}. An alternate mapping might be 1 to a, 2 to a, and 3 to a, as long as each input has exactly one output. The first mapping is a one-to-one mapping and the second is a many-to-one mapping. One way in which mappings are very useful is that they help model many of the common operations that happen in real daily computing.
The program could assign student numbers to student records, product codes to the price of the products, or usernames to account information. In Mathematics, a mapping refers to a transformation of one set of numbers, geometric figures, or abstract entities to another. They are used in databases to provide a way of mapping identifiers to values stored in the database. The concept of mappings can then be used to build knowledge of various kinds of functions and which conditions are important for them in certain applications.
Injective Functions
A function that assigns a different output to each input is called an injective function, or one-to-one function. A function f is injective if f(a) = f(b) then a = b. Or, in other words, if two inputs differ, then so do their outputs. Let f(x) = 2x for x an integer. The function is injective because, if it doubled two integers to be equal, they should be equal. On the other hand, f(x) = x², on the set Z of integers, is not injective, since 2 and −2 both give 4 as their output.
Injectivity is especially important for a system that requires identifying each record or for a system that doesn’t want multiple different keys to return the same results. For instance, each user registered into a database must have a unique identification number. But it is a uniqueness which is subject to the domain and codomain of a given system and its rules. Injective functions also play a crucial role in cryptography, data encoding, and mathematical proofs in establishing the distinguishability or recoverability of information from an output.
Surjective Functions
A function in which every element of the codomain corresponds to at least one element of the domain is called surjective (onto). That is, the range and codomain are the same. If f is surjective, then for every b in B there is at least one a in A for which f(a) = b. For example, consider f(x) = x² with domain {−2, −1, 1, 2} and codomain {1, 4}. Both numbers 1 and 4 are returned by the function, so all elements of the codomain are attained.
Thus this is surjective. The function f(x) = x² maps the same domain onto the codomain {0, 1, 4} but it would not be surjective since there is no x such that f(x) is 0. See surjective functions for a more detailed mathematical definition and more examples. In computer science, surjectivity can be helpful to determine if a mapping reaches all the desired target objects, for example, if at least one thing is mapped into each category. It is also useful for mathematicians to find out whether a function has all the values in its codomain.
Bijective Functions
A bijective function is an injection and surjection. This is to say that each element of the domain corresponds to exactly one element of the range, no two elements of the domain correspond to the same element of the range, and each element of the codomain is used. This means that there is a one-to-one relationship between the elements of the codomain and the elements of the domain. For example, let A = {1, 2, 3} and B = {a, b, c}. The function f : {1, 2, 3} → {a, b, c} is injective and surjective, as there is exactly one element of B associated with each element of A and each element of B is used exactly once.
An inverse function of a bijection “undoes” the action of the function, such that the original input is recovered from its output. Reversible data transformations, mathematical proofs, comparing set sizes all use this property of bijections. In computer science, bijective mappings can help to create systems that rely on one-to-one correspondence between identifiers and records. Not all real-world maps are bijective though; some records might be in the same category, or some possible destinations might not have an associated record. By understanding these differences, developers can choose the right data structures and make informed decisions about how to handle their data.
Applications of Sets, Relations and Functions in Computer Science
The concepts of sets, relations, and functions are important in the context of database management as they help to structure and link information within the database. The table can be considered as a set of rows and the set operations can be used to extract, join and compare records matching specific conditions. For instance, the students at a university could be represented by a collection of students studying computer science and another collection of students studying mathematics. They intersect with one another to give the students who are enrolled in both programmes. They intersect with students in either programme to give the students enrolled in both programmes.
Relationships are about relationships between students, courses, lecturers and departments. This is a many to many student to course relationship: A student may take a number of courses, and a course may have a number of students. Another application, when there is a one-to-one relationship between the unique student identifier and the student record, is functions. Database designers use these concepts to establish relationships between tables, eliminate duplicate data, and assure its integrity. While relational databases use particular structures and query rules to put these concepts in practice, it’s easier to design efficient queries and interpret the relationships in the database when you understand the math behind the concepts.
Applications in Programming and Software Development
Programming languages provide practical implementations of sets, relations, and functions through data structures, conditional logic, and reusable operations. A set data structure can store distinct values, making it useful for removing duplicates, checking membership, and comparing collections. For example, a program that records registered email addresses may use a set to determine whether an address has already been entered. Relations appear when programs store connections between users, products, permissions, or network devices. These relationships can be represented through dictionaries, graphs, tables, or lists of ordered pairs.
Functions are among the most common programming constructs because they allow developers to divide complex tasks into smaller operations. A function might calculate a student’s average score, convert a temperature, or retrieve a product price using an identifier. Injective, surjective, and bijective properties become relevant when a developer needs to establish uniqueness, coverage, or reversible mappings. These mathematical ideas help programmers reason about correctness, detect design errors, and understand how information moves through an application. They also support testing because each function can be evaluated against its expected inputs, outputs, and constraints.
Applications in Mathematics and Algorithms
Sets, relations, and functions are equally important in mathematical reasoning and algorithm design. Sets provide the language for defining problem inputs, possible solutions, and collections of states that an algorithm may visit. Relations are used to represent graph connections, ordering constraints, and logical dependencies between objects. For example, a computer network can be modelled as a graph whose vertices represent devices and whose edges represent communication links. Functions describe transformations performed by algorithms, including sorting keys, calculating distances, and assigning labels to objects.
Their properties can influence whether an algorithm produces unique results, covers every required case, or supports a reverse operation. Equivalence relations help algorithms group objects that share a particular characteristic, while set operations make it possible to compare groups efficiently. In formal verification, mathematical definitions provide precise conditions against which software behaviour can be checked. These concepts also appear in automata theory, compiler design, computational logic, and complexity analysis. A solid understanding of them therefore improves the ability to solve theoretical problems and develop software that behaves predictably.
Conclusion
Sets, relations, and functions provide essential mathematical tools for understanding how objects are grouped, how they are connected, and how values are assigned or transformed. Sets organise distinct elements and support operations such as unions, intersections, subsets, and Cartesian products. Relations describe connections between elements and can be classified according to properties such as reflexivity, symmetry, antisymmetry, and transitivity. Equivalence relations are especially useful for grouping elements that share a common characteristic.
Functions build on relations by requiring every input to have exactly one output, while injective, surjective, and bijective functions describe increasingly specific properties of mappings. These concepts are not limited to abstract mathematics; they support database design, programming, software development, algorithm construction, and many other areas of computer science. By learning their definitions and practising with concrete examples, students can develop stronger logical reasoning skills and gain a clearer understanding of how mathematical principles are applied to practical computing problems.
