Set Theory and Relations Questions and Answers

Q: A binary relation \(R\) on \(\mathbb{N} \times \mathbb{N}\) is defined as follows: \((a,b)R(c,d)\) if \(a \le c\) or \(b \le d\). Consider the following propositions:P: \(R\) is reflexiveQ: \(R\) is transitiveWhich one of the following statements is TRUE?

P is true and Q is false: \(R\) is reflexive but not transitive.Reflexive: \((a,b)R(a,b)\) holds because \(a \le a\).Not transitive: take \((1,5)R(2,1)\), true since \(1 \le 2\), and \((2,1)R(0,3)\), true since \(1 \le 3\). But \((1,5)R(0,3)\) needs \(1 \le 0\) or \(5 \le 3\), and both fail. The “or” lets each step use a different coordinate, so the chain does not carry through.Hence options calling \(R\) transitive, or not reflexive, are wrong.

Q: Let \(U = \{1, 2, \ldots, n\}\), where \(n\) is a large positive integer greater than 1000. Let \(k\) be a positive integer less than \(n\). Let \(A, B\) be subsets of \(U\) with \(|A| = |B| = k\) and \(A \cap B = \emptyset\). We say that a permutation of \(U\) separates \(A\) from \(B\) if one of the following is true.- All members of \(A\) appear in the permutation before any of the members of \(B\).- All members of \(B\) appear in the permutation before any of the members of \(A\).How many permutations of \(U\) separate \(A\) from \(B\)?

The count is \(2\binom{n}{2k}(n-2k)!\,(k!)^{2}\).Build a separating permutation in steps:Choose the 2k positions that the members of \(A \cup B\) will occupy: \(\binom{n}{2k}\) ways.Fill the other \(n - 2k\) positions with the remaining elements: \((n-2k)!\) ways.Decide which set comes first in the chosen positions: 2 ways. The first k of those positions then hold that set and the last k the other.Arrange A within its k positions and B within its k positions: \(k!\,k! = (k!)^{2}\) ways.Multiplying gives the answer. The option without the factor 2 counts only one of the two orders, the option without \((k!)^{2}\) forgets to arrange the members inside each set, and \(n!\) counts every permutation, separating or not.

Q: Let A = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5}, B = {1, 2, 3, 4, 5}, C = {1}, D = {1, {1}}S1 : A and B are equalS2 : C and D are equal then .................... is True

The answer is S1 and ~S2: S1 is true and S2 is false.A set is determined only by which elements it contains; repetition and order are ignored. Listing 2 twice or 5 five times in A adds nothing, so A = {1, 2, 3, 4, 5} = B, and S1 is true.C = {1} has one element. D = {1, {1}} has two: the number 1 and the set {1}. Since {1} is an element of D but not of C, the sets differ and S2 is false. So the true combination is S1 and the negation of S2, which rules out the other three options.

Q: The basic operations on sets :

The basic operations on sets are union, intersection, difference and subset.A set abstract data type is defined by the operations of set theory: union (elements in either set), intersection (elements in both), difference (elements in one but not the other) and the subset test, along with membership.Push and pop are stack operations. Insert and delete belong to many structures (lists, trees) and do not define a set. Traversing and merging are general operations on lists and files, not the defining operations of sets.

Q: Let A and B be the sets. The symmetric difference between A and B is :

The symmetric difference is \(A \oplus B = (A - B) \cup (B - A)\).It contains the elements that belong to exactly one of the two sets: those in A but not B, together with those in B but not A. Equivalently it is \((A \cup B) - (A \cap B)\).The other options define union, intersection and subset by formulas that do not hold; for example \((A - B) \cup (B + A)\) is just \(A \cup B\), which is not what \(A \subseteq B\) means, and a subset relation is not a set at all.

Q: For a crisp relation R(X, X), iff the pair \(\langle x, y \rangle \in R\) it is also the case that \(\langle y, x \rangle \in R\) for each \(x, y \in X\) for \(x \ne y\), then such a relation is called as a ............ relation.

Such a relation is symmetric.A relation R on X is symmetric when, for every pair of distinct elements, \(\langle x, y \rangle \in R\) implies \(\langle y, x \rangle \in R\), which is exactly the condition stated.Reflexive means every element is related to itself. Transitive means \(\langle x, y \rangle\) and \(\langle y, z \rangle\) in R give \(\langle x, z \rangle\) in R. Nontransitive means that transitivity fails for some triple. None of these concerns reversing a pair.

Q: The binary relation on a single set "is smarter than" is ................. .

'Is smarter than' is transitive.If x is smarter than y and y is smarter than z, then x is smarter than z, so the relation is transitive.It is not reflexive, because no one is smarter than themselves. It is not symmetric: if x is smarter than y, then y is not smarter than x, so it is in fact asymmetric. Since reflexivity fails, 'reflexive and transitive' is also wrong.

A binary relation \(R\) on \(\mathbb{N} \times \mathbb{N}\) is defined as follows: \((a,b)R(c,d)\) if \(a \le c\) or \(b \le d\). Consider the following propositions:

P: \(R\) is reflexive
Q: \(R\) is transitive

Which one of the following statements is TRUE?

A.Both P and Q are true.
B.P is true and Q is false.
C.P is false and Q is true.
D.Both P and Q are false.

Exam Year(s)

GATE CS - 2016,

Answer: B

P is true and Q is false: \(R\) is reflexive but not transitive.

Reflexive: \((a,b)R(a,b)\) holds because \(a \le a\).

Not transitive: take \((1,5)R(2,1)\), true since \(1 \le 2\), and \((2,1)R(0,3)\), true since \(1 \le 3\). But \((1,5)R(0,3)\) needs \(1 \le 0\) or \(5 \le 3\), and both fail. The “or” lets each step use a different coordinate, so the chain does not carry through.

Hence options calling \(R\) transitive, or not reflexive, are wrong.

Discuss in Forum

Let \(U = \{1, 2, \ldots, n\}\), where \(n\) is a large positive integer greater than 1000. Let \(k\) be a positive integer less than \(n\). Let \(A, B\) be subsets of \(U\) with \(|A| = |B| = k\) and \(A \cap B = \emptyset\). We say that a permutation of \(U\) separates \(A\) from \(B\) if one of the following is true.

- All members of \(A\) appear in the permutation before any of the members of \(B\).
- All members of \(B\) appear in the permutation before any of the members of \(A\).

How many permutations of \(U\) separate \(A\) from \(B\)?

A.\(n!\)
B.\(\binom{n}{2k}(n-2k)!\)
C.\(\binom{n}{2k}(n-2k)!\,(k!)^{2}\)
D.\(2\binom{n}{2k}(n-2k)!\,(k!)^{2}\)

Exam Year(s)

GATE CS - 2023,

Answer: D

The count is \(2\binom{n}{2k}(n-2k)!\,(k!)^{2}\).

Build a separating permutation in steps:

Choose the 2k positions that the members of \(A \cup B\) will occupy: \(\binom{n}{2k}\) ways.
Fill the other \(n - 2k\) positions with the remaining elements: \((n-2k)!\) ways.
Decide which set comes first in the chosen positions: 2 ways. The first k of those positions then hold that set and the last k the other.
Arrange A within its k positions and B within its k positions: \(k!\,k! = (k!)^{2}\) ways.

Multiplying gives the answer. The option without the factor 2 counts only one of the two orders, the option without \((k!)^{2}\) forgets to arrange the members inside each set, and \(n!\) counts every permutation, separating or not.

Discuss in Forum

Let A = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5}, B = {1, 2, 3, 4, 5}, C = {1}, D = {1, {1}}

S1 : A and B are equal
S2 : C and D are equal then .................... is True

A.S1 and S2
B.~S1 and ~S2
C.~S1 and S2
D.S1 and ~S2

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: D

The answer is S1 and ~S2: S1 is true and S2 is false.

A set is determined only by which elements it contains; repetition and order are ignored. Listing 2 twice or 5 five times in A adds nothing, so A = {1, 2, 3, 4, 5} = B, and S1 is true.

C = {1} has one element. D = {1, {1}} has two: the number 1 and the set {1}. Since {1} is an element of D but not of C, the sets differ and S2 is false. So the true combination is S1 and the negation of S2, which rules out the other three options.

Discuss in Forum

The basic operations on sets :

A.Push and pop
B.Insert and delete
C.Union, intersection, difference and subset
D.Traversing and merging

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

The basic operations on sets are union, intersection, difference and subset.

A set abstract data type is defined by the operations of set theory: union (elements in either set), intersection (elements in both), difference (elements in one but not the other) and the subset test, along with membership.

Push and pop are stack operations. Insert and delete belong to many structures (lists, trees) and do not define a set. Traversing and merging are general operations on lists and files, not the defining operations of sets.

Discuss in Forum

Let A and B be the sets. The symmetric difference between A and B is :

A.\(A \oplus B = (A - B) \cup (B - A)\)
B.\(A \cup B = (A \oplus B) \cap (B + A)\)
C.\(A \cap B = (B + A) - (B - A)\)
D.\(A \subseteq B = (A - B) \cup (B + A)\)

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: A

The symmetric difference is \(A \oplus B = (A - B) \cup (B - A)\).

It contains the elements that belong to exactly one of the two sets: those in A but not B, together with those in B but not A. Equivalently it is \((A \cup B) - (A \cap B)\).

The other options define union, intersection and subset by formulas that do not hold; for example \((A - B) \cup (B + A)\) is just \(A \cup B\), which is not what \(A \subseteq B\) means, and a subset relation is not a set at all.

Discuss in Forum

For a crisp relation R(X, X), iff the pair \(\langle x, y \rangle \in R\) it is also the case that \(\langle y, x \rangle \in R\) for each \(x, y \in X\) for \(x \ne y\), then such a relation is called as a ............ relation.

A.transitive
B.symmetric
C.reflexive
D.nontransitive

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: B

Such a relation is symmetric.

A relation R on X is symmetric when, for every pair of distinct elements, \(\langle x, y \rangle \in R\) implies \(\langle y, x \rangle \in R\), which is exactly the condition stated.

Reflexive means every element is related to itself. Transitive means \(\langle x, y \rangle\) and \(\langle y, z \rangle\) in R give \(\langle x, z \rangle\) in R. Nontransitive means that transitivity fails for some triple. None of these concerns reversing a pair.

Discuss in Forum

The binary relation on a single set "is smarter than" is ................. .

A.reflexive
B.symmetric
C.transitive
D.reflexive and transitive

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: C

'Is smarter than' is transitive.

If x is smarter than y and y is smarter than z, then x is smarter than z, so the relation is transitive.

It is not reflexive, because no one is smarter than themselves. It is not symmetric: if x is smarter than y, then y is not smarter than x, so it is in fact asymmetric. Since reflexivity fails, 'reflexive and transitive' is also wrong.

Discuss in Forum

The power set of the set {φ} is

A.{φ}
B.{φ, {φ}}
C.{0}
D.{0, φ, {φ}}

Exam Year(s)

UGC NET - 2012,

Answer: B

The power set of the set containing only the empty set is the set of all its subsets. The set {φ} has one element, so it has 2 to the power 1, that is 2, subsets: the empty set φ and the set {φ} itself. So the power set is {φ, {φ}}.

The option {φ} lists only one subset, so it is not the whole power set. {0} contains the number 0, which is not an element or subset here. {0, φ, {φ}} has the extra element 0, so it cannot be the power set, and the count of three members is also wrong, since a set with one element has only two subsets.

Discuss in Forum

The power set of \(A \cup B\), where A = {2, 3, 5, 7} and B = {2, 5, 8, 9} is

A.256
B.64
C.16
D.4

Exam Year(s)

UGC NET - 2012,

Answer: B

The union \(A \cup B\) of A = {2, 3, 5, 7} and B = {2, 5, 8, 9} is {2, 3, 5, 7, 8, 9}, which has 6 elements, since 2 and 5 are common to both sets. The power set of a set with n elements has \(2^n\) elements, so

\[ 2^6 = 64 \]

The number 256 is \(2^8\), the power set size for 8 elements, which is the count one gets by adding the sizes of the sets without removing the common elements, and 16 is \(2^4\). The keyed answer is 64.

Discuss in Forum

10.

How many relations are there on a set with n elements that are symmetric and a set with n elements that are reflexive and symmetric ?

A.\(2^{n(n+1)/2}\) and \(2^{n}\cdot 3^{n(n-1)/2}\)
B.\(3^{n(n-1)/2}\) and \(2^{n(n-1)}\)
C.\(2^{n(n+1)/2}\) and \(3^{n(n-1)/2}\)
D.\(2^{n(n+1)/2}\) and \(2^{n(n-1)/2}\)

Exam Year(s)

UGC NET - 2012,

Answer: D

A symmetric relation on n elements is fixed by choosing, for each of the n diagonal pairs and the n(n-1)/2 unordered off-diagonal pairs, whether it is in the relation, which gives \(2^{n(n+1)/2}\) relations. A reflexive and symmetric relation must contain all the diagonal pairs, so only the n(n-1)/2 off-diagonal pairs are free, which gives \(2^{n(n-1)/2}\). So the answers are \(2^{n(n+1)/2}\) and \(2^{n(n-1)/2}\), option (D). The other options use factors of 3 or other exponents, which do not count these relations.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Set Theory and Relations Questions and Answers || Set Theory and Relations MCQ Questions and Answers || Set Theory and Relations GK Questions and Answers || Set Theory and Relations GK MCQ Questions || Set Theory and Relations Multiple Choice Questions and Answers || Set Theory and Relations GK || GK on Set Theory and Relations || Discrete Mathematics Questions and Answers || Discrete Mathematics MCQ Questions and Answers || Discrete Mathematics GK Questions and Answers || GK on Discrete Mathematics

Set Theory and Relations Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications