**Set Theory**

Set Theory is undoubtedly one of the easiest and highly scoring topics in GATE. Attaining a certain degree of proficiency in this unit can immensely help you to boost your score in GATE.

This is a unit in which maximum output can be achieved by putting in minimal efforts.

With a view to make your preparation more effective for GATE, we have brought forward this post which will provide insights into all aspects associated with Set Theory.

You can download notes and solved examples from GATE on set Theory.

**SOLVED EXAMPLES From GATE**

Start Test

**Question 1**:

Compute the minimum number of ordered pairs of non-negative numbers which must be chosen to ensure that the two pairs (p, q) and (s, t) in the chosen set such that

“p ≡ s mod 3″ and “q ≡ t mod 5″

- 4
- 6
- 16
- 24

**Solution: Option (III) is correct**

**Explanation:**

p ≡ s mod 3 (given)

Therefore, p can be any one of the values: 0, 1, 2

q ≡ t mod 5 (given)

Therefore, q can be any one of the values: 0, 1, 2, 3, 4

Therefore, Ordered Pairs for (p, q) are

(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)

Therefore**,** Ordered Pair (p, q) has 15 combinations and ordered pair (s, t) has 1 combination

Therefore, Total Combinations = 15 + 1 = 16

**Must Read : **What is GATE 2017 Guarantee Pack? What is the Benefit of Availing It?

**Question 2**:

For the set N of Natural numbers and a Binary operation defined as f: N x N → N, an element z ∊ N is known as the identity for f in case the following condition holds:

f(a, z) = a = f(z, a), for all a ∊ N

Among the following alternatives, which binary operations have an identity?

- f(x, y) = x + y – 3

- f(x, y) = max(x, y)

- f(x, y) = x
^{y}

- I and II only
- II and III only
- I and III only
- None of these

**Solution: The correct option is (A)**

**Explanation:**

- f(x, y) = x+y-3

x= y+x-3

- y=3

Therefore, the identity elements is 3

- f(x, y) = max(x, y)

x=max(y, x)

=> y=1

Therefore, the identity elements is 1

- f(x, y) = x ^ y is not same as f(y, x) = y ^ x

Therefore, no identity element

** **

Start Test

**Question 3.**** **

Compute the number of onto functions (Surjective functions) from

Set P = {1, 2, 3, 4} to Set Q = {a, b, c}

- 36
- 64
- 81
- 72

**Solution**: The correct option is (A)

**Explanation**:

A function f from P to Q is referred to as onto in case for all ‘q’ in Q there is an ‘p’ in P such that f(p) = q.

All elements in Q are used in Onto Functions.

Every Onto function sends two elements of {1, 2, 3, 4} to the same element of {a, b, c}

There are ^{4}C_{2} = 6 such pairs of elements

The pairs include {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}

For a given pair {i, j} ⊂ {1, 2, 3, 4},

3! onto functions are there such that f(i) = f(j).

Therefore, the total number of Onto functions = 6 * 6 = 36

**Question 4.**

Let P denote a set of elements. Compute the number of ordered pairs in the largest and the smallest equivalence relations on P?

- n and n
- n
^{2}and n - n
^{2 }and 0 - n and 1

**Solution**: The correct option is (B)

Explanation:

Assume an example set P = {1, 2, 3}

Equivalence relations must be Reflexive, Symmetric and Transitive

**Largest ordered set = p x p**

{(1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)} = 9 = n^{2}

**Smallest Ordered Set **

{(1, 1) (2, 2) (3, 3)} = 3= n

Must Read : Proven Preparation Strategy by GATE CSE -Topper (AIR -1) | PrepLadder

We are sure that this post will definitely familiarize you with all concepts associated with Set Theory and will surely prove effective in your preparation.

## Enroll in Mentor Program and Avail your Personalized Mentor for GATE 2017 Preparation and Doubts Clarification!

What aspirants need is the right approach along with concrete strategies to reach their goals. **GATE GUARANTEE PACK has been the choice of successful GATE toppers all over India.**

It is the perfect online tool to check your level of preparedness among st students preparing all over the country where you study under guidance of mentors.

** **