12,080
edits
Changes
Relation (mathematics) (view source)
Revision as of 21:12, 12 November 2015
, 21:12, 12 November 2015update
In mathematics, a '''finitary relation''' is defined by one of the formal definitions given below.
In mathematics, a '''finitary relation''' is defined by one of the formal definitions given below.
* The basic idea is to generalize the concept of a ''[[binary relation|2-place relation]]'', such as the relation of ''[[equality (mathematics)|equality]]'' denoted by the sign "=" in a statement like "5 + 7 = 12" or the relation of ''[[order theory|order]]'' denoted by the sign "<" in a statement like "5 < 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]].
* The basic idea is to generalize the concept of a two-place relation, such as the relation of ''equality'' denoted by the sign “<math>=\!</math>” in a statement like <math>5 + 7 = 12\!</math> or the relation of ''order'' denoted by the sign “<math>{<}\!</math>” in a statement like <math>5 < 12.\!</math> 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 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.
* The concept of a two-place relation is generalized by considering relations with increasing but still finite numbers of places or roles. These are called ''finite-place'' or ''finitary'' relations. A 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. The number <math>k\!</math> is then called the ''arity'', the ''adicity'', or the ''dimension'' of the relation, respectively.
==Informal introduction==
==Informal introduction==
The definition of ''relation'' given in the next Section formally captures a concept that is actually quite familiar from everyday life. For example, consider the relationship, involving three roles that people might play, expressed in a statement of the form "''X'' suspects that ''Y'' likes ''Z'' ". The facts of a concrete situation could be organized in a Table like the following:
The definition of ''relation'' given in the next section formally captures a concept that is actually quite familiar from everyday life. For example, consider the relationship, involving three roles that people might play, expressed in a statement of the form <math>X ~\text{suspects that}~ Y ~\text{likes}~ Z.\!</math> The facts of a concrete situation could be organized in the form of a Table like the one below:
{| align="center" border="1" cellpadding="4" cellspacing="0" style="background:#f8f8ff; text-align:center; width:60%"
<br>
|+ '''Relation S : X suspects that Y likes Z'''
|- style="background:#e6e6ff"
{| align="center" border="1" cellpadding="8" cellspacing="0" style="text-align:center; width:60%"
|+ style="height:30px" |
<math>\text{Relation}~ S ~:~ X ~\text{suspects that}~ Y ~\text{likes}~ Z\!</math>
|- style="height:40px; background:ghostwhite"
| <math>\text{Person}~ X\!</math>
| <math>\text{Person}~ Y\!</math>
| <math>\text{Person}~ Z\!</math>
|-
|-
| Alice || Bob || Denise
| <math>\text{Alice}\!</math>
| <math>\text{Bob}\!</math>
| <math>\text{Denise}\!</math>
|-
|-
| Charles || Alice || Bob
| <math>\text{Charles}\!</math>
| <math>\text{Alice}\!</math>
| <math>\text{Bob}\!</math>
|-
|-
| Charles || Charles || Alice
| <math>\text{Charles}\!</math>
| <math>\text{Charles}\!</math>
| <math>\text{Alice}\!</math>
|-
|-
| Denise || Denise || Denise
| <math>\text{Denise}\!</math>
| <math>\text{Denise}\!</math>
| <math>\text{Denise}\!</math>
|}
|}
<br>
<br>
Each row of the Table records a fact or makes an assertion of the form "''X'' suspects that ''Y'' likes ''Z'' ". For instance, the first row says, in effect, "Alice suspects that Bob likes Denise". The Table represents a relation ''S'' over the set ''P'' of people under discussion:
Each row of the Table records a fact or makes an assertion of the form <math>X ~\text{suspects that}~ Y ~\text{likes}~ Z.\!</math> For instance, the first row says, in effect, <math>\text{Alice suspects that Bob likes Denise.}\!</math> The Table represents a relation <math>S\!</math> over the set <math>P\!</math> of people under discussion:
{| align="center" cellpadding="10"
| <math>P ~=~ \{ \text{Alice}, \text{Bob}, \text{Charles}, \text{Denise} \}\!</math>
|}
The data of the Table are equivalent to the following set of ordered triples:
The data of the Table are equivalent to the following set of ordered triples:
{| align="center" cellpadding="10"
|
<math>\begin{smallmatrix}
S
& =
& \{
& \text{(Alice, Bob, Denise)},
& \text{(Charles, Alice, Bob)},
& \text{(Charles, Charles, Alice)},
& \text{(Denise, Denise, Denise)}
& \}
\end{smallmatrix}\!</math>
|}
By a slight overuse of notation, it is usual to write ''S''(Alice, Bob, Denise) to say the same thing as the first row of the Table. The relation ''S'' is a ''ternary'' relation, since there are ''three'' items involved in each row. The relation itself is a mathematical object, defined in terms of concepts from [[set theory]], that carries all of the information from the Table in one neat package.
By a slight overuse of notation, it is usual to write <math>S (\text{Alice}, \text{Bob}, \text{Denise})\!</math> to say the same thing as the first row of the Table. The relation <math>S\!</math> is a ''triadic'' or ''ternary'' relation, since there are ''three'' items involved in each row. The relation itself is a mathematical object, defined in terms of concepts from set theory, that carries all the information from the Table in one neat package.
The Table for relation ''S'' is an extremely simple example of a [[relational database]]. The theoretical aspects of databases are the specialty of one branch of [[computer science]], while their practical impacts have become all too familiar in our everyday lives. Computer scientists, logicians, and mathematicians, however, tend to see different things when they look at these concrete examples and samples of the more general concept of a relation.
The Table for relation <math>S\!</math> is an extremely simple example of a relational database. The theoretical aspects of databases are the specialty of one branch of computer science, while their practical impacts have become all too familiar in our everyday lives. Computer scientists, logicians, and mathematicians, however, tend to see different things when they look at these concrete examples and samples of the more general concept of a relation.
For one thing, databases are designed to deal with empirical data, and experience is always finite, whereas mathematics is nothing if not concerned with infinity, at the very least, potential infinity. This difference in perspective brings up a number of ideas that are usefully introduced at this point, if by no means covered in depth.
For one thing, databases are designed to deal with empirical data, and experience is always finite, whereas mathematics is nothing if not concerned with infinity, at the very least, potential infinity. This difference in perspective brings up a number of ideas that are usefully introduced at this point, if by no means covered in depth.
==Example: divisibility==
==Example: Divisibility==
A more typical example of a 2-place relation in mathematics is the relation of ''[[divisor|divisibility]]'' between two positive integers ''n'' and ''m'' that is expressed in statements like "''n'' divides ''m''" or "''n'' goes into ''m''". This is a relation that comes up so often that a special symbol "|" is reserved to express it, allowing one to write "''n''|''m''" for "''n'' divides ''m''".
A more typical example of a two-place relation in mathematics is the relation of ''divisibility'' between two positive integers <math>n\!</math> and <math>m\!</math> that is expressed in statements like <math>{}^{\backprime\backprime} n ~\text{divides}~ m {}^{\prime\prime}\!</math> or <math>{}^{\backprime\backprime} n ~\text{goes into}~ m {}^{\prime\prime}.\!</math> This is a relation that comes up so often that a special symbol <math>{}^{\backprime\backprime} | {}^{\prime\prime}\!</math> is reserved to express it, allowing one to write <math>{}^{\backprime\backprime} n|m {}^{\prime\prime}\!</math> for <math>{}^{\backprime\backprime} n ~\text{divides}~ m {}^{\prime\prime}.\!</math>
To express the binary relation of divisibility in terms of sets, we have the set ''P'' of positive integers, ''P'' = {1, 2, 3, …}, and we have the binary relation ''D'' on ''P'' such that the ordered pair (''n'', ''m'') is in the relation ''D'' just in case ''n''|''m''. In other turns of phrase that are frequently used, one says that the number ''n'' is related by ''D'' to the number ''m'' just in case ''n'' is a factor of ''m'', that is, just in case ''n'' divides ''m'' with no remainder. The relation ''D'', regarded as a set of ordered pairs, consists of all pairs of numbers (''n'', ''m'') such that ''n'' divides ''m''.
To express the binary relation of divisibility in terms of sets, we have the set <math>P\!</math> of positive integers, <math>P = \{ 1, 2, 3, \ldots \},\!</math> and we have the binary relation <math>D\!</math> on <math>P\!</math> such that the ordered pair <math>(n, m)\!</math> is in the relation <math>D\!</math> just in case <math>n|m.\!</math> In other turns of phrase that are frequently used, one says that the number <math>n\!</math> is related by <math>D\!</math> to the number <math>m\!</math> just in case <math>n\!</math> is a factor of <math>m,\!</math> that is, just in case <math>n\!</math> divides <math>m\!</math> with no remainder. The relation <math>D,\!</math> regarded as a set of ordered pairs, consists of all pairs of numbers <math>(n, m)\!</math> such that <math>n\!</math> divides <math>m.\!</math>
For example, 2 is a factor of 4, and 6 is a factor of 72, which two facts can be written either as 2|4 and 6|72 or as ''D''(2, 4) and ''D''(6, 72).
For example, <math>2\!</math> is a factor of <math>4,\!</math> and <math>6\!</math> is a factor of <math>72,\!</math> which two facts can be written either as <math>2|4\!</math> and <math>6|72\!</math> or as <math>D(2, 4)\!</math> and <math>D(6, 72).\!</math>
==Formal definitions==
==Formal definitions==
==References==
==References==
* [[Charles Sanders 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 Sanders 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.
* [[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.
* Ulam, S.M., and 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.
==Bibliography==
==Bibliography==
===Focal nodes===
===Focal nodes===
* [[Inquiry Live]]
* [[Inquiry Live]]
* [[Logic Live]]
* [[Logic Live]]
===Peer nodes===
===Peer nodes===
* [http://intersci.ss.uci.edu/wiki/index.php/Relation_(mathematics) Relation @ InterSciWiki]
* [http://mywikibiz.com/Relation_(mathematics) Relation @ MyWikiBiz]
* [http://mywikibiz.com/Relation_(mathematics) Relation @ MyWikiBiz]
* [http://ref.subwiki.org/wiki/Relation_(mathematics) Relation @ Subject Wikis]
* [http://ref.subwiki.org/wiki/Relation_(mathematics) Relation @ Subject Wikis]
* [http://en.wikiversity.org/wiki/Relation_(mathematics) Relation @ Wikiversity]
* [http://beta.wikiversity.org/wiki/Relation_(mathematics) Relation @ Wikiversity Beta]
* [http://beta.wikiversity.org/wiki/Relation_(mathematics) Relation @ Wikiversity Beta]
===Logical operators===
===Logical operators===
===Related articles===
===Related articles===
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Semiotic_Information Jon Awbrey, “Semiotic Information”]
{{col-begin}}
{{col-break}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Introduction_to_Inquiry_Driven_Systems Jon Awbrey, “Introduction To Inquiry Driven Systems”]
* [http://intersci.ss.uci.edu/wiki/index.php/Cactus_Language Cactus Language]
* [http://intersci.ss.uci.edu/wiki/index.php/Futures_Of_Logical_Graphs Futures Of Logical Graphs]
* [http://mywikibiz.com/Directory:Jon_Awbrey/Essays/Prospects_For_Inquiry_Driven_Systems Jon Awbrey, “Prospects For Inquiry Driven Systems”]
* [http://intersci.ss.uci.edu/wiki/index.php/Propositional_Equation_Reasoning_Systems Propositional Equation Reasoning Systems]
{{col-break}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Inquiry_Driven_Systems Jon Awbrey, “Inquiry Driven Systems : Inquiry Into Inquiry”]
* [http://intersci.ss.uci.edu/wiki/index.php/Differential_Logic_:_Introduction Differential Logic : Introduction]
* [http://intersci.ss.uci.edu/wiki/index.php/Differential_Propositional_Calculus Differential Propositional Calculus]
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Propositional_Equation_Reasoning_Systems Jon Awbrey, “Propositional Equation Reasoning Systems”]
* [http://intersci.ss.uci.edu/wiki/index.php/Differential_Logic_and_Dynamic_Systems_2.0 Differential Logic and Dynamic Systems]
{{col-break}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Differential_Logic_:_Introduction Jon Awbrey, “Differential Logic : Introduction”]
* [http://intersci.ss.uci.edu/wiki/index.php/Introduction_to_Inquiry_Driven_Systems Introduction to Inquiry Driven Systems]
* [http://intersci.ss.uci.edu/wiki/index.php/Prospects_for_Inquiry_Driven_Systems Prospects for Inquiry Driven Systems]
* [http://planetmath.org/encyclopedia/DifferentialPropositionalCalculus.html Jon Awbrey, “Differential Propositional Calculus”]
* [http://intersci.ss.uci.edu/wiki/index.php/Inquiry_Driven_Systems Inquiry Driven Systems : Inquiry Into Inquiry]
{{col-end}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Differential_Logic_and_Dynamic_Systems_2.0 Jon Awbrey, “Differential Logic and Dynamic Systems”]
==Document history==
==Document history==
Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders.
Portions of the above article were adapted from the following sources under the [[GNU Free Documentation License]], under other applicable licenses, or by permission of the copyright holders.
* [http://intersci.ss.uci.edu/wiki/index.php/Relation_(mathematics) Relation], [http://intersci.ss.uci.edu/ InterSciWiki]
* [http://mywikibiz.com/Relation_(mathematics) Relation], [http://mywikibiz.com/ MyWikiBiz]
* [http://mywikibiz.com/Relation_(mathematics) Relation], [http://mywikibiz.com/ MyWikiBiz]
* [http://wikinfo.org/w/index.php/Relation_(mathematics) Relation], [http://wikinfo.org/w/ Wikinfo]
* [http://en.wikiversity.org/wiki/Relation_(mathematics) Relation], [http://en.wikiversity.org/ Wikiversity]
* [http://beta.wikiversity.org/wiki/Relation_(mathematics) Relation], [http://beta.wikiversity.org/ Wikiversity Beta]
* [http://beta.wikiversity.org/wiki/Relation_(mathematics) Relation], [http://beta.wikiversity.org/ Wikiversity Beta]
* [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:Combinatorics]]
[[Category:Computer Science]]
[[Category:Database Theory]]
[[Category:Discrete Mathematics]]
[[Category:Inquiry]]
[[Category:Inquiry]]
[[Category:Logic]]
[[Category:Logic]]
[[Category:Mathematics]]
[[Category:Mathematics]]
[[Category:Relation Theory]]
[[Category:Relation Theory]]
[[Category:Semiotics]]
[[Category:Set Theory]]
[[Category:Set Theory]]