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 S² 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 Í S².  
For all sets S, all R Í S² 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 x₁,x₂,...,x_k Î S 
such that k > 1 and x_jRx_j+1 for all j Î {1,2,...,k-1} and x_kRx₁. 

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 x₁,x₂,...,x_k Î S.  Assume k > 1 and 
x_jRx_j+1 for all j Î {1,2,...,k-1}.  We will show [not x_kRx₁].  Since k > 1 and 
x_jRx_j+1 for all j Î {1,2,...,k-1}, by repeated applications of transitivity x₁Rx_k.  
Since k > 1, by distinctness x₁ ¹ x_k.  Since x₁Rx_k and x₁ ¹ x_k, by asymmetry  
[not x_kRx₁].  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  
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 y.  We 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.