Prove that inclusion is a "universal" partial order

232 Views Asked by At

I wanted to prove a theorem in my textbook which states that inclusion can be viewed as a "universal" partial ordering (how cool is that!). The theorem goes like this: Let $(X, \leq)$ be a partially ordered set. Then, there exists a family of sets $A \subseteq P(X)$ such that partially ordered sets $(X, \leq)$ and $(A, \subseteq |_A)$ are isomorphic. Note: $P(A)$ means power set of set $A$ and $\subseteq|_A$ means that the inclusion was restricted to $A$.
Proof. Define $f(x)=\{a \in X:a \leq x\}$ for every $x \in X$. First let's show that $f:X \rightarrow P(X)$ is injective. Assume that $f(x)=f(y)$, where $x,y \in X$. We see that $x \in f(x)$ because $\leq$ is reflexive by definition. Since $f(x)=f(y)$, $x \in f(y)$, so $x \leq y$. Conversely, $y \in f(y)$, but $f(x)=f(y)$, so $y \leq x$. By antisimmetric property of $\leq$, we get that $x \leq y$ and $y \leq x \iff x=y$. Hence, $f$ is indeed injective. Great. Now we would like to show that $f(x) \subseteq f(y) \iff x \leq y$. Let's define $A=f(X)$. Note that $f(x)$ is a set, so $f(X)$ is a set of sets a.k.a. a family of sets. Now we should probably use the definition of subset. $$f(x) \subseteq f(y) \iff \forall_\alpha (\alpha \in f(x) \Rightarrow \alpha \in f(y)).$$ We see that $\alpha \in f(x) \iff \alpha \leq x$ and $\alpha \in f(y) \iff \alpha \leq y$, thus $$\forall_\alpha (\alpha \in f(x) \Rightarrow \alpha \in f(y)) \iff \forall_\alpha(\alpha \leq x \Rightarrow \alpha \leq y) $$ I would like to show that this is equivalent to $x \leq y$, but I have no idea how to proceed from this point onward. It makes sense for the "standard" less or equal to relation, but I don't know how to prove it rigorously. I would really like to prove this think cause it's pretty awesome in my opinion.
EDIT: In case anyone was curious how to finish the proof (basing on the kindly provided answers below). First, show that $$\forall_\alpha (\alpha \leq x \Rightarrow \alpha \leq y) \Rightarrow x \leq y.$$ Assume $\forall_\alpha (\alpha \leq x \Rightarrow \alpha \leq y)$ and choose $\alpha = x$. By the associative property, $x \leq x$, so by assumption $x \leq y$.
Second, prove that $$x \leq y \Rightarrow \forall_\alpha (\alpha \leq x \Rightarrow \alpha \leq y).$$ Suppose that $x \leq y$. Definition of transitivity tells us that $\forall_\alpha (\alpha \leq x \wedge x\leq y \Rightarrow \alpha \leq y)$. Which, by assumption, reduces to $\forall_\alpha (\alpha \leq x \Rightarrow \alpha \leq y)$. QED

2

There are 2 best solutions below

0
On BEST ANSWER

Well done! You're really extremely close at this point. So what we can do is just prove the last equivalence in two steps, one for each direction. To prove that the statement implies that x is less than or equal to y, we just pick alpha to be equal to x (and use the reflexivity property of a partial order). For the other direction we can just apply the transitivity property.

0
On

If $x\le y$ and $\alpha\le x,$ then $\alpha\le y$ by transitivity. If for all $\alpha\le x$, $\alpha\le y,$ then, in particular, $x\le x$, so $x\le y.$