michael orlitzky

Related Concepts in Algebra

There are a couple of closely related concepts in algebra that (it seems to me) should be presented one after another. In my experience, these ideas have often been presented independently and, in my opinion, out of order.

sets

A set is a collection of things. Let A and B be sets. I will refer to the elements of A and B as a1, a2... an and b1, b2... bn respectively. x ∈ A simply means that the element x is in the set A.

cartesian product

The Cartesian Product of two sets A and B, denoted A × B, is the set of all ordered pairs (x, y) such that x ∈ A and y ∈ B.

relation

A relation between two sets A and B is a subset of A × B. If B = A, S is called a relation on A.

equivalence relation

An equivalence relation (call it θ) on a set S is a relation on S such that the relation is reflexive, symmetric, and transitive. That is, ∀ x, y, z ∈ S,

  1. (x, x) ∈ θ reflexive
  2. (x, y) ∈ θ ↔ (y, x) ∈ θ symmetric
  3. (x, y) ∈ θ and (y, z) ∈ θ → (x, z) ∈ θ transitive

function

A function f from A into B is a subset of A × B such that:

  1. ∀x∈A, ∃y∈B such that (x, y) ∈ f
  2. (x, y1) ∈ f and (x, y2) ∈ f → y1 = y2