Difference between revisions of "Relation theory"

MyWikiBiz, Author Your Legacy — Thursday March 28, 2024
Jump to navigationJump to search
(update)
 
(13 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
<font size="3">&#9758;</font> This page belongs to resource collections on [[Logic Live|Logic]] and [[Inquiry Live|Inquiry]].
 
<font size="3">&#9758;</font> This page belongs to resource collections on [[Logic Live|Logic]] and [[Inquiry Live|Inquiry]].
  
'''Relation theory''', or the '''theory of relations''', treats the subject matter of [[relation]]s in its combinatorial aspect, as distinguished from, though related to, its more properly logical study on one side and its more generally mathematical study on another.
+
This article treats relations from the perspective of combinatorics, in other words, as a subject matter in discrete mathematics, with special attention to finite structures and concrete set-theoretic constructions, many of which arise quite naturally in applications.  This approach to relation theory, or the theory of relations, is distinguished from, though closely related to, its study from the perspectives of abstract algebra on the one hand and formal logic on the other.
  
A '''relation''', as conceived in the combinatorial theory of relations, is a mathematical object that in general can have a very complex type, the complexity of which is best approached in several stages, as indicated next.
+
==Preliminaries==
  
In order to approach the combinatorial definition of a relation, it helps to introduce a few preliminary notions that can serve as stepping stones to the general idea.
+
Two definitions of the relation concept are common in the literature.  Although it is usually clear in context which definition is being used at a given time, it tends to become less clear as contexts collide, or as discussion moves from one context to another.
  
A relation in mathematics is defined as an object that has its existence as such within a definite context or setting.  It is literally the case that to change this setting is to change the relation that is being defined.  The particular type of context that is needed here is formalized as a collection of elements from which are chosen the elements of the relation in question.  This larger collection of ''[[elementary relation]]s'' or ''[[tuple]]s'' is constructed by means of the set-theoretic product commonly known as the ''[[cartesian product]]''.
+
The same sort of ambiguity arose in the development of the function concept and it may save some effort to follow the pattern of resolution that worked itself out there.
  
==Preliminaries==
+
When we speak of a function <math>f : X \to Y\!</math> we are thinking of a mathematical object whose articulation requires three pieces of data, specifying the set <math>X,\!</math> the set <math>Y,\!</math> and a particular subset of their cartesian product <math>{X \times Y}.\!</math>  So far so good.
  
A '''relation''' <math>L\!</math> is defined by specifying two mathematical objects as its constituent parts:
+
Let us write <math>f = (\mathrm{obj_1}f, \mathrm{obj_2}f, \mathrm{obj_{12}}f)\!</math> to express what has been said so far.
  
{| align="center" cellspacing="6" width="90%"
+
When it comes to parsing the notation <math>{}^{\backprime\backprime} f : X \to Y {}^{\prime\prime},\!</math> everyone takes the part <math>{}^{\backprime\backprime} X \to Y {}^{\prime\prime}\!</math> to specify the ''type'' of the function, that is, the pair <math>(\mathrm{obj_1}f, \mathrm{obj_2}f),\!</math> but <math>{}^{\backprime\backprime} f {}^{\prime\prime}\!</math> is used equivocally to denote both the triple and the subset <math>\mathrm{obj_{12}}f\!</math> that forms one part of it.  One way to resolve the ambiguity is to formalize a distinction between a function and its ''graph'', letting <math>\mathrm{graph}(f) := \mathrm{obj_{12}}f.\!</math>
|
 
<p>The first part is called the ''figure'' of <math>L,\!</math> notated as <math>\operatorname{figure}(L).</math></p>
 
|-
 
|
 
<p>The second part is called the ''ground'' of <math>L,\!</math> notated as <math>\operatorname{ground}(L).</math></p>
 
|}
 
  
In the special case of a ''finitary relation'', for concreteness a ''<math>k\!</math>-place relation'', the concepts of figure and ground are defined as follows:
+
Another tactic treats the whole notation <math>{}^{\backprime\backprime} f : X \to Y {}^{\prime\prime}\!</math> as sufficient denotation for the triple, letting <math>{}^{\backprime\backprime} f {}^{\prime\prime}\!</math> denote <math>\mathrm{graph}(f).\!</math>
  
{| align="center" cellspacing="6" width="90%"
+
In categorical and computational contexts, at least initially, the type is regarded as an essential attribute or an integral part of the function itself. In other contexts it may be desirable to use a more abstract concept of function, treating a function as a mathematical object that appears in connection with many different types.
|
 
<p>The ''ground'' of <math>L\!</math> is a sequence of <math>k\!</math> nonempty sets, <math>X_1, \ldots, X_k,</math> called the ''domains'' of the relation <math>L.\!</math></p>
 
|-
 
|
 
<p>The ''figure'' of <math>L\!</math> is a subset of the cartesian product taken over the domains of <math>L.\!</math></p>
 
|-
 
|
 
<p>In sum we have:  <math>\operatorname{figure}(L) ~\subseteq~ \operatorname{ground}(L) ~=~ X_1 \times \ldots, \times X_k.</math></p>
 
|}
 
  
Strictly speaking, then, the relation <math>L\!</math> is an ordered pair of mathematical objects, <math>L = (\operatorname{figure}(L), \operatorname{ground}(L)),</math> but it is customary in loose speech to use the single name <math>L\!</math> in a systematically equivocal fashion, taking it to denote either the pair <math>L = (\operatorname{figure}(L), \operatorname{ground}(L))</math> or the figure <math>\operatorname{figure}(L).</math> There is usually no confusion about this so long as the ground of the relation can be gathered from context.
+
Following the pattern of the functional case, let the notation <math>{}^{\backprime\backprime} L \subseteq X \times Y {}^{\prime\prime}\!</math> bring to mind a mathematical object that is specified by three pieces of data, the set <math>X,\!</math> the set <math>Y,\!</math> and a particular subset of their cartesian product <math>{X \times Y}.\!</math>  As before we have two choices, either let <math>L = (X, Y, \mathrm{graph}(L))\!</math> or let <math>{}^{\backprime\backprime} L {}^{\prime\prime}\!</math> denote <math>\mathrm{graph}(L)\!</math> and choose another name for the triple.
  
 
==Definition==
 
==Definition==
  
The formal definition of a '''finite arity relation''', specifically, a '''k-ary relation''' can now be stated.
+
It is convenient to begin with the definition of a ''<math>k\!</math>-place relation'', where <math>k\!</math> is a positive integer.
  
* '''Definition.'''  A '''k-ary relation''' ''L'' over the nonempty sets ''X''<sub>1</sub>,&nbsp;…,&nbsp;''X''<sub>''k''</sub> is a (1+''k'')-tuple ''L'' = (''F''(''L''),&nbsp;''X''<sub>1</sub>,&nbsp;…,&nbsp;''X''<sub>''k''</sub>) where ''F''(''L'') is a subset of the cartesian product ''X''<sub>1</sub>&nbsp;&times;&nbsp;…&nbsp;&times;&nbsp;''X''<sub>''k''</sub>. If all of the ''X''<sub>''j''</sub> for ''j''&nbsp;=&nbsp;1&nbsp;to&nbsp;''k'' are the same set ''X'', then ''L'' is more simply called a '''''k''-ary relation over ''X'''''.  The set ''F''(''L'') is called the ''figure'' of ''L'' and, provided that the sequence of sets ''X''<sub>1</sub>,&nbsp;…,&nbsp;''X''<sub>''k''</sub> is fixed throughout a given discussion or is otherwise determinate in context, one may regard the relation ''L'' as being determined by its figure ''F''(''L'').
+
'''Definition.'''  A ''<math>k\!</math>-place relation'' <math>L \subseteq X_1 \times \ldots \times X_k\!</math> over the nonempty sets <math>X_1, \ldots, X_k\!</math> is a <math>(k+1)\!</math>-tuple <math>(X_1, \ldots, X_k, L)\!</math> where <math>L\!</math> is a subset of the cartesian product <math>X_1 \times \ldots \times X_k.\!</math>
  
The formal definition simply repeats more concisely what was said above, merely unwrapping the conceptual packaging of the relation's ground to define the relation in 1&nbsp;+&nbsp;''k'' parts, as ''L'' = (''F''(''X''),&nbsp;''X''<sub>1</sub>,&nbsp;…,&nbsp;''X''<sub>''k''</sub>), rather than just the two, as ''L'' = (''F''(''L''),&nbsp;''G''(''L'')).
+
==Remarks==
  
A ''k''-ary '''predicate''' is a ''[[boolean-valued function]]'' on ''k'' variables.
+
Though usage varies as usage will, there are several bits of optional language that are frequently useful in discussing relations.  The sets <math>X_1, \ldots, X_k\!</math> are called the ''domains'' of the relation <math>L \subseteq X_1 \times \ldots \times X_k,\!</math> with <math>{X_j}\!</math> being the <math>j^\text{th}\!</math> domain.  If all of the <math>{X_j}\!</math> are the same set <math>X\!</math> then <math>L \subseteq X_1 \times \ldots \times X_k\!</math> is more simply described as a <math>k\!</math>-place relation over <math>X.\!</math>  The set <math>L\!</math> is called the ''graph'' of the relation <math>L \subseteq X_1 \times \ldots \times X_k,\!</math> on analogy with the graph of a function.  If the sequence of sets <math>X_1, \ldots, X_k\!</math> is constant throughout a given discussion or is otherwise determinate in context, then the relation <math>L \subseteq X_1 \times \ldots \times X_k\!</math> is determined by its graph <math>L,\!</math> making it acceptable to denote the relation by referring to its graph.  Other synonyms for the adjective ''<math>k\!</math>-place'' are ''<math>k\!</math>-adic'' and ''<math>k\!</math>-ary'', all of which leads to the integer <math>k\!</math> being called the ''dimension'', ''adicity'', or ''arity'' of the relation <math>L.\!</math>
  
 
==Local incidence properties==
 
==Local incidence properties==
  
A '''local incidence property''' (LIP) of a relation ''L'' is a property that depends in turn on the properties of special subsets of ''L'' that are known as its ''local flags''.  The local flags of a relation are defined in the following way:
+
A ''local incidence property'' (LIP) of a relation <math>L\!</math> is a property that depends in turn on the properties of special subsets of <math>L\!</math> that are known as its ''local flags''.  The local flags of a relation are defined in the following way:
  
Let ''L'' be a ''k''-place relation ''L'' &sube; ''X''<sub>1</sub> × … × ''X''<sub>''k''</sub>.
+
Let <math>L\!</math> be a <math>k\!</math>-place relation <math>L \subseteq X_1 \times \ldots \times X_k.\!</math>
  
Select a relational domain ''X''<sub>''j''</sub> and one of its elements ''x''.  Then ''L''<sub>''x''.''j''</sub> is a subset of ''L'' that is referred to as the ''flag'' of ''L'' with ''x'' at ''j'', or the ''x''.''j''-flag of ''L'', an object which has the following definition:
+
Select a relational domain <math>{X_j}\!</math> and one of its elements <math>x.\!</math> Then <math>L_{x \operatorname{at} j}\!</math> is a subset of <math>L\!</math> that is referred to as the ''flag'' of <math>L\!</math> with <math>x\!</math> at <math>{j},\!</math> or the ''<math>x \operatorname{at} j\!</math>-flag'' of <math>L,\!</math> an object that has the following definition:
  
:* ''L''<sub>''x''.''j''</sub> = { (''x''<sub>1</sub>, , ''x''<sub>''j''</sub>, , ''x''<sub>''k''</sub>) &isin; ''L'' : ''x''<sub>''j''</sub> = ''x'' }.
+
{| align="center" cellpadding="8" style="text-align:center"
 +
| <math>L_{x \operatorname{at} j} ~=~ \{ (x_1, \ldots, x_j, \ldots, x_k) \in L ~:~ x_j = x \}.\!</math>
 +
|}
  
Any property ''C'' of the local flag ''L''<sub>''x''.''j''</sub> &sube; ''L'' is said to be a ''local incidence property'' of ''L'' with respect to the locus ''x'' at ''j''.
+
Any property <math>C\!</math> of the local flag <math>L_{x \operatorname{at} j} \subseteq L\!</math> is said to be a ''local incidence property'' of <math>L\!</math> with respect to the ''locus'' <math>x \operatorname{at} j.\!</math>
  
A ''k''-adic relation ''L'' &sube; ''X''<sub>1</sub> &times; … &times; ''X''<sub>''k''</sub> is said to be ''C''-regular at ''j'' if and only if every flag of ''L'' with ''x'' at ''j'' has the property ''C'', where ''x'' is taken to vary over the ''theme'' of the fixed domain ''X''<sub>''j''</sub>
+
A <math>k\!</math>-adic relation <math>L \subseteq X_1 \times \ldots \times X_k\!</math> is said to be ''<math>C\!</math>-regular'' at <math>j\!</math> if and only if every flag of <math>L\!</math> with <math>x\!</math> at <math>j\!</math> has the property <math>C,\!</math> where <math>x\!</math> is taken to vary over the ''theme'' of the fixed domain <math>X_j.\!</math>
  
Expressed in symbols, ''L'' is ''C''-regular at ''j'' if and only if ''C''(''L''<sub>''x''.''j''</sub>) is true for all ''x'' in ''X''<sub>''j''</sub>.
+
Expressed in symbols, <math>L\!</math> is ''<math>C\!</math>-regular'' at <math>j\!</math> if and only if <math>C(L_{x \operatorname{at} j})\!</math> is true for all <math>x\!</math> in <math>X_j.\!</math>
  
==Numerical incidence properties==
+
==Regional incidence properties==
  
A '''numerical incidence property''' (NIP) of a relation is a local incidence property that depends on the [[cardinality|cardinalities]] of its local flags.
+
The definition of a local flag can be broadened from a point <math>x\!</math> in <math>{X_j}\!</math> to a subset <math>M\!</math> of <math>X_j,\!</math> arriving at the definition of a ''regional flag'' in the following way:
  
For example, ''L'' is said to be ''c''-regular at ''j'' if and only if the cardinality of the local flag ''L''<sub>''x''.''j''</sub> is ''c'' for all ''x'' in ''X''<sub>''j''</sub>, or, to write it in symbols, if and only if |''L''<sub>''x''.''j''</sub>| = ''c'' for all ''x'' in ''X''<sub>''j''</sub>.
+
Suppose that <math>L \subseteq X_1 \times \ldots \times X_k,\!</math> and choose a subset <math>M \subseteq X_j.\!</math>  Then <math>L_{M \operatorname{at} j}\!</math> is a subset of <math>L\!</math> that is said to be the ''flag'' of <math>L\!</math> with <math>M\!</math> at <math>{j},\!</math> or the ''<math>M \operatorname{at} j\!</math>-flag'' of <math>L,\!</math> an object which has the following definition:
  
In a similar fashion, one can define the NIPs (< ''c'')-regular at ''j'', (> ''c'')-regular at ''j'', and so on.  For ease of reference, a few of these definitions are recorded here:
+
{| align="center" cellpadding="8" style="text-align:center"
 +
| <math>L_{M \operatorname{at} j} ~=~ \{ (x_1, \ldots, x_j, \ldots, x_k) \in L ~:~ x_j \in M \}.\!</math>
 +
|}
  
{| cellpadding="4"
+
==Numerical incidence properties==
| &nbsp;
+
 
| <math>L</math>
+
A ''numerical incidence property'' (NIP) of a relation is a local incidence property that depends on the cardinalities of its local flags.
| is
 
| align="center" | ''c''-regular
 
| at ''j''
 
| if and only if
 
| <math>|L_{x.j}|</math>
 
| =
 
| ''c''
 
| for all ''x'' in ''X''<sub>j</sub>.
 
|-
 
| &nbsp;
 
| <math>L</math>
 
| is
 
| align="center" | (< ''c'')-regular
 
| at ''j''
 
| if and only if
 
| <math>|L_{x.j}|</math>
 
| <
 
| ''c''
 
| for all ''x'' in ''X''<sub>j</sub>.
 
|-
 
| &nbsp;
 
| <math>L</math>
 
| is
 
| align="center" | (> ''c'')-regular
 
| at ''j''
 
| if and only if
 
| <math>|L_{x.j}|</math>
 
| >
 
| ''c''
 
| for all ''x'' in ''X''<sub>j</sub>.
 
|}
 
  
The definition of a local flag can be broadened from a point ''x'' in ''X''<sub>''j''</sub> to a subset ''M'' of ''X''<sub>''j''</sub>, arriving at the definition of a ''regional flag'' in the following way:
+
For example, <math>L\!</math> is said to be ''<math>c\!</math>-regular at <math>j\!</math>'' if and only if the cardinality of the local flag <math>L_{x \operatorname{at} j}\!</math> is <math>c\!</math> for all <math>x\!</math> in <math>{X_j},\!</math> or, to write it in symbols, if and only if <math>|L_{x \operatorname{at} j}| = c\!</math> for all <math>{x \in X_j}.\!</math>
  
Suppose that ''L'' &sube; ''X''<sub>1</sub> &times; … &times; ''X''<sub>''k''</sub>, and choose a subset ''M'' &sube; ''X''<sub>''j''</sub>.  Then ''L''<sub>''M''.''j''</sub> is a subset of ''L'' that is said to be the ''flag'' of ''L'' with ''M'' at ''j'', or the ''M''.''j''-flag of ''L'', an object which has the following  definition:
+
In a similar fashion, one can define the NIPs, ''<math>(<\!c)\!</math>-regular at <math>{j},\!</math>'' ''<math>(>\!c)\!</math>-regular at <math>{j},\!</math>'' and so on.  For ease of reference, a few of these definitions are recorded here:
  
{| cellpadding="4"
+
{| align="center" cellpadding="8" style="text-align:center"
| &nbsp;
+
|
| ''L''<sub>''M''.''j''</sub>
+
<math>\begin{matrix}
| =
+
L & \text{is} & c\textit{-regular} & \text{at}\ j
| { (''x''<sub>1</sub>, …, ''x''<sub>''j''</sub>, …, ''x''<sub>''k''</sub>) &isin; ''L'' : ''x''<sub>''j''</sub> &isin; ''M'' }.
+
& \text{if and only if} &
 +
|L_{x \operatorname{at} j}| & = & c & \text{for all}\ x \in X_j.
 +
\\[4pt]
 +
L & \text{is} & (<\!c)\textit{-regular} & \text{at}\ j
 +
& \text{if and only if} &
 +
|L_{x \operatorname{at} j}| & < & c & \text{for all}\ x \in X_j.
 +
\\[4pt]
 +
L & \text{is} & (>\!c)\textit{-regular} & \text{at}\ j
 +
& \text{if and only if} &
 +
|L_{x \operatorname{at} j}| & > & c & \text{for all}\ x \in X_j.
 +
\end{matrix}</math>
 
|}
 
|}
  
Returning to 2-adic relations, it is useful to describe some familiar classes of objects in terms of their local and their numerical incidence properties.  Let ''L'' &sube; ''S'' &times; ''T'' be an arbitrary 2-adic relation.  The following properties of ''L'' can be defined:
+
==Species of 2-adic relations==
 +
 
 +
Returning to 2-adic relations, it is useful to describe some familiar classes of objects in terms of their local and numerical incidence properties.  Let <math>L \subseteq S \times T\!</math> be an arbitrary 2-adic relation.  The following properties of <math>L\!</math> can be defined:
  
{| cellpadding="4"
+
{| align="center" cellpadding="8" style="text-align:center"
| &nbsp;
+
|
| <math>L</math>
+
<math>\begin{matrix}
| is
+
L & \text{is} & \textit{total} & \text{at}~ S
| align="center" | ''total''
+
& \text{if and only if} &
| at ''S''
+
L & \text{is} & (\ge 1)\text{-regular} & \text{at}~ S.
| if and only if
+
\\[4pt]
| <math>L</math>
+
L & \text{is} & \textit{total} & \text{at}~ T
| is
+
& \text{if and only if} &
| (&#8805;1)-regular
+
L & \text{is} & (\ge 1)\text{-regular} & \text{at}~ T.
| at ''S''.
+
\\[4pt]
|-
+
L & \text{is} & \textit{tubular} & \text{at}~ S
| &nbsp;
+
& \text{if and only if} &
| <math>L</math>
+
L & \text{is} & (\le 1)\text{-regular} & \text{at}\ S.
| is
+
\\[4pt]
| align="center" | ''total''
+
L & \text{is} & \textit{tubular} & \text{at}~ T
| at ''T''
+
& \text{if and only if} &
| if and only if
+
L & \text{is} & (\le 1)\text{-regular} & \text{at}~ T.
| <math>L</math>
+
\end{matrix}</math>
| is
 
| (&#8805;1)-regular
 
| at ''T''.
 
|-
 
| &nbsp;
 
| <math>L</math>
 
| is
 
| align="center" | ''tubular''
 
| at ''S''
 
| if and only if
 
| <math>L</math>
 
| is
 
| (&#8804;1)-regular
 
| at ''S''.
 
|-
 
| &nbsp;
 
| <math>L</math>
 
| is
 
| align="center" | ''tubular''
 
| at ''T''
 
| if and only if
 
| <math>L</math>
 
| is
 
| (&#8804;1)-regular
 
| at ''T''.
 
 
|}
 
|}
  
If ''L'' &sube; ''S'' × ''T'' is tubular at ''S'', then ''L'' is called a ''partial function'' or a ''prefunction'' from ''S'' to ''T'', sometimes indicated by giving ''L'' an alternate name, say, "''p''", and writing ''L'' = ''p'' : ''S'' <math>\rightharpoonup</math> ''T''.
+
If <math>L \subseteq S \times T\!</math> is tubular at <math>S\!</math> then <math>L\!</math> is called a ''partial function'' or a ''prefunction'' from <math>S\!</math> to <math>T.\!</math>  This is sometimes indicated by giving <math>L\!</math> an alternate name, say, <math>{}^{\backprime\backprime} p {}^{\prime\prime},~\!</math> and writing <math>L = p : S \rightharpoonup T.\!</math>
  
 
Just by way of formalizing the definition:
 
Just by way of formalizing the definition:
  
{| cellpadding="4"
+
{| align="center" cellpadding="8" style="text-align:center"
| &nbsp;
+
|
| ''L''
+
<math>\begin{matrix}
| =
+
L & = & p : S \rightharpoonup T
| ''p'' : ''S'' <math>\rightharpoonup</math> ''T''
+
& \text{if and only if} &
| if and only if
+
L & \text{is} & \text{tubular} & \text{at}~ S.
| ''L''
+
\end{matrix}</math>
| is
 
| tubular
 
| at ''S''.
 
 
|}
 
|}
  
If ''L'' is a prefunction ''p'' : ''S'' <math>\rightharpoonup</math> ''T'' that happens to be total at ''S'', then ''L'' is called a ''function'' from ''S'' to ''T'', indicated by writing ''L'' = ''f'' : ''S'' &rarr; ''T''.  To say that a relation ''L'' &sube; ''S'' &times; ''T'' is ''totally tubular'' at ''S'' is to say that it is 1-regular at ''S''.  Thus, we may formalize the following definition:
+
If <math>L\!</math> is a prefunction <math>p : S \rightharpoonup T\!</math> that happens to be total at <math>S,\!</math> then <math>L\!</math> is called a ''function'' from <math>S\!</math> to <math>T,\!</math> indicated by writing <math>L = f : S \to T.\!</math> To say that a relation <math>L \subseteq S \times T\!</math> is ''totally tubular'' at <math>S\!</math> is to say that it is <math>1\!</math>-regular at <math>S.\!</math> Thus, we may formalize the following definition:
  
{| cellpadding="4"
+
{| align="center" cellpadding="8" style="text-align:center"
| &nbsp;
+
|
| ''L''
+
<math>\begin{matrix}
| =
+
L & = & f : S \to T
| ''f'' : ''S'' &rarr; ''T''
+
& \text{if and only if} &
| if and only if
+
L & \text{is} & 1\text{-regular} & \text{at}~ S.
| ''L''
+
\end{matrix}</math>
| is
 
| 1-regular
 
| at ''S''.
 
 
|}
 
|}
  
In the case of a function ''f'' : ''S'' &rarr; ''T'', one has the following additional definitions:
+
In the case of a function <math>f : S \to T,\!</math> one has the following additional definitions:
  
{| cellpadding="4"
+
{| align="center" cellpadding="8" style="text-align:center"
| &nbsp;
+
|
| ''f''
+
<math>\begin{matrix}
| is
+
f & \text{is} & \textit{surjective}
| align="center" | ''surjective''
+
& \text{if and only if} &
| if and only if
+
f & \text{is} & \text{total} & \text{at}~ T.
| ''f''
+
\\[4pt]
| is
+
f & \text{is} & \textit{injective}
| align="center" | total
+
& \text{if and only if} &
| at ''T''.
+
f & \text{is} & \text{tubular} & \text{at}~ T.
|-
+
\\[4pt]
| &nbsp;
+
f & \text{is} & \textit{bijective}
| ''f''
+
& \text{if and only if} &
| is
+
f & \text{is} & 1\text{-regular} & \text{at}~ T.
| align="center" | ''injective''
+
\end{matrix}</math>
| if and only if
 
| ''f''
 
| is
 
| align="center" | tubular
 
| at ''T''.
 
|-
 
| &nbsp;
 
| ''f''
 
| is
 
| align="center" | ''bijective''
 
| if and only if
 
| ''f''
 
| is
 
| align="center" | 1-regular
 
| at ''T''.
 
 
|}
 
|}
  
 
==Variations==
 
==Variations==
  
Because the concept of a relation has been developed quite literally from the beginnings of logic and mathematics, and because it has incorporated contributions from a diversity of thinkers from many different times and intellectual climates, there is a wide variety of terminology that the reader may run across in connection with the subject.
+
Because the concept of a relation has been developed quite literally from the beginnings of logic and mathematics, and because it has incorporated contributions from a diversity of thinkers from many different times and intellectual climes, there is a wide variety of terminology that the reader may run across in connection with the subject.
  
One dimension of variation is reflected in the names that are given to k-place relations, with some writers using ''medadic'', ''monadic'', ''dyadic'', ''triadic'', ''k-adic'' where other writers use ''nullary'', ''unary'', ''binary'', ''ternary'', ''k-ary''.
+
One dimension of variation is reflected in the names that are given to <math>k\!</math>-place relations, for <math>k = 0, 1, 2, 3, \ldots,\!</math> with some writers using the Greek forms, ''medadic'', ''monadic'', ''dyadic'', ''triadic'', ''<math>k\!</math>-adic'', and other writers using the Latin forms, ''nullary'', ''unary'', ''binary'', ''ternary'', ''<math>k\!</math>-ary''.
  
One finds a relation on a finite number of domains described as either a ''finitary'' relation or a ''polyadic'' relation.  If the number of domains is finite, say equal to ''k'', then the [[parameter]] ''k'' may be referred to as the ''[[arity]]'', the ''[[adicity]]'', or the ''[[dimension]]'' of the relation.  In these cases, the relation may be described as a ''k-ary'' relation, a ''k-adic'' relation, or a ''k-dimensional'' relation, respectively.
+
The number of relational domains may be referred to as the ''adicity'', ''arity'', or ''dimension'' of the relation.  Accordingly, one finds a relation on a finite number of domains described as a ''polyadic'' relation or a ''finitary'' relation, but others count infinitary relations among the polyadic.  If the number of domains is finite, say equal to <math>k,\!</math> then the relation may be described as a ''<math>k\!</math>-adic'' relation, a ''<math>k\!</math>-ary'' relation, or a ''<math>k\!</math>-dimensional'' relation, respectively.
  
A more conceptual than nominal variation depends on whether one uses terms like 'predicate', 'relation', and even 'term' to refer to the formal object proper or else to the allied [[syntax|syntactic]] items that are used to denote them.  Compounded with this variation is still another, frequently associated with philosophical differences over the status in reality accorded formal objects.  Among those who speak of numbers, functions, properties, relations, and sets as being real, that is to say, as having objective properties, there are divergences as to whether some things are more real than others, especially whether particulars or properties are equally real or else one derivative of the other.  Historically speaking, just about every combination of modalities has been used by one school of thought or another, but it suffices here merely to indicate how the options are generated.
+
A more conceptual than nominal variation depends on whether one uses terms like ''predicate'', ''relation'', and even ''term'' to refer to the formal object proper or else to the allied syntactic items that are used to denote them.  Compounded with this variation is still another, frequently associated with philosophical differences over the status in reality accorded formal objects.  Among those who speak of numbers, functions, properties, relations, and sets as being real, that is to say, as having objective properties, there are divergences as to whether some things are more real than others, especially whether particulars or properties are equally real or else one is derivative in relationship to the other.  Historically speaking, just about every combination of modalities has been used by one school of thought or another, but it suffices here merely to indicate how the options are generated.
  
 
==Examples==
 
==Examples==
Line 242: Line 166:
 
: ''See the articles on [[relation (mathematics)|relations]], [[relation composition]], [[relation reduction]], [[sign relation]]s, and [[triadic relation]]s for concrete examples of relations.''
 
: ''See the articles on [[relation (mathematics)|relations]], [[relation composition]], [[relation reduction]], [[sign relation]]s, and [[triadic relation]]s for concrete examples of relations.''
  
Many relations of the greatest interest in mathematics are triadic relations, but this fact is somewhat disguised by the circumstance that many of them are referred to as ''[[binary operation]]s'', and because the most familiar of these have very specific properties that are dictated by their axioms.  This makes it practical to study these operations for quite some time by focusing on their dyadic aspects before being forced to consider their proper characters as triadic relations.
+
Many relations of the greatest interest in mathematics are triadic relations, but this fact is somewhat disguised by the circumstance that many of them are referred to as ''binary operations'', and because the most familiar of these have very specific properties that are dictated by their axioms.  This makes it practical to study these operations for quite some time by focusing on their dyadic aspects before being forced to consider their proper characters as triadic relations.
  
 
==References==
 
==References==
  
* [[Charles Sanders 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.
+
* Peirce, C.S., &ldquo;Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic&rdquo;, ''Memoirs of the American Academy of Arts and Sciences'', 9, 317&ndash;378, 1870.  Reprinted, ''Collected Papers'' CP 3.45&ndash;149, ''Chronological Edition'' CE 2, 359&ndash;429.
  
* [[Stanis&#322;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.
+
* Ulam, S.M. and Bednarek, A.R., &ldquo;On the Theory of Relational Structures and Schemata for Parallel Computation&rdquo;, pp. 477&ndash;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==
  
* [[Michael Barr|Barr, M.]] and [[Charles Wells|Wells, C.]], ''Category Theory for Computing Science'', [[Hemel Hempstead]], UK, 1990.
+
* Barr, Michael, and Wells, Charles (1990), ''Category Theory for Computing Science'', Prentice Hall, Hemel Hempstead, UK.
 
+
* Bourbaki, Nicolas (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.
+
* Carnap, Rudolf (1958), ''Introduction to Symbolic Logic with Applications'', Dover Publications, New York, NY.
 
+
* Chang, C.C., and Keisler, H.J. (1973), ''Model Theory'', North-Holland, Amsterdam, Netherlands.
* [[Rudolf Carnap|Carnap, Rudolf]], ''Introduction to Symbolic Logic with Applications'', Dover Publications, New York, NY, 1958.  
+
* van Dalen, Dirk (1980), ''Logic and Structure'', 2nd edition, Springer-Verlag, Berlin, Germany.
 
+
* Devlin, Keith J. (1993), ''The Joy of Sets : Fundamentals of Contemporary Set Theory'', 2nd edition, Springer-Verlag, New York, NY.
* Chang, C.C., and Keisler, H.J., ''Model Theory'', North-Holland, Amsterdam, Netherlands, 1973.
+
* Halmos, Paul Richard (1960), ''Naive Set Theory'', D. Van Nostrand Company, Princeton, NJ.
 
+
* van Heijenoort, Jean (1967/1977), ''From Frege to Gödel : A Source Book in Mathematical Logic, 1879&ndash;1931'', Harvard University Press, Cambridge, MA, 1967.  Reprinted with corrections, 1977.
* [[Dirk van Dalen|van Dalen, D.]], ''Logic and Structure'', 2nd edition, Springer-Verlag, Berlin, Germany, 1980.
+
* Kelley, John L. (1955), ''General Topology'', Van Nostrand Reinhold, New York, NY.
 
+
* Kneale, William; and Kneale, Martha (1962/1975), ''The Development of Logic'', Oxford University Press, Oxford, UK, 1962.  Reprinted with corrections, 1975.
* [[Keith J. Devlin|Devlin, K.J.]], ''The Joy of Sets: Fundamentals of Contemporary Set Theory'', 2nd edition, Springer-Verlag, New York, NY, 1993.
+
* Lawvere, Francis William; and Rosebrugh, Robert (2003), ''Sets for Mathematics'', Cambridge University Press, Cambridge, UK.
 
+
* Lawvere, Francis William; and Schanuel, Stephen H. (1997/2000), ''Conceptual Mathematics : A First Introduction to Categories'', Cambridge University Press, Cambridge, UK, 1997.  Reprinted with corrections, 2000.
* [[Paul Richard Halmos|Halmos, P.R.]], ''Naive Set Theory'', D. Van Nostrand Company, Princeton, NJ, 1960.
+
* Manin, Yu. I. (1977), ''A Course in Mathematical Logic'', Neal Koblitz (trans.), Springer-Verlag, New York, NY.
 
+
* Mathematical Society of Japan (1993), ''Encyclopedic Dictionary of Mathematics'', 2nd edition, 2 vols., Kiyosi Itô (ed.), MIT Press, Cambridge, MA.
* [[Jean van Heijenoort|van Heijenoort, J.]], ''From Frege to Gödel, A Source Book in Mathematical Logic, 1879?1931'', Harvard University Press, Cambridge, MA, 1967.  Reprinted with corrections, 1977.
+
* Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994), ''Computer Program Construction'', Oxford University Press, New York, NY. (Introduction to Tarskian relation theory and relational programming.)
 
+
* Mitchell, John C. (1996), ''Foundations for Programming Languages'', MIT Press, Cambridge, MA.
* [[John L. Kelley|Kelley, J.L.]], ''General Topology'', Van Nostrand Reinhold, New York, NY, 1955.
+
* Peirce, Charles Sanders (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 (1870), 317&ndash;378.  Reprinted (CP 3.45&ndash;149), (CE 2, 359&ndash;429).
 
+
* Peirce, Charles Sanders (1931&ndash;1935, 1958), ''Collected Papers of Charles Sanders Peirce'', vols. 1&ndash;6, Charles Hartshorne and Paul Weiss (eds.), vols. 7&ndash;8, Arthur W. Burks (ed.), Harvard University Press, Cambridge, MA.  Cited as (CP volume.paragraph).
* [[William Kneale|Kneale, W.]] and [[Martha Kneale|Kneale, M.]], ''The Development of Logic'', Oxford University Press, Oxford, UK, 1962.  Reprinted with corrections, 1975.
+
* Peirce, Charles Sanders (1981&ndash;), ''Writings of Charles S. Peirce : A Chronological Edition'', Peirce Edition Project (eds.), Indiana University Press, Bloomington and Indianapolis, IN.  Cited as (CE volume, page).
 
+
* Poizat, Bruno (2000), ''A Course in Model Theory : An Introduction to Contemporary Mathematical Logic'', Moses Klein (trans.), Springer-Verlag, New York, NY.
* [[Francis William Lawvere|Lawvere, F.W.]], and [[Robert Rosebrugh|Rosebrugh, R.]], ''Sets for Mathematics'', Cambridge University Press, Cambridge, UK, 2003.
+
* Quine, Willard Van Orman (1940/1981), ''Mathematical Logic'', 1940.  Revised edition, Harvard University Press, Cambridge, MA, 1951.  New preface, 1981.
 
+
* Royce, Josiah (1961), ''The Principles of Logic'', Philosophical Library, New York, NY.
* [[Francis William Lawvere|Lawvere, F.W.]], and [[Stephen H. Schanuel|Schanuel, S.H.]], ''Conceptual Mathematics, A First Introduction to Categories'', Cambridge University Press, Cambridge, UK, 1997.  Reprinted with corrections, 2000.
+
* Runes, Dagobert D. (ed., 1962), ''Dictionary of Philosophy'', Littlefield, Adams, and Company, Totowa, NJ.
 
+
* Shoenfield, Joseph R. (1967), ''Mathematical Logic'', Addison-Wesley, Reading, MA.
* Maddux, R.D., ''Relation Algebras'', Volume 150, 'Studies in Logic and the Foundations of Mathematics', Elsevier Science, 2006.
+
* Styazhkin, N.I. (1969), ''History of Mathematical Logic from Leibniz to Peano'', MIT Press, Cambridge, MA.
 
+
* Suppes, Patrick (1957/1999), ''Introduction to Logic'', 1st published 1957.  Reprinted, Dover Publications, New York, NY, 1999.
* [[Yu. I. Manin|Manin, Yu. I.]], ''A Course in Mathematical Logic'', Neal Koblitz (trans.), Springer-Verlag, New York, NY, 1977.
+
* Suppes, Patrick (1960/1972), ''Axiomatic Set Theory'', 1st published 1960.  Reprinted, Dover Publications, New York, NY, 1972.
 
+
* Tarski, Alfred (1956/1983), ''Logic, Semantics, Metamathematics : Papers from 1923 to 1938'', J.H. Woodger (trans.), Oxford University Press, 1956.  2nd edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.
* [[Mathematical Society of Japan]], ''Encyclopedic Dictionary of Mathematics'', 2nd edition, 2 vols., Kiyosi Itô (ed.), MIT Press, Cambridge, MA, 1993.
+
* Ulam, Stanislaw Marcin; and Bednarek, A.R. (1977), &ldquo;On the Theory of Relational Structures and Schemata for Parallel Computation&rdquo;, pp. 477&ndash;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.
 
+
* Ulam, Stanislaw Marcin (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.
* Mili, A., Desharnais, J., Mili, F., with Frappier, M., ''Computer Program Construction'', Oxford University Press, New York, NY, 1994. (Introduction to Tarskian relation theory and its applications within the relational programming paradigm.)
+
* Ullman, Jeffrey D. (1980), ''Principles of Database Systems'', Computer Science Press, Rockville, MD.
 
+
* Venetus, Paulus (1472/1984), ''Logica Parva : Translation of the 1472 Edition with Introduction and Notes'', Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.
* [[John C. Mitchell|Mitchell, J.C.]], ''Foundations for Programming Languages'', MIT Press, Cambridge, MA, 1996.
 
 
 
* Peirce, C.S., ''Collected Papers of Charles Sanders Peirce'', vols. 1&ndash;6, [[Charles Hartshorne]] and [[Paul Weiss]] (eds.), vols. 7&ndash;8, [[Arthur W. Burks]] (ed.), Harvard University Press, Cambridge, MA, 1931&ndash;1935, 1958.  Cited as CP volume.paragraph.
 
 
 
* Peirce, C.S., ''Writings of Charles S. Peirce : A Chronological Edition, Volume 2, 1867&ndash;1871'', Peirce Edition Project (eds.), Indiana University Press, Bloomington, IN, 1984.  Cited as CE 2.
 
 
 
* [[Bruno Poizat|Poizat, B.]], ''A Course in Model Theory: An Introduction to Contemporary Mathematical Logic'', Moses Klein (trans.), Springer-Verlag, New York, NY, 2000.
 
 
 
* [[Willard Van Orman Quine|Quine, W.V.]], ''Mathematical Logic'', 1940.  Revised edition, Harvard University Press, Cambridge, MA, 1951.  New preface, 1981.
 
 
 
* [[Josiah Royce|Royce, J.]], ''The Principles of Logic'', Philosophical Library, New York, NY, 1961.
 
 
 
* [[Dagobert D. Runes|Runes, D.D.]] (ed.), ''Dictionary of Philosophy'', Littlefield, Adams, and Company, Totowa, NJ, 1962.
 
 
 
* [[Joseph R. Shoenfield|Shoenfield, J.R.]], ''Mathematical Logic'', Addison-Wesley, Reading, MA, 1967.
 
 
 
* Styazhkin, N.I., ''History of Mathematical Logic from Leibniz to Peano'', MIT Press, Cambridge, MA, 1969.
 
 
 
* [[Patrick Suppes|Suppes, Patrick]], ''Introduction to Logic'', 1st published 1957.  Reprinted, Dover Publications, New York, NY, 1999.
 
 
 
* Suppes, Patrick, ''Axiomatic Set Theory'', 1st published 1960.  Reprinted, Dover Publications, New York, NY, 1972.
 
 
 
* [[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&#322;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.
 
 
 
* [[Jeffrey D. Ullman|Ullman, J.D.]], ''Principles of Database Systems'', Computer Science Press, Rockville, MD, 1980.
 
 
 
* [[Paulus Venetus|Venetus, P.]], ''Logica Parva, Translation of the 1472 Edition with Introduction and Notes'', Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany, 1984.
 
  
 
==Syllabus==
 
==Syllabus==
Line 318: Line 213:
 
===Focal nodes===
 
===Focal nodes===
  
{{col-begin}}
 
{{col-break}}
 
 
* [[Inquiry Live]]
 
* [[Inquiry Live]]
{{col-break}}
 
 
* [[Logic Live]]
 
* [[Logic Live]]
{{col-end}}
 
  
 
===Peer nodes===
 
===Peer nodes===
  
{{col-begin}}
+
* [http://intersci.ss.uci.edu/wiki/index.php/Relation_theory Relation Theory @ InterSciWiki]
{{col-break}}
 
 
* [http://mywikibiz.com/Relation_theory Relation Theory @ MyWikiBiz]
 
* [http://mywikibiz.com/Relation_theory Relation Theory @ MyWikiBiz]
* [http://mathweb.org/wiki/Relation_theory Relation Theory @ MathWeb Wiki]
+
* [http://ref.subwiki.org/wiki/Relation_theory Relation Theory @ Subject Wikis]
* [http://netknowledge.org/wiki/Relation_theory Relation Theory @ NetKnowledge]
+
* [http://en.wikiversity.org/wiki/Relation_theory Relation Theory @ Wikiversity]
{{col-break}}
+
* [http://beta.wikiversity.org/wiki/Relation_theory Relation Theory @ Wikiversity Beta]
* [http://wiki.oercommons.org/mediawiki/index.php/Relation_theory Relation Theory @ OER Commons]
 
* [http://p2pfoundation.net/Relation_Theory Relation Theory @ P2P Foundation]
 
* [http://semanticweb.org/wiki/Relation_theory Relation Theory @ SemanticWeb]
 
{{col-end}}
 
  
 
===Logical operators===
 
===Logical operators===
Line 401: Line 287:
 
{{col-break}}
 
{{col-break}}
 
* [[Inquiry]]
 
* [[Inquiry]]
 +
* [[Dynamics of inquiry]]
 +
{{col-break}}
 +
* [[Semeiotic]]
 
* [[Logic of information]]
 
* [[Logic of information]]
 
{{col-break}}
 
{{col-break}}
Line 407: Line 296:
 
{{col-break}}
 
{{col-break}}
 
* [[Pragmatic maxim]]
 
* [[Pragmatic maxim]]
* [[Pragmatic theory of truth]]
+
* [[Truth theory]]
{{col-break}}
 
* [[Semeiotic]]
 
* [[Semiotic information]]
 
 
{{col-end}}
 
{{col-end}}
  
 
===Related articles===
 
===Related articles===
  
* [http://mywikibiz.com/Directory:Jon_Awbrey/Papers/Introduction_to_Inquiry_Driven_Systems Jon Awbrey, &ldquo;Introduction To Inquiry Driven Systems&rdquo;]
+
{{col-begin}}
 
+
{{col-break}}
* [http://mywikibiz.com/Directory:Jon_Awbrey/Essays/Prospects_For_Inquiry_Driven_Systems Jon Awbrey, &ldquo;Prospects For Inquiry Driven Systems&rdquo;]
+
* [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/Papers/Inquiry_Driven_Systems Jon Awbrey, &ldquo;Inquiry Driven Systems : Inquiry Into Inquiry&rdquo;]
+
* [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/Propositional_Equation_Reasoning_Systems Jon Awbrey, &ldquo;Propositional Equation Reasoning Systems&rdquo;]
+
* [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/Differential_Logic_:_Introduction Jon Awbrey, &ldquo;Differential Logic : Introduction&rdquo;]
+
* [http://intersci.ss.uci.edu/wiki/index.php/Differential_Logic_and_Dynamic_Systems_2.0 Differential Logic and Dynamic Systems]
 
+
{{col-break}}
* [http://planetmath.org/encyclopedia/DifferentialPropositionalCalculus.html Jon Awbrey, &ldquo;Differential Propositional Calculus&rdquo;]
+
* [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://mywikibiz.com/Directory:Jon_Awbrey/Papers/Differential_Logic_and_Dynamic_Systems_2.0 Jon Awbrey, &ldquo;Differential Logic and Dynamic Systems&rdquo;]
+
* [http://intersci.ss.uci.edu/wiki/index.php/Inquiry_Driven_Systems Inquiry Driven Systems : Inquiry Into Inquiry]
 +
{{col-end}}
  
 
==Document history==
 
==Document history==
Line 433: Line 320:
 
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.
  
{{col-begin}}
+
* [http://intersci.ss.uci.edu/wiki/index.php/Relation_theory Relation Theory], [http://intersci.ss.uci.edu/ InterSciWiki]
{{col-break}}
 
 
 
 
* [http://mywikibiz.com/Relation_theory Relation Theory], [http://mywikibiz.com/ MyWikiBiz]
 
* [http://mywikibiz.com/Relation_theory Relation Theory], [http://mywikibiz.com/ MyWikiBiz]
 
+
* [http://planetmath.org/RelationTheory Relation Theory], [http://planetmath.org/ PlanetMath]
* [http://mathweb.org/wiki/Relation_theory Relation Theory], [http://mathweb.org/wiki/ MathWeb Wiki]
 
 
 
* [http://netknowledge.org/wiki/Relation_theory Relation Theory], [http://netknowledge.org/ NetKnowledge]
 
 
 
* [http://wiki.oercommons.org/mediawiki/index.php/Relation_theory Relation Theory], [http://wiki.oercommons.org/ OER Commons]
 
 
 
{{col-break}}
 
 
 
* [http://p2pfoundation.net/Relation_Theory Relation Theory], [http://p2pfoundation.net/ P2P Foundation]
 
 
 
 
* [http://semanticweb.org/wiki/Relation_theory Relation Theory], [http://semanticweb.org/ Semantic Web]
 
* [http://semanticweb.org/wiki/Relation_theory Relation Theory], [http://semanticweb.org/ Semantic Web]
 
+
* [http://wikinfo.org/w/index.php/Relation_theory Relation Theory], [http://wikinfo.org/w/ Wikinfo]
* [http://planetmath.org/encyclopedia/RelationTheory.html Relation Theory], [http://planetmath.org/ PlanetMath]
+
* [http://en.wikiversity.org/wiki/Relation_theory Relation Theory], [http://en.wikiversity.org/ Wikiversity]
 
+
* [http://beta.wikiversity.org/wiki/Relation_theory Relation Theory], [http://beta.wikiversity.org/ Wikiversity Beta]
* [http://planetphysics.org/encyclopedia/RelationTheory.html Relation Theory], [http://planetphysics.org/ PlanetPhysics]
 
 
 
{{col-break}}
 
 
 
* [http://getwiki.net/-Theory_of_Relations Relation Theory], [http://getwiki.net/ GetWiki]
 
 
 
* [http://wikinfo.org/index.php/Theory_of_relations Relation Theory], [http://wikinfo.org/ Wikinfo]
 
 
 
* [http://textop.org/wiki/index.php?title=Theory_of_relations Relation Theory], [http://textop.org/wiki/ Textop Wiki]
 
 
 
 
* [http://en.wikipedia.org/w/index.php?title=Theory_of_relations&oldid=45042729 Relation Theory], [http://en.wikipedia.org/ Wikipedia]
 
* [http://en.wikipedia.org/w/index.php?title=Theory_of_relations&oldid=45042729 Relation Theory], [http://en.wikipedia.org/ Wikipedia]
  
{{col-end}}
+
[[Category:Charles Sanders Peirce]]
 
 
<br><sharethis />
 
 
 
[[Category:Inquiry]]
 
[[Category:Open Educational Resource]]
 
[[Category:Peer Educational Resource]]
 
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]
 
[[Category:Computer Science]]
 
[[Category:Computer Science]]
Line 476: Line 335:
 
[[Category:Discrete Mathematics]]
 
[[Category:Discrete Mathematics]]
 
[[Category:Formal Sciences]]
 
[[Category:Formal Sciences]]
 +
[[Category:Inquiry]]
 
[[Category:Logic]]
 
[[Category:Logic]]
 
[[Category:Mathematics]]
 
[[Category:Mathematics]]
 
[[Category:Relation Theory]]
 
[[Category:Relation Theory]]
 +
[[Category:Set Theory]]

Latest revision as of 21:04, 16 November 2015

This page belongs to resource collections on Logic and Inquiry.

This article treats relations from the perspective of combinatorics, in other words, as a subject matter in discrete mathematics, with special attention to finite structures and concrete set-theoretic constructions, many of which arise quite naturally in applications. This approach to relation theory, or the theory of relations, is distinguished from, though closely related to, its study from the perspectives of abstract algebra on the one hand and formal logic on the other.

Preliminaries

Two definitions of the relation concept are common in the literature. Although it is usually clear in context which definition is being used at a given time, it tends to become less clear as contexts collide, or as discussion moves from one context to another.

The same sort of ambiguity arose in the development of the function concept and it may save some effort to follow the pattern of resolution that worked itself out there.

When we speak of a function \(f : X \to Y\!\) we are thinking of a mathematical object whose articulation requires three pieces of data, specifying the set \(X,\!\) the set \(Y,\!\) and a particular subset of their cartesian product \({X \times Y}.\!\) So far so good.

Let us write \(f = (\mathrm{obj_1}f, \mathrm{obj_2}f, \mathrm{obj_{12}}f)\!\) to express what has been said so far.

When it comes to parsing the notation \({}^{\backprime\backprime} f : X \to Y {}^{\prime\prime},\!\) everyone takes the part \({}^{\backprime\backprime} X \to Y {}^{\prime\prime}\!\) to specify the type of the function, that is, the pair \((\mathrm{obj_1}f, \mathrm{obj_2}f),\!\) but \({}^{\backprime\backprime} f {}^{\prime\prime}\!\) is used equivocally to denote both the triple and the subset \(\mathrm{obj_{12}}f\!\) that forms one part of it. One way to resolve the ambiguity is to formalize a distinction between a function and its graph, letting \(\mathrm{graph}(f) := \mathrm{obj_{12}}f.\!\)

Another tactic treats the whole notation \({}^{\backprime\backprime} f : X \to Y {}^{\prime\prime}\!\) as sufficient denotation for the triple, letting \({}^{\backprime\backprime} f {}^{\prime\prime}\!\) denote \(\mathrm{graph}(f).\!\)

In categorical and computational contexts, at least initially, the type is regarded as an essential attribute or an integral part of the function itself. In other contexts it may be desirable to use a more abstract concept of function, treating a function as a mathematical object that appears in connection with many different types.

Following the pattern of the functional case, let the notation \({}^{\backprime\backprime} L \subseteq X \times Y {}^{\prime\prime}\!\) bring to mind a mathematical object that is specified by three pieces of data, the set \(X,\!\) the set \(Y,\!\) and a particular subset of their cartesian product \({X \times Y}.\!\) As before we have two choices, either let \(L = (X, Y, \mathrm{graph}(L))\!\) or let \({}^{\backprime\backprime} L {}^{\prime\prime}\!\) denote \(\mathrm{graph}(L)\!\) and choose another name for the triple.

Definition

It is convenient to begin with the definition of a \(k\!\)-place relation, where \(k\!\) is a positive integer.

Definition. A \(k\!\)-place relation \(L \subseteq X_1 \times \ldots \times X_k\!\) over the nonempty sets \(X_1, \ldots, X_k\!\) is a \((k+1)\!\)-tuple \((X_1, \ldots, X_k, L)\!\) where \(L\!\) is a subset of the cartesian product \(X_1 \times \ldots \times X_k.\!\)

Remarks

Though usage varies as usage will, there are several bits of optional language that are frequently useful in discussing relations. The sets \(X_1, \ldots, X_k\!\) are called the domains of the relation \(L \subseteq X_1 \times \ldots \times X_k,\!\) with \({X_j}\!\) being the \(j^\text{th}\!\) domain. If all of the \({X_j}\!\) are the same set \(X\!\) then \(L \subseteq X_1 \times \ldots \times X_k\!\) is more simply described as a \(k\!\)-place relation over \(X.\!\) The set \(L\!\) is called the graph of the relation \(L \subseteq X_1 \times \ldots \times X_k,\!\) on analogy with the graph of a function. If the sequence of sets \(X_1, \ldots, X_k\!\) is constant throughout a given discussion or is otherwise determinate in context, then the relation \(L \subseteq X_1 \times \ldots \times X_k\!\) is determined by its graph \(L,\!\) making it acceptable to denote the relation by referring to its graph. Other synonyms for the adjective \(k\!\)-place are \(k\!\)-adic and \(k\!\)-ary, all of which leads to the integer \(k\!\) being called the dimension, adicity, or arity of the relation \(L.\!\)

Local incidence properties

A local incidence property (LIP) of a relation \(L\!\) is a property that depends in turn on the properties of special subsets of \(L\!\) that are known as its local flags. The local flags of a relation are defined in the following way:

Let \(L\!\) be a \(k\!\)-place relation \(L \subseteq X_1 \times \ldots \times X_k.\!\)

Select a relational domain \({X_j}\!\) and one of its elements \(x.\!\) Then \(L_{x \operatorname{at} j}\!\) is a subset of \(L\!\) that is referred to as the flag of \(L\!\) with \(x\!\) at \({j},\!\) or the \(x \operatorname{at} j\!\)-flag of \(L,\!\) an object that has the following definition:

\(L_{x \operatorname{at} j} ~=~ \{ (x_1, \ldots, x_j, \ldots, x_k) \in L ~:~ x_j = x \}.\!\)

Any property \(C\!\) of the local flag \(L_{x \operatorname{at} j} \subseteq L\!\) is said to be a local incidence property of \(L\!\) with respect to the locus \(x \operatorname{at} j.\!\)

A \(k\!\)-adic relation \(L \subseteq X_1 \times \ldots \times X_k\!\) is said to be \(C\!\)-regular at \(j\!\) if and only if every flag of \(L\!\) with \(x\!\) at \(j\!\) has the property \(C,\!\) where \(x\!\) is taken to vary over the theme of the fixed domain \(X_j.\!\)

Expressed in symbols, \(L\!\) is \(C\!\)-regular at \(j\!\) if and only if \(C(L_{x \operatorname{at} j})\!\) is true for all \(x\!\) in \(X_j.\!\)

Regional incidence properties

The definition of a local flag can be broadened from a point \(x\!\) in \({X_j}\!\) to a subset \(M\!\) of \(X_j,\!\) arriving at the definition of a regional flag in the following way:

Suppose that \(L \subseteq X_1 \times \ldots \times X_k,\!\) and choose a subset \(M \subseteq X_j.\!\) Then \(L_{M \operatorname{at} j}\!\) is a subset of \(L\!\) that is said to be the flag of \(L\!\) with \(M\!\) at \({j},\!\) or the \(M \operatorname{at} j\!\)-flag of \(L,\!\) an object which has the following definition:

\(L_{M \operatorname{at} j} ~=~ \{ (x_1, \ldots, x_j, \ldots, x_k) \in L ~:~ x_j \in M \}.\!\)

Numerical incidence properties

A numerical incidence property (NIP) of a relation is a local incidence property that depends on the cardinalities of its local flags.

For example, \(L\!\) is said to be \(c\!\)-regular at \(j\!\) if and only if the cardinality of the local flag \(L_{x \operatorname{at} j}\!\) is \(c\!\) for all \(x\!\) in \({X_j},\!\) or, to write it in symbols, if and only if \(|L_{x \operatorname{at} j}| = c\!\) for all \({x \in X_j}.\!\)

In a similar fashion, one can define the NIPs, \((<\!c)\!\)-regular at \({j},\!\) \((>\!c)\!\)-regular at \({j},\!\) and so on. For ease of reference, a few of these definitions are recorded here:

\(\begin{matrix} L & \text{is} & c\textit{-regular} & \text{at}\ j & \text{if and only if} & |L_{x \operatorname{at} j}| & = & c & \text{for all}\ x \in X_j. \\[4pt] L & \text{is} & (<\!c)\textit{-regular} & \text{at}\ j & \text{if and only if} & |L_{x \operatorname{at} j}| & < & c & \text{for all}\ x \in X_j. \\[4pt] L & \text{is} & (>\!c)\textit{-regular} & \text{at}\ j & \text{if and only if} & |L_{x \operatorname{at} j}| & > & c & \text{for all}\ x \in X_j. \end{matrix}\)

Species of 2-adic relations

Returning to 2-adic relations, it is useful to describe some familiar classes of objects in terms of their local and numerical incidence properties. Let \(L \subseteq S \times T\!\) be an arbitrary 2-adic relation. The following properties of \(L\!\) can be defined:

\(\begin{matrix} L & \text{is} & \textit{total} & \text{at}~ S & \text{if and only if} & L & \text{is} & (\ge 1)\text{-regular} & \text{at}~ S. \\[4pt] L & \text{is} & \textit{total} & \text{at}~ T & \text{if and only if} & L & \text{is} & (\ge 1)\text{-regular} & \text{at}~ T. \\[4pt] L & \text{is} & \textit{tubular} & \text{at}~ S & \text{if and only if} & L & \text{is} & (\le 1)\text{-regular} & \text{at}\ S. \\[4pt] L & \text{is} & \textit{tubular} & \text{at}~ T & \text{if and only if} & L & \text{is} & (\le 1)\text{-regular} & \text{at}~ T. \end{matrix}\)

If \(L \subseteq S \times T\!\) is tubular at \(S\!\) then \(L\!\) is called a partial function or a prefunction from \(S\!\) to \(T.\!\) This is sometimes indicated by giving \(L\!\) an alternate name, say, \({}^{\backprime\backprime} p {}^{\prime\prime},~\!\) and writing \(L = p : S \rightharpoonup T.\!\)

Just by way of formalizing the definition:

\(\begin{matrix} L & = & p : S \rightharpoonup T & \text{if and only if} & L & \text{is} & \text{tubular} & \text{at}~ S. \end{matrix}\)

If \(L\!\) is a prefunction \(p : S \rightharpoonup T\!\) that happens to be total at \(S,\!\) then \(L\!\) is called a function from \(S\!\) to \(T,\!\) indicated by writing \(L = f : S \to T.\!\) To say that a relation \(L \subseteq S \times T\!\) is totally tubular at \(S\!\) is to say that it is \(1\!\)-regular at \(S.\!\) Thus, we may formalize the following definition:

\(\begin{matrix} L & = & f : S \to T & \text{if and only if} & L & \text{is} & 1\text{-regular} & \text{at}~ S. \end{matrix}\)

In the case of a function \(f : S \to T,\!\) one has the following additional definitions:

\(\begin{matrix} f & \text{is} & \textit{surjective} & \text{if and only if} & f & \text{is} & \text{total} & \text{at}~ T. \\[4pt] f & \text{is} & \textit{injective} & \text{if and only if} & f & \text{is} & \text{tubular} & \text{at}~ T. \\[4pt] f & \text{is} & \textit{bijective} & \text{if and only if} & f & \text{is} & 1\text{-regular} & \text{at}~ T. \end{matrix}\)

Variations

Because the concept of a relation has been developed quite literally from the beginnings of logic and mathematics, and because it has incorporated contributions from a diversity of thinkers from many different times and intellectual climes, there is a wide variety of terminology that the reader may run across in connection with the subject.

One dimension of variation is reflected in the names that are given to \(k\!\)-place relations, for \(k = 0, 1, 2, 3, \ldots,\!\) with some writers using the Greek forms, medadic, monadic, dyadic, triadic, \(k\!\)-adic, and other writers using the Latin forms, nullary, unary, binary, ternary, \(k\!\)-ary.

The number of relational domains may be referred to as the adicity, arity, or dimension of the relation. Accordingly, one finds a relation on a finite number of domains described as a polyadic relation or a finitary relation, but others count infinitary relations among the polyadic. If the number of domains is finite, say equal to \(k,\!\) then the relation may be described as a \(k\!\)-adic relation, a \(k\!\)-ary relation, or a \(k\!\)-dimensional relation, respectively.

A more conceptual than nominal variation depends on whether one uses terms like predicate, relation, and even term to refer to the formal object proper or else to the allied syntactic items that are used to denote them. Compounded with this variation is still another, frequently associated with philosophical differences over the status in reality accorded formal objects. Among those who speak of numbers, functions, properties, relations, and sets as being real, that is to say, as having objective properties, there are divergences as to whether some things are more real than others, especially whether particulars or properties are equally real or else one is derivative in relationship to the other. Historically speaking, just about every combination of modalities has been used by one school of thought or another, but it suffices here merely to indicate how the options are generated.

Examples

See the articles on relations, relation composition, relation reduction, sign relations, and triadic relations for concrete examples of relations.

Many relations of the greatest interest in mathematics are triadic relations, but this fact is somewhat disguised by the circumstance that many of them are referred to as binary operations, and because the most familiar of these have very specific properties that are dictated by their axioms. This makes it practical to study these operations for quite some time by focusing on their dyadic aspects before being forced to consider their proper characters as triadic relations.

References

  • 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.
  • Ulam, S.M. and 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

  • Barr, Michael, and Wells, Charles (1990), Category Theory for Computing Science, Prentice Hall, Hemel Hempstead, UK.
  • Bourbaki, Nicolas (1994), Elements of the History of Mathematics, John Meldrum (trans.), Springer-Verlag, Berlin, Germany.
  • Carnap, Rudolf (1958), Introduction to Symbolic Logic with Applications, Dover Publications, New York, NY.
  • Chang, C.C., and Keisler, H.J. (1973), Model Theory, North-Holland, Amsterdam, Netherlands.
  • van Dalen, Dirk (1980), Logic and Structure, 2nd edition, Springer-Verlag, Berlin, Germany.
  • Devlin, Keith J. (1993), The Joy of Sets : Fundamentals of Contemporary Set Theory, 2nd edition, Springer-Verlag, New York, NY.
  • Halmos, Paul Richard (1960), Naive Set Theory, D. Van Nostrand Company, Princeton, NJ.
  • van Heijenoort, Jean (1967/1977), From Frege to Gödel : A Source Book in Mathematical Logic, 1879–1931, Harvard University Press, Cambridge, MA, 1967. Reprinted with corrections, 1977.
  • Kelley, John L. (1955), General Topology, Van Nostrand Reinhold, New York, NY.
  • Kneale, William; and Kneale, Martha (1962/1975), The Development of Logic, Oxford University Press, Oxford, UK, 1962. Reprinted with corrections, 1975.
  • Lawvere, Francis William; and Rosebrugh, Robert (2003), Sets for Mathematics, Cambridge University Press, Cambridge, UK.
  • Lawvere, Francis William; and Schanuel, Stephen H. (1997/2000), Conceptual Mathematics : A First Introduction to Categories, Cambridge University Press, Cambridge, UK, 1997. Reprinted with corrections, 2000.
  • Manin, Yu. I. (1977), A Course in Mathematical Logic, Neal Koblitz (trans.), Springer-Verlag, New York, NY.
  • Mathematical Society of Japan (1993), Encyclopedic Dictionary of Mathematics, 2nd edition, 2 vols., Kiyosi Itô (ed.), MIT Press, Cambridge, MA.
  • Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994), Computer Program Construction, Oxford University Press, New York, NY. (Introduction to Tarskian relation theory and relational programming.)
  • Mitchell, John C. (1996), Foundations for Programming Languages, MIT Press, Cambridge, MA.
  • Peirce, Charles Sanders (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 (1870), 317–378. Reprinted (CP 3.45–149), (CE 2, 359–429).
  • Peirce, Charles Sanders (1931–1935, 1958), Collected Papers of Charles Sanders Peirce, vols. 1–6, Charles Hartshorne and Paul Weiss (eds.), vols. 7–8, Arthur W. Burks (ed.), Harvard University Press, Cambridge, MA. Cited as (CP volume.paragraph).
  • Peirce, Charles Sanders (1981–), Writings of Charles S. Peirce : A Chronological Edition, Peirce Edition Project (eds.), Indiana University Press, Bloomington and Indianapolis, IN. Cited as (CE volume, page).
  • Poizat, Bruno (2000), A Course in Model Theory : An Introduction to Contemporary Mathematical Logic, Moses Klein (trans.), Springer-Verlag, New York, NY.
  • Quine, Willard Van Orman (1940/1981), Mathematical Logic, 1940. Revised edition, Harvard University Press, Cambridge, MA, 1951. New preface, 1981.
  • Royce, Josiah (1961), The Principles of Logic, Philosophical Library, New York, NY.
  • Runes, Dagobert D. (ed., 1962), Dictionary of Philosophy, Littlefield, Adams, and Company, Totowa, NJ.
  • Shoenfield, Joseph R. (1967), Mathematical Logic, Addison-Wesley, Reading, MA.
  • Styazhkin, N.I. (1969), History of Mathematical Logic from Leibniz to Peano, MIT Press, Cambridge, MA.
  • Suppes, Patrick (1957/1999), Introduction to Logic, 1st published 1957. Reprinted, Dover Publications, New York, NY, 1999.
  • Suppes, Patrick (1960/1972), Axiomatic Set Theory, 1st published 1960. Reprinted, Dover Publications, New York, NY, 1972.
  • Tarski, Alfred (1956/1983), Logic, Semantics, Metamathematics : Papers from 1923 to 1938, J.H. Woodger (trans.), Oxford University Press, 1956. 2nd edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.
  • Ulam, Stanislaw Marcin; and Bednarek, A.R. (1977), “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.
  • Ulam, Stanislaw Marcin (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.
  • Ullman, Jeffrey D. (1980), Principles of Database Systems, Computer Science Press, Rockville, MD.
  • Venetus, Paulus (1472/1984), Logica Parva : Translation of the 1472 Edition with Introduction and Notes, Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.

Syllabus

Focal nodes

Peer nodes

Logical operators

Template:Col-breakTemplate:Col-breakTemplate:Col-end

Related topics

Template:Col-breakTemplate:Col-breakTemplate:Col-breakTemplate:Col-end

Relational concepts

Template:Col-breakTemplate:Col-breakTemplate:Col-breakTemplate:Col-end

Information, Inquiry

Template:Col-breakTemplate:Col-breakTemplate:Col-breakTemplate:Col-breakTemplate:Col-end

Related articles

Template:Col-breakTemplate:Col-breakTemplate:Col-breakTemplate:Col-end

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.