michael orlitzky

Related concepts in algebra

There are a couple of closely related concepts in algebra that should be presented one after another. I'm not giving any background here, but if you've seen these things before, maybe this will help you remember them.

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 a₁, a₂... a_n and b₁, b₂... b_n 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, y₁) ∈ f and (x, y₂) ∈ f → y₁ = y₂