Changes

189 bytes removed ,  17:08, 14 November 2015
update
Line 5: Line 5:  
* The basic idea is to generalize the concept of a two-place relation, such as the relation of ''equality'' denoted by the sign &ldquo;<math>=\!</math>&rdquo; in a statement like <math>5 + 7 = 12\!</math> or the relation of ''order'' denoted by the sign &ldquo;<math>{<}\!</math>&rdquo; in a statement like <math>5 < 12.\!</math>&nbsp; Relations that involve two ''places'' or ''roles'' are called ''binary relations'' by some and ''dyadic relations'' by others, the latter being historically prior but also useful when necessary to avoid confusion with ''binary (base 2) numerals''.
 
* The basic idea is to generalize the concept of a two-place relation, such as the relation of ''equality'' denoted by the sign &ldquo;<math>=\!</math>&rdquo; in a statement like <math>5 + 7 = 12\!</math> or the relation of ''order'' denoted by the sign &ldquo;<math>{<}\!</math>&rdquo; in a statement like <math>5 < 12.\!</math>&nbsp; Relations that involve two ''places'' or ''roles'' are called ''binary relations'' by some and ''dyadic relations'' by others, the latter being historically prior but also useful when necessary to avoid confusion with ''binary (base 2) numerals''.
   −
* The concept of a two-place relation is generalized by considering relations with increasing but still finite numbers of places or roles.&nbsp; These are called ''finite-place'' or ''finitary'' relations.&nbsp; A&nbsp;finitary relation involving <math>k\!</math> places is variously called a ''<math>k\!</math>-ary'', a ''<math>k\!</math>-adic'', or a ''<math>k\!</math>-dimensional'' relation.&nbsp; The number <math>k\!</math> is then called the ''arity'', the ''adicity'', or the ''dimension'' of the relation, respectively.
+
* The concept of a two-place relation is generalized by considering relations with increasing but still finite numbers of places or roles.&nbsp; These are called ''finite-place'' or ''finitary'' relations.&nbsp; A&nbsp;finitary relation involving <math>k\!</math> places is variously called a ''<math>k\!</math>-ary'', ''<math>k\!</math>-adic'', or ''<math>k\!</math>-dimensional'' relation.&nbsp; The number <math>k\!</math> is then called the ''arity'', the ''adicity'', or the ''dimension'' of the relation, respectively.
    
==Informal introduction==
 
==Informal introduction==
Line 92: Line 92:  
The following considerations apply under either definition:
 
The following considerations apply under either definition:
   −
:*  The sets ''X''<sub>''j''</sub> for ''j'' = 1 to ''k'' are called the ''[[domain]]s'' of the relation. In the case of the first definition, the relation itself does not uniquely determine a given sequence of domains.
+
:*  The sets <math>X_j~\!</math> for <math>j = 1 ~\text{to}~ k\!</math> are called the ''domains'' of the relation.&nbsp; In the case of the first definition, the relation itself does not uniquely determine a given sequence of domains.
   −
:* If all of the domains ''X''<sub>''j''</sub> are the same set ''X'', then ''L'' is more simply referred to as  a ''k''-ary relation over ''X''.
+
:* If all the domains <math>X_j~\!</math> are the same set <math>X,\!</math> then <math>L\!</math> is more simply referred to as  a <math>k\!</math>-ary relation over <math>X.\!</math>
   −
:* If any of the domains ''X''<sub>''j''</sub> is empty, then the cartesian product is empty, and the only relation over such a sequence of domains is the empty relation ''L'' = <math>\varnothing</math>.  As a result, naturally occurring applications of the relation concept typically involve a stipulation that all of the domains be nonempty.
+
:* If any domain <math>X_j~\!</math> is empty then the cartesian product is empty and the only relation over such a sequence of domains is the empty relation <math>L = \varnothing.\!</math>&nbsp; Most applications of the relation concept will set aside this trivial case and assume that all domains are nonempty.
   −
As a rule, whatever definition best fits the application at hand will be chosen for that purpose, and anything that falls under it will be called a 'relation' for the duration of that discussion.  If it becomes necessary to distinguish the two alternatives, the latter type of object can be referred to as an ''embedded'' or ''included'' relation.
+
If <math>L\!</math> is a relation over the domains <math>X_1, \ldots, X_k,\!</math> it is conventional to consider a sequence of terms called ''variables'', <math>x_1, \ldots, x_k,\!</math> that are said to ''range over'' the respective domains.
   −
If ''L'' is a relation over the domains ''X''<sub>1</sub>, , ''X''<sub>''k''</sub>, it is conventional to consider a sequence of terms called ''variables'', ''x''<sub>1</sub>, …, ''x''<sub>''k''</sub>, that are said to ''range over'' the respective domains.
+
A ''[[boolean domain]]'' <math>\mathbb{B}\!</math> is a generic 2-element set, say, <math>\mathbb{B} = \{ 0, 1 \},\!</math> whose elements are interpreted as logical values, typically <math>0 = \mathrm{false}\!</math> and <math>1 = \mathrm{true}.\!</math>
   −
A ''[[boolean domain]]'' '''B''' is a generic 2-element set, say, '''B''' = {0, 1}, whose elements are interpreted as  logical values, typically 0 = false and 1 = true.
+
The ''characteristic function'' of the relation <math>L,\!</math> written <math>f_L\!</math> or <math>\chi(L),\!</math> is the [[boolean-valued function]] <math>f_L : X_1 \times \ldots \times X_k \to \mathbb{B},\!</math> defined in such a way that <math>f_L (\mathbf{x}) = 1\!</math> just in case the <math>k\!</math>-tuple <math>\mathbf{x} = (x_1, \ldots, x_k)\!</math> is in the relation <math>L.\!</math>&nbsp; The characteristic function of a relation may also be called its ''indicator function'', especially in probabilistic and statistical contexts.
   −
The ''[[characteristic function]]'' of the relation ''L'', written ''f''<sub>''L''</sub> or &chi;(''L''), is the [[boolean-valued function]] ''f''<sub>''L''</sub>&nbsp;:&nbsp;''X''<sub>1</sub>&nbsp;&times;&nbsp;…&nbsp;&times;&nbsp;''X''<sub>''k''</sub>&nbsp;→&nbsp;'''B''', defined in such a way that ''f''<sub>''L''</sub>(<math>\mathbf{x}</math>) = 1 just in case the ''k''-tuple <math>\mathbf{x}</math> is in the relation ''L''.  The characteristic function of a relation may also be called its ''[[indicator function]]'', especially in probability and statistics.
+
It is conventional in applied mathematics, computer science, and statistics to refer to a boolean-valued function like <math>f_L\!</math> as a <math>k\!</math>-place ''predicate''.&nbsp; From the more abstract viewpoints of formal logic and model theory, the relation <math>L\!</math> is seen as constituting a ''logical model'' or a ''relational structure'' that serves as one of many possible interpretations of a corresponding <math>k\!</math>-place ''predicate symbol'', as that term is used in ''predicate calculus''.
   −
It is conventional in applied mathematics, computer science, and statistics to refer to a boolean-valued function like ''f''<sub>''L''</sub> as a ''k''-place ''[[predicate]]''.  From the more abstract viewpoints of [[formal logic]] and [[model theory]], the relation ''L'' is seen as constituting a ''logical model'' or a ''relational structure'' that serves as one of many possible [[interpretation]]s of a corresponding ''k''-place ''predicate symbol'', as that term is used in ''[[first-order logic|predicate calculus]]''.
+
Due to the convergence of many traditions of study, there are wide variations in the language used to describe relations.&nbsp; The ''extensional'' approach presented in this article treats a relation as the set-theoretic ''extension'' of a relational concept or term.&nbsp; An alternative, ''intensional approach'' reserves the term ''relation'' to the corresponding logical entity, either the ''logical comprehension'', which is the totality of ''intensions'' or abstract ''properties'' that all the elements of the extensional relation have in common, or else the symbols that are taken to denote those elements and intensions.
 
  −
Due to the convergence of many different styles of study on the same areas of interest, the reader will find much variation in usage here. The variation presented in this article treats a relation as the [[set theory|set-theoretic]] ''[[extension (semantics)|extension]]'' of a relational concept or term. Another variation reserves the term 'relation' to the corresponding logical entity, either the ''[[comprehension (logic)|logical comprehension]]'', which is the totality of ''[[intension]]s'' or abstract ''[[property (philosophy)|properties]]'' that all of the elements of the relation in extension have in common, or else the symbols that are taken to denote these elements and intensions.  Further, but hardly finally, some writers of the latter persuasion introduce terms with more concrete connotations, like 'relational structure', for the set-theoretic extension of a given relational concept.
      
==Example 2. Coplanarity==
 
==Example 2. Coplanarity==
   −
For lines ''L'' in three-dimensional space, there is a ternary relation picking out the triples of lines that are [[coplanar]]. This ''does not'' reduce to the binary [[symmetric relation]] of coplanarity of pairs of lines.
+
For lines <math>\ell\!</math> in three-dimensional space, there is a triadic relation picking out the triples of lines that are coplanar.&nbsp; This does not reduce to the dyadic relation of coplanarity between pairs of lines.
   −
In other words, writing ''P''(''L'', ''M'', ''N'') when the lines ''L'', ''M'', and ''N'' lie in a plane, and ''Q''(''L'', ''M'') for the binary relation, it is not true that ''Q''(''L'', ''M''), ''Q''(''M'', ''N'') and ''Q''(''N'', ''L'') together imply ''P''(''L'', ''M'', ''N''); although the converse is certainly true (any pair out of three coplanar lines is coplanar, ''a fortiori''). There are two geometrical reasons for this.
+
In other words, writing <math>P(\ell, m, n)\!</math> when the lines <math>\ell, m, n\!</math> lie in a plane, and <math>Q(\ell, m)\!</math> for the binary relation, it is not true that <math>Q(\ell, m),\!</math> <math>Q(m, n),\!</math> and <math>Q(n, \ell)\!</math> together imply <math>P(\ell, m, n),\!</math> although the converse is certainly true:&nbsp; any two of three coplanar lines are necessarily coplanar.&nbsp; There are two geometrical reasons for this.
   −
In one case, for example taking the ''x''-axis, ''y''-axis and ''z''-axis, the three lines are concurrent, i.e. intersect at a single point. In another case, ''L'', ''M'', and ''N'' can be three edges of an infinite [[triangular prism]].
+
In one case, for example taking the <math>x\!</math>-axis, <math>y\!</math>-axis, and <math>z\!</math>-axis, the three lines are concurrent, that is, they intersect at a single point.&nbsp; In another case, <math>\ell, m, n\!</math> can be three edges of an infinite triangular prism.
    
What is true is that if each pair of lines intersects, and the points of intersection are distinct, then pairwise coplanarity implies coplanarity of the triple.
 
What is true is that if each pair of lines intersects, and the points of intersection are distinct, then pairwise coplanarity implies coplanarity of the triple.
Line 122: Line 120:  
==Remarks==
 
==Remarks==
   −
Relations are classified according to the number of sets in the cartesian product, in other words the number of terms in the expression:
+
Relations are classified by the number of sets in the cartesian product, in other words, the number of places or terms in the relational expression:
:* Unary relation or [[property (philosophy)|property]]: ''L''(''u'')
+
 
:* Binary relation: ''L''(''u'', ''v'') or ''u'' ''L'' ''v''
+
{| align="center" cellspacing="6" width="90%"
:* Ternary relation: ''L''(''u'', ''v'', ''w'')
+
| width="18%" | <math>L(a)\!</math>
:* Quaternary relation: ''L''(''u'', ''v'', ''w'', ''x'')
+
| Monadic or unary relation, in other words, a property or set
 +
|-
 +
| <math>L(a, b) ~\text{or}~ a L b\!</math>
 +
| Dyadic or binary relation
 +
|-
 +
| <math>L(a, b, c)\!</math>
 +
| Triadic or ternary relation
 +
|-
 +
| <math>L(a, b, c, d)\!</math>
 +
| Tetradic or quaternary relation
 +
|-
 +
| <math>L(a, b, c, d, e)\!</math>
 +
| Pentadic or quinary relation
 +
|}
   −
Relations with more than four terms are usually referred to as ''k''-ary, for example, "a 5-ary relation".
+
Relations with more than five terms are usually referred to as <math>k\!</math>-adic or <math>k\!</math>-ary, for example, a 6-adic, 6-ary, or hexadic relation.
    
==References==
 
==References==
Line 278: Line 289:  
* [http://en.wikipedia.org/w/index.php?title=Relation_(mathematics)&oldid=73324659 Relation], [http://en.wikipedia.org/ Wikipedia]
 
* [http://en.wikipedia.org/w/index.php?title=Relation_(mathematics)&oldid=73324659 Relation], [http://en.wikipedia.org/ Wikipedia]
    +
[[Category:Charles Sanders Peirce]]
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]
 
[[Category:Computer Science]]
 
[[Category:Computer Science]]
12,080

edits