Namespaces
Variants
Actions

Difference between revisions of "Relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 1: Line 1:
A subset of a finite Cartesian power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r0809801.png" /> of a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r0809802.png" />, i.e. a set of tuples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r0809803.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r0809804.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r0809805.png" />.
+
A subset of a finite Cartesian power $A^n = A \times \cdots \times $ of a given set $A$, i.e. a set of tuples $(a_1,\ldots,a_n)$ of $n$ elements of $A$.
  
A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r0809806.png" /> is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r0809808.png" />-place, or an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098010.png" />-ary, relation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098013.png" />. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098014.png" /> is called the rank, or type, of the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098015.png" />. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098016.png" /> is also called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098018.png" />-place, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098020.png" />-ary, predicate on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098023.png" />. The notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098024.png" /> signifies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098025.png" />.
+
A subset $R \subseteq A^n$ is called an $n$-place, or an $n$-ary, relation on $A$. The number $n$ is called the rank, or type, of the relation $R$. The notation $R(a_1,\ldots,a_n)$ signifies that $(a_1,\ldots,a_n) \in R$.
  
One-place relations are called properties. Two-place relations are called binary, three-place relations are called ternary, etc.
+
One-place relations are called properties. Two-place relations are called [[binary relation]]s, three-place relations are called ternary, etc.
  
The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098026.png" /> and the empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098027.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098028.png" /> are called, respectively, the universal relation and the zero relation of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098029.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098030.png" />. The diagonal of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098031.png" />, i.e. the set
+
The set $A^n$ and the empty subset $\emptyset$ in $R^n$ are called, respectively, the ''universal relation'' and the ''zero relation'' of rank $n$ on $A$. The diagonal of the set $A^n$, i.e. the set
 +
$$
 +
\Delta = \{ (a,a,\ldots,a) : a \in A \}
 +
$$
 +
is called the ''equality relation'' on $A$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098032.png" /></td> </tr></table>
+
If $R$ and $S$ are $n$-place relations on $A$, then the following subsets of $A^n$ will also be $n$-place relations on $A$:
 +
$$
 +
R \cap S\, \ \ R \cup S\,,\ \ R' = A^n \setminus R\,\ \ R \setminus S \ .
 +
$$
  
is called the equality relation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098033.png" />.
+
The set of all $n$-ary relations on $A$ is a [[Boolean algebra]] relative to the operations $\cup$, $\cap$, ${}'$. An $(n+1)$-place relation $F$ on $A$ is called ''functional'' if for any elements $a_1,\ldots,a_n$, $a,b$,  from $A$ it follows from $F(a_1,\ldots,a_n,a)$ and $F(a_1,\ldots,a_n,b)$ that $a = b$.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098035.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098036.png" />-place relations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098037.png" />, then the following subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098038.png" /> will also be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098039.png" />-place relations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098040.png" />:
+
See also [[Binary relation]]; [[Correspondence]]; [[Predicate]].
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098041.png" /></td> </tr></table>
 
 
 
The set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098042.png" />-ary relations on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098043.png" /> is a [[Boolean algebra|Boolean algebra]] relative to the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098044.png" />. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098045.png" />-place relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098046.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098047.png" /> is called a function if for any elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098048.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098049.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098050.png" /> it follows from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098051.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098052.png" /> that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080980/r08098053.png" />.
 
 
 
See also [[Binary relation|Binary relation]]; [[Correspondence|Correspondence]].
 
  
  
Line 25: Line 26:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.L. Bell,  M. Machover,  "A course in mathematical logic" , North-Holland  (1977)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  J.L. Bell,  M. Machover,  "A course in mathematical logic" , North-Holland  (1977)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Revision as of 16:40, 2 January 2016

A subset of a finite Cartesian power $A^n = A \times \cdots \times $ of a given set $A$, i.e. a set of tuples $(a_1,\ldots,a_n)$ of $n$ elements of $A$.

A subset $R \subseteq A^n$ is called an $n$-place, or an $n$-ary, relation on $A$. The number $n$ is called the rank, or type, of the relation $R$. The notation $R(a_1,\ldots,a_n)$ signifies that $(a_1,\ldots,a_n) \in R$.

One-place relations are called properties. Two-place relations are called binary relations, three-place relations are called ternary, etc.

The set $A^n$ and the empty subset $\emptyset$ in $R^n$ are called, respectively, the universal relation and the zero relation of rank $n$ on $A$. The diagonal of the set $A^n$, i.e. the set $$ \Delta = \{ (a,a,\ldots,a) : a \in A \} $$ is called the equality relation on $A$.

If $R$ and $S$ are $n$-place relations on $A$, then the following subsets of $A^n$ will also be $n$-place relations on $A$: $$ R \cap S\, \ \ R \cup S\,,\ \ R' = A^n \setminus R\,\ \ R \setminus S \ . $$

The set of all $n$-ary relations on $A$ is a Boolean algebra relative to the operations $\cup$, $\cap$, ${}'$. An $(n+1)$-place relation $F$ on $A$ is called functional if for any elements $a_1,\ldots,a_n$, $a,b$, from $A$ it follows from $F(a_1,\ldots,a_n,a)$ and $F(a_1,\ldots,a_n,b)$ that $a = b$.

See also Binary relation; Correspondence; Predicate.


Comments

References

[a1] J.L. Bell, M. Machover, "A course in mathematical logic" , North-Holland (1977)
How to Cite This Entry:
Relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Relation&oldid=14950
This article was adapted from an original article by D.M. Smirnov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article