Web Page

Syllabus: Sets, Relations, Functions, Partial orders, Lattices, Monoids, Groups.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum} \\\hline\textbf{1 Mark Count}&0&1&2&1&1&0&2&0&0&0&0.77&2 \\\hline\textbf{2 Marks Count}&2&1&0&0&1&1&0&1&2&0&0.88&2 \\\hline\textbf{Total Marks}&4&3&2&1&3&2&2&2&4&\bf{1}&\bf{2.55}&\bf{4}\\\hline \end{array}}}$$

# Recent questions in Set Theory & Algebra

1
Consider the following sets, where $n \geq 2$: $S_1$: Set of all $n \times n$ matrices with entries from the set $\{ a, b, c\}$ $S_2$: Set of all functions from the set $\{0,1,2, \dots, n^2-1\}$ to the set $\{0, 1, 2\}$ Which of the following ... to $S_2$ There exists a surjection from $S_1$ to $S_2$ There exists a bijection from $S_1$ to $S_2$ There does not exist an injection from $S_1$ to $S_2$
2
For two $n$-dimensional real vectors $P$ and $Q$, the operation $s(P,Q)$ is defined as follows: $s(P,Q) = \displaystyle \sum_{i=1}^n (P[i] \cdot Q[i])$ Let $\mathcal{L}$ be a set of $10$-dimensional non-zero real vectors such that for every pair of distinct vectors $P,Q \in \mathcal{L}$, $s(P,Q)=0$. What is the maximum cardinality possible for the set $\mathcal{L}$? $9$ $10$ $11$ $100$
3
Let $G$ be a group of order $6$, and $H$ be a subgroup of $G$ such that $1<|H|<6$. Which one of the following options is correct? Both $G$ and $H$ are always cyclic $G$ may not be cyclic, but $H$ is always cyclic $G$ is always cyclic, but $H$ may not be cyclic Both $G$ and $H$ may not be cyclic
4
A relation $R$ is said to be circular if $a\text{R}b$ and $b\text{R}c$ together imply $c\text{R}a$. Which of the following options is/are correct? If a relation $S$ is reflexive and symmetric, then $S$ is an equivalence relation. If a relation $S$ ... $S$ is an equivalence relation. If a relation $S$ is transitive and circular, then $S$ is an equivalence relation.
1 vote
5
The number of positive integers not exceeding $100$ that are either odd or the square of an integer is _______ $63$ $59$ $55$ $50$
1 vote
6
Show that if $S$ is a set, then there does not exist an onto function $f$ from $S$ to $P(S),$ the power set of $S$. Conclude that $\mid S\mid < \mid P(S)\mid .$ This result is known as Cantor’s theorem. [Hint: Suppose such a function $f$ existed. Let $T = \{s \in S \mid s \notin f (s)\}$ and show that no element $s$ can exist for which $f (s) = T.]$
7
We say that a function is computable if there is a computer program that finds the values of this function. Use question $37$ and $38$ to show that there are functions that are not computable.
1 vote
8
Show that the set of functions from the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is uncountable. [Hint: First set up a one-to-one correspondence between the set of real numbers between $0$ and $1$ and a subset of these functions. Do this by associating to the real number $0.\:d_{1}d_{2} \dots d_{n}\dots$ the function $f$ with $f (n) = dn.]$
9
Show that the set of all computer programs in a particular programming language is countable. [Hint: A computer program written in a programming language can be thought of as a string of symbols from a finite alphabet.]
10
Show that there is a one-to-one correspondence from the set of subsets of the positive integers to the set real numbers between $0$ and $1$. Use this result and question $34$ and $35$ to conclude that $ℵ_{0} < \mid P(Z^{+})\mid =\mid R\mid.\:[$Hint: Look at the first part of the hint for Exercise $35.]$
11
Show that there is no one-to-one correspondence from the set of positive integers to the power set of the set of positive integers. [Hint: Assume that there is such a one-to-one correspondence. Represent a subset of the set of positive integers as an infinite bit string with ... complement of the $ith$ bit of the $ith$ string in the list. Show that this new bit string cannot appear in the list.]
12
Show that $(0, 1)$ and $R$ have the same cardinality. [Hint: Use the Schröder-Bernstein theorem.]
13
Use the Schröder-Bernstein theorem to show that $(0, 1)$ and $[0, 1]$ have the same cardinality.
14
Show that when you substitute $(3n + 1)^{2}$ for each occurrence of $n$ and $(3m + 1)^{2}$ for each occurrence of m in the right-hand side of the formula for the function $f (m, n)$ in question $31,$ you obtain a one-to-one polynomial function $Z \times Z \rightarrow Z.$ It is an open question whether there is a one-to-one polynomial function $Q \times Q \rightarrow Q.$
15
Show that $Z^{+} \times Z^{+}$ is countable by showing that the polynomial function $f : Z^{+} \times Z^{+}\rightarrow Z^{+}$ with $f(m, n) = \dfrac{(m + n − 2)(m + n − 1)}{2} + m$ is one-to one and onto.
16
Show that the set of real numbers that are solutions of quadratic equations $ax^{2} + bx + c = 0,$ where $a, b,$ and $c$ are integers, is countable.
17
Show that the set of all finite bit strings is countable.
Show that the set $Z^{+} \times Z^{+}$ is countable.
Use question $25$ to provide a proof different from that in the text that the set of rational numbers is countable. [Hint: Show that you can express a rational number as a string of digits with a slash and possibly a minus sign.]