Z is not naturally ordered?
in [Math]
|
Prev: Dear Friend! You Nigerian Lottery ticket won 1,255,000 USD. I'm authorized to transfer this amount directly to your banking account.
Next: I'm gonna try this one more time CANTOR DISPROOF
From: Tegiri Nenashi on 8 Jun 2010 16:00 On Jun 8, 11:47 am, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > On Jun 8, 10:34 am, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > > On Jun 8, 1:10 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > > > > On Jun 8, 9:37 am, jdo...(a)math.UUCP (James Dolan) wrote: > > > > > exercise: > > > ... > > > > the standard order on z can be defined in terms of the standard > > > > commutative ring structure on z. > > > > Exercise in what, google skills? "commutative ring" "standard partial > > > order" seems to lead the same way as the other replies, order defined > > > as nonnegative difference: > > > > x < y <-> y - x is non-negative > > > > May I ask where the unary relation "non-negative" is coming from? > > > "Is in N". > > Well, the puzzling flavor of James' message makes me expect him coming > out with succinct first order formula involving variables over > commutative ring, and operations "*" and "+". > > Please note that in R definition of standard order is also quite > simple: > > x < y <-> exists z x + z*z = y. Well, by Lagrange four square theorem we get definition that works for all the cases. In lattice case it would look weird! x < y <-> exists u,w,t,z : x v u^u v w^w v t^t v z^z = y.
From: Arturo Magidin on 8 Jun 2010 16:03 On Jun 8, 2:35 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > On Jun 8, 10:33 am, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > > On Jun 8, 12:57 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > > > > On Jun 7, 7:53 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > > On Jun 7, 7:24 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > > > > > > I'm aware of two (partial)) order definitions (and looking forward to > > > > > expand my perspective): > > > > > 1. (Semi)lattice: x < y <-> x ^ y = y. > > > > > 2. N: x < y <-> exists z: x + z = y. > > > > > (There is no pun intended with the name "natural order" applied in > > > > > second case) > > > > > > Now it comes with a bit of surprise that there is no natural order > > > > > definition for Z. > > > > > What do you mean by "natural order"? A definition like 2? Yes, 2 does > > > > not define an order relation on Z. > > > > > However, when people talk about the "natural order" of Z, they don't > > > > refer to (2). > > > > > Generally, given a set S, a partial order on S is a binary relation # > > > > such that: > > > > > (i) For all s in S, s#s; [reflexivity] > > > > (ii) For all s and t in S, if s#t and t#s, then t=s [anti-simmetry]; > > > > (iii) For all s, t, u in S, if s#t and t#u, then s#u. [transitivity]. > > > > > If in addition we have > > > > (iv) For all s and t in S, either s#t or t#s [totality] > > > > then we say the order is a "total order". > > > > > A "strict partial order" on a set S is a binary relation < such that > > > > (1) For all s in S, s<s does not hold [areflexivity]; > > > > (2) For all s, t, u in S, if s<t and t<u, then s<u [transitivity] > > > > > If in addition we have > > > > (3) For all s and t in S, exactly one of > > > > s<t; s=t; t<s > > > > holds [trichotomy] > > > > then we have a "total strict order". > > > > > If # is a partial order, then we can define a strict order by letting > > > > s<t if and only if s#t and s=/=t. > > > > > If < is a strict partial order, then we can define a partial order by > > > > letting s#t if and only if s=t or s<t. > > > > > Lattices are special kinds of partially ordered sets, in which every > > > > pair of elements has a least upper bound and a greatest lower bound.. > > > > > The integers have "natural" (or canonical) total order, which can be > > > > either derived from the order of the natural numbers, or that can be > > > > defined "algebraically" by defining the non-zero natural numbers to be > > > > the "positive class". Details available on request. > > > > This > > > What is "this"? I wrote several things. Which one are you refering to? > > > >implies details are not as succinct as equivalences 1 and 2. > > Among other things, I forgot question mark at the end of my sentence. > I referred to the very last "Details available on request". I'm confused. The "details" that were available on request was that of defining the order of Z, algebraically, by defining the nonzero natural numbers to be the positive class; that is, details on how one defines the order. But you seem to note, elsewhere, that you are familiar with this, so surely you don't need the details. So... the fact that one can define the order of Z via the notion of "positive class" (using the ring structure, not just the additive structure), "implies details are not as succinct as equivalences 1 and 2"? Well, I don't see how they are related; nor do I see how (1) and (2) are in any sense "equivalent." Again: *IF* you have a semilattice structure on a set, then you can use that structure to define a partial ordering on the set (doesn't matter if it is an upper semi-lattice or a lower-semilattice). But this definition presupposes the existence of a lattice structure. This is, essentially, what you attempted in (1). Moreover, not every partial ordering arises from a semi-lattice structure. And of course, that structure must somehow already be present in your set if you are going to use it as a definition. And you cannot use an arbitrary partial order to define a semilattice structure using (1), which I hope is clear. Of course, if your order happens to be a total ordering, then you *do* get a (semi)lattice structure using (1), though it is a rather trivial lattice structure. In the case of N, one usually defines the order using the additive semigroup structure as you note in (2): we *define* x<y to mean "there exists z in N such that x+z = y". (If your N includes 0, this defines the usual less-than-or-equal ordering; if your N does not include 0, this defines the associated strict ordering; but the distinction does not matter here). *Once* you have this order on N, it turns out that you have a total ordering so you can define a (boring) lattice on N using this order. But while N naturally comes equipped with a "successor" function, from which we define addition, from which we define the order, it does not seem to me to come with a natural "lattice" structure that you could base the order on in the first place. > > First: what is the primitive (semi)lattice structure that you think > > you have on N on which you base (1)? For (1) to make sense, a > > (semi)lattice structure must pre-exist your definition. What is that > > structure on N? Where did it come from? > > I'm not saying one can define order on N via > x < y <-> x + y = y. > because addition operation + is not idempotent (i.e. x + x = x). Sorry > for the confusion. This does not really seem to address my question either. Unless you were trying to use "+" as your '(semi)lattice operation' on N... > > Second: what "equivalence"? The two definitions are not "a priori" > > equivalent on N, because you do not have an a priori semi-lattice > > structure on N. > > These definitions are equivalent on semi lattice. No, because semilattices do not normally come equipped with a "+" operation the way N does (cancellative, to name one property). > However, since > existential definition also works for N, I suppose it is more general. > Hope that clarifies the matter. Not to me. For example, I am still utterly mystified by what role Z is supposed to be playing, or how one "naturally orders" a set. The best I can come up with is: Suppose you have a (lower semi)lattice (L,/\). We can define a partial order on L by (i) x<=y if and only if x/\y = x. (This is a partial order, well known, standard way of doing it, etc). Now, define the binary relation (lt) by (ii) x (lt) y if and only if there exists z in L such that x = z /\ y. Are the two conditions on x and y equivalent? Yes: suppose that x<=y. Then x/\y = x, hence by setting z=x in (ii) we get x(lt)y. Conversely, suppose that x(lt)y. Then there exists z such that x=z/\y; hence x/\y = (z/\y)/\y = z/\(y/\y) = z/\y = x, so x<=y. So the two conditions binary relations are the same one, and since we know that (i) defines a partial order, we get that (ii) defines a partial order as well (the same partial order, in fact). This of course presupposes a lower semilattice structure (similar argument, in the obvious manner, handles the case where we have an upper semilattice with join operation instead of meet). But this still does not tell me what this has to do with Z or what it is you are calling "naturally ordered". -- Arturo Magidin
From: Tegiri Nenashi on 8 Jun 2010 16:23 On Jun 8, 12:03 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > On Jun 8, 2:35 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > > > > > On Jun 8, 10:33 am, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > On Jun 8, 12:57 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > > > > > On Jun 7, 7:53 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > > > On Jun 7, 7:24 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > > > > > > > I'm aware of two (partial)) order definitions (and looking forward to > > > > > > expand my perspective): > > > > > > 1. (Semi)lattice: x < y <-> x ^ y = y. > > > > > > 2. N: x < y <-> exists z: x + z = y. > > > > > > (There is no pun intended with the name "natural order" applied in > > > > > > second case) > > > > > > > Now it comes with a bit of surprise that there is no natural order > > > > > > definition for Z. > > > > > > What do you mean by "natural order"? A definition like 2? Yes, 2 does > > > > > not define an order relation on Z. > > > > > > However, when people talk about the "natural order" of Z, they don't > > > > > refer to (2). > > > > > > Generally, given a set S, a partial order on S is a binary relation # > > > > > such that: > > > > > > (i) For all s in S, s#s; [reflexivity] > > > > > (ii) For all s and t in S, if s#t and t#s, then t=s [anti-simmetry]; > > > > > (iii) For all s, t, u in S, if s#t and t#u, then s#u. [transitivity]. > > > > > > If in addition we have > > > > > (iv) For all s and t in S, either s#t or t#s [totality] > > > > > then we say the order is a "total order". > > > > > > A "strict partial order" on a set S is a binary relation < such that > > > > > (1) For all s in S, s<s does not hold [areflexivity]; > > > > > (2) For all s, t, u in S, if s<t and t<u, then s<u [transitivity] > > > > > > If in addition we have > > > > > (3) For all s and t in S, exactly one of > > > > > s<t; s=t; t<s > > > > > holds [trichotomy] > > > > > then we have a "total strict order". > > > > > > If # is a partial order, then we can define a strict order by letting > > > > > s<t if and only if s#t and s=/=t. > > > > > > If < is a strict partial order, then we can define a partial order by > > > > > letting s#t if and only if s=t or s<t. > > > > > > Lattices are special kinds of partially ordered sets, in which every > > > > > pair of elements has a least upper bound and a greatest lower bound. > > > > > > The integers have "natural" (or canonical) total order, which can be > > > > > either derived from the order of the natural numbers, or that can be > > > > > defined "algebraically" by defining the non-zero natural numbers to be > > > > > the "positive class". Details available on request. > > > > > This > > > > What is "this"? I wrote several things. Which one are you refering to? > > > > >implies details are not as succinct as equivalences 1 and 2. > > > Among other things, I forgot question mark at the end of my sentence. > > I referred to the very last "Details available on request". > > I'm confused. The "details" that were available on request was that of > defining the order of Z, algebraically, by defining the nonzero > natural numbers to be the positive class; that is, details on how one > defines the order. But you seem to note, elsewhere, that you are > familiar with this, so surely you don't need the details. > > So... the fact that one can define the order of Z via the notion of > "positive class" (using the ring structure, not just the additive > structure), "implies details are not as succinct as equivalences 1 and > 2"? > > Well, I don't see how they are related; nor do I see how (1) and (2) > are in any sense "equivalent." > > Again: *IF* you have a semilattice structure on a set, then you can > use that structure to define a partial ordering on the set (doesn't > matter if it is an upper semi-lattice or a lower-semilattice). But > this definition presupposes the existence of a lattice structure. This > is, essentially, what you attempted in (1). > > Moreover, not every partial ordering arises from a semi-lattice > structure. And of course, that structure must somehow already be > present in your set if you are going to use it as a definition. And > you cannot use an arbitrary partial order to define a semilattice > structure using (1), which I hope is clear. Of course, if your order > happens to be a total ordering, then you *do* get a (semi)lattice > structure using (1), though it is a rather trivial lattice structure. > > In the case of N, one usually defines the order using the additive > semigroup structure as you note in (2): we *define* x<y to mean "there > exists z in N such that x+z = y". (If your N includes 0, this defines > the usual less-than-or-equal ordering; if your N does not include 0, > this defines the associated strict ordering; but the distinction does > not matter here). > > *Once* you have this order on N, it turns out that you have a total > ordering so you can define a (boring) lattice on N using this order. > But while N naturally comes equipped with a "successor" function, from > which we define addition, from which we define the order, it does not > seem to me to come with a natural "lattice" structure that you could > base the order on in the first place. > > > > First: what is the primitive (semi)lattice structure that you think > > > you have on N on which you base (1)? For (1) to make sense, a > > > (semi)lattice structure must pre-exist your definition. What is that > > > structure on N? Where did it come from? > > > I'm not saying one can define order on N via > > x < y <-> x + y = y. > > because addition operation + is not idempotent (i.e. x + x = x). Sorry > > for the confusion. > > This does not really seem to address my question either. Unless you > were trying to use "+" as your '(semi)lattice operation' on N... > > > > Second: what "equivalence"? The two definitions are not "a priori" > > > equivalent on N, because you do not have an a priori semi-lattice > > > structure on N. > > > These definitions are equivalent on semi lattice. > > No, because semilattices do not normally come equipped with a "+" > operation the way N does (cancellative, to name one property). > > > However, since > > existential definition also works for N, I suppose it is more general. > > Hope that clarifies the matter. > > Not to me. For example, I am still utterly mystified by what role Z is > supposed to be playing, or how one "naturally orders" a set. > > The best I can come up with is: > > Suppose you have a (lower semi)lattice (L,/\). We can define a partial > order on L by > > (i) x<=y if and only if x/\y = x. > > (This is a partial order, well known, standard way of doing it, etc). > > Now, define the binary relation (lt) by > > (ii) x (lt) y if and only if there exists z in L such that x = z /\ > y. > > Are the two conditions on x and y equivalent? > > Yes: suppose that x<=y. Then x/\y = x, hence by setting z=x in (ii) we > get x(lt)y. Conversely, suppose that x(lt)y. Then there exists z such > that x=z/\y; hence x/\y = (z/\y)/\y = z/\(y/\y) = z/\y = x, so x<=y. > > So the two conditions binary relations are the same one, and since we > know that (i) defines a partial order, we get that (ii) defines a > partial order as well (the same partial order, in fact). This of > course presupposes a lower semilattice structure (similar argument, in > the obvious manner, handles the case where we have an upper > semilattice with join operation instead of meet). > > But this still does not tell me what this has to do with Z or what it > is you are calling "naturally ordered". I see that there is so much room for confusion that it is better to clarify what I wrote in the other thread as well. Consider an algebra with two associative binary operations "@" and "#". The formula x < y <-> exists u,w,t,z : x @ (u#u) @ (w#w) @ (t#t) @ (z@z) = y. defines a partial order. Examples: Lattices: take join ^ for #, and meet v for @. N, Z, R: take addition + for #, and multiplication * for @.
From: Arturo Magidin on 8 Jun 2010 16:30 On Jun 8, 3:23 pm, Tegiri Nenashi <tegirinena...(a)gmail.com> wrote: > > I'm confused. The "details" that were available on request was that of > > defining the order of Z, algebraically, by defining the nonzero > > natural numbers to be the positive class; that is, details on how one > > defines the order. But you seem to note, elsewhere, that you are > > familiar with this, so surely you don't need the details. > > > So... the fact that one can define the order of Z via the notion of > > "positive class" (using the ring structure, not just the additive > > structure), "implies details are not as succinct as equivalences 1 and > > 2"? > > > Well, I don't see how they are related; nor do I see how (1) and (2) > > are in any sense "equivalent." > > > Again: *IF* you have a semilattice structure on a set, then you can > > use that structure to define a partial ordering on the set (doesn't > > matter if it is an upper semi-lattice or a lower-semilattice). But > > this definition presupposes the existence of a lattice structure. This > > is, essentially, what you attempted in (1). > > > Moreover, not every partial ordering arises from a semi-lattice > > structure. And of course, that structure must somehow already be > > present in your set if you are going to use it as a definition. And > > you cannot use an arbitrary partial order to define a semilattice > > structure using (1), which I hope is clear. Of course, if your order > > happens to be a total ordering, then you *do* get a (semi)lattice > > structure using (1), though it is a rather trivial lattice structure. > > > In the case of N, one usually defines the order using the additive > > semigroup structure as you note in (2): we *define* x<y to mean "there > > exists z in N such that x+z = y". (If your N includes 0, this defines > > the usual less-than-or-equal ordering; if your N does not include 0, > > this defines the associated strict ordering; but the distinction does > > not matter here). > > > *Once* you have this order on N, it turns out that you have a total > > ordering so you can define a (boring) lattice on N using this order. > > But while N naturally comes equipped with a "successor" function, from > > which we define addition, from which we define the order, it does not > > seem to me to come with a natural "lattice" structure that you could > > base the order on in the first place. > > > > > First: what is the primitive (semi)lattice structure that you think > > > > you have on N on which you base (1)? For (1) to make sense, a > > > > (semi)lattice structure must pre-exist your definition. What is that > > > > structure on N? Where did it come from? > > > > I'm not saying one can define order on N via > > > x < y <-> x + y = y. > > > because addition operation + is not idempotent (i.e. x + x = x). Sorry > > > for the confusion. > > > This does not really seem to address my question either. Unless you > > were trying to use "+" as your '(semi)lattice operation' on N... > > > > > Second: what "equivalence"? The two definitions are not "a priori" > > > > equivalent on N, because you do not have an a priori semi-lattice > > > > structure on N. > > > > These definitions are equivalent on semi lattice. > > > No, because semilattices do not normally come equipped with a "+" > > operation the way N does (cancellative, to name one property). > > > > However, since > > > existential definition also works for N, I suppose it is more general.. > > > Hope that clarifies the matter. > > > Not to me. For example, I am still utterly mystified by what role Z is > > supposed to be playing, or how one "naturally orders" a set. > > > The best I can come up with is: > > > Suppose you have a (lower semi)lattice (L,/\). We can define a partial > > order on L by > > > (i) x<=y if and only if x/\y = x. > > > (This is a partial order, well known, standard way of doing it, etc). > > > Now, define the binary relation (lt) by > > > (ii) x (lt) y if and only if there exists z in L such that x = z /\ > > y. > > > Are the two conditions on x and y equivalent? > > > Yes: suppose that x<=y. Then x/\y = x, hence by setting z=x in (ii) we > > get x(lt)y. Conversely, suppose that x(lt)y. Then there exists z such > > that x=z/\y; hence x/\y = (z/\y)/\y = z/\(y/\y) = z/\y = x, so x<=y. > > > So the two conditions binary relations are the same one, and since we > > know that (i) defines a partial order, we get that (ii) defines a > > partial order as well (the same partial order, in fact). This of > > course presupposes a lower semilattice structure (similar argument, in > > the obvious manner, handles the case where we have an upper > > semilattice with join operation instead of meet). > > > But this still does not tell me what this has to do with Z or what it > > is you are calling "naturally ordered". > > I see that there is so much room for confusion that it is better to > clarify what I wrote in the other thread as well. > > Consider an algebra with two associative binary operations "@" and > "#". The formula > > x < y <-> exists u,w,t,z : x @ (u#u) @ (w#w) @ (t#t) @ (z@z) = y. > > defines a partial order. Examples: > > Lattices: take join ^ for #, and meet v for @. > N, Z, R: take addition + for #, and multiplication * for @. It seems that you are attempting to engage in an extended monologue with two participants. Not only did you fail to answer any of my questions or clarify any of the things I mentioned I found confusing, you also ignored everything else I wrote. If that is the case and your plans, I will bow out. -- Arturo Magidin
From: Tegiri Nenashi on 8 Jun 2010 18:11
On Jun 8, 12:03 pm, Arturo Magidin > I'm confused. The "details" that were available on request was that of > defining the order of Z, algebraically, by defining the nonzero > natural numbers to be the positive class; that is, details on how one > defines the order. But you seem to note, elsewhere, that you are > familiar with this, so surely you don't need the details. I'm not familiar with this. It is simply that your construction appears to be too elaborate for such simple concept as standard order. > So... the fact that one can define the order of Z via the notion of > "positive class" (using the ring structure, not just the additive > structure), "implies details are not as succinct as equivalences 1 and > 2"? > > Well, I don't see how they are related; nor do I see how (1) and (2) > are in any sense "equivalent." But what was your proof at the bottom? > Again: *IF* you have a semilattice structure on a set, then you can > use that structure to define a partial ordering on the set (doesn't > matter if it is an upper semi-lattice or a lower-semilattice). But > this definition presupposes the existence of a lattice structure. This > is, essentially, what you attempted in (1). Yes, order definitions (1) and (2) are the same under the following conditions on a magma with binary operation @: i) x @ x = x. %idempotence ii) (x @ x) @ y = x @ (x @ y). %alternative algebra > Moreover, not every partial ordering arises from a semi-lattice > structure. Yes, I have an example of non-associative algebra, which still defines partial order via x < y <-> x @ y = y. > And of course, that structure must somehow already be > present in your set if you are going to use it as a definition. And > you cannot use an arbitrary partial order to define a semilattice > structure using (1), which I hope is clear. Of course, if your order > happens to be a total ordering, then you *do* get a (semi)lattice > structure using (1), though it is a rather trivial lattice structure. I'm not discussing partial orders giving rise to lattices. > In the case of N, one usually defines the order using the additive > semigroup structure as you note in (2): we *define* x<y to mean "there > exists z in N such that x+z = y". (If your N includes 0, this defines > the usual less-than-or-equal ordering; if your N does not include 0, > this defines the associated strict ordering; but the distinction does > not matter here). I'm not sure why we repeatedly going over this again: -- In the case of N, one can define the standard order via "there exists z in N such that x+z = y" -- In the case of (lower semi-)lattice, one can define the partial order via "there exists z in L such that x v z = y" Also what is your emphasis on "define"? I'm routinely use Prover9 (hence "v" and "^" symbols for lattice operations), which doesn't understand the concept of "define". A formula like x < y <-> x v y = y. works just fine. > *Once* you have this order on N, it turns out that you have a total > ordering so you can define a (boring) lattice on N using this order. > But while N naturally comes equipped with a "successor" function, from > which we define addition, from which we define the order, it does not > seem to me to come with a natural "lattice" structure that you could > base the order on in the first place. I share the feeling that lattices define an order relation the most "natural" way. I don't expect this view to carry over to non- idempotent algebras (N, Z, R, etc). I'm not expecting to uncover non- vacuous lattice structure there, as you seems to imply. > ... For example, I am still utterly mystified by what role Z is > supposed to be playing, or how one "naturally orders" a set. > The best I can come up with is: > > Suppose you have a (lower semi)lattice (L,/\). We can define a partial > order on L by > > (i) x<=y if and only if x/\y = x. > > (This is a partial order, well known, standard way of doing it, etc). > > Now, define the binary relation (lt) by > > (ii) x (lt) y if and only if there exists z in L such that x = z /\ > y. > > Are the two conditions on x and y equivalent? > > Yes: suppose that x<=y. Then x/\y = x, hence by setting z=x in (ii) we > get x(lt)y. Conversely, suppose that x(lt)y. Then there exists z such > that x=z/\y; hence x/\y = (z/\y)/\y = z/\(y/\y) = z/\y = x, so x<=y. > > So the two conditions binary relations are the same one, and since we > know that (i) defines a partial order, we get that (ii) defines a > partial order as well (the same partial order, in fact). This of > course presupposes a lower semilattice structure (similar argument, in > the obvious manner, handles the case where we have an upper > semilattice with join operation instead of meet). > > But this still does not tell me what this has to do with Z or what it > is you are calling "naturally ordered". Once again, I was asking to exhibit a first order formula that defines the standard order on Z. In the monologue that upset you so much, it struck me that the formula with existential quantifier ranging over four variables seems to cover all the cases. |