Lecture 14 - Properties of Relations (Part 2)

These flashcards cover key terms and definitions related to equivalence relations and partial orders as discussed in ITSC 2175.

Equivalence Relation

A relation R on a set A that is reflexive, symmetric, and transitive.

Reflexive Property

For every element a in a set A, aRa holds.

Symmetric Property

For elements a and b in a set A, if aRb holds, then bRa also holds.

Transitive Property

For elements a, b, and c in a set A, if aRb and bRc hold, then aRc must also hold.

Equivalence Class

The set of all elements equivalent to a in a relation R, denoted as [a].

Partition

A collection of non-empty subsets of a set A such that every element of A is in exactly one of the subsets.

Partial Order

A relation R on a set S that is reflexive, transitive, and anti-symmetric.

Anti-symmetric Property

For elements a and b in a set S, if aRb and bRa hold, then a must be equal to b.

Comparable Elements

In a poset, elements a and b are comparable if either a ⪯ b or b ⪯ a.

Minimal Element

An element a in a poset such that there is no element b ≠ a with b ⪯ a.

Maximal Element

An element a in a poset such that there is no element b ≠ a with a ⪯ b.

Hasse Diagram

A visual representation of a partial order, omitting edges that are implied by reflexivity and transitivity.

Divisibility Relation

A relation aRb defined on positive integers such that a divides b, denoted as a|b.

Total Order

A partial order in which every pair of elements is comparable.