12,080
edits
Changes
Relation (mathematics) (view source)
Revision as of 18:12, 13 November 2015
, 18:12, 13 November 2015update
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 1. Divisibility==
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>
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>
==Formal definitions==
==Formal definitions==
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 <math>k\!</math>-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''<sub>1</sub>, …, ''X''<sub>''k''</sub> is a [[subset]] of their [[cartesian product]], written ''L'' ⊆ ''X''<sub>1</sub> × … × ''X''<sub>''k''</sub>. Under this definition, then, a ''k''-ary relation is simply a set of ''k''-[[tuple]]s.
'''Definition 1.''' A '''relation''' <math>L\!</math> over the sets <math>X_1, \ldots, X_k\!</math> is a subset of their cartesian product, written <math>L \subseteq X_1 \times \ldots \times X_k.\!</math> Under this definition, then, a <math>k\!</math>-ary relation is simply a set of <math>k\!</math>-tuples.
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, saying that “such and such is an <math>n\!</math>-tuple” to mean that the mathematical object being defined is determined by the specification of <math>n\!</math> component mathematical objects. In the case of a relation <math>L\!</math> over <math>k\!</math> sets, there are <math>k + 1\!</math> things to specify, namely, the <math>k\!</math> sets plus a subset of their cartesian product. In the idiom, this is expressed by saying that <math>L\!</math> is a <math>(k+1)\!</math>-tuple.
'''Definition 2.''' A '''relation''' ''L'' over the sets ''X''<sub>1</sub>, …, ''X''<sub>''k''</sub> is a (''k''+1)-tuple ''L'' = (''X''<sub>1</sub>, …, ''X''<sub>''k''</sub>, ''G''(''L'')), where ''G''(''L'') is a subset of the cartesian product ''X''<sub>1</sub> × … × ''X''<sub>''k''</sub>. ''G''(''L'') is called the ''[[graph]]'' of ''L''.
'''Definition 2.''' A '''relation''' <math>L\!</math> over the sets <math>X_1, \ldots, X_k\!</math> is a <math>(k+1)\!</math>-tuple <math>L = (X_1, \ldots, X_k, \mathrm{graph}(L)),\!</math> where <math>\mathrm{graph}(L)\!</math> is a subset of the cartesian product <math>X_1 \times \ldots \times X_k~\!</math> called the ''graph'' of <math>L.\!</math>
Elements of a relation are more briefly denoted by using boldface characters, for example, the constant element <math>\mathbf{a}</math> = (a<sub>1</sub>, …, a<sub>''k''</sub>) or the variable element <math>\mathbf{x}</math> = (''x''<sub>1</sub>, …, ''x''<sub>''k''</sub>).
Elements of a relation are sometimes denoted by using boldface characters, for example, the constant element <math>\mathbf{a} = (a_1, \ldots, a_k)\!</math> or the variable element <math>\mathbf{x} = (x_1, \ldots, x_k).\!</math>
A statement of the form "<math>\mathbf{a}</math> is in the relation ''L'' " is taken to mean that <math>\mathbf{a}</math> is in ''L'' under the first definition and that <math>\mathbf{a}</math> is in ''G''(''L'') under the second definition.
A statement of the form “<math>\mathbf{a}\!</math> is in the relation <math>L\!</math>” is taken to mean that <math>\mathbf{a}\!</math> is in <math>L\!</math> under the first definition and that <math>\mathbf{a}\!</math> is in <math>\mathrm{graph}(L)\!</math> under the second definition.
The following considerations apply under either definition:
The following considerations apply under either definition:
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.
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: 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 ''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.
==Bibliography==
==Bibliography==
* [[Nicolas Bourbaki|Bourbaki, N.]] (1994), ''Elements of the History of Mathematics'', John Meldrum (trans.), Springer-Verlag, Berlin, Germany.
* Bourbaki, N. (1994), ''Elements of the History of Mathematics'', John Meldrum (trans.), Springer-Verlag, Berlin, Germany.
* [[Paul Richard Halmos|Halmos, P.R.]] (1960), ''Naive Set Theory'', D. Van Nostrand Company, Princeton, NJ.
* Halmos, P.R. (1960), ''Naive Set Theory'', D. Van Nostrand Company, Princeton, NJ.
* [[Francis William Lawvere|Lawvere, F.W.]], and [[Robert Rosebrugh|Rosebrugh, R.]] (2003), ''Sets for Mathematics'', Cambridge University Press, Cambridge, UK.
* Lawvere, F.W., and Rosebrugh, R. (2003), ''Sets for Mathematics'', Cambridge University Press, Cambridge, UK.
* Maddux, R.D. (2006), ''Relation Algebras'', vol. 150 in 'Studies in Logic and the Foundations of Mathematics', Elsevier Science.
* Maddux, R.D. (2006), ''Relation Algebras'', vol. 150 in Studies in Logic and the Foundations of Mathematics, Elsevier Science.
* Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994), ''Computer Program Construction'', Oxford University Press, New York, NY.
* Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994), ''Computer Program Construction'', Oxford University Press, New York, NY.
* [[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.
* Minsky, M.L., and Papert, S.A. (1969/1988), ''Perceptrons, An Introduction to Computational Geometry'', MIT Press, Cambridge, MA, 1969. Expanded edition, 1988.
* [[Charles Sanders 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 Sanders 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.
* [[Josiah Royce|Royce, J.]] (1961), ''The Principles of Logic'', Philosophical Library, New York, NY.
* Royce, J. (1961), ''The Principles of Logic'', Philosophical Library, New York, NY.
* [[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.
* 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.
* [[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.
* 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.
* [[Paulus Venetus|Venetus, P.]] (1984), ''Logica Parva, Translation of the 1472 Edition with Introduction and Notes'', Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.
* Venetus, P. (1984), ''Logica Parva, Translation of the 1472 Edition with Introduction and Notes'', Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.
==Syllabus==
==Syllabus==