imports from: relations, highschool
Properties of binary Relations
  • Definition

    A relation ( R ⊆ ( A × A ) ) is called

    • reflexive on A , iff ( ∀ a . ( ( ⟨ a , a ⟩ ) ∈ R ) )
    • symmetric on A , iff ( ∀ a , b . ( ( ( ⟨ a , b ⟩ ) ∈ R ) ⇒ ( ( ⟨ b , a ⟩ ) ∈ R ) ) )
    • antisymmetric on A , iff ( ∀ a , b . ( ( ( ( ⟨ a , b ⟩ ) ∈ R ) ∧ ( ( ⟨ b , a ⟩ ) ∈ R ) ) ⇒ ( a = b ) ) )
    • transitive on A , iff ( ∀ a , b , c . ( ( ( ( ⟨ a , b ⟩ ) ∈ R ) ∧ ( ( ⟨ b , c ⟩ ) ∈ R ) ) ⇒ ( ( ⟨ a , c ⟩ ) ∈ R ) ) )
    • equivalence relation on A , iff R is reflexive, symmetric, and transitive
    • partial order on A , iff R is reflexive, antisymmetric, and transitive on A .
    • a linear order on A , iff R is transitive and for all inset ( x , y , A ) with ne ( x , y ) either ( ( ⟨ x , y ⟩ ) ∈ R ) or ( ( ⟨ y , x ⟩ ) ∈ R )
  • Example

    The equality relation is an equivalence relation on any set.

  • Example

    The ≤ relation is a linear order on N all elements are comparable

  • Example

    On sets of persons, the “mother-of” relation is an non-symmetric, non-reflexive relation.

  • Example

    On sets of persons, the “ancestor-of” relation is a partial order that is not linear.