1A binary relation from a set to a set is defined as a subset of:
introduction
Easy
A.The union
B.The difference
C.The Cartesian product
D.The intersection
Correct Answer: The Cartesian product
Explanation:
By definition, a binary relation from a set to a set is a set of ordered pairs, which makes it a subset of the Cartesian product .
Incorrect! Try again.
2If set has elements and set has elements, what is the total number of possible relations from to ?
introduction
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The Cartesian product has elements. Since a relation is any subset of , the number of possible subsets (and thus relations) is .
Incorrect! Try again.
3A relation on a set is reflexive if:
reflexive relations
Easy
A.For all ,
B.For some ,
C.For all ,
D.If , then
Correct Answer: For all ,
Explanation:
A relation is reflexive if every element in the set is related to itself. Mathematically, , the ordered pair must be in .
Incorrect! Try again.
4A relation on a set is called symmetric if, whenever , then:
symmetric relations
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
A symmetric relation is one where order does not matter: if is related to , then must also be related to .
Incorrect! Try again.
5Which condition defines an antisymmetric relation on a set ?
antisymmetric relations
Easy
A.If and , then
B.If , then
C.For all ,
D.If and , then
Correct Answer: If and , then
Explanation:
Antisymmetry means that the only way for both and to be in the relation is if and are the exact same element.
Incorrect! Try again.
6A relation is transitive if and logically implies:
transitive relations
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Transitivity means that if an element is related to , and is related to , then must also be related directly to .
Incorrect! Try again.
7An equivalence relation on a set must satisfy which three properties?
equivalence relations
Easy
A.Irreflexive, symmetric, and transitive
B.Reflexive, symmetric, and antisymmetric
C.Reflexive, symmetric, and transitive
D.Reflexive, antisymmetric, and transitive
Correct Answer: Reflexive, symmetric, and transitive
Explanation:
By definition, a relation is an equivalence relation if and only if it is reflexive, symmetric, and transitive.
Incorrect! Try again.
8A partial ordering relation on a set must satisfy which three properties?
partial ordering relations
Easy
A.Reflexive, antisymmetric, and transitive
B.Irreflexive, antisymmetric, and transitive
C.Symmetric, antisymmetric, and transitive
D.Reflexive, symmetric, and transitive
Correct Answer: Reflexive, antisymmetric, and transitive
Explanation:
A partial order (or partial ordering relation) is defined by being reflexive, antisymmetric, and transitive.
Incorrect! Try again.
9A partition of a set divides the set into non-empty subsets that are pairwise:
partitions
Easy
A.Disjoint
B.Symmetric
C.Overlapping
D.Infinite
Correct Answer: Disjoint
Explanation:
The subsets in a partition do not share any elements. Therefore, they are pairwise disjoint (their intersection is empty).
Incorrect! Try again.
10The symmetric closure of a relation is obtained by taking the union of with:
Closure properties
Easy
A.The inverse relation
B.The diagonal relation
C.The empty relation
D.The universal relation
Correct Answer: The inverse relation
Explanation:
To make a relation symmetric, you must add the reverse of every existing ordered pair. This is done by taking the union of and its inverse .
Incorrect! Try again.
11The relation on a set is known as the:
types of relations
Easy
A.Empty relation
B.Identity relation
C.Universal relation
D.Inverse relation
Correct Answer: Universal relation
Explanation:
The universal relation on a set contains every possible ordered pair of elements from , which is exactly the Cartesian product .
Incorrect! Try again.
12In a partition of a set , the union of all the subsets in the partition must equal:
partitions
Easy
A.The Cartesian product
B.The set itself
C.The power set of
D.The empty set
Correct Answer: The set itself
Explanation:
A partition completely covers the original set without leaving any elements out, so the union of all parts equals the original set .
Incorrect! Try again.
13For an equivalence relation on a set , the set of all elements related to an element is called its:
equivalence relations
Easy
A.Equivalence class
B.Power set
C.Partition block
D.Closure
Correct Answer: Equivalence class
Explanation:
The equivalence class of an element , often denoted , is the subset of all elements in that are related to by the equivalence relation.
Incorrect! Try again.
14The reflexive closure of a relation on a set is given by , where represents:
Closure properties
Easy
A.The empty set
B.The set of all possible pairs in
C.The diagonal relation consisting of all pairs for
D.The set of all reversed pairs
Correct Answer: The diagonal relation consisting of all pairs for
Explanation:
To make a relation reflexive, it must contain for every element . Adding the diagonal relation to achieves this.
Incorrect! Try again.
15Let . Which of the following relations on is reflexive?
reflexive relations
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
For the relation to be reflexive on , it must contain the pairs and .
Incorrect! Try again.
16Let . Which of the following relations is symmetric?
symmetric relations
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
A relation is symmetric if every pair has a matching . Here, matches with , and matches with itself.
Incorrect! Try again.
17A set equipped with a partial ordering relation is commonly referred to as a:
partial ordering relations
Easy
A.Equivalence class
B.Graph
C.Tree
D.Poset
Correct Answer: Poset
Explanation:
The term 'poset' stands for Partially Ordered Set, which consists of a set along with a partial ordering relation.
Incorrect! Try again.
18The relation (less than or equal to) on the set of real numbers is an example of a relation that is:
antisymmetric relations
Easy
A.Symmetric
B.Antisymmetric
C.Irreflexive
D.Not transitive
Correct Answer: Antisymmetric
Explanation:
The relation is antisymmetric because if and , then it must be that .
Incorrect! Try again.
19The 'is a descendant of' relation on a set of people is an example of a relation that is:
transitive relations
Easy
A.Reflexive
B.Transitive
C.Symmetric
D.Equivalence
Correct Answer: Transitive
Explanation:
If person A is a descendant of B, and B is a descendant of C, then A is a descendant of C. This represents a transitive relation.
Incorrect! Try again.
20A relation on a set that contains no ordered pairs (i.e., ) is called the:
types of relations
Easy
A.Equivalence relation
B.Empty relation
C.Identity relation
D.Universal relation
Correct Answer: Empty relation
Explanation:
The relation consisting of the empty set, which means no element is related to any element, is called the empty relation.
Incorrect! Try again.
21Let have 4 elements and have 3 elements. How many distinct relations can be defined from to ?
introduction
Medium
A.$12$
B.$81$
C.
D.
Correct Answer:
Explanation:
A relation from to is a subset of the Cartesian product . Since , there are possible subsets, and therefore relations.
Incorrect! Try again.
22Let relation on the set of integers be defined as . What is the domain of ?
introduction
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The integer solutions to are and . The domain consists of all possible -values, which are .
Incorrect! Try again.
23Let and be relations. What is the composition ?
types of relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
For , we look for and to form . and gives . and gives .
Incorrect! Try again.
24If is a relation from to , which of the following represents the inverse relation ?
types of relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The inverse relation is obtained by reversing the elements of each ordered pair in . Hence, if , then .
Incorrect! Try again.
25Which of the following relations on the set of integers is reflexive?
reflexive relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
A relation is reflexive if is true for all . Since holds for all integers, it is reflexive. The other options fail when substituting for .
Incorrect! Try again.
26Let . What is the minimum number of ordered pairs a relation on must contain to be reflexive?
reflexive relations
Medium
A.9
B.0
C.3
D.6
Correct Answer: 3
Explanation:
A reflexive relation on a set must contain at least the pairs for every . Since the cardinality of is 3, must contain at least 3 pairs: .
Incorrect! Try again.
27Let be a relation on the set of all straight lines in a plane, defined by if is perpendicular to . Which property does strictly satisfy?
symmetric relations
Medium
A.Transitive
B.Reflexive
C.Equivalence
D.Symmetric
Correct Answer: Symmetric
Explanation:
If line is perpendicular to , then is perpendicular to , making the relation symmetric. It is not reflexive (a line isn't perpendicular to itself) nor transitive.
Incorrect! Try again.
28How many distinct symmetric relations can be defined on a set containing 3 elements?
symmetric relations
Medium
A.$27$
B.$512$
C.$8$
D.$64$
Correct Answer: $64$
Explanation:
The number of symmetric relations on a set of elements is given by . For , the exponent is . Thus, .
Incorrect! Try again.
29Let relation on the set of positive integers be defined by . Is this relation antisymmetric?
antisymmetric relations
Medium
A.No, because 2 divides 4 but 4 does not divide 2.
B.No, because it does not contain for all .
C.Yes, because if divides and divides , then for positive integers.
D.Yes, because it is also symmetric.
Correct Answer: Yes, because if divides and divides , then for positive integers.
Explanation:
Antisymmetry means if and , then . In positive integers, if divides and divides , they must be equal, satisfying antisymmetry.
Incorrect! Try again.
30If a relation on set is both symmetric and antisymmetric, which of the following must be true?
antisymmetric relations
Medium
A. must be the universal relation .
B. is an empty relation.
C.
D. contains only elements where .
Correct Answer:
Explanation:
Symmetry means if then . Antisymmetry means if and , then . For both to hold, can only contain diagonal pairs .
Incorrect! Try again.
31Let on set . What is the minimum set of pairs that must be added to to make it transitive?
transitive relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
For transitivity, if and , then must be in . We have and , so we must add . No further additions are required.
Incorrect! Try again.
32Which of the following relations defined on the set of positive integers is transitive?
transitive relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
If and , then . Therefore, the strict inequality relation is transitive. The other relations fail transitivity under specific conditions.
Incorrect! Try again.
33Find the symmetric closure of the relation on the set .
Closure properties
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The symmetric closure of is . Since , their union gives .
Incorrect! Try again.
34What is the transitive closure of the relation on ?
Closure properties
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The transitive closure is the smallest transitive relation containing . Since and are in , we add to satisfy transitivity.
Incorrect! Try again.
35Let be a relation on integers defined by . What is the equivalence class of 2, denoted as ?
equivalence relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The equivalence class contains all integers such that is a multiple of 5. This forms the set .
Incorrect! Try again.
36If and are equivalence relations on a set , which of the following is ALWAYS an equivalence relation?
equivalence relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The intersection of two equivalence relations preserves reflexivity, symmetry, and transitivity. The union of two equivalence relations is not necessarily transitive.
Incorrect! Try again.
37Let . How many valid partitions can be formed from the set ?
partitions
Medium
A.8
B.4
C.3
D.5
Correct Answer: 5
Explanation:
The valid partitions are: , , , , and . This yields exactly 5 partitions (known as the Bell number ).
Incorrect! Try again.
38Which of the following defines the relationship between partitions and equivalence relations on a given set?
partitions
Medium
A.Partitions only map to symmetric relations, not equivalence relations.
B.Every partition corresponds to exactly one equivalence relation.
C.Every partition corresponds to multiple equivalence relations.
D.Equivalence relations cannot be derived from partitions.
Correct Answer: Every partition corresponds to exactly one equivalence relation.
Explanation:
The Fundamental Theorem of Equivalence Relations states that every equivalence relation on a set yields a unique partition of that set, and conversely, every partition yields a unique equivalence relation.
Incorrect! Try again.
39Which of the following relations forms a partial ordering on the set of integers ?
partial ordering relations
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
A partial ordering must be reflexive, antisymmetric, and transitive. satisfies all three properties. Strict inequality () is not reflexive.
Incorrect! Try again.
40In the Hasse diagram for the poset where is the set of positive divisors of 24, which elements are the immediate predecessors of (i.e., are covered by) 24?
partial ordering relations
Medium
A.4 and 12
B.12 and 16
C.8 and 12
D.6 and 8
Correct Answer: 8 and 12
Explanation:
An element is covered by if and there is no intermediate divisor . For 24, the divisors are 1, 2, 3, 4, 6, 8, 12, 24. 8 and 12 divide 24 and no other divisor sits strictly between them and 24.
Incorrect! Try again.
41Let be a set containing elements. How many relations on are neither reflexive nor irreflexive?
reflexive relations
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
A relation is determined by its possible ordered pairs. The non-diagonal elements can be chosen in ways. For a relation to be reflexive, all diagonal elements must be present. For it to be irreflexive, none of the diagonal elements can be present. Since a relation cannot be both reflexive and irreflexive (for ), the number of relations that are either reflexive or irreflexive is . The total number of relations is , so the number of relations that are neither is .
Incorrect! Try again.
42Let be a set with elements. How many relations on are both reflexive and symmetric?
symmetric relations
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
For a relation to be reflexive, all diagonal pairs must be included (1 choice each). For it to be symmetric, the inclusion of perfectly determines the inclusion of . There are such distinct pairs of off-diagonal elements. We have 2 choices (include or exclude) for each of these pairs, leading to such relations.
Incorrect! Try again.
43What is the total number of antisymmetric relations on a set containing elements?
antisymmetric relations
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
An antisymmetric relation can optionally include any of the diagonal elements (yielding choices). For any pair of distinct elements and , an antisymmetric relation can either contain , contain , or contain neither (3 choices). There are such pairs. Thus, the total number of antisymmetric relations is .
Incorrect! Try again.
44Let and be two transitive relations on a set . Which of the following statements is unconditionally true?
transitive relations
Hard
A.The complement of is always a transitive relation.
B. is always a transitive relation.
C. is always a transitive relation.
D. is always a transitive relation.
Correct Answer: is always a transitive relation.
Explanation:
If and , then and are in both and . Because and are transitive, and . Hence, . The union, complement, and composition of transitive relations are not necessarily transitive.
Incorrect! Try again.
45The number of equivalence relations on a set of 5 elements is given by the 5th Bell number, . What is the value of ?
equivalence relations
Hard
A.203
B.15
C.52
D.120
Correct Answer: 52
Explanation:
The Bell numbers count the number of partitions of a set, which corresponds to the number of equivalence relations. They can be computed using the Bell triangle or the recurrence relation . The first few Bell numbers are .
Incorrect! Try again.
46Let be a set with elements (). The number of distinct partitions of into exactly two non-empty blocks is given by the Stirling number of the second kind, . Which formula represents this?
partitions
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
To form a partition with exactly two non-empty blocks, we assign each of the elements to one of two distinct sets (yielding ways). However, we must exclude the 2 cases where one of the sets is empty. Since the two blocks are unlabelled and unordered in a partition, we divide by 2!. Thus, .
Incorrect! Try again.
47Let be a relation on a set that is simultaneously an equivalence relation and a partial order. What must be true about the relation ?
partial ordering relations
Hard
A.Such a relation cannot exist on a non-empty set.
B. is the universal relation .
C. is the equality (identity) relation on .
D. must be strictly antisymmetric but not reflexive.
Correct Answer: is the equality (identity) relation on .
Explanation:
An equivalence relation is symmetric, and a partial order is antisymmetric. If is both symmetric and antisymmetric, then (symmetry). By antisymmetry, and . Since both require reflexivity, must consist of exactly the diagonal elements for all . This is the equality (identity) relation.
Incorrect! Try again.
48Let be a relation from to and be a relation from to . If the composition is injective (as a function), what can be strictly inferred about and ?
introduction
Hard
A. must be injective, but need not be.
B.Neither nor is necessarily injective.
C.Both and must be injective.
D. must be injective, but need not be injective everywhere.
Correct Answer: must be injective, but need not be injective everywhere.
Explanation:
In functional composition , if is injective, then must be injective. If , then , so . However, only needs to be injective on the range (image) of , not necessarily on its entire domain .
Incorrect! Try again.
49Let be a relation on . If denotes the symmetric closure of , what is the symmetric closure of the inverse relation ?
Closure properties
Hard
A.
B.Both and , since they are equal.
C.
D.
Correct Answer: Both and , since they are equal.
Explanation:
The symmetric closure of a relation is defined as . Therefore, . The symmetric closure of is . Hence, .
Incorrect! Try again.
50A relation on a set is called 'asymmetric' if implies . Which of the following statements precisely characterizes an asymmetric relation?
antisymmetric relations
Hard
A. is antisymmetric and irreflexive.
B. is irreflexive but not necessarily antisymmetric.
C. is neither antisymmetric nor irreflexive.
D. is antisymmetric but not necessarily irreflexive.
Correct Answer: is antisymmetric and irreflexive.
Explanation:
If is asymmetric, . Setting yields , which means can never be in , making it irreflexive. Additionally, the premise of antisymmetry (if and then ) holds vacuously because the antecedent is always false. Thus, it is both antisymmetric and irreflexive.
Incorrect! Try again.
51Let and be sets, and be an arbitrary mapping. A relation on is defined by . Which of the following statements is true regarding the equivalence classes of ?
equivalence relations
Hard
A.The number of equivalence classes is exactly .
B.The number of equivalence classes is exactly the cardinality of the image of .
C.The number of equivalence classes is exactly .
D. is a partial order, not an equivalence relation.
Correct Answer: The number of equivalence classes is exactly the cardinality of the image of .
Explanation:
The relation defined by is the kernel of the function . It trivially satisfies reflexivity, symmetry, and transitivity, making it an equivalence relation. Each equivalence class corresponds to the pre-image of a single element in the image of . Therefore, the number of distinct equivalence classes matches the number of elements in the image (or range) of .
Incorrect! Try again.
52Let be a relation on a set with elements. What is the minimum power such that the transitive closure of , denoted , is guaranteed to be equal to ?
Closure properties
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
By a property of relations on finite sets, any path in the directed graph representing the relation that has length greater than must contain a cycle. Therefore, the existence of a path of any length between two nodes implies the existence of a path of length at most . Thus, the transitive closure is exactly the union of from to .
Incorrect! Try again.
53Let be a finite poset. If the Hasse diagram of this poset is a rooted tree with the root at the bottom (the minimum element), which of the following properties must hold?
partial ordering relations
Hard
A.The relation is a total order.
B.Every element has at most one immediate successor.
C.The poset is a lattice.
D.Every element has exactly one immediate predecessor, except the root which has none.
Correct Answer: Every element has exactly one immediate predecessor, except the root which has none.
Explanation:
In a Hasse diagram, edges represent immediate predecessor/successor relations. If the diagram is a tree rooted at the bottom, edges point upward from the root. By the definition of a tree, every node except the root has a unique parent (immediate predecessor). It is not necessarily a lattice (lacks upper bounds for disparate branches), nor a total order, and elements can have multiple successors.
Incorrect! Try again.
54Given a set , what is the total number of distinct equivalence relations on in which the elements 1 and 2 belong to the same equivalence class?
partitions
Hard
A.15
B.20
C.10
D.52
Correct Answer: 15
Explanation:
If elements 1 and 2 must be in the same equivalence class, we can treat them as a single 'glued' element. The problem then reduces to finding the total number of equivalence relations (or partitions) on a set of 4 elements (the glued {1,2}, 3, 4, 5). The number of partitions of a 4-element set is the 4th Bell number, . Since , there are 15 such equivalence relations.
Incorrect! Try again.
55Let and be equivalence relations on a set . Under what condition is the composition guaranteed to be an equivalence relation?
types of relations
Hard
A.If and only if .
B.If and only if .
C.If and only if or .
D. is always an equivalence relation.
Correct Answer: If and only if .
Explanation:
The composition of two equivalence relations and is an equivalence relation if and only if they commute, i.e., . If they commute, is symmetric and transitive, thus an equivalence relation. If they don't commute, the resulting relation will fail to be symmetric.
Incorrect! Try again.
56Consider the relation defined on the set of integers by . What type of relation is ?
transitive relations
Hard
A.Symmetric and transitive, but not reflexive.
B.An equivalence relation.
C.A partial order.
D.Reflexive and transitive, but not symmetric.
Correct Answer: An equivalence relation.
Explanation:
The relation is defined by a mapping , such that . Any relation defined by equality of a function applied to the elements is automatically reflexive, symmetric, and transitive, and hence is an equivalence relation.
Incorrect! Try again.
57Let be a reflexive relation on a set . Which of the following statements about the composition (denoted ) is TRUE?
reflexive relations
Hard
A. is not necessarily reflexive.
B. always.
C. always.
D. always.
Correct Answer: always.
Explanation:
Because is reflexive, for any , . If , then because , by composition . Thus, every element in is also in , meaning . would only be true if were transitive.
Incorrect! Try again.
58Warshall's algorithm is used to compute the transitive closure of a relation on a finite set of elements. What is the fundamental recurrence relation used to update the boolean matrix in the -th step?
Closure properties
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
In Warshall's algorithm, a path exists from node to node using intermediate nodes up to if either there is already a path using intermediate nodes up to (), OR there is a path from to AND a path from to using intermediate nodes up to . This corresponds precisely to the boolean expression .
Incorrect! Try again.
59Let be a relation on defined by the boolean matrix . If (where is the matrix of all 1s, representing the universal relation) and (where is the identity matrix), what type of relation does represent?
types of relations
Hard
A.A total (linear) order.
B.A partial order.
C.An equivalence relation.
D.A tournament (a strict total order if transitive).
Correct Answer: A total (linear) order.
Explanation:
The condition strictly implies antisymmetry (since non-diagonal elements cannot be symmetric) and reflexivity (all diagonal elements are 1). The condition implies that for all distinct , either or (strongly connected / totality). A relation that is reflexive, antisymmetric, and total is a total order. (Though transitivity is conventionally required for a total order, these matrix properties strictly define the reflexive and antisymmetric comparability properties unique to linear orders in this context).
Incorrect! Try again.
60In a Boolean algebra viewed as a partially ordered set (poset), elements and have a least upper bound (LUB) and a greatest lower bound (GLB). What do the LUB and GLB correspond to respectively in the Boolean algebra?
partial ordering relations
Hard
A.LUB corresponds to complementation (), GLB corresponds to identity.
B.LUB corresponds to logical OR (), GLB corresponds to logical AND ().
C.LUB corresponds to logical AND (), GLB corresponds to logical OR ().
D.LUB corresponds to logical XOR (), GLB corresponds to logical XNOR.
Correct Answer: LUB corresponds to logical OR (), GLB corresponds to logical AND ().
Explanation:
In any lattice formed by a Boolean algebra (like the power set under inclusion ), the least upper bound (supremum) is achieved via the join operation, which is logical OR () or set union. The greatest lower bound (infimum) is achieved via the meet operation, which is logical AND () or set intersection.