I am currently dealing with a set theory problem where I am told to show that any well-founded partial ordering is also a well-ordering (in those words exactly, no other givens). I know I have the ability to solve this problem - the issue is, I am unsure exactly what a 'well-founded partial ordering' is. You see, by definition (at least, as I have learned them):

If $R \subseteq A \times A$ is a partial ordering, it is reflexive, transitive, and antisymmetric.

If $R \subseteq A \times A$ is well-founded, then $$\forall B \subseteq A(B \neq \emptyset \Rightarrow \exists x \in B \forall y \in B (\lnot yRx)).$$

(In other words, every nonempty subset of $A$ has a minimal element.)

The problem? For each $B$ and each minimal element $x \in B$, wouldn't this imply that $\lnot xRx$ for each of these minimal elements spanning across the various nonempty subsets of $A$? However, we stated that $R$ is a partial order, and hence reflexive (ergo $xRx$ for all $x \in A$). I see a contradiction here...

So is this entity known as a 'well-founded partial ordering' necessarily strict (read: irreflexive)? If so, why wouldn't the author have just stated that instead of calling it a 'well-founded partial ordering'?

Anyways, any clarification would be helpful from a set theory minded person. Also, not trying to be sarcastic or anything, I just don't see what good ambiguity brings to learning undergrad mathematics.

  • 1
    $\begingroup$ According to wikipedia, "In order theory, a partial order is called well-founded if the corresponding strict order is a well-founded relation." So given a partial order $R$ there is a strict order $S$ which is defined as $xSy$ iff $x\neq y$ and $xRy.$ This essentially means that your expression should end $\forall y\in B(y=x\lor \lnot yRx).$ en.wikipedia.org/wiki/Well-founded_relation $\endgroup$ – Thomas Andrews Oct 1 '19 at 17:24
  • 2
    $\begingroup$ On the other hand, it is not true that any well-founded partial ordering is a well-ordering, unless you have an unusual definition of well-ordering. $\endgroup$ – Thomas Andrews Oct 1 '19 at 17:28

There are two equivalent ways of defining a partial order on a set $A$:

(1) a partial order is a subset $R\subset A\times A$ such that $R$ is reflexive, anti-symmetric (for every $x,y \in A$ if $xRy$ and $yRx$ then $x=y$) and transitive.

(2) a partial order is a subset $R'\subset A\times A$ such that $R'$ is anti-reflexive (for every $x \in A$ it is the case that $x\not R'x$) and transitive.

Indeed, if you have an $R'$, the corresponding $R$ is $R' \cup \{(x,x):x\in A \}$ and if you have an $R$ you just remove the couples of the form $(x,x)$ in order to get the corresponding $R'$.

I guess that your definition of well-founded partial order is based on the definition (2).

  • $\begingroup$ Thank you. I whipped out Enderton's set theory book and it had 10x the clarification the class notes I was working out of had. In short, if R is a relation then R' is a transitive relation and R is a subset of R'. He also states R is well-founded implies R' is well-founded and a partial ordering on A. Lastly, he also states there are two equivalent ways of defining a partial order on a set A. Thanks again! $\endgroup$ – greycatbird Oct 1 '19 at 17:37

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.