| |
 |
|
|
Science Forum Index » Mathematics Forum » Well-founded relation
Page 1 of 1
|
| Author |
Message |
| Guest |
 Posted: Sat Apr 26, 2008 11:58 am |
|
|
|
|
A question on well-founded relations. Obviously, (IN, <) is a well-
founded relation. What about (IR+, <), where IR+ denotes all real
numbers >= 0. At first, I would say no since for any subset of IR
there is an infinite chain of descending elements. However, at the
same time every subset of IR has a minimal element: if (a, b) denotes
the subset of IR of all real numbers from a to b (inclusive), then
clearly a is the minimal element.
Where's my faulty thinking? |
|
|
| Back to top |
|
| Guest |
| Posted: Sat Apr 26, 2008 12:36 pm |
|
|
|
|
On 26 Apr., 23:18, José Carlos Santos <jcsan...@fc.up.pt> wrote:
Quote: On 26-04-2008 22:58, Whateve...@web.de wrote:
A question on well-founded relations. Obviously, (IN, <) is a well-
founded relation. What about (IR+, <), where IR+ denotes all real
numbers >= 0.
I don't know what you have in mind when you write about "well-founded
relations", but if < is not well-founded within the real numbers, then
even the set IR+ is not defined, right?!
I don't see what you mean. I am talking about well-founded relations
in the usual sense:
(1) Definition: A well-founded relation is a binary relation on a
set A such that
there are no infinite descending chains ... < a_i < · · · < a1 <
a0.
or, equivalently
(2) Let be a binary relation on a set A. The relation < is
well-founded iff any nonempty subset Q of A has a minimal element.
Quote: At first, I would say no since for any subset of IR
there is an infinite chain of descending elements.
Trivially false. Where do you get "an infinite chain of descending
elements" from {0}?
Ok, forget that. I mean that I can construct infinitely descending
chains, referring to definition (1).
Quote: However, at the
same time every subset of IR has a minimal element: if (a, b) denotes
the subset of IR of all real numbers from a to b (inclusive),
Bad choice of notation, since (a,b) stands for the set of all real
numbers _x_ such that a < x < b. The usual notation for what you want is
[a,b].
then clearly a is the minimal element.
How did you deduce from the (trivial) fact that every set of the form
[a,b] has a minimal element that "every subset of IR has a minimal
element"?
I meant that every subset of IR+ has a minimal element: if we consider
the subset [a,b] for example, then a is the minimal element of this
subset. This refers to definition (2).
So from definition (1) I get a "NO", from (2) I get a "YES". What's
wrong? |
|
|
| Back to top |
|
| Arturo Magidin |
| Posted: Sat Apr 26, 2008 3:05 pm |
|
|
|
Guest
|
In article <e7371eb6-b327-4464-ae05-9be2448a40e5@d45g2000hsc.googlegroups.com>,
<Whatever5k@web.de> wrote:
Quote: A question on well-founded relations. Obviously, (IN, <) is a well-
founded relation. What about (IR+, <), where IR+ denotes all real
numbers >= 0. At first, I would say no since for any subset of IR
there is an infinite chain of descending elements.
You don't need every subset of R to have an infinite descending
chain. (And it is not true that this holds anyway).
According to the definition you supply later, an order relation
on a set X is well-founded if and only if there are no infinite
descending chains in the set. It is enough for you to find ONE
infinite descending chain in the positive integers so that the
relation is not well founded. And this is trivial:
... < 1/(n+2) < 1/(n+1) < 1/n < ... < 1
Quote: However, at the
same time every subset of IR has a minimal element:
Not true either. There is no minimal positive real, and there is no
minimal real. But in any case irrelevant. You can have a minimum and
still have an infinite descending chain. For example, the collection
of all subsets of the natural numbers, ordered by inclusion, has a
minimum (the empty set), but the relation is still not well-founded,
since we have an infinite descending chain
N > {2,3,4,...} > {3,4,5,...} > ...
Quote: if (a, b) denotes
the subset of IR of all real numbers from a to b (inclusive),
This is usually denoted by [a,b]; the notation (a,b) is usually
reserved for the collection of all real numbers STRICTLY between a and
b (that is, excluding both a and b).
Quote: then clearly a is the minimal element.
So what?
Quote: Where's my faulty thinking?
While a nonempty partially ordered set with no minimal element will
necessarily be non-well founded (at least, assuming some form of
choice), this is not an "if and only if"; so while having no minimal
elements is a guarantee that the set is not well founded, having
minimal elements does not tell you anything either way: you could have
a well-founded or a non-well founded set.
You are incorrect in stating that every nonempty subset of the real
numbers has a minimal element. Remember that minimal is not the same
as infinimum (which means "greatest lower bound").
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org |
|
|
| Back to top |
|
| José Carlos Santos |
| Posted: Sat Apr 26, 2008 5:18 pm |
|
|
|
Guest
|
On 26-04-2008 22:58, Whatever5k@web.de wrote:
Quote: A question on well-founded relations. Obviously, (IN, <) is a well-
founded relation. What about (IR+, <), where IR+ denotes all real
numbers >= 0.
I don't know what you have in mind when you write about "well-founded
relations", but if < is not well-founded within the real numbers, then
even the set IR+ is not defined, right?!
Quote: At first, I would say no since for any subset of IR
there is an infinite chain of descending elements.
Trivially false. Where do you get "an infinite chain of descending
elements" from {0}?
Quote: However, at the
same time every subset of IR has a minimal element: if (a, b) denotes
the subset of IR of all real numbers from a to b (inclusive),
Bad choice of notation, since (a,b) stands for the set of all real
numbers _x_ such that a < x < b. The usual notation for what you want is
[a,b].
Quote: then clearly a is the minimal element.
How did you deduce from the (trivial) fact that every set of the form
[a,b] has a minimal element that "every subset of IR has a minimal
element"?
Best regards,
Jose Carlos Santos |
|
|
| Back to top |
|
| Jannick Asmus |
| Posted: Sat Apr 26, 2008 5:59 pm |
|
|
|
Guest
|
On 26.04.2008 23:58, Whatever5k@web.de wrote:
Quote: A question on well-founded relations. Obviously, (IN, <) is a well-
founded relation. What about (IR+, <), where IR+ denotes all real
numbers >= 0.
No, it is not well-founded.
Quote: At first, I would say no since for any subset of IR
there is an infinite chain of descending elements.
No. Take a finite subset.
Quote: However, at the
same time every subset of IR has a minimal element:
No. Take {x in R s.t. x>0}.
Note that every non-void subset of R bounded from below has an infimum
(by completeness), i.e. a biggest lower bound. But the infimum is not
necessarily contained in the subset.
Quote: if (a, b) denotes
the subset of IR of all real numbers from a to b (inclusive), then
clearly a is the minimal element.
Where's my faulty thinking?
There are a lot more subsets of R which are not closed intervals.
HTH.
--
Best wishes,
J. |
|
|
| Back to top |
|
| N. Silver |
| Posted: Sat Apr 26, 2008 6:09 pm |
|
|
|
Guest
|
Whatever wrote:
Quote: A question on well-founded relations. Obviously, (IN, <) is a well-
founded relation. What about (IR+, <), where IR+ denotes all real
numbers >= 0.
Since (0, 1) is a non-empty subset of R+ and (0, 1) does
not have a least element, R+ is not well-founded. |
|
|
| Back to top |
|
| Angus Rodgers |
| Posted: Sat Apr 26, 2008 6:46 pm |
|
|
|
Guest
|
On Sat, 26 Apr 2008 15:36:06 -0700 (PDT), Whatever5k@web.de wrote:
Quote: On 26 Apr., 23:18, José Carlos Santos <jcsan...@fc.up.pt> wrote:
On 26-04-2008 22:58, Whateve...@web.de wrote:
A question on well-founded relations. Obviously, (IN, <) is a well-
founded relation. What about (IR+, <), where IR+ denotes all real
numbers >= 0.
I don't know what you have in mind when you write about "well-founded
relations", but if < is not well-founded within the real numbers, then
even the set IR+ is not defined, right?!
I don't see what you mean. I am talking about well-founded relations
in the usual sense:
(1) Definition: A well-founded relation is a binary relation on a
set A such that
there are no infinite descending chains ... < a_i < · · · < a1
a0.
or, equivalently
(2) Let be a binary relation on a set A. The relation < is
well-founded iff any nonempty subset Q of A has a minimal element.
At first, I would say no since for any subset of IR
there is an infinite chain of descending elements.
Trivially false. Where do you get "an infinite chain of descending
elements" from {0}?
Ok, forget that. I mean that I can construct infinitely descending
chains, referring to definition (1).
However, at the
same time every subset of IR has a minimal element: if (a, b) denotes
the subset of IR of all real numbers from a to b (inclusive),
Bad choice of notation, since (a,b) stands for the set of all real
numbers _x_ such that a < x < b. The usual notation for what you want is
[a,b].
then clearly a is the minimal element.
How did you deduce from the (trivial) fact that every set of the form
[a,b] has a minimal element that "every subset of IR has a minimal
element"?
I meant that every subset of IR+ has a minimal element: if we consider
the subset [a,b] for example, then a is the minimal element of this
subset. This refers to definition (2).
So from definition (1) I get a "NO", from (2) I get a "YES". What's
wrong?
The clause "any nonempty subset Q of A has a minimal element" implies
that the element in question belongs to Q (not just to A, which is
the interpretation you seem to be giving it).
In your chosen example, a bounded open interval (a, b), a is a minimal
element of the half-open interval [a, b), but does not belong to (a, b).
Also, even if some subset you picked /did/ happen to have a minimal
element, this would not prove that /every/ nonempty subset of R has
a minimal element.
--
Angus Rodgers
(twirlip@ eats spam; reply to angusrod@)
Contains mild peril |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Sun Sep 07, 2008 7:38 pm
|
|