Talk:Finitary relation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
High Importance
 Field: Foundations, logic, and set theory
This article has comments.

For older discussion, see Talk:Relation (mathematics)/Archive. Paolo.dL (talk) 11:09, 15 March 2008 (UTC)

Requested move part 1[edit]

Note: This section was formerly titled, “Is a relation usually n-ary?”

I know no author who thinks of n-ary relations (n≠2) without explicitely saying it, while I could cite many references where "binary relation on E" means "relation from E to E" (thus 2-ary, of course) and therefore (although less frequently and usually explained to avoid confusion), "binary relation on ExF" means "relation from ExF to ExF".

I'm not "against" n-ary relations (how could I...), but I would not start the article like "the notion of relation is a generalization of ... binary relation" but rather put "the notion of n-ary relation is a generalization of ..." and all that is about n-ary relations in one single paragraph like a "special case", maybe creating an extra page the day where there is enough to say about, and clearly state that this page mainly deals with the principal case, which are the 2-place relations ("from some set E to some set F, for which one has composition, reciprocal, injectivity, surjectivity, etc. etc.).

Those who are against, please give a reference where a "relation" is n-ary with n arbitrary, without this being explicitely mentioned.

As a side note, notice that apart from the definition, all examples given on that page are binary relations. — MFH:Talk 17:26, 13 October 2006 (UTC)

For one thing, there's a separate article on binary relation. I had suggested previously that we should move this article to another location, such as n-ary relation or something similar. It might be a good idea to make that suggestion on WP:RM, to get a wider input. Mangojuicetalk 20:26, 13 October 2006 (UTC)
Perhaps it's hard to tell from the above discussions, but actually pretty much everybody would agree with you that this article should be on the usual definition of relation, i.e. binary relation. As far as I can tell, only one editor, Jon Awbrey, thought otherwise. His unflagging energy at debating somehow resulted in a kind of compromise article between him and the few people with the desire to argue endlessly with him. Such a version is of course not the same as it would be if one actually got input from everybody. I would say, do the move and the relevant changes. --C S (Talk) 15:50, 13 March 2007 (UTC)
Agree w/Chan Ho, can't we get an admin to do the move? If this is going to be contentious, can't we get some sort of "article for move" vote going? linas 16:36, 6 April 2007 (UTC)
What exactly is being requested? Is it this?
1. Binary relation moves to Relation (mathematics)
2. Relation (mathematics) moves to Finitary relation
That seems unobjectionable to me, and I would be glad to do it if there is consensus. I dislike the title n-ary relation because of typesetting difficulties. CMummert · talk 17:01, 6 April 2007 (UTC)
Yes, I believe that's the proposal. linas 18:25, 7 April 2007 (UTC)

Discussion continued below.

Infinitary relations?[edit]

Do we have an article on infinitary relations? I had to do a hack job to define one for the definition of a complete free lattice; I would lke to see an article devoted to the correct, proper definition. linas 16:33, 6 April 2007 (UTC)

I would think that the ordinary way of defining the supremum relation is as a binary relation between a set of elements and its sup. In this way, by using higher types, it isn't necessary for the relation itself to be infinitary. CMummert · talk 16:53, 6 April 2007 (UTC)
I don't think I'm the first, but my Ph.D. thesis used infinitary operations in a universal algebra setting. I'll help proof the article, but the initial draft would have to be written by someone with less familiarity with the concept than I have. I'd probably miss something which is obvious to me but confusing to the readers. For instance, one can use the "usual" theorems of universal algebra to construct a free countably complete Boolean algebra on a countable set of generators. My thesis generalized that to "constructing" a free algebra over a proper class of operators and equations. If I can find my thesis, one of the books referenced in that section should have something on infinitary universal algebra. — Arthur Rubin | (talk) 19:47, 6 April 2007 (UTC)
Yes. Per Arthur Rubin, the whole point of an infinitary relation is to be able to talk about what happens after you take the limit to infinity, and way beyond (i.e. proper classes) . Invoking an inductive argument doesn't work for large cardinals (i.e. anything bigger than countable infinity). An important part of the article would explain why this doesn't work, and why one needs to introduce the concept in the first place. Another important part of the article would be to show applications; the one application I know of is to show that something is a proper class, where the relation is used to construct a sequence that is bigger than every cardinal. (I guess that describes your thesis? I just skimmed over a similar progression, where a free lattice is built, and shown to be countably infinite; however the complete free lattice is a proper class (attributed to A.W. Hales, 1964)). I could not begin to write a draft, I've never studied the thing. I think I have just barely enough background to read about it, and thus explain why its confusing, in an unconfusing way. linas 18:51, 7 April 2007 (UTC)

History of Relations[edit]

Approximately how old are relations? About when were they introduced?

def 1 VS def 2[edit]

For the formal definition of a relation which is more prefered among the majority of people? Lol nub 08:53, 23 June 2007 (UTC)

Coplanarity[edit]

What is the point of the "coplanarity" section? It does very little to cast light on the general concept of a relation. It appears like it might be intended as a motivating example for some kind of higher-arity equivalence concept (responding to some implicit objection that binary relations would suffice), but there is no trace of such a concept elsewhere in the article. –Henning Makholm 20:21, 19 January 2008 (UTC)

That appears, indeed, to be the purpose: to give a counterexample to the hypothesis that ternary relations can always be expressed as a conjunction of binary relations. However, the point is not made explicitly, and I don't know if it is worth making here at all. If it is, a simple examples are collinearity of three points in the Euclidean plane. An example of an n-ary relation that is not reducible to a combination of relations of lower arities is the property of a multiset of n numbers of adding up to 0.  --Lambiam 01:45, 20 January 2008 (UTC)

The intro needs revisions[edit]

It is not clear why "5 + 7 = 12" is presented as an example of binary rather than ternary relation. Based on what I have read in the previous paragraphs, I can easily think of it as a combination of three individuals that meet a given condition (specified by the equation). On the contrary, I have no problem to accept that "5 < 12" is a binary relation (second example in the introduction).

It is not easy to interpret "0∈{0,1}" as a binary relation (third example). It comes easier to see it as unary. It is difficult to think of {0,1} as an individual. As far as I know (based on the information provided by this introduction), the definition of this relation might be "the individual x has the property of being included in a given set".

My purpose is not to obtain an answer in this talk page. I am just trying to show that the introduction is not clear. I am not a mathematician and I describe my doubts because I believe that many other readers may have similar doubts. I assume that ignorant readers, like me, can more easily see where necessary information is missing. Paolo.dL (talk) 23:20, 3 March 2008 (UTC)

Thanks to Lambiam for his/her edits. There's still something which could be improved. I believe that "a relation arises when" is not clear. What about "a relation is" (for instance, "a connection existing between a combination of k individuals"?). Please find a simple sentence. Then you can give more details in the successive sentence. For instance: "This connection is described by a property, which may or may not hold...". This makes it possible to associate to the combination a truth value.

Also, I believe that an exsample about equality should be used (for instance, just a function: a function is a relation, isn't it?), because equality is the most common "logical connection", and we are talking about common use.

Also, the description of zero-place relations is not understandable. How can we describe the property of zero individuals? What is the true or false condition? Why "true and false", rather than "true or false"? Paolo.dL (talk) 11:01, 4 March 2008 (UTC)

I agree that "arises" is unclear. Actually a relation is the mathematical formalization of a property, where the subject of the property is a tuple of individuals. Unfortunately, later on it is formalized as a subset of the Cartesian product. The definition of a relation as being a predicate on that Cartesian product is more to my taste; then xRy is just another notation for R(x,y) rather than for (x,y) ∈ R. But, of course, there is a bijection between the powerset of set A and the predicates on A. Setting that issue aside, you'd get something like:
... a relation is a property that assigns truth values to combinations (k-tuples) of k individuals. The property gives a possible connection between tuples of individuals, and the truth value is assigned according to whether the property does or does not hold.
Is that clearer?
I removed equality because of your objection above; to avoid possible confusion I confined the examples to cases where only two individuals were involved, unlike the three in "5 + 7 = 12". For equality we could simply use "x = 0", but I wanted to give examples that evaluate to true, and then you don't have much choice beyond "1 = 1".
A zero-place relation is simply an assignment of truth values to the 0-tuples. As there is only one 0-tuple, there is a bijection between the zero-place relations and the truth values.
If you work within classical logic, there are just two truth values, usually called "true" and "false", but in other logics there is no such dichotomy (see Truth value object and Intuitionistic logic).
 --Lambiam 22:32, 4 March 2008 (UTC)

Dear Lambiam, thanks for your explanations and your edits.

  1. The new definition you suggest is very good in my opinion, and definitely clearer than the current one. Please insert it in the article.
  2. What about an equality such as: f(5) = 12, where f(x) = x + 7? Is this the correct interpretation of the example "5 + 7 = 12"?
  3. I still can't understand the definition of a zero-place relation. Maybe I miss something. Actually, I can't understand the concept of 0-tuples, unless I am allowed to associate them to absolutely nothing, i.e. the absence of individuals. And since there's nothing in a 0-tuple, how can that nothing have a property, except for the total absence of properties? ... I trust you when you say that there's one 0-tuple, but that is highly couterintuitive and I can't undertand why. When I read this intro, I can easily understand the definition of binary relations, and I can see that a relation involves a combination of k individuals, also called k-tuple. This is sufficient to understand the definition of 1-place relations, although my best guess is that this is a generalization of the concept, because the intuitive meaning of the word relation involves at least two individuals. However, my intuition is absolutely defeated when I read the sentence about 0-tuples (which actually is quite interesting and arouses my curiosity; I am not suggesting to delete it). May be I could solve this problem by reading the article about tuples, but should a reader be forced to read other articles to understand an introduction? Of course, I might miss some concept that may be evident to most readers. I assume that most readers are not mathematicians and that I am representative of them, but I might be wrong.

Paolo.dL (talk) 13:29, 5 March 2008 (UTC)

I've made the change to the first paragraph, mentioned equality without giving an actual example, and attempted to clarify zero-place relations. As to there being exactly one 0-tuple, consider how many n-tuples there are if each component is a digit in the range from 0 to 9: 10n. Put n = 0, and you get 100, which equals 1. In general, if you must select one object from each of n sets, then if n = 0 there is only one thing you can do: not pick any objects – since there are no sets to pick objects from. But then, by doing that – not picking any objects – you have fulfilled your task: from each of the given sets you have selected one object! See also Empty product. 19:56, 8 March 2008 (UTC)

Thank you. Ok, I can easily accept that there's one and only one empty set, because a set of zero apples is not different from a set of zero oranges. However, your words seem to imply that this set has one and only one property, hasn't it? Then what is exactly this property? Would you mind to specify in the article? Intuitively, the property "contains 0 elements" seems to define at least a 1-place relation because it deals with at least one individual (the 0-tuple)... as you can see, I am still puzzled. Paolo.dL (talk) 11:30, 9 March 2008 (UTC)

About 0-place relations[edit]

In my opinion, the sentence about 0-place relations remains unclear, even after the latest edit by Lambiam. I'll try to explain how many doubts it might create. Based on the examples, I am led to hypothesize that the property should refer to what is contained in the tuple, and not to the tuple (for instance "won the Nobel prize" refers to the elements in the 1-tuple). So, the properties that I can think of and that hold for the elements contained in the 0-tuple are infineitely many:

  • "does not exist",
  • "is not green"
  • "is not an apple",
  • "did not win the Nobel prize", etc.

The property "is a tuple" seems to be valid for a 0-tuple (an "individual"), not for what is in it (nothing). Similarly, I can think of infinitely many properties that do not hold for the contents of a 0-tuple:

  • "exists",
  • "is green", etc.

However, the recently published sentence refers to only one "property that holds" and to only one "property that does not hold". Laypersons are not likely to understand that sentence. Also, it is not clear in which context the 0-place relations are used and useful. Notice that I won't edit because I am ignorant about this topic. As I explained above, I just immodestly assume that I represent many other ignorant readers. Paolo.dL (talk) 18:49, 11 March 2008 (UTC)

The property should hold (or not hold) for the tuple as a whole. For example, to take an example from the article:
The property "... was-introduced-to ... by ..." holds for the triple (Beatrice Wood, Henri-Pierre Roché, Marcel Duchamp), but not for the triple (Karl Marx, Friedrich Engels, Queen Victoria).
Furthermore, if two properties defined on k-tuples come out the same for all k-tuples, they are considered the same, and give rise to the same relation. For example, between two non-negative numbers X and Y, "X is the square root of Y" and "X squared is equal to Y" are the same property. On the set of 0-tuples, all properties you can define come out as one of the following two
  • "is a 0-tuple",
  • "is not a 0-tuple".
If you take the definition of a k-place relation as being as subset of the set of all k-tuples, it is even simpler to understand the situation. As there is only one 0-tuple, the set of 0-tuples is a singleton set: {()}. It has two subsets: itself, and the empty set. Hope this is clear now.  --Lambiam 20:00, 11 March 2008 (UTC)

Lambiam, your explanation is crystal clear. And yes, the definition of a relation as a subset does make it simpler to understand. Thank you very much for explaining. The only point that is not clear is in which context the 0-place relations are considered to be useful (or are they just a pure exercise of logic without application?).

Anyway, the ultimate purpose of this discussion is to find out how to make the short sentence in the article clearer (if possible), before the formal definition is given. See my edit. It is not complete. The examples in the introduction should be immediately clear. I suggest to state that "the first relation identifies a set containing the 0-tuple itself (singleton set), and the second an empty set". Another option would be to describe 0-place relations and 1-place relations in a specific section of the article. In this case, the intro would just say:

  • "0-place and 1-place relations are defined below".

Paolo.dL (talk) 16:27, 12 March 2008 (UTC)

Apparent contradiction between introduction and formal definition[edit]

Please check my edits in the intro. I hope they are correct. I decided to be bold because I believe they might avoid misunderstandings (provided that they are correct!). Paolo.dL (talk) 10:55, 15 March 2008 (UTC)

These edits, however, make more evident a contradiction in this article. In the intro, a relation seems to define at least two subsets of a given set or tuples (those for which the property hold, and those for which the property does not hold). In the formal definition, the relation is described as a single subset... Paolo.dL (talk) 10:55, 15 March 2008 (UTC)

A subset of a set determines another subset, its relative complement in the set. A subset also corresponds with a property, the property of being a member of the set. Conversely, a property on a set corresponds with a subset, consisting of those elements for which it holds, and then of course it also determines another property, its negation, corresponding to the complement of that subset. There is a one-to-one correspondence between properties on a set and subsets of that set. In the intro, the relation is described as a property, since intuitively, it is easier to think of "<" in "x < y" as describing the property of being smaller, than as the set {{(0,1) (0,2), (1,2), (0,3), (1,3), (2,3), (0,4), ...}.  --Lambiam 08:12, 16 March 2008 (UTC)

Well, then I assume that my edits are correct, and I am glad to have been of service. I believe that the introduction is now clear enough to be understood by readers as ignorant as I were before reading Lambiam's explanations. Lambiam, thank you very much for your enlightening contributions. Paolo.dL (talk) 20:02, 16 March 2008 (UTC)

Suggested reading[edit]

The article has

Texts on set theory typically include a chapter on relations (e.g., chpt. 3 in Suppes 1972). But there is no systematic treatise on the theory of relations, even though relations can be found everywhere in mathematics, logic, and theoretical science, and are well-grounded in elementary set theory. Likewise, there is no comprehensive discussion of how algebraic structures emerge from the assumed properties of relations. These lacunae are all the more amazing given that functions are relations, and function is arguably the most ubiquitous concept in all of mathematics. Carnap (1958) is an introduction to mathematical logic that includes an unusual amount of relation theory, but employs an unconventional notation and terminology. In Lucas (1999), relations are an important part of the intersection of mathematics and philosophy. For an introduction to the closely related subject of relation algebra, see Maddux (2006).

I found this surprising and possibly POV. Comments? --Salix alba (talk) 20:40, 19 September 2008 (UTC)

Well, it appears that the premise of the paragraph that there is no systematic treatise is no longer correct and since it is a section called Suggested Reading I am going to replace the paragraph with a suggestion for the systematic treatise.

Netrapt (talk) 22:34, 24 December 2008 (UTC)

Requested move part 2[edit]

Discussion continued from above.

The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the move request was moved to Finitary relation. Relation (mathematics) retargeted to Binary relation. -- Aervanath (talk) 03:43, 22 April 2009 (UTC)


I have formally requested that this page be moved to Finitary relation. Having this be the main Relation (mathematics) page is potentially confusing, since many (or most) books define a relation as simply a binary relation. My vote would be:

  1. Move the present contents of this page to Finitary relation.
  2. Make Relation (mathematics) into a disambiguation page pointing to both Binary relation and Finitary relation.

No matter what, the current contents of this page really ought to be moved. Jim (talk) 04:29, 14 April 2009 (UTC)

We generally try to avoid disambiguation pages when there are only two articles to disambiguate. Would it be acceptable to have Relation (mathematics) redirect to Binary relation, with a hatnote at the top linking to Finitary relation? -GTBacchus(talk) 02:16, 20 April 2009 (UTC)
That would be fine with me. Jim (talk) 13:30, 21 April 2009 (UTC)
The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

Spam links[edit]

I have removed some obsolete and spam links (especially some links made by banned editor Jon Awbrey) off of this page. Please let me know if this was done in error. Throw it in the Fire (talk) 22:57, 16 October 2010 (UTC)