Lecture 13 - Properties of Relations (Part 1)

These flashcards cover key vocabulary and definitions related to binary relations from the lecture notes on logic and algorithms.

Reflexivity

A relation R on set A is reflexive if ∀x ∈ A, (x, x) ∈ R.

Counterexample

An example that disproves a proposition or relation.

Symmetry

A relation R is symmetric if ∀x, y ∈ A, if (x, y) ∈ R then (y, x) ∈ R.

Anti-symmetry

A relation R is anti-symmetric if for all x, y ∈ A, if x ≠ y then (x, y) ∈ R implies (y, x) ∉ R.

Transitivity

A relation R is transitive if ∀x, y, z ∈ A, if (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R.

Relation

A relation R on set A is a subset of the Cartesian product A × A.

Domain

The set of all possible inputs for a function or relation.

Modulus

The operation that finds the remainder after division of one number by another.

Proof by exhaustion

A method of proving a statement by checking all possible cases.

Universal generalization

The principle that states if a property holds for all members of a set, it can be generalized for the set.