**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*^{2}
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*^{2}.

For all sets *S*, all *R* ⊆ *S*^{2}
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*_{1}*,x*_{2}*,...,x _{k}*
∈

such that

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*_{1}*,x*_{2}*,...,x _{k}*
∈

Since

[not

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.