Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: lexicographic order?

Bottom of Page

1 to 6 of 6

  1.  
    • CommentRowNumber1.
    • CommentAuthorEman
    • CommentTimeMar 15th 2014
    Hello all,
    I liked very much the nLab-entry "well-founded relation": concise and informative.
    Do you think "lexicographic order" may be included in the section Examples as another, practically relevant example of well-founded relation?
    If yes, I would be very grateful if somebody could do that (I am not an expert).

    Best regards from Germany
    • CommentRowNumber2.
    • CommentAuthorEman
    • CommentTimeMar 15th 2014
    Motivation: perhaps I should have said right away, that I am interested in *using* mathematical induction for some proofs of program properties. These inductions tend to need lexicographic ordering. So I would like to know, just how much or how little I must assume in order to use it. Hence, not the most general formulation, but something like:
    having an n-tuple of sets, each equipped with a total(?) ordering Ri, ...

    so basically, a practical and reasonably powerful special case.
    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 15th 2014

    We do have an entry lexicographic order; does it meet your needs? I guess a remark could be put in about the case where the orders L iL_i involved are well-ordered. Thanks for the suggestion!

    • CommentRowNumber4.
    • CommentAuthorEman
    • CommentTimeMar 15th 2014
    Well I am interested in a simple issue: If I have linearly ordered sets (Si, <i), i=1,....n, is the lexicographic order defined upon these necessarily well-founded? In other words, may I use this lexicographic order for mathematical induction, or do I need more assumptions?
    Normally when discussing program properties, one has "rich", "nicely-behaved" sets, there should be no surprises, but I am trying to assemble some definitions for my work.

    BTW, concerning entry "well-founded relation", in section Examples it is said "Let S be a finite set. Then any relation on S is well-founded." How about the relation (a,a)?

    Thank you for help.
    • CommentRowNumber5.
    • CommentAuthorTodd_Trimble
    • CommentTimeMar 15th 2014

    I think that for nonempty S iS_i, the product ∏ iS i\prod_i S_i under the lexicographic order is well-founded if and only if all the S iS_i are well-founded. This is because each S iS_i embeds as a suborder of ∏ iS i\prod_i S_i, and a suborder of a well-founded order is also well-founded. So you need to be able to do induction over all the S iS_i in order to do induction over ∏ iS i\prod_i S_i.

    Thanks for pointing out the error under the Examples section; I think it’s fixed now.

    • CommentRowNumber6.
    • CommentAuthorEman
    • CommentTimeMar 15th 2014
    Thank you for your prompt help.

1 to 6 of 6

  1.