In mathematics, a finitary relation over a sequence of sets X1, ..., Xn is a subset of the Cartesian product X1 × ... × Xn; that is, it is a set of n-tuples (x1, ..., xn), each being a sequence of elements xi in the corresponding Xi. Typically, the relation describes a possible connection between the elements of an n-tuple. For example, the relation "x is divisible by y and z" consists of the set of 3-tuples such that when substituted to x, y and z, respectively, make the sentence true.
The non-negative integer n that gives the number of "places" in the relation is called the arity, adicity or degree of the relation. A relation with n "places" is variously called an n-ary relation, an n-adic relation or a relation of degree n. Relations with a finite number of places are called finitary relations (or simply relations if the context is clear). It is also possible to generalize the concept to infinitary relations with infinite sequences.
Definitions
When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation.
- Definition
- R is an n-ary relation on sets X1, ..., Xn is given by a subset of the Cartesian product X1 × ... × Xn.
Since the definition is predicated on the underlying sets X1, ..., Xn, R may be more formally defined as the (n + 1)-tuple (X1, ..., Xn, G), where G, called the graph of R, is a subset of the Cartesian product X1 × ... × Xn.
As is often done in mathematics, the same symbol is used to refer to the mathematical object and an underlying set, so the statement (x1, ..., xn) ∈ R is often used to mean (x1, ..., xn) ∈ G is read "x1, ..., xn are R-related" and are denoted using prefix notation by Rx1⋯xn and using postfix notation by x1⋯xnR. In the case where R is a binary relation, those statements are also denoted using infix notation by x1Rx2.
The following considerations apply:
- The set Xi is called the ith domain of R. In the case where R is a binary relation, X1 is also called simply the domain or set of departure of R, and X2 is also called the codomain or set of destination of R.
- When the elements of Xi are relations, Xi is called a nonsimple domain of R.
- The set of ∀xi ∈ Xi such that Rx1⋯xi−1xixi+1⋯xn for at least one (x1, ..., xn) is called the ith domain of definition or active domain of R. In the case where R is a binary relation, its first domain of definition is also called simply the domain of definition or active domain of R, and its second domain of definition is also called the codomain of definition or active codomain of R.
- When the ith domain of definition of R is equal to Xi, R is said to be total on its ith domain (or on Xi, when this is not ambiguous). In the case where R is a binary relation, when R is total on X1, it is also said to be left-total or serial, and when R is total on X2, it is also said to be right-total or surjective.
- When ∀x ∀y ∈ Xi. ∀z ∈ Xj. xRijz ∧ yRijz ⇒ x = y, where i ∈ I, j ∈ J, Rij = πijR, and {I, J} is a partition of {1, ..., n}, R is said to be unique on {Xi}i∈I, and {Xi}i∈J is called a primary key of R. In the case where R is a binary relation, when R is unique on {X1}, it is also said to be left-unique or injective, and when R is unique on {X2}, it is also said to be univalent or right-unique.
- When all Xi are the same set X, it is simpler to refer to R as an n-ary relation over X, called a homogeneous relation. Without this restriction, R is called a heterogeneous relation.
- When any of Xi is empty, the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation R = ∅.
Let a Boolean domain B be a two-element set, say, B = {0, 1}, whose elements can be interpreted as logical values, typically 0 = false and 1 = true. The characteristic function of R, denoted by χR, is the Boolean-valued function χR: X1 × ... × Xn → B, defined by χR((x1, ..., xn)) = 1 if Rx1⋯xn and χR((x1, ..., xn)) = 0 otherwise.
In applied mathematics, computer science and statistics, it is common to refer to a Boolean-valued function as an n-ary predicate. From the more abstract viewpoint of formal logic and model theory, the relation R constitutes a logical model or a relational structure, that serves as one of many possible interpretations of some n-ary predicate symbol.
Because relations arise in many scientific disciplines, as well as in many branches of mathematics and logic, there is considerable variation in terminology. Aside from the set-theoretic extension of a relational concept or term, the term "relation" can also be used to refer to the corresponding logical entity, either the logical comprehension, which is the totality of intensions or abstract properties shared by all elements in the relation, or else the symbols denoting these elements and intensions. Further, some writers of the latter persuasion introduce terms with more concrete connotations (such as "relational structure" for the set-theoretic extension of a given relational concept).
Specific values of n
Nullary
Nullary (0-ary) relations count only two members: the empty nullary relation, which never holds, and the universal nullary relation, which always holds. This is because there is only one 0-tuple, the empty tuple (), and there are exactly two subsets of the (singleton) set of all 0-tuples. They are sometimes useful for constructing the base case of an induction argument.
Unary
Unary (1-ary) relations can be viewed as a collection of members (such as the collection of Nobel laureates) having some property (such as that of having been awarded the Nobel Prize).
Every nullary function is a unary relation.
Binary
Binary (2-ary) relations are the most commonly studied form of finitary relations. Homogeneous binary relations (where X1 = X2) include
- Equality and inequality, denoted by signs such as = and < in statements such as "5 < 12", or
- Divisibility, denoted by the sign | in statements such as "13 | 143".
Heterogeneous binary relations include
- Set membership, denoted by the sign ∈ in statements such as "1 ∈ N".
Ternary
Ternary (3-ary) relations include, for example, the binary functions, which relate two inputs and the output. All three of the domains of a homogeneous ternary relation are the same set.
Example
Consider the ternary relation R "x thinks that y likes z" over the set of people P = { Alice, Bob, Charles, Denise }, defined by:
- R = { (Alice, Bob, Denise), (Charles, Alice, Bob), (Charles, Charles, Alice), (Denise, Denise, Denise) }.
R can be represented equivalently by the following table:
| x | y | z |
|---|---|---|
| Alice | Bob | Denise |
| Charles | Alice | Bob |
| Charles | Charles | Alice |
| Denise | Denise | Denise |
Here, each row represents a triple of R, that is it makes a statement of the form "x thinks that y likes z". For instance, the first row states that "Alice thinks that Bob likes Denise". All rows are distinct. The ordering of rows is insignificant but the ordering of columns is significant.
The above table is also a simple example of a relational database, a field with theory rooted in relational algebra and applications in data management. Computer scientists, logicians, and mathematicians, however, tend to have different conceptions what a general relation is, and what it is consisted of. For example, databases are designed to deal with empirical data, which is by definition finite, whereas in mathematics, relations with infinite arity (i.e., infinitary relation) are also considered.
History
The logician Augustus De Morgan, in work published around 1860, was the first to articulate the notion of relation in anything like its present sense. He also stated the first formal results in the theory of relations (on De Morgan and relations, see Merrill 1990).
Charles Peirce, Gottlob Frege, Georg Cantor, Richard Dedekind and others advanced the theory of relations. Many of their ideas, especially on relations called orders, were summarized in The Principles of Mathematics (1903) where Bertrand Russell made free use of these results.
In 1970, Edgar Codd proposed a relational model for databases, thus anticipating the development of data base management systems.
See also
- Incidence structure
- Hypergraph
- Logic of relatives
- Logical matrix
- Partial order
- Predicate (mathematical logic)
- Projection (set theory)
- Reflexive relation
- Relation algebra
- Relational algebra
- Relational model
- Relations (philosophy)
References
- Codd 1970
- "Relation – Encyclopedia of Mathematics". www.encyclopediaofmath.org. Retrieved 2019-12-12.
- "Definition of n-ary Relation". cs.odu.edu. Retrieved 2019-12-12.
- Nivat 1981
- De Morgan 1966
- "Relations – CS441" (PDF). www.pitt.edu. Retrieved 2019-12-11.
Bibliography
- Bourbaki, N. (1994), Elements of the History of Mathematics, translated by John Meldrum, Springer-Verlag
- Carnap, Rudolf (1958), Introduction to Symbolic Logic with Applications, Dover Publications
- Codd, Edgar Frank (June 1970). "A Relational Model of Data for Large Shared Data Banks" (PDF). Communications of the ACM. 13 (6): 377–387. doi:10.1145/362384.362685. S2CID 207549016. Retrieved 2020-04-29.
- Codd, Edgar Frank (1990). The Relational Model for Database Management: Version 2 (PDF). Boston: Addison-Wesley. ISBN 978-0201141924.
- De Morgan, A. (1966) [1858], "On the syllogism, part 3", in Heath, P. (ed.), On the syllogism and other logical writings, Routledge, p. 119
- Halmos, P.R. (1960), Naive Set Theory, Princeton NJ: D. Van Nostrand Company
- Lawvere, F.W.; Rosebrugh, R (2003), Sets for Mathematics, Cambridge Univ. Press
- Lewis, C.I. (1918) A Survey of Symbolic Logic, Chapter 3: Applications of the Boole–Schröder Algebra, via Internet Archive
- Lucas, J.R. (1999), Conceptual Roots of Mathematics, Routledge
- Maddux, R.D. (2006), Relation Algebras, Studies in Logic and the Foundations of Mathematics, vol. 150, Elsevier Science
- Merrill, Dan D. (1990), Augustus De Morgan and the logic of relations, Kluwer
- Nivat, M. (1981). "Infinitary relations". In Astesiano, Egidio; Böhm, Corrado (eds.). Caap '81. Lecture Notes in Computer Science. Vol. 112. Springer Berlin Heidelberg. pp. 46–75. doi:10.1007/3-540-10828-9_54. ISBN 978-3-540-38716-9.
- 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–78, 1870. Reprinted, Collected Papers CP 3.45–149, Chronological Edition CE 2, 359–429.
- Peirce, C.S. (1984) Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 1867–1871. Peirce Edition Project, eds. Indiana University Press.
- Russell, B. (1938) [1903], The Principles of Mathematics (2nd ed.), Cambridge Univ. Press.
- Suppes, P. (1972) [1960], Axiomatic Set Theory, Dover Publications
- Tarski, A. (1983) [1956], Logic, Semantics, Metamathematics, Papers from 1923 to 1938, translated by J.H. Woodger (1st ed.), Oxford University Press 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
- Ulam, S.M. and (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. (1990), A.R. Bednarek; Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, University of California Press
- Fraïssé, R. (2000) [1986], Theory of Relations, North Holland
In mathematics a finitary relation over a sequence of sets X1 Xn is a subset of the Cartesian product X1 Xn that is it is a set of n tuples x1 xn each being a sequence of elements xi in the corresponding Xi Typically the relation describes a possible connection between the elements of an n tuple For example the relation x is divisible by y and z consists of the set of 3 tuples such that when substituted to x y and z respectively make the sentence true The non negative integer n that gives the number of places in the relation is called the arity adicity or degree of the relation A relation with n places is variously called an n ary relation an n adic relation or a relation of degree n Relations with a finite number of places are called finitary relations or simply relations if the context is clear It is also possible to generalize the concept to infinitary relations with infinite sequences DefinitionsWhen two objects qualities classes or attributes viewed together by the mind are seen under some connexion that connexion is called a relation Augustus De Morgan Definition R is an n ary relation on sets X1 Xn is given by a subset of the Cartesian product X1 Xn Since the definition is predicated on the underlying sets X1 Xn R may be more formally defined as the n 1 tuple X1 Xn G where G called the graph of R is a subset of the Cartesian product X1 Xn As is often done in mathematics the same symbol is used to refer to the mathematical object and an underlying set so the statement x1 xn R is often used to mean x1 xn G is read x1 xn are R related and are denoted using prefix notation by Rx1 xn and using postfix notation by x1 xnR In the case where R is a binary relation those statements are also denoted using infix notation by x1Rx2 The following considerations apply The set Xi is called the i th domain of R In the case where R is a binary relation X1 is also called simply the domain or set of departure of R and X2 is also called the codomain or set of destination of R When the elements of Xi are relations Xi is called a nonsimple domain of R The set of xi Xi such that Rx1 xi 1xixi 1 xn for at least one x1 xn is called the ith domain of definition or active domain of R In the case where R is a binary relation its first domain of definition is also called simply the domain of definition or active domain of R and its second domain of definition is also called the codomain of definition or active codomain of R When the i th domain of definition of R is equal to Xi R is said to be total on its ith domain or on Xi when this is not ambiguous In the case where R is a binary relation when R is total on X1 it is also said to be left total or serial and when R is total on X2 it is also said to be right total or surjective When x y Xi z Xj xRijz yRijz x y where i I j J Rij pijR and I J is a partition of 1 n R is said to be unique on Xi i I and Xi i J is called a primary key of R In the case where R is a binary relation when R is unique on X1 it is also said to be left unique or injective and when R is unique on X2 it is also said to be univalent or right unique When all Xi are the same set X it is simpler to refer to R as an n ary relation over X called a homogeneous relation Without this restriction R is called a heterogeneous relation When any of Xi is empty the defining Cartesian product is empty and the only relation over such a sequence of domains is the empty relation R Let a Boolean domain B be a two element set say B 0 1 whose elements can be interpreted as logical values typically 0 false and 1 true The characteristic function of R denoted by xR is the Boolean valued function xR X1 Xn B defined by xR x1 xn 1 if Rx1 xn and xR x1 xn 0 otherwise In applied mathematics computer science and statistics it is common to refer to a Boolean valued function as an n ary predicate From the more abstract viewpoint of formal logic and model theory the relation R constitutes a logical model or a relational structure that serves as one of many possible interpretations of some n ary predicate symbol Because relations arise in many scientific disciplines as well as in many branches of mathematics and logic there is considerable variation in terminology Aside from the set theoretic extension of a relational concept or term the term relation can also be used to refer to the corresponding logical entity either the logical comprehension which is the totality of intensions or abstract properties shared by all elements in the relation or else the symbols denoting these elements and intensions Further some writers of the latter persuasion introduce terms with more concrete connotations such as relational structure for the set theoretic extension of a given relational concept Specific values of nNullary Nullary 0 ary relations count only two members the empty nullary relation which never holds and the universal nullary relation which always holds This is because there is only one 0 tuple the empty tuple and there are exactly two subsets of the singleton set of all 0 tuples They are sometimes useful for constructing the base case of an induction argument Unary Unary 1 ary relations can be viewed as a collection of members such as the collection of Nobel laureates having some property such as that of having been awarded the Nobel Prize Every nullary function is a unary relation Binary Binary 2 ary relations are the most commonly studied form of finitary relations Homogeneous binary relations where X1 X2 include Equality and inequality denoted by signs such as and lt in statements such as 5 lt 12 or Divisibility denoted by the sign in statements such as 13 143 Heterogeneous binary relations include Set membership denoted by the sign in statements such as 1 N Ternary Ternary 3 ary relations include for example the binary functions which relate two inputs and the output All three of the domains of a homogeneous ternary relation are the same set ExampleConsider the ternary relation R x thinks that y likes z over the set of people P Alice Bob Charles Denise defined by R Alice Bob Denise Charles Alice Bob Charles Charles Alice Denise Denise Denise R can be represented equivalently by the following table Relation R x thinks that y likes z x y zAlice Bob DeniseCharles Alice BobCharles Charles AliceDenise Denise Denise Here each row represents a triple of R that is it makes a statement of the form x thinks that y likes z For instance the first row states that Alice thinks that Bob likes Denise All rows are distinct The ordering of rows is insignificant but the ordering of columns is significant The above table is also a simple example of a relational database a field with theory rooted in relational algebra and applications in data management Computer scientists logicians and mathematicians however tend to have different conceptions what a general relation is and what it is consisted of For example databases are designed to deal with empirical data which is by definition finite whereas in mathematics relations with infinite arity i e infinitary relation are also considered HistoryThe logician Augustus De Morgan in work published around 1860 was the first to articulate the notion of relation in anything like its present sense He also stated the first formal results in the theory of relations on De Morgan and relations see Merrill 1990 Charles Peirce Gottlob Frege Georg Cantor Richard Dedekind and others advanced the theory of relations Many of their ideas especially on relations called orders were summarized in The Principles of Mathematics 1903 where Bertrand Russell made free use of these results In 1970 Edgar Codd proposed a relational model for databases thus anticipating the development of data base management systems See alsoIncidence structure Hypergraph Logic of relatives Logical matrix Partial order Predicate mathematical logic Projection set theory Reflexive relation Relation algebra Relational algebra Relational model Relations philosophy ReferencesCodd 1970 Relation Encyclopedia of Mathematics www encyclopediaofmath org Retrieved 2019 12 12 Definition of n ary Relation cs odu edu Retrieved 2019 12 12 Nivat 1981 De Morgan 1966 Relations CS441 PDF www pitt edu Retrieved 2019 12 11 BibliographyBourbaki N 1994 Elements of the History of Mathematics translated by John Meldrum Springer Verlag Carnap Rudolf 1958 Introduction to Symbolic Logic with Applications Dover Publications Codd Edgar Frank June 1970 A Relational Model of Data for Large Shared Data Banks PDF Communications of the ACM 13 6 377 387 doi 10 1145 362384 362685 S2CID 207549016 Retrieved 2020 04 29 Codd Edgar Frank 1990 The Relational Model for Database Management Version 2 PDF Boston Addison Wesley ISBN 978 0201141924 De Morgan A 1966 1858 On the syllogism part 3 in Heath P ed On the syllogism and other logical writings Routledge p 119 Halmos P R 1960 Naive Set Theory Princeton NJ D Van Nostrand Company Lawvere F W Rosebrugh R 2003 Sets for Mathematics Cambridge Univ Press Lewis C I 1918 A Survey of Symbolic Logic Chapter 3 Applications of the Boole Schroder Algebra via Internet Archive Lucas J R 1999 Conceptual Roots of Mathematics Routledge Maddux R D 2006 Relation Algebras Studies in Logic and the Foundations of Mathematics vol 150 Elsevier Science Merrill Dan D 1990 Augustus De Morgan and the logic of relations Kluwer Nivat M 1981 Infinitary relations In Astesiano Egidio Bohm Corrado eds Caap 81 Lecture Notes in Computer Science Vol 112 Springer Berlin Heidelberg pp 46 75 doi 10 1007 3 540 10828 9 54 ISBN 978 3 540 38716 9 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 78 1870 Reprinted Collected Papers CP 3 45 149 Chronological Edition CE 2 359 429 Peirce C S 1984 Writings of Charles S Peirce A Chronological Edition Volume 2 1867 1871 Peirce Edition Project eds Indiana University Press Russell B 1938 1903 The Principles of Mathematics 2nd ed Cambridge Univ Press Suppes P 1972 1960 Axiomatic Set Theory Dover Publications Tarski A 1983 1956 Logic Semantics Metamathematics Papers from 1923 to 1938 translated by J H Woodger 1st ed Oxford University Press 2nd edition J Corcoran ed Indianapolis IN Hackett Publishing Ulam S M and 1990 On the Theory of Relational Structures and Schemata for Parallel Computation pp 477 508 in A R Bednarek and Francoise 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 1990 A R Bednarek Francoise Ulam eds Analogies Between Analogies The Mathematical Reports of S M Ulam and His Los Alamos Collaborators University of California Press Fraisse R 2000 1986 Theory of Relations North Holland
