# 原问题

For finite choice set $X$, show that if there exists a choice function $c(\cdot)$ which satisfies finitely non-emptiness and choice coherence, there exists a utility function $u:X\rightarrow \mathbb{R}$ such that $c(A)=\{x\in A:u(x)\geq u(y),\forall y\in A\}$ for $\forall A\subseteq X$.

# 一般证法

# 大帝证法

精妙至极

For the choice function:

$$c(\cdot): 2^X \rightarrow 2^X,$$

define

$$AC(x | B)=\{A \in 2^B | x\in c(A)\},$$

which means that, after the correspondence of $c(\cdot)$, all the elements in $AC(x | B)$ (in fact the subsets of $B$) are containing $x$.

Lemma. $\left \| AC(x | B) \right \| \leq 2^{k-1},k=\left \| B \right \|$

Proof: For $\forall x \in B$, the number of subsets containg $x$ is $2^{k-1}$. Then for $\forall x \in B, A=\{C \in 2^B| x \in C\}$, if $x \in c(A), \forall A$, which means that for all subsets containing $x$, $x$ is the chosen one. Thus the $AC(x | B)$ is identical to the family of all the sets containing $x$ (they are all subsets of $B$), $\left \| AC(x | B) \right \|=2^{k-1}.$ If $\exists x'\in B, \exists A,x' \notin c(A)$, which means that there exists subsets containing $x'$, $x'$ is not the chosen one, so that $\left \| AC(x | B) \right \| < 2^{k-1}.$

Then define the utility function $u(x)$:

$$u(x) = \left \| AC(x | A) \right \|, \text{for}\ \forall x \in A,\\ c(A) = \{x\in A | u(x) \geq u(y),\forall y \in A\}$$

Claim that

$$x \in c(A) \Leftrightarrow \left \| AC(x | A) \right \| \geq \left \| AC(y | A) \right \|, \text{for}\ \forall y \in A.$$

Proof:

("$\Rightarrow$") Without loss of generality, assume $\left \| A \right \| = k$. Then from the Lemma $\forall y \in A$, $\left \| AC(y | A) \right \| \leq 2^{k-1}$.

Meanwhile, $x \in c(A)$ means that $\left \| AC(x | A) \right \| = 2^{k-1}$.

Thus $\left \| AC(x | A) \right \| \geq \left \| AC(y | A) \right \|, \text{for}\ \forall y \in A$ holds.

("$\Leftarrow$") $\forall S \in 2^A, S \neq \emptyset$, from the finintely nonemptiness of the choice function, $c(S) \neq \emptyset$. Then $c(A\setminus \{x\}) \neq \emptyset$.

For $\forall y \in c(A\setminus\{x\})$, if $y \notin c(A)$, by the finintely nonemptiness of the choice function, $x \in c(A)$; if $y \in c(A)$, by the choice coherence of the choice function, $y$ is the chosen one in all subsets of $A$ which are containg $y$, $\left \| AC(y | A) \right \|=2^{k-1}$. We know that $\left \| AC(x | A) \right \| \geq \left \| AC(y | A) \right \|, \text{for}\ \forall y \in A$, then $\left \| AC(x | A) \right \| = 2^{k-1}$, which means that $x$ is also the chosen one in all subsets of $A$ which are containg $x$, thus $x \in c(A)$.

✔️三人行，必有我师焉。