Set Theory & Algebra · Discrete Mathematics · GATE CSE

Let $P$ be the partial order defined on the set {1,2,3,4} as follows: $P = \{(x, x) \mid x \in \{1,2,3,4\}\} \cup \{(1,2), (3,2), (3,4)\}$ The number ...

Let $A$ and $B$ be non-empty finite sets such that there exist one-to-one and onto functions (i) from $A$ to $B$ and (ii) from $A \times A$ to $A \cup...

Consider the following sets, where n > 2: S1: Set of all n x n matrices with entries from the set {a, b, c} S2: Set of all functions from the set ...

Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is ______.

Let R be the set of all binary relations on the set {1,2,3}. Suppose a relation is chosen from R at random. The probability that the chosen relation i...

Let G be an arbitrary group. Consider the following relations on G : R1: ∀a,b ∈ G, aR1b if and only if ∃g ∈ G such that a = g-1bg R2: ∀a,b ∈ G, aR2b...

Let U = {1, 2 ,..., n}. Let A = {(x, X) | x ∈ X, X ⊆ U}. Consider the following two statements on |A|. I. |A| = n2n–1 II. |A| = $$\sum\limits_{k = 1}^...

For a set A, the power set of A is denoted by 2A. If A = {5, {6}, {7}}, which of the following options are TRUE? I. $$\phi \in {2^A}$$ II. $$\phi \s...

Suppose $$𝑈$$ is the power set of the set $$S = \left\{ {1,2,3,4,5,6,} \right\}$$. For any $$T \in U,$$ let $$\left| T \right|$$ denote the number of...

Let $$𝑅$$ be the relation on the set of positive integers such that $$aRb$$ if and only if $$𝑎 $$ and $$𝑏$$ are distinct and have a common divisor ...

The cardinally of the power set of $$\left\{ {0,1,2,\,\,....,\,\,10} \right.\left. \, \right\}$$ is _____________.

Let $$X$$ and $$Y$$ be finite sets and $$f:X \to Y$$ be a function. Which one of the following statements is TRUE?

Which one of the following functions is continuous at $$x = 3$$?

A Binary operation $$ \oplus $$ on a set of integers is defined as $$x$$ $$ \oplus $$ $$y$$ $$ = {x^2} + {y^2}$$. Which one of the following statem...

What is the possible number of reflexive relations on a set $$5$$ elements?

Consider the set $$S = \left\{ {1,\,\omega ,\,{\omega ^2}} \right\},$$ where $$\omega $$ and $${{\omega ^2}}$$, are cube roots of unity. If $$ * $$ de...

Which one of the following in NOT necessarily a property of Group?

consider the binary relation $$R = \left\{ {\left( {x,y} \right),\,\left( {x,z} \right),\,\left( {z,x} \right),\,\left( {z,y} \right)} \right\}$$ on t...

If $$P, Q, R$$ are subsets of the universal set $$U$$, then $$\left( {P \cap Q \cap R} \right) \cup \left( {{P^c} \cap Q \cap R} \right) \cup {Q^c} \...

What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?

Let $$S$$ be a set6 of $$n$$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $$S$$ are

The set $$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$ under multiplication modulo 10 is not a group. Given below are four plausible rea...

For the set $$N$$ of natural numbers and a binary operation $$f:N \times N \to N$$, an element $$z \in N$$ is called an identity for $$f$$ if $$f\left...

Let $$X,. Y, Z$$ be sets of sizes $$x, y$$ and $$z$$ respectively. Let $$W = X x Y$$ and $$E$$ be the set of all subjects of $$W$$. The number ...

A relation $$R$$ is defined on ordered pairs of integers as follows: $$\left( {x,y} \right)R\left( {u,v} \right)\,if\,x < u$$ and $$y > v$$. Th...

The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is a group under multiplication modulo $$15$$. The inverse of $$4$$ and ...

Let $$f$$ be a function from a set $$A$$ to a set $$B$$, $$g$$ a function from $$B$$ to $$C$$, and $$h$$ a function from $$A$$ to $$C$$, such that $$h...

The following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \right\}, \prec } \right]$$ The poset is: ...

Let $$A$$, $$B$$ and $$C$$ be non-empty sets and let $$X = (A - B) - C$$ and $$Y = (A - C) - (B - C)$$ Which one of the following is TRUE?

Consider the binary relation: $$S = \left\{ {\left( {x,y} \right)|y = x + 1\,\,and\,\,x,y \in \left\{ {0,1,2,...} \right\}} \right\}$$ The reflexive ...

Let $${R_1}$$ be a relation from $$A = \left\{ {1,3,5,7} \right\}$$ to $$B = \left\{ {2,4,6,8} \right\}$$ and $${R_2}$$ be another relation from $$B$$...

The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (Note: power ($$2,$$ $$x$$) is s...

Consider the following relations: $${R_1}\,\,\left( {a,\,\,b} \right)\,\,\,iff\,\,\left( {a + b} \right)$$ is even over the set of integers $${R_2}\,\...

The number of binary relations on a set with $$n$$ elements is:

Let $${R_1}$$ and $${R_2}$$ be two equivalence relations on a set. Consider the following assertions: (i)$$\,\,\,\,{R_1} \cup {R_2}$$ is an euivalence...

Suppose $$A$$ is a finite set with $$n$$ elements. The number of elements in the Largest equivalence relation of $$A$$ is

The number of functions from an $$m$$ element set to an $$n$$ element set is

The number of equivalence relations on the set $$\left\{ {1,2,3,4} \right\}$$ is

Let $$A$$ and $$B$$ be sets and let $${A^c}$$ and $${B^c}$$ denote the complements of the sets $$A$$ and $$B$$. The set $$\left( {A - B} \right) \cup ...

Let $$X$$ $$X = \left\{ {2,3,6,12,24} \right\}$$. Let $$ \le $$ the partial order defined by $$x \le y$$ if $$x$$ divides $$y$$. The number of edges...

Suppose $$X$$ and $$Y$$ are sets and $$\left| X \right|$$ and $$\left| Y \right|$$ are their respective cardinalities. It is given that there are exac...

Which of the following statements is false?

Let $$R$$ be a symmetric and transitive relation on a set $$A$$. Then

The number of elements in the power set $$P(S)$$ of the set $$S = \left\{ {\left\{ \phi \right\},1,\left\{ {2,3} \right\}} \right\}$$ is

Let $${\rm A}$$ be a finite set of size $$n$$. The number of elements in the power set of $${\rm A} \times {\rm A}$$ is

Let $$S$$ be an infinite set and $${S_1},\,\,{S_2},....\,\,{S_n}$$ be sets such that $${S_1} \cup {S_2} \cup ....... \cup {S_n} = S$$. Then

(a) How many binary relations are there on a set A with n elements? (b) How many one - to - one functions are there from a set A with n elements onto ...

State whether the following statement are TRUE or FALSE: (a) The union of two equivalence relations is also an equivalence relation.

Let Zn be the group of integers {0, 1, 2, ..., n − 1} with addition modulo n as the group operation. The number of elements in the group Z2 × Z3 × Z4 ...

Consider the operators $\diamond$ and $\square$ defined by $a \diamond b=a+2 b, a \square b=a b$, for positive integers. Which of the following statem...

Let $$f:A \to B$$ be an onto (or surjective) function, where A and B are nonempty sets. Define an equivalence relation $$\sim$$ on the set A as $${a_1...

Let X be a set and 2$$^X$$ denote the powerset of X. Define a binary operation $$\Delta$$ on 2$$^X$$ as follows: $$A\Delta B=(A-B)\cup(B-A)$$. Let $$H...

Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is _______

A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?...

Consider the first order predicate formula φ: ∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))] Here 'a|b' denotes t...

Let N be the set of natural numbers. Consider the following sets. $$\,\,\,\,\,\,\,\,$$ $$P:$$ Set of Rational numbers (positive and negative) $$\,\,\...

Consider a set $$U$$ of $$23$$ different compounds in a Chemistry lab. There is a subset $$S$$ of $$U$$ of $$9$$ compounds, each of which reacts with ...

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

A function $$f:\,\,{N^ + } \to {N^ + },$$ defined on the set of positive integers $${N^ + },$$ satisfies the following properties: $$$\eqalign{ &am...

Let $$R$$ be a relation on the set of ordered pairs of positive integers such that $$\left( {\left( {p,q} \right),\left( {r,s} \right)} \right) \in R$...

The number of onto functions (subjective functions) from set $$X = \left\{ {1,2,3,4} \right\}$$ to set $$Y = \left\{ {a,b,c} \right\}$$ is __________...

Let $$X$$ and $$Y$$ denote the sets containing $$2$$ and $$20$$ distinct objects respectively and $$𝐹$$ denote the set of all possible functions defi...

Consider the following relation on subsets of the set S integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the mini...

There are two elements $$x, y$$ in a group $$\left( {G,\, * } \right)$$ such that every elements in the group can be written as a product of some numb...

Consider the set of all functions $$f:\left\{ {0,\,1,.....,2014} \right\} \to \left\{ {0,\,1,.....,2014} \right\}$$ such that $$f\left( {f\left( i \ri...

Let S denote the set of all functions $$f:\,{\{ 0,\,1\} ^4}\, \to \,\{ 0,\,1\} $$. Denote by N the number of functions from S to the set {0, 1}. The v...

How many onto (or subjective) functions are there form an n-element $$(n\, \ge \,2)$$ set to a 2-element set ?

For the compositive table of a cyclic group shown below Which one of the following choices is correct?...

How many different non-isomorphic Abelian groups of order 4 are there?

Consider the set of (column) vectors defined by $$X = \,\{ \,x\, \in \,{R^3}\,\left| {{x_1}\, + \,{x_2}\, + \,{x_3} = 0} \right.$$, where $${x^T} = \...

Consider the following Hasse diagrams. Which all of the above represent a lattice? ...

A partial order P is defined on the set of natural numbers as following. Herw x/y denotes integer division. i) (0, 0) $$ \in \,P$$. ii) (a, b) $$ \i...

Consider the set S = {a, b, c, d}. Consider the following 4 partitions $$\,{\pi _1},\,{\pi _2},\,{\pi _3},\,{\pi _4}$$ on $$S:\,{\pi _1} = \left\{ {\o...

Let S = {1, 2, 3,....., m} , m > 3. Let $${X_1},\,....,\,{X_n}$$ be subsets of S each of size 3. Define a function f from S to the set of natural n...

Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \subseteq \,N\,$$ and $$B\, \subseteq \,N\,$$, how many of the n! permuta...

Let E, F and G be finite sets. Let $$X = \,\left( {E\, \cap \,F\,} \right)\, - \,\left( {F\, \cap \,G\,} \right)$$ and $$Y = \,\left( {E\, - \left( ...

Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets $${S_1}$$ and $${S_2}$$ in C, either $${S...

Let R and S be any two equivalence relations on a non-emply set A. Which one of the following statements is TRUE?

Let f: $$\,B \to \,C$$ and g: $$\,A \to \,B$$ be two functions and let h = fog. Given that h is an onto function which one of the following is TRUE?

The inclusion of which of the following sets into S = { {1, 2}, 1, 2, 3}, {1, 3, 5}, {1, 2, 4}, {1, 2, 3, 4, 5} } Is necessary and sufficient to m...

The following is the incomplete operation table of a 4-element group. The last row of the table is ...

The binary relation $$S = \phi $$ (emply set) on set A = {1, 2, 3} is

Consider the following statements: S1: There exist infinite sets A, B, C such that $$A\, \cap \left( {B\, \cup \,C} \right)$$ is finite. S2: Ther...

Let $$f:\,A\, \to B$$ be a function, and let E and F be subsets of A. Consider the following statements about images. $$S1:\,f\,\left( {E\, \cup \,F}...

Let P(S) denote the power set of a set S. Which of the following is always true?

A relation R is defined on the set of integers as zRy if f (x + y) is even. Which of the following statements is true?

(a) Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof. ...

Let (A, *) be a semigroup. Furthermore, for every a and b in A, if $$a\, \ne \,b$$, then $$a\,*\,b \ne \,\,b\,*\,a$$. (a) Show that for every a in A ...

The binary relation R = {(1, 1)}, (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4) } on the set A = { 1, 2, 3, 4} is

Suppose A = {a, b, c, d} and $${\Pi _1}$$ is the following partition of A $${\Pi _1}\, = \,\{ \{ a,\,\,b,\,\,c\,\} \,,\,\{ d\} \,\} $$ (a) List the ...

Let R denote the set of real numbers. Let f: $$R\,x\,R \to \,R\,x\,R\,$$ be a bijective function defined by f (x, y ) = (x + y, x - y). The inverse fu...

Which one of the following is false?

Let R be a non-emply relation on a collection of sets defined by $${A^R}\,B $$ if and only if $$A\, \cap \,B\, = \,\phi $$. Then, (pick the true state...

Let A be the set of all nonsingular matrices over real numbers and let * be the matrix multiplication operator. Then

Some group (G, o) is known to be abelian. Then, which one of the following is true for G?

The transitive closure of the relation $$\left\{ {\left( {1,2} \right)\left( {2,3} \right)\left( {3,4} \right)\left( {5,4} \right)} \right\}$$ on th...

The complement(s) of the element 'a' in the lattice shown in Fig. is (are) ........... . ...

Let $$A$$ be a set of $$n\left( { > 0} \right)$$ elements. Let $${N_r}$$ be the number of binary relations on $$A$$ and Let $${N_r}$$ be the number...

(a) $$S = \left\{ { < 1,2 > ,\, < 2,1 > } \right\}$$ is binary relation on set $$A = \left\{ {1,2,3} \right\}$$. Is it irreflexive? Add th...

A multiset is an unordered collection of elements where elements may repeat ay number of times. The size of a multiset is the number of elements in it...

Let $$S = \left\{ {0,1,2,3,4,5,6,7} \right\}$$ and $$ \otimes $$ denote multiplication modulo $$8$$, that is, $$x \otimes y = \left( {xy} \right)$$ mo...

Let $${G_1}$$ and $${G_2}$$ be subgroups of a group $$G$$. (a) Show that $${G_1}\, \cap \,{G_2}$$ is also a subgroup of $$G$$. (b) $${\rm I}$$s $${G_...

(a) If G is a group of even order, then show that there exists an element $$a \ne e$$, the identifier $$g$$, such that $${a^2} = e$$ (b) Consider t...