0
$\begingroup$

Given an arbitrary partial order $P=(X,R)$ if for any $a,b\in X$ with $(a,b)\not\in R$ and $(b,a)\not\in R$ we define $R'=R\cup\{x\in X:(x,a)\in R\}\times \{x\in X:(b,x)\in R\}$ then I can show that $P'=(X,R')$ is an order extension of $P$ and by repeating this processes if $X$ is finite, I can then obtain all linear extensions, and show the intersection of them is equal to $P$. However my argument only works for finite partial orders, so with all of that said how can I prove every uncountable partial order is the intersection of all of its linear extenstions?

$\endgroup$
  • $\begingroup$ @Andrés: I'm not sure about the AC tag... $\endgroup$ – Asaf Karagila Feb 9 at 15:19
  • $\begingroup$ @Asaf You need choice to find linear extensions at all. It seems more appropriate than 'set theory', the tag that was used previously but which is too vague in this context. $\endgroup$ – Andrés E. Caicedo Feb 9 at 15:51
  • $\begingroup$ @Andrés: Sure, but if we start tagging under AC all questions where choice is necessary, we're gonna get a lot on our hands. $\endgroup$ – Asaf Karagila Feb 9 at 17:01
  • $\begingroup$ @Asaf I definitely agree. It just felt less aggressive than simply removing the set theory tag(s). I mean, if there was any sense to it, the AC tag was the right one to use. I just didn't want to presume that tags had been originally assigned senselessly. $\endgroup$ – Andrés E. Caicedo Feb 9 at 17:11
2
$\begingroup$

"Uncountable" has nothning to do with it; every partial order, whether finite, uncountable, or countably infinite, is the intersection of all its linear intersections.

What you need to show, of course, is that if $a$ and $b$ are two incomparable elements in the poset $P=(X,R)$, then there is a linear order $T$ of $X$ such that $R\subseteq T$ and $(a,b)\in T$ (so that $(b,a)\notin T$). You can do this in two steps.

  1. Construct a partial order $S$ of $X$ suth that $R\subseteq S$ and $(a,b)\in S$.

  2. Construct a linear order $T$ of $X$ such that $S\subseteq T$.

For step 1, let $S$ be the transitive closure of $S\cup\{(a,b)\}$ and prove that it's a partial order.

For step 2, if you haven't already proved that every partial order can be extended to a linear order, use Zorn's lemma to show that there is a maximal partial order extending $S$. Then show (as in step 1) that a maximal partial order on a set $X$ must be a linear order.

$\endgroup$
  • $\begingroup$ Thanks I understand that every partial order is equal to the intersection of its linear extensions, the reason I specified uncountable was because I was already able to give a contrusctive proof for the countable case. Also is there a way to show that the axiom of choice implies zorn's lemma without using ordinal numbers? $\endgroup$ – user3865391 Feb 9 at 3:01
  • $\begingroup$ I don't me. If you post that as a new question, I'm sure one of the set theory experts will give you an answer, or point to where it has already been asked and answered. $\endgroup$ – bof Feb 9 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.