Exams › GATE › Engineering Mathematics

Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S, we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements: S1: There is a subset of S that is larger than every other subset. S2: There is a subset of S that is smaller than every other subset. Which one of the following is correct?

1. Both S1 and S2 are true
2. S1 is true and S2 is false
3. S2 is true and S1 is false
4. Neither S1 nor S2 is true

Correct answer: Both S1 and S2 are true

Solution

This relation is essentially lexicographic order on subsets when elements are considered in increasing order. The subset containing the smallest possible differing element is larger, so the full set is the maximum and the empty set is the minimum. Hence both statements are true.

Related GATE Engineering Mathematics questions

• Let p and q be two propositions. Consider the following two formulae in propositional logic: S1: (¬p ∧ (p ∨ q)) → q S2: q → (¬p ∧ (p ∨ q)) Which of the following is correct?
• How many different non-isomorphic abelian groups of order 4 are there?
• Let \(\mathrm{Graph}(x)\) be a predicate denoting that \(x\) is a graph, and let \(\mathrm{Connected}(x)\) be a predicate denoting that \(x\) is connected. Which of the following first-order logic sentences does NOT represent the statement: “Not every graph is connected”?
• Suppose we uniformly and randomly select a permutation from the \(20!\) permutations of \(1,2,3,\ldots,20\). What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?
• Statement for Linked Answer Questions 78 and 79: Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. Which of the following recurrences does $x_n$ satisfy?
• Let \(G=(V,E)\) be a graph. Define \(\xi(G)=\sum r_i d_i^2\), where \(r_i\) is the number of vertices of degree \(d_i\) in \(G\). If \(S\) and \(T\) are two different trees with \(\xi(S)=\xi(T)\), then:

⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →