Theory of Computation: Question Set – 03
What is the inverse of a relation?
The inverse of a relation R on a set A is the relation obtained by swapping the first and second elements in each pair of R. Formally, if (a, b) is in R, then (b, a) is in the inverse relation R-1.
What is a reflexive relation?
A reflexive relation on a set A is a relation that relates every element of A to itself. Formally, a relation R on A is reflexive if (a, a) is in R for every a in A.
What is a symmetric relation?
A symmetric relation on a set A is a relation where if (a, b) is in the relation, then (b, a) is also in the relation. Formally, a relation R on A is symmetric if (a, b) is in R implies that (b, a) is in R.
What is a transitive relation?
A transitive relation on a set A is a relation where if (a, b) and (b, c) are in the relation, then (a, c) is also in the relation. Formally, a relation R on A is transitive if (a, b) is in R and (b, c) is in R implies that (a, c) is in R.
What is an anti-symmetric relation?
An anti-symmetric relation on a set A is a relation where if (a, b) and (b, a) are in the relation and a is not equal to b, then the only possibility is that a and b are equal.
What is a function in mathematics?
A function is a mathematical concept that describes a relationship between two sets of objects, called the domain and the range. A function assigns each element in the domain exactly one element in the range. For example, the function f(x) = 2x + 1 assigns to each real number x a unique value 2x + 1. The domain of this function is the set of all real numbers, and the range is also the set of all real numbers.
What is a one-to-one function?
A function is one-to-one if each element in the domain maps to a unique element in the range, and no two elements in the domain map to the same element in the range. In other words, if f(a) = f(b) implies a = b for any two elements a and b in the domain of the function. A one-to-one function is also called an injective function.
What is an onto function?
A function is onto if every element in the range is mapped to by at least one element in the domain. In other words, for any element y in the range of the function, there exists an element x in the domain such that f(x) = y. An onto function is also called a surjective function.