Show that $dim(X,\succeq)\leq |X^2|$ when $X$ is finite I am trying to prove that when $(X,\succeq)$ is a finite preorder, the $dim(X,\succeq)\leq |X^2|$.
Here's the full context (Exercise 11 (a)):



My idea of resolution was to show that any set of elements of $X^2$ can be created through the intersection of at most $n^2$ different sets. But since $\succeq$ is reflexive, it already has $n$ elements, namely $(x_1,x_1),\cdots,(x_n,x_n)$, so the number of sets required to make it (through intersections) is less than $n^2-n\leq |X^2|$.
I have two problems, though.


*

*Insecurity: I don't know if this idea is correct;

*Writing: I don't know how to translate that into math.


Can someone give me some help?
Thanks for helping!
 A: You’re looking in the right general direction, but you need to look a little closer at how individual pairs of elements of $X$ can behave.
Suppose that $\dim(X,\succeq)=k$, and that $\succeq=R_1\cap\ldots\cap R_k$, where each $R_i$ is a complete preorder extending $\succeq$. Consider a pair $\{x,y\}$ of (not necessarily distinct) elements of $X$. 


*

*If $x\succeq y$ and $y\succeq x$, then both $\langle x,y\rangle$ and $\langle y,x\rangle$ must belong to every $R_i$.  

*If $x\succeq y$ and $y\not\succeq x$, then $\langle x,y\rangle$ must belong to every $R_i$, but there must be at least one $i\in\{1,\ldots,k\}$ such that $\langle y,x\rangle\notin R_i$.  

*Similarly, if $x\not\succeq y$ and $y\succeq x$, then $\langle y,x\rangle$ must belong to every $R_i$, but there must be at least one $i$ such that $\langle x,y\rangle\notin R_i$.  

*Finally, the interesting case is when $x\not\succeq y$ and $y\not\succeq x$. Each $R_i$ must contain at least one of $\langle x,y\rangle$ and $\langle y,x\rangle$, but neither of these ordered pairs can belong to every $R_i$. Thus, there must be distinct $i,j\in\{1,\ldots,k\}$ such that $\langle x,y\rangle\in R_i\setminus R_j$ and $\langle y,x\rangle\in R_j\setminus R_i$.


None of these possibilities requires more than two complete extensions of $\succeq$. In fact, we can start with an $R_1$ that contains every ordered pair that must belong to all of the $R_i$, like the pairs $\langle x,x\rangle$. Then at worst we must add one more total extension for each pair of the second and third types and two more for each pair of the fourth type.
Let $n=|X|$. There are $\binom{n}2=\frac12n(n-1)$ pairs of distinct elements of $X$, so even if all of them are of the fourth type, we need to intersect at most
$$1+2\cdot\frac12n(n-1)=n^2-n+1\le n^2$$
complete extensions of $\succeq$ to get $\succeq$. (I am assuming here that $n\ge 1$.)
