Difference between revisions of "Binary relation"
(→Formal Definition and Notation) |
|||
(9 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
A '''binary relation''' is a [[relation]] which relates pairs of objects. | A '''binary relation''' is a [[relation]] which relates pairs of objects. | ||
− | Thus, the relation <math>\sim</math> of [[triangle]] [[similarity]] is a binary relation over the [[set]] of triangles but the relation <math>R(x, y, z) = \{(x, y, z) \mid x, y, z \in \mathbb{Z}_{>0}, x\cdot y = z\}</math> which says <math>x\cdot y</math> is a | + | Thus, the relation <math>\sim</math> of [[triangle]] [[similarity]] is a binary relation over the [[set]] of triangles but the relation <math>R(x, y, z) = \{(x, y, z) \mid x, y, z \in \mathbb{Z}_{>0}, x\cdot y = z\}</math> which says <math>x\cdot y</math> is a [[divisor | factor]]ization of <math>z</math> over the [[positive integer]]s is not a binary relation because it takes 3 arguments. |
+ | |||
+ | == Formal Definition and Notation == | ||
+ | |||
+ | Formally, we say that a relation <math>\mathfrak{R}</math> on sets <math>A</math> and <math>B</math> is a subset of <math>A \times B</math> (the [[Cartesian product]] of <math>A</math> and <math>B</math>). We often write <math>a \, \mathfrak{R} \, b</math> instead of <math>(a,b) \in \mathfrak{R}</math>. If <math>A=B</math> (the case of most common interest), then we say that <math>\mathfrak{R}</math> is a relation on <math>A</math>. | ||
+ | |||
+ | Thus, in the example of <math>\sim</math> above, we may let <math>\sim</math> be the set of ordered pairs of triangles in the Euclidean plane which are similar to each other. We could also define a relation <math>\leq</math> on the [[power set]] of a set <math>S</math>, so that <math>(A,B) \in \leq</math>, or <math>A\leq B</math>, if and only if <math>A</math> and <math>B</math> are [[subset]]s of <math>S</math> and <math>A</math> is a subset of <math>B</math>. This is a common example of an [[order relation]]. | ||
+ | |||
+ | More generally, we say that a relation <math>\mathfrak{R}(x,y)</math> is a mathematical sentence in which two letters, <math>x</math> and <math>y</math>, are of particular interest. This more general definition is useful because it admits relations whose "domain" is a class of sets too large to constitute a set. For instance, the relation <math>\mathfrak{R}(x,y)</math> defined as <math>(x=y)</math> applies to all sets, not just sets contained in some larger set. | ||
+ | |||
+ | == Domain and Range == | ||
+ | |||
+ | The domain of a binary relation <math>\mathfrak{R}</math> over <math>A</math> and <math>B</math>, written <math>\text{Dom}(\mathfrak{R})</math>, is defined to be the set <math>\{x \in A | (\exists y \in B)(x,y) \in \mathfrak{R}\}</math>. It is thus the set of the first components of the ordered pairs in <math>\mathfrak{R}</math>. | ||
+ | |||
+ | The range of a binary relation <math>\mathfrak{R}</math> over <math>A</math> and <math>B</math>, written <math>\text{Ran}(\mathfrak{R})</math>, is defined to be the set <math>\{y \in B | (\exists x \in A)(x,y) \in \mathfrak{R}\}</math>. It is thus the set of the second components of the ordered pairs in <math>\mathfrak{R}</math>. | ||
+ | |||
+ | == Reflexivity, Symmetry and Transitivity == | ||
+ | |||
+ | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be reflexive if <math>(\forall a \in A)(a \mathfrak{R} a)</math>. | ||
+ | |||
+ | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be symmetric if <math>(\forall (a,b) \in A^2)((a \mathfrak{R} b) \rightarrow (b \mathfrak{R} a))</math>. | ||
+ | |||
+ | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be anti-symmetric if <math>(\forall (a,b) \in A^2)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} a)) \rightarrow (a = b))</math>. | ||
+ | |||
+ | A binary relation <math>\mathfrak{R}</math> over <math>A</math> is defined to be transitive if <math>(\forall (a,b,c) \in A^3)(((a \mathfrak{R} b) \wedge (b \mathfrak{R} c)) \rightarrow (a \mathfrak{R} c))</math>. | ||
+ | |||
+ | A reflexive, symmetric and transitive relation is called an [[equivalence relation]]. A reflexive, anti-symmetric and transitive relation is called an [[order relation]]. | ||
+ | |||
+ | ==See also== | ||
+ | |||
+ | * [[Equivalence relation]] | ||
+ | * [[Order relation]] | ||
+ | * [[Function]] | ||
+ | * [[Reflexive]] | ||
+ | |||
+ | {{stub}} |
Latest revision as of 21:33, 18 May 2008
A binary relation is a relation which relates pairs of objects.
Thus, the relation of triangle similarity is a binary relation over the set of triangles but the relation which says is a factorization of over the positive integers is not a binary relation because it takes 3 arguments.
Contents
[hide]Formal Definition and Notation
Formally, we say that a relation on sets and is a subset of (the Cartesian product of and ). We often write instead of . If (the case of most common interest), then we say that is a relation on .
Thus, in the example of above, we may let be the set of ordered pairs of triangles in the Euclidean plane which are similar to each other. We could also define a relation on the power set of a set , so that , or , if and only if and are subsets of and is a subset of . This is a common example of an order relation.
More generally, we say that a relation is a mathematical sentence in which two letters, and , are of particular interest. This more general definition is useful because it admits relations whose "domain" is a class of sets too large to constitute a set. For instance, the relation defined as applies to all sets, not just sets contained in some larger set.
Domain and Range
The domain of a binary relation over and , written , is defined to be the set . It is thus the set of the first components of the ordered pairs in .
The range of a binary relation over and , written , is defined to be the set . It is thus the set of the second components of the ordered pairs in .
Reflexivity, Symmetry and Transitivity
A binary relation over is defined to be reflexive if .
A binary relation over is defined to be symmetric if .
A binary relation over is defined to be anti-symmetric if .
A binary relation over is defined to be transitive if .
A reflexive, symmetric and transitive relation is called an equivalence relation. A reflexive, anti-symmetric and transitive relation is called an order relation.
See also
This article is a stub. Help us out by expanding it.