سوال ۹۸ کنکور ارشد علوم کامپیوتر ۱۳۹۸

We must find the one statement whose proof goes through in plain ZF, without any appeal to the Axiom of Choice (AC). The recurring theme is: choosing one element from each set in some family. AC is needed exactly when there is no uniform rule for the choice; it becomes unnecessary as soon as the underlying sets are already well-orderable, because then "take the least element" is a definable choice rule.

Option 3 — the correct answer (no AC needed). This asks for a choice function on the nonempty subsets of $\mathbb{N}$: one element selected from every nonempty $X \subseteq \mathbb{N}$. But $\mathbb{N}$ carries its canonical well-order $<$, so we can define the choice function explicitly: $f(X) = \min(X).$ Every nonempty subset of $\mathbb{N}$ has a least element (well-ordering of $\mathbb{N}$ is a theorem of ZF, indeed of induction), so $f$ is a total, definable function with $f(X) \in X$. No choice principle is invoked — the selection rule is given outright.

Option 2 — needs AC (it is AC). "Every set admits a well-ordering" is the Well-Ordering Theorem, which Zermelo proved to be equivalent to the Axiom of Choice. So its proof requires AC by definition.

Option 4 — needs AC. A family of pairwise-disjoint nonempty sets, together with a set $C$ meeting each member in exactly one point, is precisely a transversal / choice set. "Every family of pairwise-disjoint nonempty sets has a transversal" is one of the classical equivalent formulations of AC (the multiplicative axiom). Here the sets are arbitrary, with no given well-order, so AC is essential.

Option 1 — needs (a weak form of) AC. The completeness theorem for first-order logic, in its general form over arbitrary languages, is equivalent to the Boolean Prime Ideal / Ultrafilter Lemma, a nontrivial weak choice principle; building a maximal consistent (Henkin) extension of an arbitrary theory uses choice. So in general it is not provable in ZF alone.

Options 1, 2, 4 all rest on choosing from families with no canonical order. Only Option 3 lives entirely inside the well-ordered set $\mathbb{N}$, where $\min$ supplies the choice for free.

Exam trick: A choice function over subsets of a well-orderable set (like $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, or any countable set) is definable as "take the least element" and needs no Axiom of Choice. AC only bites when the index family lacks a usable order — e.g. choosing from arbitrary sets of reals or from a general disjoint family.