Definitions of Set Operators and Binary Relations

(Note that some symbols may not display properly when viewed with a browser which does
not support HTML 4.0 or if the browser is not configured to display the "Symbol" font.)

A set is an unordered collection of distinct "elements" such as {x,y,z,...}.

For all sets S
x Î S means x is an element in S
x Ï S means x is not an element in S.
#S denotes the number of elements in S.                          ("cardinality")
For all sets S and S'
S È S' denotes the elements in S or in S' or in both.          ("union")
S Ç S' denotes the elements in S that are also in S'.           ("intersection")
S\S' denotes the elements in S that are not in S'
S Í S' means S is a subset of S'.  That is, all elements in S are also in S'.
S Ì S' means S is a strict subset of S'.  That is, S is a subset of S' and
at least one element in S' is not in S
S Ê S' means S is a superset of S'.  That is, all elements in S' are also in S

For all sets S, let S2 denote S ´ S, the set of all possible ordered pairs
of elements of S. (That is, all (x,y) such that x Î S and y Î S.)
Elsewhere we also call this Pairs(S).

For all sets S, call R a binary relation on S if and only if R Í S2.
For all sets S, all R Í S2 and all x,y Î S, abbreviate xRy to mean (x,y) Î R.

Call a binary relation R on a set S reflexive if and only if xRx for all x Î S

Call a binary relation R on a set S irreflexive if and only if
[not xRx] for all x Î S.

Call a binary relation R on a set S complete if and only if
[xRy or yRx] for all distinct x,y Î S.

Call a binary relation R on a set S asymmetric if and only if
[xRy implies [not yRx]] for all distinct x,y Î S.

Call a binary relation R on a set S transitive if and only if
[[xRy and yRz] implies xRz] for all x,y,z Î S.

Call a binary relation R on a set S negatively transitive if and only if
[[[not xRy] and [not yRz]] implies [not xRz]] for all x,y,z Î S.

Call a binary relation R on a set S cyclic if and only if there
exists a finite sequence of distinct elements x1,x2,...,xk Î S
such that k > 1 and xjRxj+1 for all j Î {1,2,...,k-1} and xkRx1

Call a binary relation R on a set S acyclic if and only if it is not cyclic

Note that any transitive asymmetric binary relation is acyclic.  Proof:  Pick
any finite sequence of distinct elements x1,x2,...,xk Î S.  Assume k > 1 and
xjRxj+1 for all j Î {1,2,...,k-1}.  We will show [not xkRx1].  Since k > 1 and
xjRxj+1 for all j Î {1,2,...,k-1}, by repeated applications of transitivity x1Rxk.
Since k > 1, by distinctness x1 ¹ xk.  Since x1Rxk and x1 ¹ xk, by asymmetry
[not xkRx1].  Thus R cannot be cyclic, so it is acyclic.

Call a binary relation R on a set S an ordering of S of type ">" (in other
words, the irreflexive type) if and only if R is irreflexive, asymmetric
transitive and negatively transitive

Call a binary relation R on a set S an ordering of S of type "³" (in other
words, the reflexive type) if and only if R is reflexive, complete
transitive and negatively transitive.

For all binary relations R that order S and all x,y Î S, say that R orders x
y if and only if [xRy and [not yRx]], and say that R orders x
equal to
y if and only if either [xRy and yRx] or [[not xRy] and [not yRx]].

An ordering is also called a ranking.  Saying x is ordered ahead of y is synonymous
to saying x is ranked over y, and to saying x precedes yWe use the term "ranking"
only when the relation is on a set of alternatives being considered in an election or poll.

Call a binary relation R on a set S a strict ordering (i.e., linear ordering) of S
if and only if R is a complete asymmetric ordering of S. (Note that if R is
a strict ordering, R either orders x ahead of y or y ahead of x, but not both,
for all distinct x,y Î S.)

For our purposes, we will deal primarily with irreflexive relations such as is over
precedes, is preferred to, and is larger than (in other words, ">" type relations),
and this type should be assumed of an ordering when neither type is specified.

For all sets S, let O(S) denote the set of all possible orderings of S.
For all sets S, let L(S) denote the set of all possible irreflexive strict orderings
of S. (The "L" symbol connotes "linear" and is often used in the literature.)

Note that all irreflexive complete asymmetric transitive binary relations are
also negatively transitive.  Proof:  Assume R is an irreflexive complete
asymmetric transitive binary relation on a set S.  Pick any x,y,z Î S.
Assume [not xRy] and [not yRz].  We must show [not xRz].
There are four cases to consider:
Case 1:  x = y.  Since [not yRz], [not xRz].
Case 2:  y = z.  Since [not xRy], [not xRz].
Case 3:  x = z.  Since R is irreflexive, [not xRz].
Case 4.  x ¹ y and y ¹ z and x ¹ z.  Since R is complete and x ¹ y
and [not xRy], yRx.  Since R is complete and y ¹ z and [not yRz],
zRy.  Since R is transitive and zRy and yRx, zRx.  Since R is
asymmetric and x ¹ z and zRx, [not xRz].
Since [not xRz] in all four cases, R is negatively transitive.  Thus all irreflexive
complete asymmetric transitive binary relations are negatively transitive
It follows that all irreflexive complete asymmetric transitive binary relations
are strict orderings. 