# Equivalence between Minimality Conidition, Well-Founded Property, Descending-Chain-Condition, and Noertherin Induction

Let $(M, \preceq)$ denote a partially ordered set $M$ along with a partial order $\preceq$ on it.

Proof of the equivalence between:

A: Descending Chain Condition If ($\mathcal{C}$ is a decresasing chain in M) $\rightarrow$ ($\mathcal{C}$ is finite) More formally: For any chain $a_o \succeq a_1 \succeq ... a_i \succeq ...$, there exists a number n such that $a_n = a_{n+1} =...$

B: Well-Founded-Property: There does not exist an infinite strictly decreasing chain in M

C: Minimality Property: Every non-empty subset in M has a minimal element

condition 1) P(x) is true for all minimal elements x $\in$ M
condition 2) If P(z) is true $\forall$ z $\in$ M such that z $<$ y, for some y $\in$ M $\rightarrow$ P(y)


D: Noertherian Induction Property: (condition1 $\wedge$ condition2) $\rightarrow$ P(a) $\forall a \in M$

We will first prove $A \rightarrow B$ Proof by contradiction

Assume $A$ $\wedge \neg B$

Then we are assuming A, as well as the existence of an infinite descending chain in M. Let us call this chain $\mathcal{C}$ But by A, since $\mathcal{C}$ is a descending chain it should be finite, but by our assumption of $\neg B$ we are assuming otherwise.

proof of $B \rightarrow C$ Proof by contradiction

Assume $B$ $\wedge \neg C$

Let $\mathcal{C}$ be a non-empty subset of M such that there is no minimal element in $\mathcal{C}$. This set exists by assumption of $\neg C$.

Since $\mathcal{C}$ is not empty, there exists an $a_0 \in \mathcal{C}$.

If there does not exist a second element $a_1 \in \mathcal{C}$, then $a_0$ would constitute a minimal element (w.r.t $\mathcal{C}$). This would contradict assumption $C$.

Then $\mathcal{C}$ must contain more than one element.

Since $\mathcal{C}$ does not contain a minimal element, there must exist $a_1$ in $\mathcal{C}$ such that $a_o \succ a_1$ Since $a_1$ cannot be a minimal element there must exist $a_2$ in $\mathcal{C}$ such that $a_o \succ a_1 \succ a_2$

If there exists an $a_k$ in $\mathcal{C}$ such that $a_0 \succ a_1 \succ a_2 \succ ... \succ a_k$, for all $a_i \neq a_k \in \mathcal{C}$,then $a_k$ would constitue a minimal element. This would contradict assumption $B$.

Therefore, $\mathcal{C}$ does not have a minimal element, yet constitues an infinite strictly descending chain.

This is our final contradiction, as this contradicts assumption $B$.

We want to now prove $C \rightarrow D$

Assume $C \wedge \neg D$ Then we are assuming $C$ $\wedge$ [condition1 $\wedge$ condition2] $\wedge$ $[\exists a \in M$ such that $\neg$P(a)]

Let $P(x)$ be a propositional function that satisfies conditions 1 and 2

Let $\mathcal{X} = \{ x \in M \, | \, \neg P(x) \}.$

Our assumption of $\neg D$ assumes that $\mathcal{X}$ is not empty

Then by assumption $C$, every non-empty set has a minimal element. Thus there exists a minimal element, $x_0$ in $\mathcal{X}$

Since we are assuming condition1, P($x_0$) must hold.

This yields a contradiction as P($x_0$) holds, yet $x_0$ is in $\mathcal{X}$ which is defined to be such that $\neg$ P($x$) holds for all elements which are members.

The contradiction is that P($x_0$) and $\neg$ P($x_0$) cannot both hold.

Therefore, $\mathcal{X}$ cannot be non-empty, and therefore is empty. Thus, our condition of $\neg D$, that of: [condition1 $\wedge$ condition2] $\wedge$ $[\exists a \in M$ such that $\neg$P(a)], is contradicted

We want to now prove $D \rightarrow A$ Proof by contradiction

Assume $D \wedge \neg A$ Then we are assuming the Noertherian Induction Property as well as the negation of the Descending Chain Condition That is, we are assuming the Noertherian Induction Property and If ($\mathcal{C}$ is a decresasing chain in M) $\rightarrow$ ($\mathcal{C}$ is finite)

I am stuck for this last part of the proof.

So is what I have so far ok, and also can anyone help with the remaining piece? Thanks

• Well-foundedness should be formulated in terms of minimal elements, namely C in your list. In the absence of the axiom of choice A and B are not equivalent to C and D. – Asaf Karagila May 12 '16 at 7:04

Here is a hint for $D\implies A$: We are going to prove its contraposition. Assume that there is an infinite decreasing sequence $A=\{a_1,a_2,\cdots\}$ and consider the proposition $x\not\in A$. Every minimal element is not in $A$. Moreover if $y\in A$ then it has a predecessor $z\in A$, and its contrapositive is the condition 2 of your statement of Noetherian induction. However not every element satisfies $x\notin A$.
• @Boolean_functions I refer the previous statement of that. You can see that the contrapositive of "$y\in A$ has a predecessor $z\in A$ is "if no predecessor of $y$ is in $A$ then $y\not\in A$". – Hanul Jeon May 12 '16 at 7:55