Relations: Difference between revisions
| Line 20: | Line 20: | ||
<span id='Transitive_Relation'></span>A binary relation R ⊆ A x A is '''transitive''' if ''a R b'' and ''b R c'' implies ''a R c'' for all a, b, c ∈ A. | <span id='Transitive_Relation'></span>A binary relation R ⊆ A x A is '''transitive''' if ''a R b'' and ''b R c'' implies ''a R c'' for all a, b, c ∈ A. | ||
=Equivalence= | |||
<span id=Equivalence_Relation'></span>A relation that is [[#Reflexive_Relation|reflexive]], [[#Symmetric_Relation|symmetric]] and [[#Transitive_Relation|transitive]] is an '''equivalence relation'''. For example, "=" is an equivalence relation on the natural numbers. | <span id=Equivalence_Relation'></span>A relation that is [[#Reflexive_Relation|reflexive]], [[#Symmetric_Relation|symmetric]] and [[#Transitive_Relation|transitive]] is an '''equivalence relation'''. For example, "=" is an equivalence relation on the natural numbers. | ||
<span id=Equivalence_Class'></span>'''Equivalence class'''. If R is an [[#Equivalence_Relation|equivalence relation]] on the set A, then for a ∈ A, the '''equivalence class''' of a is the set [a] = {b ∈ A, where a R b}. In other words, the equivalence set of a is the set of all elements equivalent to a, relative to relation R. | <span id=Equivalence_Class'></span>'''Equivalence class'''. If R is an [[#Equivalence_Relation|equivalence relation]] on the set A, then for a ∈ A, the '''equivalence class''' of a is the set [a] = {b ∈ A, where a R b}. In other words, the equivalence set of a is the set of all elements equivalent to a, relative to relation R. | ||
'''Theorem: An equivalence relation is the same as a partition'''. The equivalence classes of any equivalence relation R on a set A for a partition of A, and any partition of A determines an equivalence relation on A for which the sets in the partition are the equivalence classes. | |||
=TODO= | =TODO= | ||
<font color=darkgray>[[CLRS]] page 1163</font> | <font color=darkgray>[[CLRS]] page 1163</font> | ||
Revision as of 21:58, 27 August 2018
Internal
Overview
A binary relation R on two sets A and B is a subset of the Cartesian product A x B. If (a, b) belongs to the subset of the Cartesian product that defines the relation, we write a R b.
A binary relation R on a set A is a subset of the Cartesian product A x A.
A n-ary relation on sets A1, A2, .... An is a subset of the Cartesian product A1 x A2 x ... x An.
An example of a binary relation on a finite set is the edge set of a graph.
Binary Relation Properties
A binary relation R ⊆ A x A is reflexive if a R a for all a ∈ A.
A binary relation R ⊆ A x A is symmetric if a R b implies b R a for all a, b ∈ A.
A binary relation R ⊆ A x A is transitive if a R b and b R c implies a R c for all a, b, c ∈ A.
Equivalence
A relation that is reflexive, symmetric and transitive is an equivalence relation. For example, "=" is an equivalence relation on the natural numbers.
Equivalence class. If R is an equivalence relation on the set A, then for a ∈ A, the equivalence class of a is the set [a] = {b ∈ A, where a R b}. In other words, the equivalence set of a is the set of all elements equivalent to a, relative to relation R.
Theorem: An equivalence relation is the same as a partition. The equivalence classes of any equivalence relation R on a set A for a partition of A, and any partition of A determines an equivalence relation on A for which the sets in the partition are the equivalence classes.
TODO
CLRS page 1163