Some theorems useful in proofs about MAM

Revised:  December 28, 2002

For definitions of terms, refer to the formal definitions of MAM and MAM₂.

Theorem: "Random Voter Hierarchy is a Strict Ordering": 
(1) For all s Î L(R,A) and all alternatives a Î A, RVH(A,R,s) does not 
rank a over a. (That is, RVH is irreflexive.)  
(2) For all s Î L(R,A) and all distinct alternatives a,b Î A, if RVH(A,R,s) does 
not rank a over b then RVH(A,R,s) ranks b over a. (That is, RVH is complete.)  
(3) For all s Î L(R,A) and all alternatives a,b Î A, if RVH(A,R,s) ranks a over b  
then RVH(A,R,s) does not rank b over a. (That is, RVH is asymmetric.)
(4) For all s Î L(R,A) and all alternatives a,b,c Î A, if RVH(A,R,s) ranks a  
over b and b over c then RVH(A,R,s) ranks a over c. (That is, RVH is transitive.)

Proofs of (1,2,3):  These follow by inspection of the definition of RVH().

Proof of (4):  Pick any s Î L(R,A).  Abbreviate RVH = RVH(A,R,s).  
Pick any alternatives a,b,c Î A (not necessarily distinct).  Assume RVH ranks 
a over b and b over c.  We must show RVH ranks a over c.  By 1, RVH is 
irreflexive, so a ¹ b and b ¹ c.  By 3, RVH is asymmetric, so a ¹ c.  
Thus a,b,c are three distinct alternatives.  There are four cases to consider: 

Case 4.1:  Every voter voted indifference between a,b and indifference 
between b,c.  This implies R^(ab) is empty and R^(bc) is empty and 
R^(ac) is empty.  Since R^(ab) is empty and RVH ranks a over b, it follows 
by the definition of RVH() that s_A ranks a over b.  Since R^(bc) is empty 
and RVH ranks b over c, it follows by the definition of RVH() that 
s_A ranks b over c.  Thus s_A ranks a over c.  Since R^(ac) is empty 
and s_A ranks a over c, it follows that RVH ranks a over c in case 4.1.

Case 4.2:  At least one voter did not vote indifference between a,b 
and every voter voted indifference between b,c.  This implies R^(ab)  
is not empty and R^(bc) is empty.  By the definition of RVH(), 
both of the following must hold: 
        (4.2.1)  R^sab (the vote in R^(ab) ranked highest by s_R) ranks a 
                     over b and is indifferent between b,c.  
        (4.2.2)  Every vote in R ranked over R^sab by s_R is indifferent 
                     between a,b and indifferent between b,c.
By 4.2.1, R^sab ranks a over c.  Thus, by 4.2.2 and the definition 
of RVH(), RVH ranks a over c in case 4.2.  

Case 4.3:  Every voter voted indifference between a,b and at least one 
voter did not vote indifference between b,c.  By reasoning that parallels 
case 4.2, RVH ranks a over c in case 4.3.  

Case 4.4:  At least one voter did not vote indifference between a,b 
and at least one voter did not vote indifference between b,c.  
This implies R^(ab) is not empty and R^(bc) is not empty.  By the 
definition of RVH(), the following four statements must hold:  
        (4.4.1)  R^sab (the vote in R^(ab) ranked highest by s_R) ranks a over b.  
        (4.4.2)  Every vote in R ranked over R^sab by s_R is indifferent 
                     between a,b.  
        (4.4.3)  R^sbc (the vote in R^(bc) ranked highest by s_R) ranks b over c.  
        (4.4.4)  Every vote in R ranked over R^sbc by s_R is indifferent 
                     between b,c.  
There are two subcases to consider:  
        Case 4.4.5:  R^sab = R^sbc.  Since R^sab ranks a over b and b over c, 
                R^sab ranks a over c.  Since every vote in R ranked over R^sab 
                by s_R is indifferent between a,b,c, it follows that RVH ranks 
                a over c in case 4.4.5.  
        Case 4.4.6:  R^sab ¹ R^sbc.  Since s_R is a strict ordering of the ballots, 
                either s_R ranks R^sab over R^sbc or s_R ranks R^sbc over R^sab.  
                Thus there are two subcases to consider: 
                        Case 4.4.6.1:  s_R ranks R^sab over R^sbc.  By 4.4.4, R^sab is 
                                indifferent between b,c.  Thus R^sab ranks a over c.  
                                By 4.4.2 and 4.4.4, every vote in R ranked over R^sab 
                                by s_R is indifferent between a,b,c.  Thus it follows 
                                that RVH ranks a over c in case 4.4.6.1.  
                        Case 4.4.6.2:  s_R ranks R^sab over R^sbc.  By reasoning 
                                that parallels case 4.4.6.1, RVH ranks a over c 
                                in case 4.4.6.2. 
                Since RVH ranks a over c in both subcases, RVH ranks a 
                over c in case 4.4.6. 
Since RVH ranks a over c in both subcases, RVH ranks a over c 
in case 4.4. 

Since RVH ranks a over c in all four cases, this means it is transitive.  
Since RVH is irreflexive, complete, asymmetric and transitive, 
RVH is a strict ordering of the alternatives.                              QED

Theorem: "Precedence is a Strict Ordering":
(1) For all s Î L(R,A) and all p Î Pairs, p does not precede p given (R,s).  
(In other words, precedence is irreflexive.)
(2) For all s Î L(R,A) and all distinct ordered pairs p,p' Î Pairs,
if p does not precede p' given (R,s) then p' precedes p given (R,s). 
(In other words, precedence is complete.)  
(3) For all s Î L(R,A) and all ordered pairs p,p' Î Pairs,
if p precedes p' given (R,s) then p' does not precede p given (R,s). 
(In other words, precedence is asymmetric.)
(4) For all s Î L(R,A) and all ordered pairs p,p',p" Î Pairs,
if p precedes p' given (R,s) and p' precedes p" given (R,s),
then p precedes p" given (R,s). (In other words, precedence is transitive.)

Proof of (1):  Pick any s Î L(R,A) and any p Î Pairs.  Abbreviate by 
omitting R and s from the notation, and abbreviate  RVH = RVH(s).  
Let (a,b) denote p.  Clearly none of the following four conditions holds:  
     #R(a,b) > #R(a,b) 
     #R(b,a) > #R(b,a)  
     RVH ranks b over b.  
     RVH ranks a over a.  
It follows by the definition of  precedence that p does not precede p, 
meaning precedence is irreflexive.

Proof of (2):  Pick any s Î L(R,A) and any distinct p,p' Î Pairs.  
Abbreviate by omitting R and s from the notation, and abbreviate 
RVH = RVH(s).  Assume p does not precede p'.  Let (a,b) denote p 
and let (c,d) denote p'.  Since (a,b) does not precede (c,d), by the 
definition of precedence none of the following four conditions can hold:  
     #R(a,b) > #R(c,d) 
     #R(a,b) = #R(c,d) and #R(d,c) > #R(b,a)  
     #R(a,b) = #R(c,d) and #R(d,c) = #R(b,a) and RVH ranks d over b.  
     #R(a,b) = #R(c,d) and #R(d,c) = #R(b,a) and d=b and RVH ranks a over c.  
Thus, by theorem "Random Voter Hierarchy is a Strict Ordering", 
at least one of the following four conditions must hold:  
     #R(c,d) > #R(a,b) 
     #R(c,d) = #R(a,b) and #R(b,a) > #R(d,c)  
     #R(c,d) = #R(a,b) and #R(b,a) = #R(d,c) and RVH ranks b over d.  
     #R(c,d) = #R(a,b) and #R(b,a) = #R(d,c) and b=d and RVH ranks c over a.  
This implies p' precedes p given (R,s), establishing (2), 
meaning precedence is complete.

Proof of (3):  Pick any s Î L(R,A) and any p,p' Î Pairs.  Abbreviate 
by omitting R and s from the notation.  Abbreviate RVH = RVH(s).  
Assume p precedes p'.  By 1 (irreflexivity), p ¹ p'.  Let (a,b) denote p 
and let (c,d) denote p'.  Since (a,b) precedes (c,d), one of the following 
four conditions must hold:  
     #R(a,b) > #R(c,d) 
     #R(a,b) = #R(c,d) and #R(d,c) > #R(b,a)  
     #R(a,b) = #R(c,d) and #R(d,c) = #R(b,a) and RVH ranks d over b.  
     #R(a,b) = #R(c,d) and #R(d,c) = #R(b,a) and d=b and RVH ranks a over c.  
By inspection and by theorem "Random Voter Hierarchy is a Strict Ordering", 
none of the following four conditions can hold:  
     #R(c,d) > #R(a,b) 
     #R(c,d) = #R(a,b) and #R(b,a) > #R(d,c)  
     #R(c,d) = #R(a,b) and #R(b,a) = #R(d,c) and RVH ranks b over d.  
     #R(c,d) = #R(a,b) and #R(b,a) = #R(d,c) and b=d and RVH ranks c over a.  
This means p' cannot precede p given (R,s), establishing (3), 
meaning precedence is asymmetric.

Proof of (4):  Pick any s Î L(R,A) and any p,p',p" Î Pairs.  
Abbreviate by omitting R and s from the notation.  Abbreviate 
RVH = RVH(s).  Assume p precedes p' and p' precedes p".  
Let (a,b) denote p, let (c,d) denote p', and let (e,f) denote p".  
Since (a,b) precedes (c,d), (c,d) cannot be larger than (a,b), 
meaning one of the following two conditions must hold:  
     #R(a,b) > #R(c,d) 
     #R(a,b) = #R(c,d) and #R(d,c) ³ #R(b,a)  
Since (c,d) precedes (e,f), (e,f) cannot be larger than (c,d), 
meaning one of the following two conditions must hold:  
     #R(c,d) > #R(e,f) 
     #R(c,d) = #R(e,f) and #R(f,e) ³ #R(d,c)  
Thus there are four cases to consider:

Case 4.1:  #R(a,b) > #R(c,d)  and #R(c,d) > #R(e,f).  Clearly 
#R(a,b) > #R(e,f), implying p is larger than p", implying p precedes p".

Case 4.2:  #R(a,b) > #R(c,d) and #R(c,d) = #R(e,f) 
and #R(f,e) ³ #R(d,c).  Clearly #R(a,b) > #R(e,f), 
implying p is larger than p", implying p precedes p".

Case 4.3:  #R(a,b) = #R(c,d) and #R(d,c) ³ #R(b,a) 
and #R(c,d) > #R(e,f).  Clearly #R(a,b) > #R(e,f), 
implying p is larger than p", implying p precedes p".

Case 4.4:  #R(a,b) = #R(c,d) and #R(d,c) ³ #R(b,a) 
and #R(c,d) = #R(e,f) and #R(f,e) ³ #R(d,c).  Thus 
#R(a,b) = #R(c,d) = #R(e,f).  There are three subcases to consider:

Case 4.4.1:  #R(d,c) > #R(b,a).  Here #R(a,b) = #R(e,f) 
and #R(f,e) > #R(b,a), meaning p is larger than p", 
implying p precedes p".  

Case 4.4.2:  #R(f,e) > #R(d,c).  Here #R(a,b) = #R(e,f) 
and #R(f,e) > #R(b,a), meaning p is larger than p", 
implying p precedes p".  

Case 4.4.3:  #R(d,c) = #R(b,a) and #R(f,e) = #R(d,c).  
Here p and p' and p" are the same size, so precedence is 
determined by RVH.  There are two subcases to consider:

Case 4.4.3.1:  p, p', and p" all have the same second alternative. 
(In other words, b = d = f.)  Since p precedes p', RVH must rank 
a over c.  Similarly, since p' precedes p" RVH must rank c over e.  
Thus, by theorem "Random Voter Hierarchy is a Strict Ordering" 
RVH ranks a over e, from which it follows that p precedes p". 

Case 4.4.3.2:  p, p', and p" do not all have the same second 
alternative. (In other words, if b = d then b ¹ f, etc.)  Since p  
precedes p', RVH does not rank b over d.  Since p' precedes p", 
RVH does not rank d over f.  Thus, by theorem "Random Voter 
Hierarchy is a Strict Ordering",  RVH must rank f over b.  
It follows that p precedes p".

Since p precedes p" in both subcases, p precedes p" in case 4.4.3.  

Since p precedes p" in all three subcases, p precedes p" in case 4.4.

Since p precedes p" given (R,s) in all four cases, (4) is established, 
meaning precedence is transitive.  
Since precedence is irreflexive, complete, asymmetric and transitive, 
precedence is a strict ordering of Pairs(A).                   QED

Theorem: "Dominance is an Ordering": 
(1)  For all r Î L(A) and all s Î L(R,A), r does not dominate itself 
       given (R,s). (That is, dominance is irreflexive.)
(2)  For all r,r' Î L(A) and all s Î L(R,A), if r dominates r' given (R,s), 
       then r' does not dominate r given (R,s). (That is, dominance is asymmetric.) 
(3)  For all r,r',r" Î L(A) and all s Î L(R,A), if r dominates r' given (R,s)  
       and r' dominates r" given (R,s), then r dominates r" given (R,s). 
       (That is, dominance is transitive.) 
(4)  For all r,r',r" Î L(A) and all s Î L(R,A), if r dominates r' given (R,s) 
       and r" does not dominate r' given (R,s), then r dominates r" given (R,s).  
(5)  For all r,r',r" Î L(A) and all s Î L(R,A), if r' does not dominate r  
       given (R,s)  and r' dominates r" given (R,s), then r dominates r" given (R,s).  
(6)  For all r,r',r" Î L(A) and all s Î L(R,A), if r does not dominate r'  
       given (R,s)  and r' does not dominate r" given (R,s), then r does not 
       dominate r" given (R,s). (That is, dominance is negatively transitive.) 

Proof of (1):  Irreflexivity follows by inspection of the definition of dominance. 

Proof of (2):  Pick any s Î L(R,A).  Abbreviate by omitting "given (R,s)" 
from the notation.  Make the following abbreviations:

For all r Î L(A), Agreed(r) = Agreed(r,R).  
For all r,r' Î L(A), Distinct(r,r') = DistinctAgreed(r,r',A,R).  
For all r,r' Î L(A) such that Distinct(r,r') is not empty, 
          LDA(r,r') = LargestDistinctAgreed(r,r',A,R,s).

Assume r dominates r'.  By the definition of dominance, this 
implies LDA(r,r') Î Agreed(r) and LDA(r,r') Ï Agreed(r').  
This implies r' does not dominate r.  Thus dominance is asymmetric.  

Proof of (3):  Pick any s Î L(R,A).  Make the same abbreviations as in (2).  
Assume r dominates r' and r' dominates r".  This implies Distinct(r,r') is not 
empty and Distinct(r',r") is not empty.  By theorem "Precedence is a Strict 
Ordering" and the definition of LargestDistinctAgreed(), we can let (x,y) 
denote the unique ordered pair LDA(r,r') and can let (z,w) denote the unique 
ordered pair LDA(r',r").  Clearly (x,y) Î Agreed(r) and (z,w) Î Agreed(r') 
and (x,y) ¹ (z,w).  There are two cases to consider: 

Case 3.1:  (x,y) precedes (z,w).  Since LDA(r',r") = (z,w) this implies 
(x,y) Ï Distinct(r',r").  Thus, since r' ranks y over x, r" must also rank y  
over x.  Since r ranks x over y and r" ranks y over x, (x,y) Î Distinct(r,r").  
To show that r dominates r", suppose the contrary.  Then there must exist 
(a,b) Î Agreed(r")\Agreed(r) which precedes (x,y).  This implies r" ranks a  
over b and r ranks b over a.  Since r ranks b over a and LDA(r,r') = (x,y), 
r' must also rank b over a.  Thus (a,b) Î Agreed(r")\Agreed(r').  Since 
(a,b) precedes (x,y) and (x,y) precedes (z,w), by theorem "Precedence 
is a Strict Ordering" (a,b) must precede (z,w).  But this means LDA(r',r") 
is not (z,w), a contradiction which refutes the contrary assumption and 
establishes r dominates r" in case 3.1.

Case 3.2:  (z,w) precedes (x,y).  Since LDA(r,r') = (x,y), this implies 
(z,w) Ï Distinct(r,r').  Thus, since r' ranks z over w, r must also rank z  
over w.  Since r ranks z over w and r" ranks w over z, (z,w) Î Distinct(r,r").  
To show that r dominates r", suppose the contrary.  Then there must 
exist (a,b) Î Agreed(r")\Agreed(r) which precedes (z,w).  This implies 
r" ranks a  over b and r ranks b over a.  Since (a,b) precedes (z,w)  
and (z,w) precedes (x,y), by theorem "Precedence is a Strict Ordering" 
(a,b) must precede (x,y).  Since r ranks b over a and (a,b) precedes (x,y), 
r' must also rank b over a.  Thus (a,b) Î Agreed(r")\Agreed(r').  
But since (a,b) precedes (z,w), this implies LDA(r',r") is not (z,w), 
a contradiction which refutes the contrary assumption and 
establishes r dominates r" in case 3.2.  

Since r dominates r" in both cases, dominance is transitive.

Proof of (4):  Make the same abbreviations as in (2).  Assume r dominates r'  
and r" does not dominate r'.  By theorem "Precedence is a Strict Ordering"  
and the definition of LargestDistinctAgreed(), we can let (x,y) denote 
the unique ordered pair LDA(r,r').  Clearly (x,y) Î Agreed(r).  
There are two cases to consider:

Case 4.1:  Distinct(r',r") is empty.  This implies r' ranks a and b the same 
as r" does for all (a,b) Î Majorities(A,R).  This means r' and r" can only 
disagree on alternatives which tie pairwise.)  This implies LDA(r,r") = (x,y),
so r dominates r" in case 4.1.

Case 4.2:  Distinct(r',r") is not empty.  By theorem "Precedence is a Strict 
Ordering" and the definition of LargestDistinctAgreed(), we can let (z,w)  
denote the unique ordered pair LDA(r',r").  Since r" does not dominate r', 
this implies (z,w) Ï Agreed(r").  Therefore (z,w) Î Agreed(r'), which 
implies r' dominates r".  By 3 (transitivity), r dominates r" in case 4.2.

Since r dominates r" in both cases, (4) is established. 

Proof of (5):  Make the same abbreviations as in (2) above.  Assume r' does not 
dominate r and r' dominates r".  By theorem "Precedence is a Strict Ordering" 
and the definition of LargestDistinctAgreed(), we can let (z,w) denote 
the unique ordered pair LDA(r',r").  Clearly (z,w) Î Agreed(r').  
There are two cases to consider:

Case 5.1:  Distinct(r,r') is empty.  This implies r ranks a relative to b 
the same as r' does for all (a,b) Î Majorities(A,R). (In other words, 
r and r' can only disagree on alternatives which tie pairwise.)  This 
implies LDA(r,r") = (z,w) and thus r dominates r" in case 5.1.

Case 5.2:  Distinct(r,r') is not empty.  By theorem "Precedence is 
a Strict  Ordering" and the definition of LargestDistinctAgreed(), 
we can let (x,y) denote the unique ordered pair LDA(r,r').  Since r'  
does not dominate r, (x,y) Ï Agreed(r').  Therefore (x,y) Î Agreed(r), 
implying r dominates r'.   Since r dominates r' and r' dominates r", 
by 3 (transitivity) r dominates r" in case 5.2.

Since r dominates r" in both cases, (5) is established.  

Proof of (6):  Make the same abbreviations as in (2) above.  Assume r does 
not dominate r' and r' does not dominate r".  There are three cases to consider:

Case 6.1:  r' dominates r.  By 5 (swapping the labels of r and r"), 
r" dominates r.  By 2 (asymmetry), r does not dominate r". 

Case 6.2:  r" dominates r'.  By 4 (swapping the labels of r and r"), 
r" dominates r.  By 2 (asymmetry), r does not dominate r". 

Case 6.3:  r' does not dominate r and r" does not dominate r'.  Since r 
does not dominate r' and r' does not dominate r, Distinct(r,r') must be 
empty.  Since r' does not dominate r" and r" does not dominate r', 
Distinct(r',r") must be empty.  Since Distinct(r,r') is empty, r ranks a 
relative to b the same as r'   does for all (a,b) Î Majorities(A,R).  
Since Distinct(r',r") is empty, r' ranks a relative to b the same as r" does 
for all (a,b) Î Majorities(A,R).  Combining the last two statements, 
r ranks a relative to b the same as r" does for all (a,b) Î Majorities(A,R).  
Thus Distinct(r,r") is empty, which implies r does not dominate r". 

Since r does not dominate r" in all three cases, dominance is negatively 
transitive.  
Since dominance is irreflexive, asymmetric, transitive and negatively 
transitive, it is an ordering of L(A) (the set of all strict rankings of 
the alternatives).                  QED

Theorem: "Weak Dominance is a Strict Ordering": 
(1)  For all r Î L(A) and all s Î L(R,A), r does not weakly dominate 
       itself given (R,s). (In other words, weak dominance is irreflexive.)
(2)  For all distinct r,r' Î L(A) and all s Î L(R,A), if r does not weakly 
       dominate r' given (R,s),  then r' weakly dominates r given (R,s). 
       (In other words, weak dominance is complete.) 
(3)  For all r,r' Î L(A) and all s Î L(R,A), if r weakly dominates r'  
       given (R,s),  then r' does not weakly dominate r given (R,s). 
       (In other words, weak dominance is asymmetric.) 
(4)  For all r,r',r" Î L(A) and all s Î L(R,A), if r weakly dominates r'  
       given (R,s)   and r' weakly dominates r" given (R,s), 
       then r weakly dominates r" given (R,s). 
       (In other words, weak dominance is transitive.) 
(5)  For all r,r',r" Î L(A) and all s Î L(R,A), if r does not weakly 
       dominate r' given (R,s)  and r' does not weakly dominate r" given (R,s), 
       then r does not weakly dominate r" given (R,s). 
       (In other words, dominance is negatively transitive.) 

Proof of (1):  Pick any s Î L(R,A) and any r Î L(A).  By theorem "Dominance 
is an Ordering (1)", dominance is irreflexive, so r does not dominate itself 
given (R,s).  Thus condition 1 of the definition of weak dominance does not 
hold.  Since r = r, condition 2 of the definition of weak dominance does not hold.  
Since neither condition holds, r does not weakly dominate itself given (R,s).  
Since r and s were picked arbitrarily, this means weak dominance is irreflexive.  

Proof of (2):  Pick any s Î L(R,A).  Abbreviate by omitting "given (R,s)" 
from the notation.  Make the following abbreviations:

RVH = RVH(A,R,s). 
For all distinct r,r' Î L(A), TDA(r,r') = TopmostDifferentAlternative(r,r').

Pick any distinct r,r' Î L(A).  Assume r does not weakly dominate r'.  
By the definition of weak dominance, r does not dominate r' and 
[either r' dominates r or RVH does not rank TDA(r,r') over TDA(r',r)].  
Thus there are two cases to consider:  

Case 2.1:  r' dominates r.  It follows by condition 1 of the definition of 
weak dominance that r' weakly dominates r in case 2.1.  

Case 2.2:  r' does not dominate r.  This implies RVH does not rank TDA(r,r') 
over TDA(r',r).  By theorem "Random Voter Hierarchy is a Strict Ordering", 
RVH must rank TDA(r',r) over TDA(r,r').  Since r does not dominate r' and 
r ¹ r' and RVH ranks TDA(r',r) over TDA(r,r'), it follows by condition 2 
of the definition of weak dominance that r' weakly dominates r in case 2.2.

Since in both cases r' weakly dominates r, this means weak dominance is complete.  

Proof of (3):  Pick any s Î L(R,A).  Make the same abbreviations as in (2).  
Pick any r,r' Î L(A).  Assume r weakly dominates r'.  There are two cases:  

Case 3.1:  r dominates r'.  By theorem "Dominance is an Ordering", 
dominance is asymmetric, so r' does not dominate r.  By inspection of 
the definition of weak dominance, r' does not weakly dominate r in case 3.1.  

Case 3.2:  r does not dominate r'.  Since r weakly dominates r' but does not 
dominate r', it follows by condition 2 of the definition of weak dominance 
that r' does not dominate r and RVH ranks TDA(r,r') over TDA(r',r).  
This implies r' does not weakly dominate r in case 3.2.

Since in both cases r' does not weakly dominate r, weak dominance is asymmetric.  

Proof of (4):  Pick any s Î L(R,A).  Make the same abbreviations as in (2).  
Pick any r,r',r" Î L(A).  Assume r weakly dominates r' and r' weakly 
dominates r".  There are three cases to consider:  

Case 4.1:  r dominates r'.  Since r' weakly dominates r", by 3 (asymmetry) 
r" does not weakly dominate r', so by condition 1 of the definition of weak 
dominance r" does not dominate r'.  Since r dominates r' and r" does not 
dominate r', by theorem "Dominance is an Ordering (4)" r dominates r".  
By condition 1 of the definition of weak dominance, r weakly dominates r".

Case 4.2:  r' dominates r".  Since r weakly dominates r', by 3 (asymmetry) 
r' does not weakly dominate r, so by condition 1 of the definition of weak 
dominance r' does not dominate r.  Since r' dominates r" and r' does not 
dominate r, by theorem "Dominance is an Ordering (5)", r dominates r".  
By condition 1 of the definition of weak dominance, r weakly dominates r".  

Case 4.3:  r does not dominate r' and r' does not dominate r".  By 1, weak 
dominance is irreflexive, so r ¹ r' and r' ¹ r".  By 3, weak dominance is 
asymmetric, so r ¹ r".  Thus r, r' and r" are three distinct rankings of the 
alternatives.  Thus we can let x denote TDA(r,r') and let x' denote TDA(r',r) 
and let y' denote TDA(r',r") and let y" denote TDA(r",r') and let z denote 
TDA(r,r") and let z" denote TDA(r",r).  Clearly x ¹ x' and y' ¹ y" 
and z ¹ z" and the following two statements hold: 
        (4.3.1)  Over(r,x) = Over(r',x').  
        (4.3.2)  Over(r',y') = Over(r",y").  
By 3 (asymmetry), r' does not weakly dominate r.  Thus by condition 1 
of the definition of weak dominance r' does not dominate r.  Similarly, 
r" does not weakly dominate r' nor dominate r'.  Since r weakly 
dominates r' but does not dominate r', by condition 2 of the definition of 
weak dominance RVH ranks x over x'.  Similarly, RVH ranks y' over y".  
There are three subcases to consider:  

Case 4.3.3:  x' = y'.  Since RVH ranks x over x' and x' over y", 
by theorem "Random Voter Hierarchy is a Strict Ordering" 
RVH ranks x over y".  Thus x ¹ y".  By 4.3.1 and 4.3.2, 
Over(r,x) = Over(r",y").  Furthermore, it follows by the definitions 
of TopmostDifferentPlace() and TopmostDifferentAlternative() 
that z = x and z" = y".  

Case 4.3.4:  r' ranks x' over y'.  By 4.3.2, r" ranks x' over y" and, 
furthermore, it follows by the definitions of TopmostDifferentPlace() 
and TopmostDifferentAlternative() that z = x and z" = x'.  

Case 4.3.5:  x' ¹ y' and r' does not rank x' over y'.  Since r' is 
a strict ranking, r' ranks y' over x'.  By 4.3.1, r ranks y' over x and, 
furthermore, it follows by the definitions of TopmostDifferentPlace() 
and TopmostDifferentAlternative() that z = y' and z" = y".  

Since in all three subcases r" does not dominate r and r ¹ r" and 
RVH ranks z over z", by condition 2 of the definition of weak dominance 
r weakly dominates r" in case 4.3.  

Since r weakly dominates r" in all three cases, weak dominance is transitive.

Proof of (5):  Pick any s Î L(R,A).  Make the same abbreviations as in (2).  
Pick any r,r',r" Î L(A).  Assume r does not weakly dominate r' and 
r' does not weakly dominate r".  There are four cases to consider:

Case 5.1:  r = r'.  By inspection of the assumptions, 
r does not weakly dominate r". 

Case 5.2:  r' = r".  By inspection of the assumptions, 
r does not weakly dominate r". 

Case 5.3:  r = r".  By 1 (irreflexivity), 
r does not weakly dominate r".

Case 5.4:  r, r' and r" are three distinct rankings.  By 2 (completeness), 
r' weakly dominates r and r" weakly dominates r'.  By 4 (transitivity), 
r" weakly dominates r.  By 3 (asymmetry), r does not weakly dominate r". 

Since in all four cases r does not weakly dominate r", weak dominance is 
negatively transitive. (Note that in general, negative transitivity is always 
implied by the combination of irreflexivity, completeness, asymmetry 
and transitivity, by reasoning as in this proof.)
Since weak dominance is irreflexive, complete, asymmetric, transitive 
and negatively transitive, it is a strict ordering of L(A).           QED

Properties of Internal Consistency and Internal Inconsistency 

Theorem: "Consistency Means Acyclicity":
(1)  For all P Í Pairs, P is internally consistent if and only if 
       there do not exist (a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) Î P such that a_k = a₁.  
(2)  For all P Í Pairs, P is internally consistent if and only if 
       (a,a) is consistent with P for all a Î A.

Proof of (1):  First we prove the "only if":  Assume P Í Pairs and P is internally 
consistent.  We show there do not exist (a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) Î P such 
that a_k = a₁.  Suppose to the contrary that (a₁,a₂),(a₂,a₃),...,(a_k-1,a₁) Î P.  
Since (a₂,a₃),...,(a_k-1,a₁) Î P, (a₁,a₂) is inconsistent with P.  Since (a₁,a₂) Î P  
and (a₁,a₂) is inconsistent with P, P is internally inconsistent.  This contradicts 
the assumption that P is internally consistent, refuting the contrary assumption 
and establishing the "only if" clause.

Next we prove the "if":  Assume P Í Pairs and that there do not exist 
(a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) Î P such that a_k = a₁.  We want to show P is 
internally consistent.  Suppose to the contrary P is internally inconsistent.  
This means there exist (b₁,b₂),(b₂,b₃),...,(b_j-1,b_j) Î P such that (b_j,b₁) Î P.  
Let a_i = b_i for all i Î {1,2,...,j}.  Let k = j+1 and let a_k = b₁.  Since a_k = b₁ = a₁ 
and (a₁,a₂),(a₂,a₃),...,(a_k-2,a_k-1),(a_k-1,a_k) Î P, this contradicts the assumption 
that there do not exist (a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) Î P such that a_k = a₁.  
Thus the contrary assumption is refuted, establishing P is internally consistent.  
Since both the "if" and "only if" clauses have been established, (1) is established.

Proof of (2):  First we prove the "only if" clause:  Assume P is internally consistent.  
We must show (a,a) is consistent with P for all a Î A.  Suppose to the contrary 
that (x,x) is inconsistent with P for some x Î A.  This means there exist 
(a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) Î P such that a₁ = a_k = x.  Let j = k-1.  
Since (a₁,a₂),(a₂,a₃),...,(a_j-1,a_j) Î P, (a_j,a₁) is inconsistent with P.  
Since (a_j,a₁) = (a_k-1,a_k) and (a_k-1,a_k) Î P, P is internally inconsistent.  
This contradicts the given assumption that P is internally consistent, refuting 
the contrary assumption and establishing (a,a) is consistent with P for all a Î A.

Next we prove the "if" clause:  Assume (a,a) is consistent with P for all a Î A.  
We must show P is internally consistent.  Suppose to the contrary P is internally 
inconsistent.  There must exist (a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) Î P such that 
(a_k,a₁) Î P.  Clearly (a₁,a₂),(a₂,a₃),...,(a_k-1,a_k),(a_k,a₁) Î P.  Let j = k+1 
and let a_j denote a₁.  Since (a₁,a₂),(a₂,a₃),...,(a_j-2,a_j-1),(a_j-1,a_j) Î P  
and a_j = a₁, (a₁,a₁) is inconsistent with P.  Since a₁ Î A, this contradicts 
the given assumption that (a,a) is consistent with P for all a Î A.  This refutes 
the contrary assumption and establishes P is internally consistent.  Since both 
the "if" and "only if" clauses have been established, (2) is established.    QED

Theorem: "Reversed Inconsistent Pair is Consistent":
(1)  For all internally consistent P Í Pairs and all a,b Î A such 
that (a,b) is inconsistent with P, (b,a) is consistent with P.

Proof:  Pick any P Í Pairs and any a,b Î A.  Assume P is internally 
consistent and (a,b) is inconsistent with P.  Suppose to the contrary that 
(b,a) is inconsistent with P.  Since (a,b) is inconsistent with P, by the 
definition of inconsistent there must exist (x₁,x₂),(x₂,x₃),...,(x_k-1,x_k) Î P  
such that x₁ = b and x_k = a.  Similarly, since (b,a) is inconsistent with P 
there must exist (y₁,y₂),(y₂,y₃),...,(y_j-1,y_j) Î P such that y₁ = a and y_j = b.  
Clearly (x₂,x₃,),...,(x_k-1,a),(a,y₂),(y₂,y₃,),...,(y_j-1,x₁) Î P.  This implies 
(x₁,x₂) is inconsistent with P.  Since (x₁,x₂) Î P and (x₁,x₂) is inconsistent 
with P, P is not internally consistent.  But this is a contradiction, so the 
contrary assumption cannot hold, establishing the theorem.     QED

Theorem: "Minimal Inconsistent Set":
(1)  For all a,b Î A and all P Í Pairs such that (a,b) is inconsistent with P, 
       there exists at least one P₀ Í P such that P₀ is a minimal set with 
       which (a,b) is inconsistent.
(2)  For all distinct a,b Î A and all P Í Pairs such that P is a minimal set 
       with which (a,b) is inconsistent, a is not the first alternative in any ordered 
       pair in P and b is not the second alternative in any ordered pair in P.
(3)  For all a,b,c Î A and all P Í Pairs such that P is a minimal set with which 
       (a,b) is inconsistent, if c is not the second alternative in any ordered pair 
       in P È {(a,b)} then c is not an alternative in any ordered pair in P È {(a,b)}.

Proof of (1):  Suppose (a,b) is inconsistent with P.  Let P^ab denote the set of 
all subsets of P with which (a,b) is inconsistent.  Since P Î P^ab, P^ab is not empty.  
Thus there must exist at least one P₀ Î P^ab such that #P₀ £ #P' for all P' Î P^ab.  
This implies no strict subset of P₀ is in P^ab.  Therefore P₀ is a minimal set with 
which (a,b) is inconsistent.  Thus (1) has been established.

Proof of (2):  Assume a ¹ b and P is a minimal set with which (a,b) is inconsistent.  
This means there exist (a₁,a₂),(a₂,a₃,),...,(a_k-1,a_k) Î P such that a₁ = b and a_k = a.  
Since P is minimal, P must be {(a₁,a₂),(a₂,a₃,),...,(a_k-1,a_k)}.  First we show a is 
not the first alternative in any pair in P.  Suppose the contrary.  This means a_j = a  
for some j Î {1,...,k-1}.  Since a ¹ b, it follows that a₁ ¹ a, so 1 < j < k.  By the 
definition of consistent, (a,b) is inconsistent with {(a₁,a₂),(a₂,a₃,),...,(a_j-1,a_j)}, 
which is a strict subset of P.  But this contradicts the assumption that P is minimal.  
Thus the contrary assumption cannot hold, establishing a is not first in any pair in P.  

Next we prove b is not the second alternative in any pair in P.  Suppose 
the contrary.  This means a_j = b for some j Î {2,...,k}.  Since a ¹ b, 
it follows that a_k ¹ b, thus 1 < j < k.  Clearly (a,b) is inconsistent with 
{(a_j,a_j+1),(a_j+1,a_j+2,),...,(a_k-1,a_k)}, which is a strict subset of P.  
But this contradicts the assumption that P is minimal, so the contrary 
assumption cannot hold, establishing b is not second in any pair in P.  
Thus (2) has been established.

Proof of (3):  Suppose P is a minimal set with which (a,b) is inconsistent 
and c is not second in any pair in P È {(a,b)}.  This implies there exist 
(a₁,a₂),(a₂,a₃,),...,(a_k-1,a_k) Î P such that a₁ = b and a_k = a.  Since P is 
minimal, P must be {(a₁,a₂),(a₂,a₃,),...,(a_k-1,a_k)}.  Let P' denote P È {(a,b)}. 
(Possibly P' = P.)  By inspection of P', every alternative which is first in 
at least one pair in P' is also second in at least one pair in P'.  Thus, 
since c is not second in any pair in P', c cannot be first in any pair in P'.  
Since c is neither first nor second in any pair in P', c is not in any pair in P'.  
Thus (3) has been established.     QED

Theorem: "More Inconsistent":
        Definition: For all a Î A and all P Í Pairs, 
        let I(a,P) denote {x Î A\{a} such that (a,x) is inconsistent with P}.  
For all a,b Î A and all P Í Pairs, if (a,b) is inconsistent with P then #I(a,P) > #I(b,P).

Proof:  Assume a,b Î A and P Í Pairs and (a,b) is inconsistent with P.  
Abbreviate I_a = I(a,P) and I_b = I(b,P).  For all x Î I_b there must exist 
(a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) Î P such that a₁ = x and a_k = b (for some k 
which may vary with x).  Since (a,b) is inconsistent with P, there must exist 
(b₁,b₂),(b₂,b₃),...,(b_j-1,b_j) Î P such that b₁ = b and b_j = a.  Thus for all x Î I_b 
there must exist (x,a₂),(a₂,a₃),...,(a_k-1,b),(b,b₂),(b₂,b₃),...,(b_j-1,a) Î P.  
Therefore (a,x) is inconsistent with P for all x Î I_b.  This means x Î I_a 
for all x Î I_b.  Thus I_b Í I_a.  Since (a,b) is inconsistent with P, b Î I_a.  
By the definition of I(), b Ï I_b.  Since b Î I_a and b Ï I_b, I_b ¹ I_a.  
Since I_b Í I_a and I_b ¹ I_a, I_b must be a strict subset of I_a.  
Since A is finite, this implies #I_a > #I_b.     QED

Theorem: "Consistency Maintained":
(1)  For all internally consistent P Í Pairs(A) and all a,b Î A such 
       that (a,b) is consistent with P, P È (a,b) is internally consistent.
(2)  For all s Î L(R,A), Affirmed(A,R,s) is internally consistent.

Proof of (1):  Assume P Í Pairs(A) and P is internally consistent and 
(a,b) is consistent with P.  Let P' denote P È (a,b).  Suppose to the contrary 
that P' is internally inconsistent.  This implies (a,b) Ï P.  Since P' is internally 
inconsistent there must exist (a₁,a₂),(a₂,a₃,),...,(a_k-1,a_k) Î P' such that 
(a_k,a₁) Î P'.  There are three cases to consider:

Case 1.1:  There exists no j Î {1,2,...,k-1} such that (a_j,a_j+1) = (a,b).  
Thus, (a₁,a₂),(a₂,a₃,),...,(a_k-1,a_k) Î P.  There are two subcases to consider:  

Case 1.1.1: (a_k,a₁) = (a,b).  This implies (a,b) is inconsistent 
with P.  But this is a contradiction, so case 1.1.1 is impossible.  

Case 1.1.2: (a_k,a₁) ¹ (a,b).  Since (a_k,a₁) Î P', (a_k,a₁) Î P.  
This implies P is internally inconsistent.  But this is a contradiction, 
so case 1.1.2 is impossible.  

Since both subcases are impossible, case 1.1 is impossible.

Case 1.2:  There exists at least one j Î {1,2,...,k-1} such that 
(a_j,a_j+1) = (a,b).  Thus we can let i denote the smallest integer in 
{1,2,...,k-1} such that (a_i,a_i+1) = (a,b), and we can let j denote the 
largest integer in {1,2,...,k-1} such that (a_j,a_j+1) = (a,b).  (Possibly i = j.)  
Clearly 1 £ i £ j < k.  There are two subcases to consider:  

Case 1.2.1:  j = k-1.  Clearly (a_k,a₁),(a₁,a₂),(a₂,a₃),...,(a_i-1,a_i) Î P.  
Since a_k = b and a_i = a, this means (a,b) is inconsistent with P.  
But this is a contradiction, so case 1.2.1 is impossible.  

Case 1.2.2:  j ¹ k-1.  This implies j < k-1.  By inspection, we see that 
(a_j+1,a_j+2),(a_j+2,a_j+3,),...,(a_k-1,a_k),(a_k,a₁),(a₁,a₂),(a₂,a₃),...,(a_i-1,a_i) Î P.  
Since a_j+1 = b and a_i = a, this means (a,b) is inconsistent with P.  
But this is a contradiction, so case 1.2.2 is impossible. 

Since both subcases are impossible, case 1.2 is impossible.

Since both cases are impossible, the contrary assumption cannot hold, 
establishing (1).

Proof of (2):  Suppose to the contrary there exists s Î L(R,A) such that 
Affirmed(A,R,s) is internally inconsistent.  Make the following abbreviations: 

For all (a,b) Î Pairs(A), Precede(a,b) = Precede(a,b,A,R,s).
Aff = Affirmed(A,R,s).  

For all (a,b) Î Aff, let Aff_ab+ denote Aff Ç Precede(a,b).  Since the empty 
set f is internally consistent and Aff is assumed internally inconsistent, 
by induction and theorem "Precedence is a Strict Ordering" there must 
exist (x,y) Î Aff such that both of the following conditions hold: 

(2.1)  Aff_xy+ is internally consistent. 
(2.2)  Aff_xy+ È {(x,y)} is internally inconsistent.  

Since (x,y) Î Aff, by the definition of Affirmed() (x,y) must be consistent 
with Aff_xy+.  Since Aff_xy+ is internally consistent and (x,y) is consistent 
with Aff_xy+, by theorem "Consistency Maintained (1)" Aff_xy+ È (x,y) must 
be internally consistent.  But this contradicts 2.2, so the contrary assumption 
cannot hold.  Thus Affirmed(A,R,s) is internally consistent for all s Î L(R,A).  
QED

Theorem: "At Least One Top":
(1)  For all non-empty B Í A and all internally consistent P Í Pairs(B), 
       at least one alternative in B is not second in any ordered pair in P.
(2)  For all s Î L(R,A), Top(s) is not empty.  
(3)  For all internally consistent P Í Pairs(A), if Tied(P) is not empty 
       then TopTied(P) is not empty.  

Proof of (1):  Assume B is a non-empty subset of A and P is an internally 
consistent subset of Pairs(B).  For all b Î B, let I_b denote {b' Î B such 
that (b,b') is inconsistent with P}.  Since A is finite, I_b must be finite for all b Î B, 
so there must exist at least one x Î B such that #I_x £ #I_b for all b Î B.  We 
aim to show x is not second in any ordered pair in P.  Suppose to the contrary 
there exists y Î B such that (y,x) Î P.  This implies (x,y) is inconsistent with P.  
Since P is internally consistent, by theorem "More Inconsistent" #I_x > #I_y.  
But this contradicts the definition of x, so the contrary assumption cannot hold.  
Thus x Î B and x is not second in any pair in P.

Proof of (2):  Pick any s Î L(R,A).  By theorem "Consistency  Maintained 
(3)", Affirmed(s) is internally consistent.  By the definition of Affirmed(), 
Affirmed(s) Í Pairs(A).  Thus, by theorem "At Least One Top (1)"  
at least one alternative in A is not second in any pair in Affirmed(s).  
By the definition of Top(), this implies Top(s) is not empty. 

Proof of (3):  Pick any P Í Pairs(A).  Assume P is internally consistent 
and Tied(P) is not empty.  By (1), there exists at least one a Î Tied(P) 
such that, for all b Î Tied(P), (b,a) Ï P.  It follows by the definition 
of TopTied() that a Î TopTied(P), and hence that TopTied(P) is 
not empty.           QED  

Theorem:  " Random Voter Hierarchy satisfies strong Pareto":  
For all s Î L(R,A) and all a,b Î A, if no voters rank b over a and 
at least one voter ranks a over b, then RVH(A,R,s) ranks a over b.

Proof:  Assume a,b Î A, no voters rank b over a and at least one 
voter ranks a over b.  Thus R(b,a) is empty and R(a,b) is not 
empty.  Pick any s Î L(R,A).  Abbreviate RVH = RVH(A,R,s).  
We must show RVH ranks a over b.  Since R^(ab) is not empty, 
by the definition of RVH() RVH ranks a relative to b the same 
as R^sab does.  Since R(b,a) is empty, R^sab Î R(a,b).  
Thus RVH ranks a over b.     QED

Theorem:  "Majorities are independent of irrelevant alternatives":  
For all non-empty B Í A, Majorities(A,R) Ç Pairs(B) = Majorities(B,R|_B), 
where R|_B denotes the restriction of R to B. (That is, R|_B is the same as R  
except the alternatives not in B are deleted.)

Proof:  This follows by inspection of the definition of Majorities().   QED 

Theorem: "Random Voter Hierarchy is independent of irrelevant alternatives."  
Some definitions: 

For all non-empty B Í A and all r Î L(A), let r|_B denote the restriction 
of r to B. (That is, r|_B is the strict ordering of B which is the same as r  
except all alternatives not in B are deleted.)  

For all non-empty B Í A, let R|_B denote the restriction of R to B. (That is, 
R|_B is the same as the votes in R except all alternatives not in B are deleted.)  

For all non-empty B Í A and all s Î L(R,A), let s|_B denote the restriction of s  
to B. (That is, s|_B = (s_R|_B,s_A|_B) Î L(R|_B,B) where s_R|_B is the same as s_R 
except all alternatives not in B are deleted, and s_A|_B is the strict ordering of B  
which is the same as s_A except all alternatives not in B are deleted.)

For all non-empty B Í A and all s Î L(R,A), RVH(A,R,s)|_B = RVH(B,R|_B,s|_B).  

Proof:  Arbitrarily pick non-empty B Í A and s Î L(R,A) and distinct a,b Î B.  
Thus s|_B = (s_R|_B,s_A|_B) Î L(R|_B,B).  Abbreviate RVH = RVH(A,R,s) and 
RVH' = RVH(B,R|_B,s|_B).  There are two cases to consider:

Case 1.1:  R^(ab)  is not empty. (That is, at least one voter is not indifferent 
between a,b.)  By the definition of RVH(), RVH ranks a relative to b 
the same as R^sab does. (That is, the same as the ballot in R^(ab) ranked 
highest by s_R.)  Clearly R|_B(a,b) = R(a,b)|_B and R|_B(b,a) = R(b,a)|_B.  
Thus R|_B^(ab) is not empty, implying RVH' ranks a relative to b the same 
as R|_B^sR^|B^ab does.  Clearly R|_B^sR^|B^ab = R^sab|_B, which means RVH' 
ranks a relative to b the same as RVH does.

Case 1.2:  R^(ab)  is empty.  By the definition of RVH(), RVH ranks a  
relative to b the same as s_A does.  Clearly R|_B^(ab) is empty, implying 
RVH' ranks a relative to b the same as s_A|_B does, which is the same 
as s_A does, which is the same as RVH does. 

Since in both cases RVH' ranks a relative to b the same as RVH does, 
and since B, s, a and b were picked arbitrarily, the theorem has been 
established.     QED

Theorem:  "Precedence is independent of irrelevant alternatives": 
For all non-empty B Í A, let R|_B denote the restriction of R to B. 
(That is, R|_B is the same as R except all alternatives not in B are deleted.)  
For all s Î L(R,A) and all non-empty B Í A, let s|_B denote the restriction 
of s to B. (That is, s|_B is the same as s except all alternatives not in B are 
deleted.)  For all s Î L(R,A), all non-empty B Í A and all a,b Î B, 
Precede(a,b,A,R,s) Ç Pairs(B) = Precede(a,b,B,R|_B,s|_B). 

Proof:  Clearly the following statement must hold: 

(1)  For all a,b Î B, R(a,b) = R|_B(a,b).  

By theorem "Random Voter Hierarchy is independent of 
irrelevant alternatives", the following condition must hold: 

(2)  For all a,b Î B, RVH(A,R,s) ranks a over b if and only if 
       RVH(B,R|_B,s|_B) ranks a over b. 

The theorem will follow immediately if we establish the following two propositions:  

(3)  For all a,b,c,d Î B and all s Î L(R,A), if (c,d) Î Precede(a,b,A,R,s) 
       then (c,d) Î Precede(a,b,B,R|_B,s|_B). 
(4)  For all a,b,c,d Î B and all s Î L(R,A), if (c,d) Î Precede(a,b,B,R|_B,s|_B) 
       then (c,d) Î Precede(a,b,A,R,s).

First we establish 3:  Assume a,b,c,d Î B and s Î L(R,A) and 
(c,d) Î Precede(a,b,A,R,s).  We must show (c,d) Î Precede(a,b,B,R|_B,s|_B).   
By the definition of precedence, one of the following four conditions must hold:

(3.1)  #R(c,d) > #R(a,b). 
(3.2)  #R(c,d) = #R(a,b) and #R(d,c) < #R(b,a). 
(3.3)  #R(c,d) = #R(a,b) and #R(d,c) = #R(b,a) 
          and RVH(A,R,s) ranks b over d. 
(3.4)  #R(c,d) = #R(a,b) and #R(d,c) = #R(b,a) 
          and b = d and RVH(A,R,s) ranks c over a.

Therefore, by 1 and 2 one of the following four conditions must hold:

(3.5)  #R|_B(c,d) > #R|_B(a,b). 
(3.6)  #R|_B(c,d) = #R|_B(a,b) and #R|_B(d,c) < #R|_B(b,a). 
(3.7)  #R|_B(c,d) = #R|_B(a,b) and #R|_B(d,c) = #R|_B(b,a) 
          and RVH(B,R|_B,s|_B) ranks b over d. 
(3.8)  #R|_B(c,d) = #R|_B(a,b) and #R|_B(d,c) = #R|_B(b,a) 
          and b = d and RVH(B,R|_B,s|_B) ranks c over a.

Thus, by the definition of precedence (c,d) Î Precede(a,b,B,R|_B,s|_B), 
establishing 3.  Next we establish 4:  Assume a,b,c,d Î B and s Î L(R,A) 
and (c,d) Î Precede(a,b,B,R|_B,s|_B).  We need to show that 
(c,d) Î Precede(c,d,A,R,s).  Since (c,d) Î Precede(a,b,B,R|_B,s|_B), 
by the definition of precedence one of the following four conditions must hold:

(4.1)  #R|_B(c,d) > #R|_B(a,b). 
(4.2)  #R|_B(c,d) = #R|_B(a,b) and #R|_B(d,c) < #R|_B(b,a). 
(4.3)  #R|_B(c,d) = #R|_B(a,b) and #R|_B(d,c) = #R|_B(b,a) 
          and RVH(B,R|_B,s|_B) ranks b over d. 
(4.4)  #R|_B(c,d) = #R|_B(a,b) and #R|_B(d,c) = #R|_B(b,a) 
          and b = d and RVH(B,R|_B,s|_B) ranks c over a.

Therefore, by 1 and 2 one of the following four conditions must hold:

(4.5)  #R(c,d) > #R(a,b). 
(4.6)  #R(c,d) = #R(a,b) and #R(d,c) < #R(b,a). 
(4.7)  #R(c,d) = #R(a,b) and #R(d,c) = #R(b,a) 
          and RVH(A,R,s) ranks b over d. 
(4.8)  #R(c,d) = #R(a,b) and #R(d,c) = #R(b,a) 
          and b = d and RVH(A,R,s) ranks c over a.

Thus, by the definition of precedence (c,d) Î Precede(a,b,A,R,s), 
establishing 4.  
Having established both 3 and 4, the theorem is established.        QED 

Theorem: "MAM is resolute":  
For all s Î L(R,A), MAM(A,R,s) is a single alternative in A.   

Proof:  Pick any s Î L(R,A).  By theorem "At Least One Top (2)", 
Top(A,R,s) is not empty.  Thus, by theorem "Random Voter Hierarchy 
is a Strict Ordering" there must exist a unique alternative x Î Top(A,R,s) 
such that, for all y Î Top(A,R,s)\{x}, RVH(A,R,s) ranks x over y.  
By inspection of the definition of MAM(), MAM(A,R,s) = x, 
a single alternative.        QED   

Theorem: "Properties of R_social":  (See the section "The MAM social 
ordering" in the document "MAM Formal Definition" for definitions.)
(1)  For all s Î L(R,A), R_social(A,R,s) is a strict ordering of A. (That is, R_social() 
       is irreflexive, complete, asymmetric, transitive and negatively transitive.)  
(2)  For all s Î L(R,A), R_social(A,R,s) ranks MAM(A,R,s) over all other alternatives.  
(3)  For all s Î L(R,A) and all (a,b) Î Affirmed(A,R,s), 
       R_social(A,R,s) ranks a over b.  
(4)  For all s Î L(R,A) and all (a,b) Î Majorities(A,R)\Affirmed(A,R,s), 
       R_social(A,R,s) ranks b over a. 
       (Note that 3 and 4 imply Affirmed(A,R,s) = Agreed(R_social(A,R,s)).)
(5)  For all s Î L(R,A), R_social(A,R,s) Î UndominatedRankings(A,R,s).  
(6)  For all s Î L(R,A) and all a,b Î A, if (a,b) is inconsistent 
       with Affirmed(A,R,s) then R_social(A,R,s) ranks b over a.  
(7)  For all s Î L(R,A) and all non-empty B Ì A such that 
       R_social(A,R,s) ranks every alternative in A\B over every 
       alternative in B, both of the following conditions hold: