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
       xS means x is an element in S
       xS means x is not an element in S.
       #S denotes the number of elements in S.                          ("cardinality") 
For all sets S and S'
       SS' denotes the elements in S or in S' or in both.          ("union")
       SS' denotes the elements in S that are also in S'.           ("intersection") 
       S\S' denotes the elements in S that are not in S'
       SS' means S is a subset of S'.  That is, all elements in S are also in S'.
       SS' 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
       SS' 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 xS and yS.)  
Elsewhere we also call this Pairs(S). 

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

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

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

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

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

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

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,zS.  

Call a binary relation R on a set S cyclic if and only if there 
exists a finite sequence of distinct elements x1,x2,...,xkS 
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,...,xkS.  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 x1xk.  Since x1Rxk and x1xk, 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,yS, say that R orders x  
ahead of
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,yS.)  

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,zS.  
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.  xy and yz and xz.  Since R is complete and xy 
                and [not xRy], yRx.  Since R is complete and yz and [not yRz],
                zRy.  Since R is transitive and zRy and yRx, zRx.  Since R is
                asymmetric and xz 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.