Properties of Binary Relations

Let be a homogenous binary relation over the set , and let .

• Reflexive:
  • Irreflexive: not
• Symmetric:
  • Asymmetric:
  • Antisymmetric:
• Transitive:
• Connected:
  • Strongly connected:
• Dense:

is reflexive iff for all ,

The relation is reflexive (i.e )

A relation is reflexive if and only if its complement is irreflexive

is irreflexive (or strict) iff for all , not

The relation is irreflexive (i.e )

is symmetric iff for all , if , then

• The relation is symmetric (i.e )
• The relation "is blood relative of" is symmetric

A relation is equal to its converse if and only if it is symmetric

is asymmetric iff for all , if , then not

The relation is asymmetric (i.e )

A binary relation is asymmetric if and only if it is both irreflexive and antisymmetric

is antisymmetric iff for all , if and , then

• The relation is antisymmetric (i.e )
• The relation (subset) is antisymmetric (i.e ), which is the definition of set equality
• The relation divisibility over natural numbers is antisymmetric (i.e )

This is NOT the same as asymmetric

is transitive iff for all , if and , then

• The relation is transitive (i.e )
• The relation divisibility is transitive (i.e )
• The relation "is ancestor of" is transitive, but the relation "is parent of" is not

A transitive relation is irreflexive if and only if it is asymmetric

is connected iff for all , if , then or

The relation over is connected (i.e )

A relation is connected if and only if its complement is antisymmetric

is strongly connected iff for all , or

The relation over is strongly connected (i.e )

A relation is strongly connected if and only if it is connected and reflexive

A relation is strongly connected if and only if its complement is asymmetric

is dense iff for all , if , then there exists some such that and

The relation is dense (i.e )

For example, let (that is, some real value between and , which will always exist, since ), then

is injective iff for all , if and then .

is functional iff for all , if and then .

is total iff for all , there exists some such that .

is surjective iff for all , there exists an such that .

is bijective iff it is both injective and surjective

• One-to-one: injective and functional
• One-to-many: injective and not functional
• Many-to-one: not injective, functional
• Many-to-many: not injective nor functional

A partial order over a set is an arrangement such that, for each pair of elements, one precedes the other.

The word partial indicates that not every pair of elements needs to be comparable, only that adjacent ones do.

A partial order is a relation that is reflexive, antisymmetric, and transitive.

The relation on a set is a partial order. That is, it fulfils the properties:

• Reflexive:
• Antisymmetric: if and then
• Transitive: if and then

A strict partial order is a relation that is irreflexive, antisymmetric, and transitive.

The relation on a set is a strict partial order. That is, it fulfils the properties:

• Irreflexive: not
• Asymmetric: if , then not
• Transitive: if and , then

A total order over a set is an arrangement such that, for each pair of elements, one precedes the other.

The word total indicates that every pair of elements needs to be comparable.

A total order is a relation that is reflexive, antisymmetric, transitive, and connected

A strict total order is a relation that is irreflexive, antisymmetric, transitive, and connected