Let $R \subset N \times N$ . Which of the following statements is necessarily true?

Answer (Detailed Solution Below)View answer ▾

Answer: Option C — If for some $a \in N$ the set $R_{a}$ is infinite, then $R_{a}$ and $R$ have the same cardinality

Detailed Solution

Step 1 (A is not necessary): 'at most 1' allows $R_{a}$ to be empty, so some $a$ may have no image. Example $R = ϕ$ is not a function on $N$ .

Step 2 (B is not necessary): it restricts inputs per output, not outputs per input. Again $R = ϕ$ satisfies it.

Step 3 (C is true): $R_{a} \subseteq N$ is infinite, so it is countably infinite. $R \subseteq N \times N$ is countable and contains the infinite set $a \times R_{a}$ , so $R$ is countably infinite too. Same cardinality $ℵ_{0}$ .

Step 4 (D is false): even if every $R_{a}$ is infinite, $R \subseteq N \times N$ is still countable, so $∣ R ∣ = ∣ R_{a} ∣ = ℵ_{0}$ .

Quick tip

$N \times N$ is countable: every infinite subset has cardinality $ℵ_{0}$

💬 Discussions on this question

Ask a doubt ›

Still stuck on this question? Ask our faculty and fellow students — answers appear here.

Ask a doubt

Set Theory — Preparation

This question tests your understanding of Set Theory, a key topic in the Quantitative Aptitude section. The detailed solution above uses a step-by-step approach to show the reasoning, and where available, a shortcut that helps you solve similar questions in under 90 seconds during the actual exam.

A set is a well-defined collection of objects. Set theory covers types of sets (finite, infinite, empty, singleton, equal and equivalent sets), subsets and power sets, and operations on sets such as union, intersection, difference and complement. It also covers De Morgan's laws and the cardinality formula n(A union B) = n(A) + n(B) - n(A intersection B). In entrance exams, the most common questions are word problems about people who like one, two or three activities, solved with Venn diagrams and the cardinality formula. Questions also ask for the number of subsets of a set (2^n for a set with n elements) and test set notation and properties. Practise the set theory questions below. Each comes with a step-by-step solution and a Venn diagram where it helps.

‹ All Set Theory questions Browse all topics ›

Let $R \subset N \times N$ . Which of the following statements is necessarily true?

💬 Discussions on this question

More Set Theory Questions

More Quantitative Aptitude Questions

Set Theory — Preparation

Let R⊂N×N. Which of the following statements is necessarily true?

💬 Discussions on this question

More Set Theory Questions

More Quantitative Aptitude Questions

Set Theory — Preparation

Let $R \subset N \times N$ . Which of the following statements is necessarily true?