请输入您要查询的字词:

 

单词 OperationsOnRelations
释义

operations on relations


Recall that an n-ary relationMathworldPlanetmathPlanetmath (n>0) is a subset of a productMathworldPlanetmathPlanetmath of some n sets. In this definition, any n-ary relation for which n>1 is automatically an (n-1)-ary relation, and consequently a binary relation. On the other hand, a unary, or 1-ary relation, being the subset B of some set A, can be viewed as a binary relation (either realized as B×B or ΔB:={(b,b)bB}) on A. Hence, we shall concentrate our discussion on the most important kind of relations, the binary relations, in this entry.

Compositions, Inverses, and Complements

Let ρA×B and σB×C be two binary relations. We define the compositionMathworldPlanetmathPlanetmath of ρ and σ, the inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath (or converseMathworldPlanetmath) and the complementMathworldPlanetmathPlanetmath of ρ by

  • ρσ:={(a,c)(a,b)ρ and (b,c)σ for some bB},

  • ρ-1:={(b,a)(a,b)ρ}, and

  • ρ:={(a,b)(a,b)ρ}.

ρσ,ρ-1 and ρ are binary relations of A×C,B×A and A×B respectively.

Properties.Suppose ρ,σ,τ are binary relations of A×B,B×C,C×D respectively.

  1. 1.

    Associativity of relational compositionsPlanetmathPlanetmath: (ρσ)τ=ρ(στ).

  2. 2.

    (ρσ)-1=σ-1ρ-1.

  3. 3.

    For the rest of the remarks, we assume A=B. Define the power of ρ recursively by ρ1=ρ, and ρn+1=ρρn. By 1 above, ρn+m=ρnρm for m,n.

  4. 4.

    ρ-n may be also be defined, in terms of ρ-1 for n>0.

  5. 5.

    However, ρn+mρnρm for all integers, since ρ-1ρρρ-1 in general.

  6. 6.

    Nevertheless, we may define Δ:={(a,a)aA}. This is called the identityPlanetmathPlanetmath or diagonal relation on A. It has the property that Δρ=ρΔ=ρ. For this, we may define, for every relation ρ on A, ρ0:=Δ.

  7. 7.

    Let be the set of all binary relations on a set A. Then (,) is a monoid (http://planetmath.org/Monoid) with Δ as the identity elementMathworldPlanetmath.

Let ρ be a binary relation on a set A, below are some special relations definable from ρ:

  • ρ is reflexiveMathworldPlanetmathPlanetmath if Δρ;

  • ρ is symmetricMathworldPlanetmathPlanetmath if ρ=ρ-1;

  • ρ is anti-symmetric if ρρ-1Δ;

  • ρ is transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmath if ρρρ;

  • ρ is a pre-order if it is reflexive and transitive

  • ρ is a partial orderMathworldPlanetmath if it is a pre-order and is anti-symmetric

  • ρ is an equivalence if it is a pre-order and is symmetric

Of these, only reflexivity is preserved by and both symmetryMathworldPlanetmath and anti-symmetry are preserved by the inverse operationMathworldPlanetmath.

Other Operations

Some operations on binary relations yield unary relations. The most common ones are the following:

Given a binary relation ρA×B, and an elements aA and bB, define

ρ(a,):={y(a,y)ρ} and ρ(,b):={x(x,b)ρ}.

ρ(a,)B is called the sectionMathworldPlanetmath of ρ in B based at a, and ρ(,b)A is the section of ρ in A (based) at b. When the base points are not mentioned, we simply say a section of ρ in A or B, or an A-section or a B-section of ρ.

Finally, we define the domain and range of a binary relation ρA×B, to be

  • dom(ρ):={a(a,b)ρ for some bB}, and

  • ran(ρ):={b(a,b)ρ for some aA}.

respectively. When ρ is a function, the domain and range of ρ coincide with the domain of range of ρ as a function.

Remarks. Given a binary relation ρA×B.

  1. 1.

    ρ(a,), realized as a binary relation {a}×ρ(a,) can be viewed as the composition of Δaρ, where Δa={(a,a)}. Similarly, ρΔb=ρ(,b)×{b}.

  2. 2.

    dom(ρ) is the disjoint unionMathworldPlanetmath of A-sections of ρ and ran(ρ) is the disjoint union of B-sections of ρ.

  3. 3.

    dom(ρ-1)=ran(ρ) and ran(ρ-1)=dom(ρ).

  4. 4.

    ρρ-1=dom(ρ)×dom(ρ) and ρ-1ρ=ran(ρ)×ran(ρ).

  5. 5.

    If A=B, then dom(ρ)×A=ρA2 and ran(ρ)=A2ρ.

  6. 6.

    The composition of binary relations can be generalized: let R be a subset of A1××An and S be a subset of B1××Bm, where m,n are positive integers. Further, we assume that An=B1=C. Define RS, as a subset of A1××An-1×B2×Bm, to be the set

    {(a1,,an-1,b2,,bm)cC with (a1,,an-1,c)R and (c,b2,,bm)S}.

    If m=n=2, then we have the familiar composition of binary relations. If m=1 and n=2, then RS={a(a,c)R and cS}. The case where m=2 and n=1 is similarMathworldPlanetmathPlanetmath. If m=n=1, then RS={ true } if RS. Otherwise, it is set to { false }.

Titleoperations on relations
Canonical nameOperationsOnRelations
Date of creation2013-03-22 16:26:40
Last modified on2013-03-22 16:26:40
OwnerCWoo (3771)
Last modified byCWoo (3771)
Numerical id14
AuthorCWoo (3771)
Entry typeDefinition
Classificationmsc 08A02
Classificationmsc 03E20
Synonyminverse relation
Synonymrelation composition
Synonymconverse of a relation
Synonymdiagonal relation
Related topicGeneralAssociativity
Related topicRelationAlgebra
Definespower of a relation
Definesrelational composition
Definesinverse of a relation
Definessection
Definesdomain
Definesrange
Definesidentity relation

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 16:53:22