66881

a and b\

relation is transitive if whenever its graph contains arcs (a, b) and (b, c), then it also contains the arc (a, c), completing the “triangle" with verlices o, b and c;

Theorem Ifa relation R is both symmetric and antisymmetric,

then no two distinct elements of A can be related.

Proof: Let's have a, b GA. If aRb =Xfxom symmetry) bRa=>{from antisymmetry) a = b. The graph of R (in the case, that A is finite) must contain no edges other than loops.

Theorem If a relation R is both contrareflexive and trans itive,

then it is also contrasymmetric.

Proof: Lct‘s assume, that R is symmetric, so:

Va, b ^A aRb=>bRa. From transitivity: a Ra.

But R is contrareflexive, so: Va GA faRa).

So R can't be symmetric =?R is contrasymmetric.

Examples:

1.    The eąuality relation ”=” on the set A is:

-    reflexive, sińce Va GA a= a\

-    symmetric, sińce Va, b GA a- b =>b = a;

-    antisymmetric, sińce Va, b GA a= b Ab = a =>a = b\

-    transitive, sińce Va, b, c GA a= b Ab = c =>a = c.

2.    The relation "less than or equal” "6" on the set R is:

-    reflexive, sińce Va a 6 a;

-    antisymmetric, sińce Va, b ^R a 6 b Ab 6 a =>a = b\