Talk:Total order

Totality

Total relation was turned into a redirect to serial relation a few weeks ago (see diff), and now Total order was reworded to use the term connex relation instead of total relation/totality throughout the article (see diff). I am not really happy with these changes since every source I have ever seen that defined the term "total order" used the word "totality" to denote the property that every element is related to every other element. – Tea2min (talk) 06:43, 30 May 2018 (UTC)

The problem is that "total relation" can be used to describe two different and unrelated properties, viz. serial relation (∀x∃y. xRy) and connex relation (∀x,y. xRy ∨ yRx). After I saw the rewording, I glanced at some textbooks, and found that "total(ly) order(ed set)" is used often, but -to my surprise- "totailty property" and "total relation" is not.

For example, Birkhoff ("Lattice Theory", AMS Colloquium Publications vol. 25, 1967) defines on p.1 "partial ordered set", naming all three involved properties ("Reflexive", "Antisymmetry", "Transitivity"), on p.2 he defines "simply ordered set" = "totally ordered set" = "chain", showing the connex formula without a name. Grätzer ("General Lattice Theory", Birkhäuser, 2003) uses on p.1 the name "linearity" property, and on p.2 "chain" and all of Birkhoff's synonyms. A calculus textbook, Heuser ("Lehrbuch der Analysis 1", B.G.Teubner, 1980, I don't have English ones available) defines on p.36 the notion of trichotomy property. Halmos ("Naive Mengenlehre", Vandenhoeck&Ruprecht, 1976; German translation of "Naive Set Theory", Nostrand, 1968, I have only the German book) defines in ch.14 on p.72 "reflexive", "anti-symmetric", "transitive" relations, and "total" = "simple" = "linear" "orders", again without naming the connex property.

Therefore, and since recent publications appear to use "connex" more often (this word didn't appear at all in the above books; a few recent publications that use it are listed at Connex relation#References), I think the rewording is ok. However, we should add warning sentences or footnotes about the two meanings of "totality" at appropriate places. I tried to phrase such a warning in the lead of Connex relation.

A problem with "connex" is that it is not an adjective, thus often requiring clumsy grammatical constructions in enumerations (e.g. "A relation is trichotomous if, and only if, it is irreflexive, asymmetric, and a semi-connex relation." at Trichotomy (mathematics)#Properties). However, the adjective "linear" is not a good alternative, since it is associated with vector spaces, and "simple" cannot be associated to anything. I believe I saw "fully ordered set" (as opposed to "partially ordered set") somewhere, but "full" isn't a good adjective either. - Jochen Burghardt (talk) 11:46, 30 May 2018 (UTC)

I never heard or saw the word "connex" before it was added to this article. JRSpriggs (talk) 05:03, 31 May 2018 (UTC)

Neither did I. Do you have another suggestion about how to avoid confusion? - Jochen Burghardt (talk) 16:37, 31 May 2018 (UTC)

Example of total order that is not a strict total order?

I think I'm sure I've seen one, but can't think of an example just right now. 67.198.37.16 (talk) 18:11, 16 January 2019 (UTC)

A total order is reflexive (x ≤ x), while a strict total is not ($x\not <x$). So a total order is never a strict total order. The article explains in detail the relationship between the two concepts, namely that there are equivalent (a total order defines a strict total order, a strict total order defines a total order, and these two operations are inverses one to other). D.Lazard (talk) 23:24, 16 January 2019 (UTC)

Smallest bounded sets

From the examples section.

The unique order on the empty set, ∅, is a total order.

...

The natural numbers comprise the smallest totally ordered set with no upper bound.

The integers comprise the smallest totally ordered set with neither an upper nor a lower bound.

The linked article on Upper and lower bounds only talks about upper and lower bounds of subsets of an ordered set. If we interpret the above remarks about the natural numbers and integers as statements about these sets as subsets of themselves, then the remarks are not correct. ∅ (viewed as a subset of itself) is the smallest unbounded totally ordered set, there being no element of ∅ capable of serving as a bound. On the other hand, if we view these sets as proper subsets of some other totally-ordered superset, then ∅ is not an unbounded set, being bounded by every element of its superset. But in this case whether the natural numbers or integers are bounded depends upon the nature of the total order of their superset. For example if the natural numbers are viewed as an initial segment of some larger ordinal, then they are bounded above.

Either way, the statements as currently written are not universally true.

Minimally the the word "non-empty" needs to be inserted, which I will do shortly. Beyond that, either the statements in this article should to be revised to make it clear that the sets are being viewed as subsets of themselves, or if it is commonplace in current mathematical discourse to refer to bounds of ordered sets without reference to subsets, then the article on Upper and lower bounds should be edited to explain this usage. — Preceding unsigned comment added by 93.97.176.246 (talk) 05:56, 11 March 2020 (UTC)

Intuitionistic comment

I think it is possible to add a remark that the approach

"We can work the other way and start by choosing < as a transitive trichotomous binary relation;"

is equivalent in the classical logic, but is stronger in the intuitionistic logic. (So one who uses it is advised to choose the "Strict Total Order" in one's definitions.) — Preceding unsigned comment added by Georgydunaev (talk • contribs) 08:52, 6 September 2020 (UTC)

Mistake about rational numbers?

The article states "The rational numbers comprise the smallest totally ordered set which is dense in the real numbers.". I don't think that's true. Smallest in which sense? I think that e.g. rational numbers whose denominators are powers of two are one possible "smaller" dense set (and every subset of the reals is clearly totally ordered). Am I right? — Preceding unsigned comment added by 46.13.147.72 (talk) 16:57, 9 March 2021 (UTC)

"Smallest" is defined a few lines above, but is confusing as the definition does not excludes the existence of an strict subset that is order isomorphic (for example, the even integers are order isomorphic to the integers).

So, I have replaced "smallest" by "initial", as the concept is close (although weaker) to the concept of initial object. I have also tagged these examples with {{citation needed}}.

I would not oppose to remove all mentions of "smallest / initial". D.Lazard (talk) 21:01, 9 March 2021 (UTC)

(I posed the initial question.) Thanks, this is much better. One often does not read the whole article, and while everyone thinks to know what "smallest" means and thus gets confused, the word "initial" does not have this problem. ... Also, I apologise if I didn't do something quite properly; it's been ages since I last edited Wikipedia (not the English one) and I am therefore familiar with neither the written not the unwritten rules. But I guess when one only edits the "talk", one cannot do that much harm. Thanks once more, cheers! 46.13.147.72 (talk) 09:07, 12 March 2021 (UTC)

Meaning of "chain"

In the lead and in the section "Chain", it is asserted that "chain" and "total order" are synonyms. If true, $\mathbb {R}$ would be a chain. I never heard such an assertion. As far as I know, a "chain" generally refers to a sequence of elements of an ordered set such that each element of the sequence is either greater (ascending chain) or smaller (descending chain) than the preceding one. In other words, a chain is the image of a strictly monotone function of the natural numbers (or of an initial interval of the natural numbers) into an ordered set.

I intend to rewrite this section. However I am not sure that this article is the right place for defining chains. So, I wait for further input before editing this section. D.Lazard (talk) 16:52, 23 April 2021 (UTC)

You are right that "chain" as a straightforward synonym for "totally ordered set" is uncommon, but there is a reference given in the lead; here's another: Fraïssé, R. (2011-08-18). Theory of Relations. Elsevier. ISBN 978-0-08-096041-8. p. 35. The use of "chain" for "totally ordered subset of a partially ordered set" is very common (eg https://encyclopediaofmath.org/wiki/Chain). Since ascending and descending chains are introduced below as special cases of chains, probably this can be cleaned up simply by removing everything between "chain" and "is often used"? Richard Zach (talk) 18:20, 23 April 2021 (UTC)

(But the section needs to be rewritten so it's not just a list of bullet points so power to you!) Richard Zach (talk) 18:23, 23 April 2021 (UTC)

It seems a matter of context; for example, in Zorn's lemma, "chain" is used as a synonym for a totally ordered subset. Also, in the discussion of ascending chain conditions or descending chain conditions, chains are not limited to sequences. —- Taku (talk) 07:04, 24 April 2021 (UTC) I don’t know if this note [1] is reliable but it defines a chain as a totally ordered subset; so any subset (even empty??) of R is a chain. I doubt we know whether the empty set is a chain or not. —- Taku (talk) 07:17, 24 April 2021 (UTC)

This article Chain-complete partial order talks about a countable chain, which suggests there can be a uncountable one :) -- Taku (talk) 07:30, 24 April 2021 (UTC)

I added the Fraïssé reference, and removed the ((dubious)) tag; this shouldn't interfer too much with D.Lazard's intended rewriting, I hope. According to Halmos, a chain may be empty, and (another one) may be uncoutable (cf. my edit summary). However, e.g. Ascending chain condition uses D.Lazard's notion of "chain", viz. a sequence of elements of an ordered set. - Jochen Burghardt (talk) 16:09, 29 April 2021 (UTC)

I have some difficulties for rewriting the section, because it needs to report common usages of a concept that is rarely formally defined. As far as I know, "a chain" refers generally to a set of subsets of a given set, which is totally ordered by inclusion. For example, the Krull dimension of a commutative ring is the maximal length of chains of prime ideals. It seems that the use of "chain" for other partial orders than inclusion results generally from a generalization of this case. For example, Zorn's lemma is stated for any ordered set, but most of its applications are for sets (of some specific type) ordered by inclusion. So, the section must mention three main contexts where the term "chain" is used: for stating and using Zorn's lemma; for ascending chains and descending chains, which are monotone sequence; for finite chains that are used for many notions of dimensions (the dimension of a vector space the the maximal length of chains of linear subspaces), and also in graph theory as a synonym of walk (graph theory) (this needs some explanations for being related to the the concept discussed here).

This is the way I intend to rewrite the section. However I may miss some important things, and a feedback on the above summary would be welcome. D.Lazard (talk) 17:40, 29 April 2021 (UTC)

From your description, I'd suggest the following hierachy of meanings of "chain":

• 1. Any total order (Halmos, Fraisse)
  • 1.1. A totally ordered set as subset of some partial order (Zorn's lemma for partial orders)
  • 1.2. A total order of order type ω (a.k.a. sequence indexed by natural numbers) (ascending chain condition, walk (graph theory))
  • 1.3. ⊆ as a total order (Zorn's lemma for sets)
    • 1.3.1. Inclusion morphism as a total order (Krull dimension: ring homomorphisms)

This seema to cover all uses seen so far.

I also had a look at two lattice theory books:

• Davey.Priestley.1990 define "chain" as in 1. (p.3), but use it mostly in the sense of 1.1. (Zorn: p.100, chain-completeness p.5); they use "sequence", not "chain" in the definition of ACC and DCC (p.38), and use 1.1. for Zorn's lemma (p.100).
• Gratzer.2003 defines "chain" as in 1., and "chain in a PO" as in 1.1. but nonempty (both p.2); he defines "increasing chain" on the fly as in 1.2. (p.15, exercise about ACC).

This also shows that an author needn't stick with a single node in the hierarchy. - Jochen Burghardt (talk) 19:39, 29 April 2021 (UTC)

I have rewritten the section. I have not changed the references, and I left to others to add further references and/or to find a better place, if needed, for the existing ones. I think that this version is much better than the previous one, but feel free for improving it further (and fix my mistakes, if any). D.Lazard (talk) 14:19, 30 April 2021 (UTC)

References

Binary relations table

When viewing the article on mobile the binary relations table shows first, fully expanded. I’m not sure how best to fix this (and I am on mobile) but it seems an unhelpful way to begin new readers. — HTGS (talk) 08:22, 15 June 2021 (UTC)

Being not about the subject of this article, this table does not belong to the lead. I have moved it to the section "Related structures, where it is more appropriate. D.Lazard (talk) 12:08, 15 June 2021 (UTC)

The current definition is redundant

A total order is currently being defined as follows: "That is, a total order is a binary relation $\leq$ on some set $X$, which satisfies the following for all $a,b$ and $c$ in $X$:

1. $a\leq a$ (reflexive).
2. If $a\leq b$ and $b\leq c$ then $a\leq c$ (transitive).
3. If $a\leq b$ and $b\leq a$ then $a=b$ (antisymmetric).
4. $a\leq b$ or $b\leq a$ (strongly connected, formerly called total)."

This is redundant – 1. follows from 4. if you substitute $a$ for $b$ (since it doesn't say "for all distinct $a,b$").

Joriki (talk) 19:26, 16 February 2023 (UTC)

 Done. I added a remark in the lead about that. - Jochen Burghardt (talk) 08:58, 17 February 2023 (UTC)

Non-strict total order should be defined

I expected the section "Strict and non-strict total orders" to contain a definition of a non-strict total order. It currently only defines only strict total orders and then discusses relationship between strict and non-strict total orders. Including a definition would help readers' understandings of core concepts in this article. Bradknox (talk) 21:18, 11 May 2023 (UTC)

An occurence of "strict" was omitted. Otherwise, the definition of a (non strict) total order is given in the preceding section D.Lazard (talk) 21:45, 11 May 2023 (UTC)

I added an appropriate sentence to the article. - Jochen Burghardt (talk) 12:42, 13 May 2023 (UTC)