# Given a rational $\succsim$ over a finite set $X$, show that there exists $x \in X$ such that $x \succsim y, \forall y \in X$

I have been able to show this constructively, but would like to prove it by induction. However, I am stuck with the induction step:

Consider $$\succsim$$ defined over $$X=\{x_1,...,x_n\}$$ and where without loss of generality $$x_1$$ is the element such that $$x_1 \succsim x, \forall x \in X$$. Now, consider adding element $$x_{n+1}$$ to the set. My reasoning is that since $$\succsim$$ is defined over the original $$X$$, there is nothing telling us that $$x_{n+1}$$ should be in a complete relation with the elements in $$X$$ (i.e. $$\succsim$$ is not defined over a bigger set).

Is this reasoning correct? In that case, I don't see how you could prove this by induction.

You are almost there, but I think you are starting in the wrong place. I think the key is as follows: we want to prove the claim for set $$X=\{x_1,\ldots,x_n\}$$.

Start with some $$X'\subseteq{X}$$ for which the claim is true. Such an $$X'$$ exists because the claim is true for the set $$\{x_1\}$$ (by completeness and reflexivity).

If $$X'=X$$ then we're done. If $$X'\neq X$$ then we proceed with induction:

Denote by $$\bar{x}$$ an $$x\in X'$$ such that $$\bar{x}\succsim y, \forall\ y\in X'$$.

Now construct a new set $$X''=X'\cup\{x_i\}$$, where $$x_i\in X\backslash X'$$. Because $$\succsim$$ is rational (preferences are complete) over $$X$$, we either have $$x_i\succsim \bar{x}$$ or $$\bar{x}\succsim x_i$$ or both. Thus, if the claim holds for $$X'$$ it also holds for $$X''$$.

We can repeat this inductive step until $$X''=X$$, which must happen after finitely many iterations because $$X$$ is finite.

• Thank you very much. Induction on subsets makes sense. – econ86 Oct 1 '19 at 15:25