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 cardinality facts.
Both \[ \mathbb N \quad\text{and}\quad \mathbb N\times\mathbb N \] are countably infinite sets. Any infinite subset of a countable set is also countably infinite.

Step 2: Analyze option (C).
Suppose for some \(a\in\mathbb N\), \[ R_a = \{b:(a,b)\in R\} \] is infinite. Since \(R_a\subseteq \mathbb N\), \[ |R_a|=\aleph_0. \] Also, \[ R\subseteq \mathbb N\times\mathbb N. \] Therefore \(R\) is at most countably infinite. Since \(R\) contains the infinite subset \(R_a\), \[ |R|=\aleph_0. \] Hence \[ |R_a|=|R|. \] Thus statement (C) is necessarily true.

Step 3: Check other options.
Option (B) is not sufficient for a function because existence is not guaranteed for every element of \(\mathbb N\). Option (D) describes injectivity conditions, not necessarily a function. Option (A) is false because both sets may have the same countable cardinality. Therefore, \[ \boxed{\text{Option (C)}} \]