In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a finitary relation over sets is a subset of the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
; that is, it is a set of ''n''-tuples consisting of elements ''x''
''i'' in ''X''
''i''.
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'' giving the number of "places" in the relation is called the ''
arity
Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
'', ''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.
An ''n''-ary relation over sets is an element of the
power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of .
0-ary relations count only two members: the one that always holds, and the one that never holds. This is because there is only one 0-tuple, the empty tuple (). They are sometimes useful for constructing the base case of an
induction
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
argument.
Unary relations can be viewed as a collection of members (such as the collection of
Nobel laureates
The Nobel Prizes ( sv, Nobelpriset, no, Nobelprisen) are awarded annually by the Royal Swedish Academy of Sciences, the Swedish Academy, the Karolinska Institutet, and the Norwegian Nobel Committee to individuals and organizations who make ou ...
) having some property (such as that of having been awarded the
Nobel prize
The Nobel Prizes ( ; sv, Nobelpriset ; no, Nobelprisen ) are five separate prizes that, according to Alfred Nobel's will of 1895, are awarded to "those who, during the preceding year, have conferred the greatest benefit to humankind." Alfr ...
).
Binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
s are the most commonly studied form of finitary relations. When ''X''
1 = ''X''
2 it is called a
homogeneous relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
, for example:
*
Equality
Equality may refer to:
Society
* Political equality, in which all members of a society are of equal standing
** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elite ...
and
inequality
Inequality may refer to:
Economics
* Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy
* Economic inequality, difference in economic well-being between population groups
* ...
, denoted by signs such as = and < in statements such as "", or
*
Divisibility
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
, denoted by the sign , in statements such as "13, 143".
Otherwise it is a
heterogeneous relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
, for example:
*
Set membership
In mathematics, an element (or member) of a set is any one of the distinct objects that belong to that set.
Sets
Writing A = \ means that the elements of the set are the numbers 1, 2, 3 and 4. Sets of elements of , for example \, are subsets o ...
, denoted by the sign ∈ in statements such as "".
Example
Consider the ternary relation ''R'' "''x'' thinks that ''y'' likes ''z''" over the set of people , defined by:
: .
''R'' can be represented equivalently by the following table:
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 relational database is a (most commonly digital) database based on the relational model of data, as proposed by E. F. Codd in 1970. A system used to maintain relational databases is a relational database management system (RDBMS). Many relatio ...
, a field with theory rooted in
relational algebra
In database theory, relational algebra is a theory that uses algebraic structures with a well-founded semantics for modeling data, and defining queries on it. The theory was introduced by Edgar F. Codd.
The main application of 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.
Definitions
The first definition of relations encountered in mathematics is:
; Definition 1: An ''n''-ary relation ''R'' over sets is a subset of the Cartesian product .
The second definition of relations 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 mathematical objects with ''n'' elements. In the case of a relation ''R'' over ''n'' sets, there are things to specify, namely, the ''n'' sets plus a subset of their Cartesian product. In the idiom, this is expressed by saying that ''R'' is a ()-tuple.
; Definition 2: An ''n''-ary relation ''R'' over sets is an ()-tuple where ''G'' is a subset of the Cartesian product called the ''graph'' of ''R''.
As a rule, whatever definition best fits the application at hand will be chosen for that purpose, and if it ever becomes necessary to distinguish between the two definitions, then an entity satisfying the second definition may be called an ''embedded'' or ''included relation''.
Both statements (under the first definition) and (under the second definition) read "''x''
1, ⋯, ''x''
''n'' are ''R''-related" and are denoted using
prefix notation
Polish notation (PN), also known as normal Polish notation (NPN), Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators ''precede'' their operands, in contrast t ...
by and using
postfix notation
Reverse Polish notation (RPN), also known as reverse Łukasiewicz notation, Polish postfix notation or simply postfix notation, is a mathematical notation in which operators ''follow'' their operands, in contrast to Polish notation (PN), in whi ...
by . In the case where ''R'' is a binary relation, those statements are also denoted using
infix notation
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands—" infixed operators"—such as the plus sign in .
Usage
Binary relations a ...
by .
The following considerations apply under either definition:
* The set ''X''
''i'' is called the th ''domain'' of ''R''.
Under the first definition, the relation does not uniquely determine a given sequence of domains. In the case where ''R'' is a binary relation, ''X''
1 is also called simply the
''domain'' or ''set of departure'' of ''R'', and ''X''
2 is also called the
''codomain'' or ''set of destination'' of ''R''.
* When the elements of ''X''
''i'' are relations, ''X''
''i'' is called a ''nonsimple domain'' of ''R''.
* The set of for which there exists such that is called the ''i''th ''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 th domain of definition of ''R'' is equal to ''X''
''i'', ''R'' is said to be ''total'' on ''X''
''i''. In the case where ''R'' is a binary relation, when ''R'' is total on ''X''
1, it is also said to be
''left-total'' or ''serial'', and when ''R'' is total on ''X''
2, it is also said to be
''right-total'' or ''surjective''.
* When , where , , , and is a
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of , ''R'' is said to be ''unique'' on , and is called ''a
primary key
In the relational model of databases, a primary key is a ''specific choice'' of a ''minimal'' set of attributes (Column (database), columns) that uniquely specify a tuple (Row (database), row) in a Relation (database), relation (Table (database), t ...
''
of ''R''. In the case where ''R'' is a binary relation, when ''R'' is unique on , it is also said to be
''left-unique'' or ''injective'', and when ''R'' is unique on , it is also said to be
''right-unique'' or ''functional''.
* When all ''X''
''i'' are the same set ''X'', it is simpler to refer to ''R'' as an ''n''-ary relation over ''X'', called a ''homogeneous relation''. Otherwise ''R'' is called a ''heterogeneous relation''.
* When any of ''X''
''i'' is empty, the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation . Hence it is commonly stipulated that all of the domains be nonempty.
Let a
Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...
B be a two-element set, say, , whose elements can be interpreted as logical values, typically and . The
characteristic function In mathematics, the term "characteristic function" can refer to any of several distinct concepts:
* The indicator function of a subset, that is the function
::\mathbf_A\colon X \to \,
:which for a given subset ''A'' of ''X'', has value 1 at points ...
of ''R'', denoted by χ
''R'', is the
Boolean-valued function
A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements are in ...
, defined by if and otherwise.
In applied mathematics,
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
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
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
and
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, 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
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
, there is considerable variation in terminology. Aside from the
set-theoretic
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
extension
Extension, extend or extended may refer to:
Mathematics
Logic or set theory
* Axiom of extensionality
* Extensible cardinal
* Extension (model theory)
* Extension (predicate logic), the set of tuples of values that satisfy the predicate
* E ...
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
intension
In any of several fields of study that treat the use of signs — for example, in linguistics, logic, mathematics, semantics, semiotics, and philosophy of language — an intension is any property or quality connoted by a word, phrase, or anoth ...
s 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).
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
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic phil ...
,
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
,
Richard Dedekind
Julius Wilhelm Richard Dedekind (6 October 1831 – 12 February 1916) was a German mathematician who made important contributions to number theory, abstract algebra (particularly ring theory), and
the axiomatic foundations of arithmetic. His ...
and others advanced the theory of relations. Many of their ideas, especially on relations called
orders
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
, were summarized in ''
The Principles of Mathematics
''The Principles of Mathematics'' (''PoM'') is a 1903 book by Bertrand Russell, in which the author presented his famous paradox and argued his thesis that mathematics and logic are identical.
The book presents a view of the foundations of ...
'' (1903) where
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...
made free use of these results.
In 1970,
Edgar Codd
Edgar Frank "Ted" Codd (19 August 1923 – 18 April 2003) was an English computer scientist who, while working for IBM, invented the relational model for database management, the theoretical basis for relational databases and relational databa ...
proposed a
relational model
The relational model (RM) is an approach to managing data using a Structure (mathematical logic), structure and language consistent with first-order logic, first-order predicate logic, first described in 1969 by English computer scientist Edgar F. ...
for
database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
s, thus anticipating the development of
data base management system
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases s ...
s.
See also
*
Incidence structure
In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore al ...
*
Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
*
Logic of relatives
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism".
Educated as a chemist and employed as a scientist for t ...
*
Logical matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
*
Partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
*
Predicate (mathematical logic)
In logic, a predicate is a symbol which represents a property or a relation. For instance, in the first order formula P(a), the symbol P is a predicate which applies to the individual constant a. Similarly, in the formula R(a,b), R is a predicat ...
*
Projection (set theory) In set theory, a projection is one of two closely related types of functions or operations, namely:
* A set-theoretic operation typified by the ''j''th projection map, written \mathrm_, that takes an element \vec = (x_1,\ \ldots,\ x_j,\ \ldots,\ x_ ...
*
Reflexive relation
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal to ...
*
Relation algebra
In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2''X''² of all binary relations ...
*
Relational algebra
In database theory, relational algebra is a theory that uses algebraic structures with a well-founded semantics for modeling data, and defining queries on it. The theory was introduced by Edgar F. Codd.
The main application of relational algebra ...
*
Relational model
The relational model (RM) is an approach to managing data using a Structure (mathematical logic), structure and language consistent with first-order logic, first-order predicate logic, first described in 1969 by English computer scientist Edgar F. ...
*
Relations (philosophy)
Relations are ways in which things, the relata, stand to each other. Relations are in many ways similar to Properties (philosophy), properties in that both characterize the things they apply to. Properties are sometimes treated as a special case of ...
References
Bibliography
*
*
Bourbaki, N. (1994) ''Elements of the History of Mathematics'', John Meldrum, trans. Springer-Verlag.
*
Carnap, Rudolf (1958) ''Introduction to Symbolic Logic with Applications''. Dover Publications.
*
Halmos, P.R. (1960) ''Naive Set Theory''. Princeton NJ: D. Van Nostrand Company.
*
Lawvere, F.W., and R. Rosebrugh (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
The Internet Archive is an American digital library with the stated mission of "universal access to all knowledge". It provides free public access to collections of digitized materials, including websites, software applications/games, music, ...
*
Lucas, J. R. (1999) ''Conceptual Roots of Mathematics''. Routledge.
*
Maddux, R.D. (2006) ''Relation Algebras'', vol. 150 in "Studies in Logic and the Foundations of Mathematics". Elsevier Science.
* Merrill, Dan D. (1990) ''Augustus De Morgan and the logic of relations''. Kluwer.
*
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, Bertrand (1903/1938)
The Principles of Mathematics, 2nd ed.' Cambridge Univ. Press.
*
Suppes, Patrick (1960/1972) ''Axiomatic Set Theory''. Dover Publications.
*
Tarski, A. (1956/1983) ''Logic, Semantics, Metamathematics, Papers from 1923 to 1938'', J.H. Woodger, trans. 1st edition, Oxford University Press. 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
*
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.
*
Ulam, S.M. (1990) ''Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators'' in A.R. Bednarek and Françoise Ulam, eds., University of California Press.
*
Roland Fraïssé
Roland Fraïssé (; 12 March 1920 – 30 March 2008) was a French mathematical logician.
Fraïssé received his doctoral degree from the University of Paris in 1953. In his thesis, Fraïssé used the back-and-forth method to determine whether t ...
(2000)
986
Year 986 (Roman numerals, CMLXXXVI) was a common year starting on Friday (link will display the full calendar) of the Julian calendar.
Events
By place
Byzantine Empire
* August 17 – Battle of the Gates of Trajan: Emperor Basil ...
''Theory of Relations'', North Holland
{{Authority control
Mathematical logic
Mathematical relations