R is reflexive if for every a, r contains a,a.
r is symmetric if for every a and b, r contains a,b iff R contains b,a.
R is transitive if for every a, b, and c, r contains a,c whenever r contains both a,b and b,c.
A relation possessing all three properties is called an equivalence relation. The relation partitions the set S into disjoint subsets called equivalence classes. When r is an equivalence relation, a simpler function q carries the same information. Here q is an equivalence class function, where q(a) determines the subset of S that contains a.
A pre ordering is reflexive and transitive.
R is irreflexive if for every a, r does not contain a,a.
r is antisymmetric if a,b and b,a implies a = b. This is where we start using the ≤ notation, for if a ≤ b and b ≤ a then a must equal b. However, this notation can be confusing, at first, because everybody is use to numbers, and given any two numbers, one is always less than or equal to the other. But the elements of an antisymmetric relation need not be comparable. In fact, r could be the empty set, no ordered pairs at all, and the relation is still anticymmetric. We only require that any two elements not be ≤ each other, unless they are the same.
If the relation is irreflexive, you can define antisymmetric as a,b implies not b,a. In this case we use the < operator. That is, a < b means we cannot have b < a. Again, all pairs of elements need not be comparable.
The relation r is a partial ordering on the set S, or S is a partially ordered set via r, or S is a poset, if r is transitive and antisymmetric. Once again we use the ≤ operator, or the < operator if r is irreflexive. (These are sometimes called weak and strong partial orderings, respectively.) Now transitivity is written: a ≤ b and b ≤ c implies a ≤ c. The notation is helping us along, because arithmetic ≤ is certainly transitive. But unlike the arithmetic ≤ operator, elements need not be comparable. Here is an example. Set a < b and c, and b and c < d, which means a < d, yet b and c might not be comparable. Neither is less than the other. This is illustrated by a square with a in the lower left corner and d in the upper right. Arrows, or directed arcs, establish the relation. Two arrows run from a to b and c, and two more arrows run from b and c up to d. One element is less than another if there is an arrow-compliant path from one to the other.
An upper bound of a set within a larger poset is an element that is ≥ every member of the subset. The least upper bound (lub) is an upper bound that is ≤ every upper bound. Since two elements ≤ each other are the same, the lub is unique. Lower bounds are defined similarly, with the arrows reversed.
A minimal element in a set means no element is smaller. The smallest or minimum element is less than every other element in the set. Thus minimum implies minimal, and is unique, relative to that set. Maximal and maximum are defined similarly, with the arrows reversed.
A well founded partial order admits at least one minimal element within every set.
A relation is complete if it is a partial ordering, and every nonempty set bounded above has a least upper bound, or equivalently, every nonempty set bounded below has a greatest lower bound. Let's see why these conditions are the same. Given least upper bounds, and a nonempty set S bounded below, let W be the set of lower bounds of S, which is nonempty, and bounded above by every point of S (and perhaps other points as well). Thus every point of S is an upper bound for W. Let x be the least upper bound of W. Since x ≤ every point of S, x is a lower bound for S. Thus x belongs to W, and x is the greatest lower bound.
A lattice is a partial ordering with a lub and a glb for every pair of points. (don't confuse this with a regular lattice in n space.) Given x and y, the join is the lub and the meet is the glb. If x ≤ y means x is a subset of y, the union of x and y is the join, and the intersection is the meet. This is a "subset lattice". If the set is the integers, and ≤ means a factor of, then the lcm is the join and the gcd is the meet.
A complete lattice has a lub and a glb for every set of elements. Equivalently, a complete lattice is a complete relation with a bound on every set. The power set of a given set S forms a complete lattice, using "subset of" as our relation. All the subsets are bounded above by S, and bounded below by the empty set. Within an integral domain, "contained in" defines a complete lattice on ideals, bounded above by the entire ring and below by 0.
A linear ordering, or total ordering, is a partial ordering where all pairs of elements are comparable. They can all be placed in a line. The real numbers are linearly ordered, where ≤ has its usual meaning.
Every linear ordering is a lattice, since the join is the larger element and the meet is the smaller.
A chain is a subset of a poset that is linearly ordered. Usually the chain is ascending or descending.
A well ordering is a partial ordering such that every subset has a least, or minimal, element. Take a subset of two elements, and one is less than the other; hence a well ordering is automatically a linear ordering. The reciprocols 1/n are not well ordered, because there is no least element. The rationals and reals are not well ordered because they contain the reciprocols as a subset.
A well founded linear ordering is a well ordering. Two distinct minimal elements cannot exist, as all pairs are comparable, hence there is one minimum element.
To show the positive integers are well ordered, assume S is a subset with no least element, and let T be its complement. If S contains 1 it is well ordered, so T contains 1. By induction T contains all positive integers, and S is empty. Of course, the integers are not well ordered.