Question

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

• A. If for all \(a\in\mathbb N\), the set \(R_a\) is infinite then cardinality of \(R\) is larger than that of \(R_a\)
• B. If for each \(a\in\mathbb N\), the set \(R_a=\{b\in\mathbb N:(a,b)\in R\}\) has cardinality at most \(1\), then \(R\) represents a function \(f:\mathbb N\to\mathbb N\)
• C. If for some \(a\in\mathbb N\), the set \(R_a\) is infinite then \(R_a\) and \(R\) have same cardinality
• D. If for each \(b\in\mathbb N\), the set \(R_b=\{a\in\mathbb N:(a,b)\in R\}\) has cardinality at most \(1\), then \(R\) represents a function

Hint:

Any infinite subset of \(\mathbb N\) has cardinality \(\aleph_0\). Therefore all countably infinite sets have the same cardinality.

Answer 1

The Correct Option is C

Step 1: Recall the relevant cardinality facts.
Both $\mathbb N$ and $\mathbb N\times\mathbb N$ are countably infinite, and any infinite subset of a countable set is again countably infinite (cardinality $\aleph_0$).
Step 2: Focus on option 3.
It claims: if some row $R_a=\{b:(a,b)\in R\}$ is infinite, then $R_a$ and $R$ have the same cardinality.
Step 3: Bound $R_a$ from above.
Since $R_a\subseteq\mathbb N$ and is infinite, $|R_a|=\aleph_0$.
Step 4: Bound $R$.
Since $R\subseteq\mathbb N\times\mathbb N$, we have $|R|\le\aleph_0$. But $R$ contains the infinite subset $R_a$, so $|R|\ge\aleph_0$. Hence $|R|=\aleph_0=|R_a|$. So option 3 is true.
Step 5: Reject options that fail.
Option 1 is false: two countably infinite sets can have equal cardinality, not strictly larger. Options 2 and 4 fail because bounding row or column sizes by $1$ does not guarantee a value for every input, so $R$ need not be a total function.
Step 6: Conclude.
Only option 3 is necessarily true.
\[ \boxed{\text{If for some } a\in\mathbb N,\ R_a \text{ is infinite then } R_a \text{ and } R \text{ have same cardinality}} \]