I'm trying to figure out how to determine if a set is well-founded. From my class I am given this:

Suppose (S, $\le$) is a Partial Order Set:

$\le$ is said to be Well-Founded $\iff$ every nonempty subset of S has a minimal element (the minimal condition). This definition is equivalent to the following one: There is no infinite descending sequence, i.e., there is no infinite subset {$x_1$, $x_2$, $x_3$, ... } such that ... $\le$ $x_3$ $\le$ $x_2$ $\le$ $x_1$

Pretty much I don't understand the above. There's also Well-Ordered, but to my understanding from my class, it's pretty much the same as the above, except the set is a Total Ordered Set instead of a Partial Order Set. In other words, Total Ordered Set + Well-Founded = Well-Ordered.

Here's an example I hope someone could help me work through and understand:

Is this relation set Well-Founded, Well-Ordered, or Neither?
($\Bbb N$, $\le$)
This set is reflexive, transitive, and antisymmetric. Thus it is a Partial Ordered Set. Furthermore, the set is a Total Order Set because for every two elements, they are comparable.

After this I'm stuck.

Thanks for the help in advance!

EDIT: Gonna try at Asaf Karagila's hint

Proof by induction:
Suppose that $A$ is a subset of $\Bbb N$ without a minimal element

$0 \notin A$
Because for the minimal element implication, $0 \le 0 \Rightarrow 0=0$, is true, and for all other implications
($1 \le 0 \Rightarrow 1=0, 2 \le 0 \Rightarrow 2=0, ...)$
The implication is true (since the left inequality is false; implication is always true)

Assume $n \notin A$
This means $n$ is a minimal element. For $n$ to be a minimal element, any element smaller than $n$ (such as $n-1, n-2, ...$) does not exist in A. If they did, for example $(n-1)$, we would find the implication for the minimal element, $(n-1) \le n \Rightarrow$ n = (n-1) false, which would make $n$ not a minimal element, causing it to exist in A.

$(n+1) \notin A$ Proof:
The previous assumption causes (n+1) to be the smallest element. If $(n+1)$ is the smallest element, we can see that the Minimal Element Implication is true for all cases.
$(n+1) \le (n+1) \Rightarrow (n+1)=(n+1)$   True
$(n+2) \le (n+1) \Rightarrow (n+1)=(n+2)$   True
(Left side is false, causing implication to be true)

Therefore, $\Bbb N\cap A=\varnothing$. Or in other words, there are no nonempty subsets without a Minimal Element

That was my shot at it. It might sound a little weird/being a bit wrong, but I tried.


HINT: Suppose that $A$ is a subset of $\Bbb N$ without a minimal element. Prove by induction on $n$ that $A$ is empty (clearly $0\notin A$; and if $n\notin A$ conclude somehow that $n+1\notin A$; therefore $\Bbb N\cap A=\varnothing$).

  • $\begingroup$ Just gave a whack at it in the edit, would've tried to do it sooner but I had to think it out and then write it out (kinda slow at the symbols) $\endgroup$ – Matt Feb 17 '14 at 6:36

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.