During the last week I kept on thinking about what looked an easy problem at a first glance.
Let $(X,\succsim)$ be a preordered set, and define $\mathcal{L}(\succsim)$ as the set of all complete preorders that extend $\succsim$. Define $\dim(X,\succsim)$ as the smallest positive integer $k$ such that $\succsim = R_1 \cap \cdots \cap R_k$ for some $R_i \in \mathcal{L}(\succsim)$, with $i=1,\cdots,k$.
Show that $\dim(X,\succsim)\leq|X^2|$.
In order to attack the problem, first of all I took a look at $\dim(X,X^2)$ and $\dim(X,\Delta_X)$, where $\Delta_X$ is the diagonal relation. In this question I got a feedback on my conclusions: indeed $\dim(X,X^2)=1$ and $\dim(X,\Delta_X)=2$. The interesting case is $\dim(X,\Delta_X)$, because this is the one that gave me a bit of intuition on how to attack the problem that I present now.
Given a $\Delta_X$, we have that $\dim(X,\Delta_X)=2$, because we can imagine all the elements of the diagonal relation (let's call them $x_1,\cdots,x_n$) separated. I literally imagine $n$ loops, one for each element, that are all unrelated. This is a preorder. In order to make it a complete preorder we start to connect them. Now, we can have in the family of complete preorders that extend the original preorder two complete preorders:
- one in which all the arrows move from $x_1$ to $x_n$,
- and another in which the arrows move in the opposite direction.
Here, the direction of the arrows is not such a big problem, so it is without loss of generality. Interestingly, if we intersect those two complete preorders we come up with the original preorder. Thus, $\dim(X,\Delta_X)=2$.
Focusing now on the original problem of $\dim(X,\succsim)\leq|X^2|$, I think that I have two problems:
1) I am not sure what the question is really about. Indeed, I think that - stricly speaking - the question is all about proving the (probably) trivial result that in principle $\dim(X,\succsim)$ cannot be bigger than $|X^2|$. So we should prove it by contradiction, coming up with the fact that $|X^2|$ represents the biggest possible numbers of connection we can have on a finite set.
[Not sure, if I expressed this idea properly, so feel free to correct me]
However, another possible way of looking as this problem is that what we really have to prove is that $|X^2|$ is the upper bound of $\dim(X,\succsim)$. And here, part of my problems get serious...
2) ...because I cannot see how it can be that $\dim(X,\succsim)>2$. This is the case even if I found myself downloading most of the papers written on the topic during the last fifty years (yep, I am kinda perfectionist, so when I do not understand, I find myself trying to read every possible paper on a topic... this is the case also because I am basically self-taught). So, the point here is that I cannot see how $\dim(X,\succsim)>2$, because I can apply the procedure I used to come up with $\dim(X,\Delta_X)=2$ basically always. In other words, I can always find a relation that completes another with some arrows, and another that completes the very same relation with arrows of the opposite direction, coming up with the intersection of the two complete relation equal to the original incomplete relation.
In the end, sorry for this long post, for a probably easy question. I guess that some of my problems can be related to my idea of extension of a preorder or a poset. Anyway, I am positive about the fact that with your help I will find what my problems are all about.
Looking forward to any feedback.
Thanks in advance.
PS: I add the tag of "Graph Theory", because I tried to use a lot of that kind of intuition to figure out what the problem is all about, and I am sure that having a feedback from that point of view on this issue can be really helpful (both from a pedagogical and theoretical perspective).
Edit:
I added the following picture in order to show what is the problem I still have, beyond kind and comprehensive Brian M.Scott's answer.
Let's say this is an Hasse diagram of a poset, so let's try to focus on the dimension of posets instead of preorders, like in my original problem. In order to make this poset complete (so, to come up with a linear extension of it) I can add a connection that moves from $b$ to $c$ ($bRc$) and another from $a$ to $c$ ($aRc$). Let's call this linear extension $R_1$. Now, let's come up with a new linear extension that moves from the same Hasse diagram, but that has connections that move in the opposite directions (which means that we have $cRa$ and $cRb$). Let's call this new linear extension $R_2$. If we intersect the two linear extension we built up, the result is the original poset.
What seems to me is that we can come up with this trick almost always... however, Brian M.Scott pointed me out that I should see this doesn't work even from $n=4$, where $n$ is the cardinality of the poset.
Exactly, what am I missing that should be really obvious?
I am really sorry for this late edit and by this dumb question, but I don't see how to solve this problem.
Really thanks a lot for any feedback.
Let me start by exhibiting a partial order of dimension $n$ for an arbitrary positive integer $n$. Let $X=\{1,2,\dots,n\}$. For $k\in X$ let $S_k=\{k\}$ and $C_k=X\setminus\{k\}$, and let $$\mathscr{X}=\{S_k:k\in X\}\cup\{C_k:k\in X\}\;;$$ I claim that $\langle\mathscr{X},\subseteq\rangle$ is a partial order of dimension $n$.
If $n=1$, then $\mathscr{X}=\big\{\{1\},\varnothing\big\}$, and $\langle\mathscr{X},\subseteq\rangle$ is clearly already a linear order, so we may assume that $n>1$. For $k\in X$ define $\prec_k$ as follows:
Informally, $\prec_k$ orders the sets $S_\ell$ with $\ell\in C_k$ first, in numerical order by subscript; these are followed by $C_k$, which is followed by $S_k$, which is followed by the sets $C_\ell$ with $\ell\in C_k$ in numerical order by subscript. It’s routine to check that $\prec_k$ is a strict linear order on $\mathscr{X}$.
Suppose that $A,B\in\mathscr{X}$ and $A\prec_i B$ for each $i\in X$. Let $k,\ell\in X$; then $S_k\not\prec_k S_\ell$ and $C_k\not\prec_\ell C_\ell$. Moreover, $S_k\prec C_\ell$ iff $k\ne\ell$, and $C_k\prec_k S_\ell$ iff $k=\ell$. Suppose that $A=C_k$ and $B=S_k$ for some $k\in X$. By hypothesis $n>1$, so there is some $\ell\in X\setminus\{k\}$. But then $A=C_k\not\prec_\ell S_k=B$, which is impossible. Thus, there are distinct $k,\ell\in X$ such that $A=S_k$ and $B=C_\ell$ and hence $A\subseteq B$.
Conversely, if $A,B\in\mathscr{X}$ and $A\subsetneqq B$, there are distinct $k,\ell\in X$ such that $A=S_k$ and $B=C_\ell$, and it’s straightforward to check that $A\prec_i B$ for all $i\in X$. Thus, the relation $\subseteq$ on $\mathscr{X}$ is the intersection of the linear orders $\preceq_k$ for $k\in X$ and is therefore of dimension at most $n$.
For each $k\in X$ we have $S_k\nsubseteq C_k\nsubseteq S_k$. If $\prec$ is any strict linear order on $\mathscr{X}$, either $S_k\prec C_k$ or $C_k\prec S_k$. Thus, if $\subsetneqq$ is the intersection of a family $\{\prec_\alpha:\alpha\in A\}$ of strict linear orders on $\mathscr{X}$, there must be distinct $\alpha,\beta\in A$ such that $S_k\prec_\alpha C_k$ and $C_k\prec_\beta S_k$. In particular, for each $k\in X$ there must be an $\alpha\in A$ such that $C_k\prec_\alpha S_k$.
Suppose that $k,\ell\in X$ with $k\ne\ell$, and suppose that $\prec$ is a strict linear order extending $\subsetneqq$ on $X$ such that $C_k\prec S_k$ and $C_\ell\prec S_\ell$. Since $S_k\subsetneqq C_\ell$ and $S_\ell\subsetneqq C_k$, we must have
$$C_k\prec S_k\prec C_\ell\prec S_\ell\prec C_k\;,$$
which is absurd. Thus, a strict linear order $\prec$ extending $\subsetneqq$ on $\mathscr{X}$ can satisfy $C_k\prec S_k$ for at most one $k\in X$, and it follows from the preceding paragraph that we need to intersect at least $n$ strict linear orders on $\mathscr{X}$ to get $\subsetneqq$. Thus, the dimension of $\langle\mathscr{X},\subseteq\rangle$ is precisely $n$.
(With a slight refinement of this argument one can actually show that for any set $X$, the dimension of the partial order $\langle\wp(X),\subseteq\rangle$ is $|X|$.)
For the actual result, let $P=\{\langle x,y\rangle\in X\times X:x\not\succeq y\text{ and }y\not\succeq x\}$; clearly $|P|\le\left|X^2\right|$. For each $p=\langle x,y\rangle\in P$ let $\succeq_p$ be a linear order on $X$ extending $\succeq$ and such that $x\succeq_p y$. Show that
$$\succeq\;=\;\bigcap_{p\in P}\succeq_p\;.$$