2
$\begingroup$

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.

Contradiction

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$

Proof by contradiction

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila May 12 '16 at 7:04
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you for your response. A bit confused on what you mean by "Moreover if y∈A then it has a predecessor z∈A, and its contrapositive is the condition 2 of your statement of Noetherian induction." What is 'its' referring to here? $\endgroup$ – Boolean_functions May 12 '16 at 4:58
  • $\begingroup$ @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$". $\endgroup$ – Hanul Jeon May 12 '16 at 7:55
  • $\begingroup$ Ah, figured it out. thanks $\endgroup$ – Boolean_functions May 14 '16 at 2:20

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.