Changes

: ''This article presents the generalized concept of a relation.  For more basic presentations see the articles on [[binary relation]]s and [[triadic relation]]s.''

: ''This article presents the generalized concept of a relation.  For more basic presentations see the articles on [[binary relation]]s and [[triadic relation]]s.''

In mathematics, the concept of a '''relation''' is a generalization of ''[[binary relation|2-place relation]]s'', such as the relation of ''[[equality (mathematics)|equality]],'' denoted by the sign "=" in a statement like "5&nbsp;+&nbsp;7&nbsp;=&nbsp;12," or the relation of ''[[order theory|order]],'' denoted by the sign "<" in a statement like "5&nbsp;<&nbsp;12".  Relations that involve two ''places'' or ''roles'' are called ''[[binary relation]]s'' by some and ''dyadic relations'' by others, the latter being historically prior but also useful when necessary to avoid confusion with [[binary numeral system|binary (base 2) numerals]].

In mathematics, a '''finitary relation''' is defined by one of the formal definitions given below.

The next step up is to consider relations that can involve more than two places or roles, but still a finite number of them.  These are called ''finite place'' or '''finitary''' relations.  A finitary relation that involves ''k'' places is variously called a ''k-ary'', a ''k-adic'', or a ''k-dimensional'' relation.  The number ''k'' is then called the ''[[arity]]'', the ''adicity'', or the ''[[dimension]]'' of the relation, respectively. See the formal definitions below.

 

* The next step up is to consider relations that involve increasing but still finite numbers of places or roles.  These are called ''finite place'' or ''finitary'' relations.  A finitary relation that involves ''k'' places is variously called a ''k-ary'', a ''k-adic'', or a ''k-dimensional'' relation.  The number ''k'' is then called the ''[[arity]]'', the ''adicity'', or the ''[[dimension]]'' of the relation, respectively.

==Informal introduction==

==Informal introduction==

There are two definitions of k-place relations that are commonly encountered in mathematics.  In order of simplicity, the first of these definitions is as follows:

There are two definitions of k-place relations that are commonly encountered in mathematics.  In order of simplicity, the first of these definitions is as follows:

'''Definition 1.''' A '''relation''' ''L'' over the [[set]]s ''X''₁, …, ''X''_''k'' is a [[subset]] of their [[cartesian product]], written ''L'' ⊆ ''X''₁ &times; … &times; ''X''_''k''.  Under this definition, then, a ''k''-ary relation is simply a set of ''k''-[[tuple]]s.

'''Definition 1.''' A '''relation''' ''L'' over the [[set]]s ''X''₁, …, ''X''_''k'' is a [[subset]] of their [[cartesian product]], written ''L'' &sube; ''X''₁ &times; … &times; ''X''_''k''.  Under this definition, then, a ''k''-ary relation is simply a set of ''k''-[[tuple]]s.

The second definition makes use of an idiom that is common in mathematics, stipulating that "such and such is an ''n''-tuple" in order to ensure that such and such a mathematical object is determined by the specification of ''n'' component mathematical objects.  In the case of a relation ''L'' over ''k'' sets, there are ''k'' + 1 things to specify, namely, the ''k'' sets plus a subset of their cartesian product.  In the idiom, this is expressed by saying that ''L'' is a (''k''+1)-tuple.

The second definition makes use of an idiom that is common in mathematics, stipulating that "such and such is an ''n''-tuple" in order to ensure that such and such a mathematical object is determined by the specification of ''n'' component mathematical objects.  In the case of a relation ''L'' over ''k'' sets, there are ''k'' + 1 things to specify, namely, the ''k'' sets plus a subset of their cartesian product.  In the idiom, this is expressed by saying that ''L'' is a (''k''+1)-tuple.

'''Definition 2.''' A '''relation''' ''L'' over the sets ''X''₁, …, ''X''_''k'' is a (''k''+1)-tuple ''L'' = (''X''₁, …, ''X''_''k'', ''G''(''L'')), where ''G''(''L'') is a subset of the cartesian product ''X''₁ &times; … &times; ''X''_''k''.  ''G''(''L'') is called the ''graph'' of ''L''.

'''Definition 2.''' A '''relation''' ''L'' over the sets ''X''₁, …, ''X''_''k'' is a (''k''+1)-tuple ''L'' = (''X''₁, …, ''X''_''k'', ''G''(''L'')), where ''G''(''L'') is a subset of the cartesian product ''X''₁ &times; … &times; ''X''_''k''.  ''G''(''L'') is called the ''[[graph]]'' of ''L''.

Elements of a relation are more briefly denoted by using boldface characters, for example, the constant element <math>\mathbf{a}</math> = (a₁,&nbsp;…,&nbsp;a_''k'') or the variable element <math>\mathbf{x}</math> = (''x''₁,&nbsp;…,&nbsp;''x''_''k'').

Elements of a relation are more briefly denoted by using boldface characters, for example, the constant element <math>\mathbf{a}</math> = (a₁,&nbsp;…,&nbsp;a_''k'') or the variable element <math>\mathbf{x}</math> = (''x''₁,&nbsp;…,&nbsp;''x''_''k'').

The following considerations apply under either definition:

The following considerations apply under either definition:

:*  The sets ''X''_''j'' for ''j'' = 1 to ''k'' are called the ''[[domain (mathematics)|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 ''X''_''j'' 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.

:* If all of the domains ''X''_''j'' are the same set ''X'', then ''L'' is more simply referred to as  a ''k''-ary relation over ''X''.

:* If all of the domains ''X''_''j'' are the same set ''X'', then ''L'' is more simply referred to as  a ''k''-ary relation over ''X''.

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.

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 ''L'', written ''f''_''L'' or χ(''L''), is the [[boolean-valued function]] ''f''_''L''&nbsp;:&nbsp;''X''₁&nbsp;&times;&nbsp;…&nbsp;&times;&nbsp;''X''_''k''&nbsp;→&nbsp;'''B''', defined in such a way that ''f''_''L''(<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.

The ''[[characteristic function]]'' of the relation ''L'', written ''f''_''L'' or &chi;(''L''), is the [[boolean-valued function]] ''f''_''L''&nbsp;:&nbsp;''X''₁&nbsp;&times;&nbsp;…&nbsp;&times;&nbsp;''X''_''k''&nbsp;→&nbsp;'''B''', defined in such a way that ''f''_''L''(<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 ''f''_''L'' 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]]''.

It is conventional in applied mathematics, computer science, and statistics to refer to a boolean-valued function like ''f''_''L'' 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]]''.

==References==

==References==

* [[Charles Peirce|Peirce, C.S.]] (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", ''Memoirs of the American Academy of Arts and Sciences'' 9, 317–378, 1870.  Reprinted, ''Collected Papers'' CP 3.45–149, ''Chronological Edition'' CE 2, 359–429.

* [[Charles Peirce|Peirce, C.S.]], "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", ''Memoirs of the American Academy of Arts and Sciences'', 9, 317-378, 1870.  Reprinted, ''Collected Papers'' CP 3.45-149, ''Chronological Edition'' CE 2, 359-429.

* [[Stanisław Marcin Ulam|Ulam, S.M.]] and [[Al Bednarek|Bednarek, A.R.]] (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.), ''Analogies Between Analogies:  The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', University of California Press, Berkeley, CA.

* [[Stanisław Marcin Ulam|Ulam, S.M.]] and [[Al Bednarek|Bednarek, A.R.]], "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477-508 in A.R. Bednarek and Françoise Ulam (eds.), ''Analogies Between Analogies:  The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', University of California Press, Berkeley, CA, 1990.

==Bibliography==

==Bibliography==

* [[Nicolas Bourbaki|Bourbaki, N.]] (1994), ''Elements of the History of Mathematics'', John Meldrum (trans.), Springer-Verlag, Berlin, Germany.

* [[Nicolas Bourbaki|Bourbaki, N.]], ''Elements of the History of Mathematics'', John Meldrum (trans.), Springer-Verlag, Berlin, Germany, 1994.

* [[Paul Richard Halmos|Halmos, P.R.]] (1960), ''Naive Set Theory'', D. Van Nostrand Company, Princeton, NJ.

* [[Paul Richard Halmos|Halmos, P.R.]], ''Naive Set Theory'', D. Van Nostrand Company, Princeton, NJ, 1960.

* [[Francis William Lawvere|Lawvere, F.W.]], and [[Robert Rosebrugh|Rosebrugh, R.]] (2003), ''Sets for Mathematics'', Cambridge University Press, Cambridge, UK.

* [[Francis William Lawvere|Lawvere, F.W.]], and [[Robert Rosebrugh|Rosebrugh, R.]], ''Sets for Mathematics'', Cambridge University Press, Cambridge, UK, 2003.

* Maddux, R.D. (2006), ''Relation Algebras'', vol.&nbsp;150 in 'Studies in Logic and the Foundations of Mathematics', Elsevier Science.

* Maddux, R.D., ''Relation Algebras'', vol.&nbsp;150 in 'Studies in Logic and the Foundations of Mathematics', Elsevier Science, 2006.

* [[Marvin L. Minsky|Minsky, M.L.]], and [[Seymour A. Papert|Papert, S.A.]] (1969/1988), ''[[Perceptron]]s, An Introduction to Computational Geometry'', MIT Press, Cambridge, MA, 1969. Expanded edition, 1988.

* [[Marvin L. Minsky|Minsky, M.L.]], and [[Seymour A. Papert|Papert, S.A.]], ''[[Perceptron]]s, An Introduction to Computational Geometry'', MIT Press, Cambridge, MA, 1969. Expanded edition, 1988.

* [[Charles Peirce|Peirce, C.S.]] (1984), ''Writings of Charles S. Peirce:  A Chronological Edition, Volume 2, 1867-1871'', Peirce Edition Project (eds.), Indiana University Press, Bloomington, IN.

* [[Charles Peirce|Peirce, C.S.]], ''Writings of Charles S. Peirce:  A Chronological Edition, Volume 2, 1867-1871'', Peirce Edition Project (eds.), Indiana University Press, Bloomington, IN, 1984. (= CE 2)

* [[Josiah Royce|Royce, J.]] (1961), ''The Principles of Logic'', Philosophical Library, New York, NY.

* [[Josiah Royce|Royce, J.]], ''The Principles of Logic'', Philosophical Library, New York, NY, 1961.

* [[Alfred Tarski|Tarski, A.]] (1956/1983), ''Logic, Semantics, Metamathematics, Papers from 1923 to 1938'', J.H. Woodger (trans.), 1st edition, Oxford University Press, 1956.  2nd edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.

* [[Alfred Tarski|Tarski, A.]], ''Logic, Semantics, Metamathematics, Papers from 1923 to 1938'', J.H. Woodger (trans.), first edition, Oxford University Press, 1956, second edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.

* [[Stanisław Marcin Ulam|Ulam, S.M.]] (1990), ''Analogies Between Analogies:  The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', A.R. Bednarek and Françoise Ulam (eds.), University of California Press, Berkeley, CA.

* [[Stanisław Marcin Ulam|Ulam, S.M.]], ''Analogies Between Analogies:  The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'', A.R. Bednarek and Françoise Ulam (eds.), University of California Press, Berkeley, CA, 1990.

* [[Paulus Venetus|Venetus, P.]] (1984), ''Logica Parva, Translation of the 1472 Edition with Introduction and Notes'', Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.

* [[Paulus Venetus|Venetus, P.]], ''Logica Parva, Translation of the 1472 Edition with Introduction and Notes'', Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany, 1984.

==See also==

==See also==