PDA

View Full Version : Well Founded Sets


Mikemaths
Apr5-10, 11:13 AM
I am struggling to properly understand the concept of a well-founded set.

Is this well founded, d = {{x},{x,y},{x,y,z}}

because there exists an element of d i.e. {x} = e

such that d n e = 0 ???

vici10
Apr5-10, 02:44 PM
Well-foundness usually is related to a relation (order).

Well-foundness is generalization of well-order. The difference is that well-order is linear and well-found is not necessary linear, but is partial order.

The definition is:
The relation E on set P is well-founded if any non-empty subset has E-minimal element.
Now, very often the natural order(relation) for sets is belonging \in.

So in this case, in your example d is well-founded since any non-empty subset:
1){{x}},2) {{x,y}},3) {{x,y,z}}, 4){{x},{x,y}}, 5){{x},{x,y,z}}, 6){{x,y}, {x,y,z}} , 7){{x},{x,y},{x,y,z}} has a minimal elements such as:
1){x}, 2){x,y}, 3){x,y,z}, 4){x}, {x,y} (since {x} \notin {x,y} 5) {x}, {x,y,z} 6) {x,y} , {x,y,z} 7) {x}, {x,y} {x,y,z}

Notice that \in is partial order on your set d. That is why 4), 5) 6) and 7) have several minimal elements.

So d is well-founded but not well-ordered, since it is not linear ordered by \in.