GATE 2010 CS (CS1) – Question 13

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 1 mark · Multiple choice

How many reflexive relations exist on a five-element set?

$2^{10}$
$2^{15}$
$2^{20}$
$2^{25}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $2^{20}$

Explanation

There are 5²=25 possible ordered pairs. Reflexivity fixes all five diagonal pairs as present. Each of the remaining twenty pairs can independently be present or absent, giving 2²⁰ relations, C.

More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions

GATE 2015 CS (CS2) Q12 – Find the cardinality of the power set of 0,1,2,…,10.
GATE 2015 CS (CS2) Q13 – On positive integers, aRb iff a≠b and a,b have a common divisor greater than one. Which…
GATE 2015 CS (CS3) Q12 – U is the power set of S=1,2,3,4,5,6. T is cardinality, T′ complement in S, and T∖R set…
GATE 2015 CS (CS3) Q60 – On ordered pairs of positive integers, ((p,q),(r,s))∈R iff p−s=q−r. Which describes R?
GATE 2021 CS (CS2) Q21 – For n≥2, S1 contains all n×n matrices over a,b,c, and S2 contains all functions from…
GATE 2026 CS (CS2) Q26 – Let R be a binary relation on the set \1,2,,10\, where (x,y) R if the product xy is the…

All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →