Talk:Connected relation

Dialogue and suggestions

This talk is dedicated to Connex relations to support the general study of binary relations. Readers, editors, anyone can comment or suggest here, more confidentially than in the article or edit summary. One can also suggest a source to be included that will improve this article's description of relations of this type. — Rgdboer (talk) 21:39, 14 June 2018 (UTC)[reply]

Connex relations can not be symmetric?

The "A connex relation cannot be symmetric" property seems wrong because a relation that holds (xRy and yRx) for any pair should be connex and symmetric. If that is not the case, then it might help to clarify that aspect. Thx. Rehierl (talk) 07:47, 15 July 2018 (UTC)[reply]

I mentioned the "universal relation" (i.e. the relation that holds for any pair; unfortunately, there is currently neither a wikilink "universal relation" nor a suitable article section such a link could be redirected to) as an exception. In fact, the universal relation is the one exception: If R is symmetric and connex, for arbitrary x,y we have (xRy or yRx) by the latter property, hence xRy by the former one, so R must be the universal relation. - Do you think this should be mentioned in another footnote in the article? - Jochen Burghardt (talk) 12:25, 15 July 2018 (UTC)[reply]

Hmm, I can't (yet) state that I understand the second part of your reply, which is probably because I still can't wrap my head around the alternative characterizations. (-1-) From what you wrote, the "universal relation" holds all possible pairs; so U = { aRb | for all a and b in A } = X×X for some relation R = (A,A,G). But then U is as large as it can get, which is consistent with "universal set". As such it can't be a strict subset of anything. Hence, $X\times X\subset R\cup R^{T}$ is odd because the strict-subset-of operator seems to have the wrong direction. (-2-) Likewise, the "identity relation" does not seem to have a dedicated definition; I hope it isn't wrong if I read it as I = { aRa | for all a in A }. In addition to the strict-subset-of operator seeming to be "flipped" in ${\bar {I}}\subset R\cup R^{T}$ , that seems to raise another question: If I don't mistakenly assume ${\bar {I}}$ and U \ I to be equivalent, then the initial expression effectively removes all "reflexive edges" from U. But that seems to overshoot the purpose as the initial definition (when x≠y and (x,y) ∉ R implies (y,x) ∈ R) doesn't disallow these edges. (-3-) All in all, I'd say it would help if you could add definitions for U and I in "Binary relation" under "Relations over a set". In addition to that, it could help to add two short paragraphs which clarify in words what both alternative characterizations are supposed to mean. Rehierl (talk) 18:08, 15 July 2018 (UTC)[reply]

You are right that the "

\subset

" operator shouldn't be used. Apparently, the editor who used it intended to mean "subset or equal" by it (some people use this notation). I'll change the operator to

\subseteq

which can't be misinterpreted. This should resolve most of your questions. - Your understanding of U, I,

{\bar {I}}

, and U \ I coincides with mine. - Adding the definition of "universal relation", "identity relation", and "empty relation" (not referenced here, but in many other articles) is a good idea, but since each of them is a particular relation, they don't fit very well under "Relations over a set", where properties of relations are handled. However, probably that section is still the best place to add them. - An explanation of each of the "alternative characterizations" would amount to what has said immediately before it, i.e. to the "non-alternative" characterization. Maybe when the "subset"/"strict subset" issue is clarified, the equivalence of "non-alternative" and "alternataive" characterization becomes clear? - Jochen Burghardt (talk) 20:46, 15 July 2018 (UTC)[reply]

Besides changing the

\subset

operator symbols, I added a section Binary relation#Particular binary relations, and created redirects to there from empty relation, universal relation, and identity relation. - Jochen Burghardt (talk) 21:06, 15 July 2018 (UTC)[reply]

There are two aspects that weren't clear to me: (1) In this context, the universal relation has to be thought of as being reduced to a bare minimum (i.e. "universal" only with regards to R). And more importantly (2) for a relation to be connex, it also has to be reflexive. So, if you add all those edges that keep it from being symmetric, you automatically end up with the universal relation. Hence, a relation that is connex and not the universal relation, can indeed not be symmetric. Thanks for your help. Rehierl (talk) 06:36, 16 July 2018 (UTC)[reply]

Both informations are present in the article, but somewhat hidden: (1) The phrase "the universal relation X×X" denotes the universal relation on the set X under consideration. (2) The "only-if" direction of the third property implies that each connex relation is (semi-connex and) reflexive. - I'm not sure whether (and how) to make them more explicit in the text (without adding too much redundancy). Maybe "the universal relation on X" is better? But then "X×X" appears unmotivated in the formula after the text. Likewise, the third property could be moved up before the formal definition; but usually the definition comes first, and its properties after that. - Jochen Burghardt (talk) 11:18, 16 July 2018 (UTC)[reply]

The is-reflexive property is actually a direct consequence of the formal definition (x=y); it just took me some time to notice it as a consequence. But I agree, further changes would add confusion (the universal relation X) or unnecessary redundancy (3rd property). Rehierl (talk) 16:14, 16 July 2018 (UTC)[reply]

Non-standard terminology

The term "connex" is not the standard term for this property; mathematical texts overwhelmingly use "connected". See eg the Oxford Dictionary of Mathematics: https://www.oxfordreference.com/view/10.1093/acref/9780199679591.001.0001/acref-9780199679591-e-598 The entry seems to have been renamed a couple of years ago but I can't see a reason given. I find this very confusing and suggest it be fixed. The non-standard term "connex" seems to be only used in a couple (originally German) computer science texts. Richard Zach (talk) 15:15, 1 April 2021 (UTC)[reply]

I propose to make this page reflect the terminology that's standard in English-language mathematics, to make it more useful to the user. The most common use of the term is that of "connected" as what is defined here as semiconnex.^[1]^[2] I would rename the page to "connected relation", lead with "connected" ("semiconnex") as the standard definition, introduce strongly connected ("connex"), and describe the different terminologies in use (connected-strongly connected; weakly connected-connected; semiconnex-connex are all in use). "Connected" in the sense of connex is common, e.g., in the literature on modal logic ^[3] and in the literature on preference relations in social choice theory^[4]. Of course the most important use is in the definition of total orders. Richard Zach (talk) 15:50, 12 April 2021 (UTC)[reply]

References

^ Clapham, Christopher; Nicholson, James (2014-09-18). "connected". The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN 978-0-19-967959-1. Retrieved 2021-04-12.
^ Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p. 182. ISBN 978-1-4939-3223-8.
^ Blackburn, Patrick; Rijke, Maarten de; Venema, Yde (2001). Modal logic. Cambridge University Press. p. 327. ISBN 978-0-521-52714-9.
^ Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9.

Having gotten a masters and undergraduate degree in mathematics, I can comfortably say that never have I seen the phrase "connex relation." I have certainly seen "connected relation" many times before. I second Richard Zach's suggestion that it should be changed to accord with standard mathematical usage, especially since students may be led amiss by this entry's idiosyncratic phrase for the notion at hand. LogicalAtomist (talk) 03:26, 18 April 2021 (UTC)[reply]

Zach's proposal is definitely to the point. The term virtually appears nowhere. But is the common term really "connected" (as opposed to "total")? Melancholist20 (talk) 06:35, 18 April 2021 (UTC)[reply]

I can't judge on "connex" vs. "connected", as I'm not a native English speaker. However, I'd oppose against "total", since it is likely to be confused with "serial". I suggest that the relation property names are chosen away from the confusion term "total", that is, that we prefer "serial" and "connex/connected". Moreover, redirects involving "total" should be turned into disambiguation pages. Of course, both the Serial relation and the Connex relation (or whatever) article should mention the use of "total", and warn about possible confusion with the respective other meaning. - Jochen Burghardt (talk) 10:41, 18 April 2021 (UTC)[reply]

My sense from trying to find uses of "total relation" on Google Books is this: whenever people call /arbitrary/ relations "total" they usually have in mind the sense of serial relations (i.e., graphs of total functions). It is very rare to see "total" used in the sense of connected /except/ for orders. OTOH orders of all kinds (strict, partial, pre-) which are connected are almost always called either "total" or "linear". I agree with Jochen Burghardt that the article should state this. Richard Zach (talk) 20:18, 18 April 2021 (UTC)[reply]

I've made a draft in User:Rzach/sandbox, check it out. Richard Zach (talk) 21:00, 19 April 2021 (UTC)[reply]

Looks great to me, but I'd like to suggest a few minor changes. Is it ok when I edit directly in your sandbox? Deferring the synonyms list to an own section is unusual in Wikipedia (I feel), but it may be necessary here. But then I'd like to remove "total" from the lead, unless it is really significantly used more often than the other synonyms (I feel that is true, but actually I can't judge on that). I just looked at the lead and the Terminology section - did you make changes elsewhere? - Jochen Burghardt (talk) 08:33, 20 April 2021 (UTC)[reply]

Sure go ahead. I felt in the end that it would make sense to include "total" in the head since it is very common, but relegated the others to their own section. I think it is warranted in this case, since there are so many options. It would just be confusing to throw all those terms at the reader at the top, before even explaining what the notion is. I then added a section that explains that when you're talking about orders, connected/semiconnex expresses the linearity of the ordering for both partial and strict orders, but strongly connected/connex does not (essentially justifying why connected and not strongly connected is the primary concept in most applications). In the terminology section I give the different terminology (found another pair: connex/strictly connex btw). I also wrote out the equivalences in the characterization section. The line in the properties section that says that connex relations can't be symmetric struck me as odd so I re-wrote it. — Preceding unsigned comment added by Rzach (talk • contribs) 13:17, 20 April 2021 (UTC)[reply]

Also, agree with your suggestion to make a disambiguation page for "total relation"! Richard Zach (talk) 13:35, 20 April 2021 (UTC)[reply]

On the disambiguation page issue, there is already a disambiguation page for Total. What's the best practice? Redirect Total relation there (and add a link here)? Make a separate disambiguation page just for Total relation which links to here and to serial relation? Richard Zach (talk) 00:02, 21 April 2021 (UTC)[reply]

Done minor change suggestions in User:Rzach/sandbox. I'm not sure about my very last edit, which removed all reasons from the 2nd paragraph of "Connectedness and total orders"; I wouldn't defend it if you'd reverted it. My reason for this edit is that the previous version is somewhat overwhelming, juggling a large number of different notions.

As for the redirects, the best might be to turn Total relation (currently a redirect) into a 2-entry disambiguation page, to keep its entry at Total, and to add a hat note at connected relation and at serial relation informing about the synonym "total relation", and its deviating meaning. This way, somebody who looks up "total relation" will find something, even if (s)he was unaware of the two meanings. Moreover, it appears to be not that easy to get a redirect page deleted. The disadvantage of this approach is that we'll have an almost trivial disambiguation page forever. However, I have no idea whether this is in accordance with Wikipedia rules (if there are any about such issues). - Jochen Burghardt (talk) 11:45, 21 April 2021 (UTC)[reply]

[1] Clapham, Christopher; Nicholson, James (2014-09-18). "connected". The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN 978-0-19-967959-1. Retrieved 2021-04-12.

[2] Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p. 182. ISBN 978-1-4939-3223-8.

[3] Blackburn, Patrick; Rijke, Maarten de; Venema, Yde (2001). Modal logic. Cambridge University Press. p. 327. ISBN 978-0-521-52714-9.

[4] Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9.

[1]

[2]

[3]

[4]