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

We use the von Neumann convention $n = \{0,1,\dots,n-1\}$ (so each ordinal is the set of all smaller ones) and the Kuratowski pair $\langle x,y\rangle = \{\{x\},\{x,y\}\}$. Two facts drive everything: for ordinals the elements are nested ($0 \subseteq 1 \subseteq \dots$), so $a \cup b = \max\{a,b\}$, and $\bigcup$ of a set of nested ordinals returns the largest one.

(a) $\bigcup(n+1) = n$ — TRUE. Here $n+1 = \{0,1,\dots,n\}$, a chain of nested ordinals. Its union is the largest member: $\bigcup(n+1) = 0 \cup 1 \cup \dots \cup n = n.$ (Check $n=0$: $\bigcup 1 = \bigcup\{0\} = 0 = \varnothing$. ✓) This is the standard fact $\bigcup(\alpha+1)=\alpha$ for a successor ordinal.

(b) $\bigcup\bigcup\langle m,n\rangle = \max\{m,n\}$ — TRUE. Unfold the Kuratowski pair one $\bigcup$ at a time: $\bigcup\langle m,n\rangle = \bigcup\{\{m\},\{m,n\}\} = \{m\}\cup\{m,n\} = \{m,n\},$ $\bigcup\{m,n\} = m \cup n = \max\{m,n\}.$ So applying union twice peels off the pair structure and returns the larger coordinate.

(c) $m < n \iff m \in n$ — TRUE. This is the defining order on the von Neumann ordinals: $m < n$ exactly when $m$ is one of the elements $\{0,\dots,n-1\}$ of $n$, i.e. $m \in n$.

(d) $n+1 = n \cup \{n\}$ — TRUE. The successor is defined precisely this way: $n+1 = \{0,\dots,n-1,n\} = \{0,\dots,n-1\} \cup \{n\} = n \cup \{n\}$.

(e) $n$ is an $n$-element set — TRUE. By construction $n = \{0,1,\dots,n-1\}$ has exactly $n$ (distinct) elements. So as a set its cardinality is $n$.

(f) $\langle x,y\rangle \in \mathcal{P}(x\cup y)$ — FALSE. $\langle x,y\rangle \in \mathcal{P}(x\cup y)$ would mean $\langle x,y\rangle \subseteq x\cup y$, i.e. both elements $\{x\}$ and $\{x,y\}$ of the pair lie in $x\cup y$. But $\{x\}\in x\cup y$ requires $\{x\}\in x$ or $\{x\}\in y$, which fails in general. Concretely take $x=0,\ y=1$: then $x\cup y = 1 = \{0\}$, and $\langle 0,1\rangle = \{\{0\},\{0,1\}\}$; since $\{0,1\}\not\subseteq\{0\}$ we get $\{0,1\}\notin\{0\}$, so $\langle x,y\rangle\not\subseteq x\cup y$. The correct level is one power set higher: $\langle x,y\rangle \in \mathcal{P}\big(\mathcal{P}(x\cup y)\big),$ because $\{x\},\{x,y\}\subseteq x\cup y$ are subsets, hence elements of $\mathcal{P}(x\cup y)$.

Tally: (a),(b),(c),(d),(e) are true and only (f) is false, so 5 statements are correct → option 3.

Pitfall: A Kuratowski pair lives in $\mathcal{P}(\mathcal{P}(x\cup y))$, not in $\mathcal{P}(x\cup y)$ — its members are subsets of $x\cup y$, not elements of it. Dropping one power set is the trap in (f).