Relations: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 18: Line 18:


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 '''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.


=TODO=
=TODO=


<font color=darkgray>[[CLRS]] page 1163</font>
<font color=darkgray>[[CLRS]] page 1163</font>

Revision as of 21:50, 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.

TODO

CLRS page 1163