Some theorems useful in proofs about MAM

Revised:  December 28, 2002

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

Theorem: "Random Voter Hierarchy is a Strict Ordering": 
(1) For all σ ∈ L(R,A) and all alternatives aA, RVH(A,R,σ) does not 
rank a over a(That is, RVH is irreflexive.)  
(2) For all σ ∈ L(R,A) and all distinct alternatives a,bA, if RVH(A,R,σ) does 
not rank a over b then RVH(A,R,σ) ranks b over a(That is, RVH is complete.)  
(3) For all σ ∈ L(R,A) and all alternatives a,bA, if RVH(A,R,σ) ranks a over b  
then RVH(A,R,σ) does not rank b over a(That is, RVH is asymmetric.)
(4) For all σ ∈ L(R,A) and all alternatives a,b,cA, if RVH(A,R,σ) ranks a  
over b and b over c then RVH(A,R,σ) 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 σ ∈ L(R,A).  Abbreviate RVH = RVH(A,R,σ).  
Pick any alternatives a,b,cA (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 ab and bc.  By 3, RVH is asymmetric, so ac.  
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 σA ranks a over b.  Since R(bc) is empty 
and RVH ranks b over c, it follows by the definition of RVH() that 
σA ranks b over c.  Thus σA ranks a over c.  Since R(ac) is empty 
and σ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σab (the vote in R(ab) ranked highest by σR) ranks a 
                     over b and is indifferent between b,c.  
        (4.2.2)  Every vote in R ranked over Rσab by σR is indifferent 
                     between a,b and indifferent between b,c.
By 4.2.1, Rσab 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σab (the vote in R(ab) ranked highest by σR) ranks a over b.  
        (4.4.2)  Every vote in R ranked over Rσab by σR is indifferent 
                     between a,b.  
        (4.4.3)  Rσbc (the vote in R(bc) ranked highest by σR) ranks b over c.  
        (4.4.4)  Every vote in R ranked over Rσbc by σR is indifferent 
                     between b,c.  
There are two subcases to consider:  
        Case 4.4.5:  Rσab = Rσbc.  Since Rσab ranks a over b and b over c
                Rσab ranks a over c.  Since every vote in R ranked over Rσab 
                by σ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σabRσbc.  Since σR is a strict ordering of the ballots, 
                either σR ranks Rσab over Rσbc or σR ranks Rσbc over Rσab.  
                Thus there are two subcases to consider: 
                        Case 4.4.6.1:  σR ranks Rσab over Rσbc.  By 4.4.4, Rσab is 
                                indifferent between b,c.  Thus Rσab ranks a over c.  
                                By 4.4.2 and 4.4.4, every vote in R ranked over Rσab 
                                by σ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:  σR ranks Rσab over Rσbc.  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 σ ∈ L(R,A) and all pPairs, p does not precede p given (R,σ).  
(In other words, precedence is irreflexive.)
(2) For all σ ∈ L(R,A) and all distinct ordered pairs p,p'Pairs,
if p does not precede p' given (R,σ) then p' precedes p given (R,σ)
(In other words, precedence is complete.)  
(3) For all σ ∈ L(R,A) and all ordered pairs p,p'Pairs,
if p precedes p' given (R,σ) then p' does not precede p given (R,σ)
(In other words, precedence is asymmetric.)
(4) For all σ ∈ L(R,A) and all ordered pairs p,p',p" ∈ Pairs,
if p precedes p' given (R,σ) and p' precedes p" given (R,σ),
then p precedes p" given (R,σ). (In other words, precedence is transitive.)

Proof of (1):  Pick any σ ∈ L(R,A) and any pPairs.  Abbreviate by 
omitting R and σ from the notation, and abbreviate  RVH = RVH(σ).  
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 σ ∈ L(R,A) and any distinct p,p'Pairs.  
Abbreviate by omitting R and σ from the notation, and abbreviate 
RVH = RVH(σ).  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,σ), establishing (2), 
meaning precedence is complete.

Proof of (3):  Pick any σ ∈ L(R,A) and any p,p'Pairs.  Abbreviate 
by omitting R and σ from the notation.  Abbreviate RVH = RVH(σ).  
Assume p precedes p'.  By 1 (irreflexivity), pp'.  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,σ), establishing (3), 
meaning precedence is asymmetric.

Proof of (4):  Pick any σ ∈ L(R,A) and any p,p',p" ∈ Pairs.  
Abbreviate by omitting R and σ from the notation.  Abbreviate 
RVH = RVH(σ).  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 bf, 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,σ) 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 rL(A) and all σ ∈ L(R,A), r does not dominate itself 
       given (R,σ)(That is, dominance is irreflexive.)
(2)  For all r,r'L(A) and all σ ∈ L(R,A), if r dominates r' given (R,σ)
       then r' does not dominate r given (R,σ)(That is, dominance is asymmetric.) 
(3)  For all r,r',r" ∈ L(A) and all σ ∈ L(R,A), if r dominates r' given (R,σ)  
       and r' dominates r" given (R,σ), then r dominates r" given (R,σ)
       (That is, dominance is transitive.) 
(4)  For all r,r',r" ∈ L(A) and all σ ∈ L(R,A), if r dominates r' given (R,σ) 
       and r" does not dominate r' given (R,σ), then r dominates r" given (R,σ).  
(5)  For all r,r',r" ∈ L(A) and all σ ∈ L(R,A), if r' does not dominate r  
       given (R,σ)  and r' dominates r" given (R,σ), then r dominates r" given (R,σ).  
(6)  For all r,r',r" ∈ L(A) and all σ ∈ L(R,A), if r does not dominate r'  
       given (R,σ)  and r' does not dominate r" given (R,σ), then r does not 
       dominate r" given (R,σ)(That is, dominance is negatively transitive.) 

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

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

For all rL(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,σ).

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 σ ∈ 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 xr" 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 wr 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 rL(A) and all σ ∈ L(R,A), r does not weakly dominate 
       itself given (R,σ)(In other words, weak dominance is irreflexive.)
(2)  For all distinct r,r'L(A) and all σ ∈ L(R,A), if r does not weakly 
       dominate r' given (R,σ),  then r' weakly dominates r given (R,σ)
       (In other words, weak dominance is complete.) 
(3)  For all r,r'L(A) and all σ ∈ L(R,A), if r weakly dominates r'  
       given (R,σ),  then r' does not weakly dominate r given (R,σ)
       (In other words, weak dominance is asymmetric.) 
(4)  For all r,r',r" ∈ L(A) and all σ ∈ L(R,A), if r weakly dominates r'  
       given (R,σ)   and r' weakly dominates r" given (R,σ)
       then r weakly dominates r" given (R,σ)
       (In other words, weak dominance is transitive.) 
(5)  For all r,r',r" ∈ L(A) and all σ ∈ L(R,A), if r does not weakly 
       dominate r' given (R,σ)  and r' does not weakly dominate r" given (R,σ)
       then r does not weakly dominate r" given (R,σ)
       (In other words, dominance is negatively transitive.) 

Proof of (1):  Pick any σ ∈ L(R,A) and any rL(A).  By theorem "Dominance 
is an Ordering (1)"
, dominance is irreflexive, so r does not dominate itself 
given (R,σ).  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,σ).  
Since r and σ were picked arbitrarily, this means weak dominance is irreflexive.  

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

RVH = RVH(A,R,σ). 
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 
rr' 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 σ ∈ 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 σ ∈ 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 rr' and r'r".  By 3, weak dominance is 
asymmetric, so rr".  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 xx' and y'y
and zz" 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 xy".  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 rr" 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 σ ∈ 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 PPairs, P is internally consistent if and only if 
       there do not exist (a1,a2),(a2,a3),...,(ak-1,ak)P such that ak = a1.  
(2)  For all PPairs, P is internally consistent if and only if 
       (a,a) is consistent with P for all aA.

Proof of (1):  First we prove the "only if":  Assume PPairs and P is internally 
consistent.  We show there do not exist (a1,a2),(a2,a3),...,(ak-1,ak)P such 
that ak = a1.  Suppose to the contrary that (a1,a2),(a2,a3),...,(ak-1,a1)P.  
Since (a2,a3),...,(ak-1,a1)P, (a1,a2) is inconsistent with P.  Since (a1,a2)P  
and (a1,a2) 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 PPairs and that there do not exist 
(a1,a2),(a2,a3),...,(ak-1,ak)P such that ak = a1.  We want to show P is 
internally consistent.  Suppose to the contrary P is internally inconsistent.  
This means there exist (b1,b2),(b2,b3),...,(bj-1,bj)P such that (bj,b1)P.  
Let ai = bi for all i ∈ {1,2,...,j}.  Let k = j+1 and let ak = b1.  Since ak = b1 = a1 
and (a1,a2),(a2,a3),...,(ak-2,ak-1),(ak-1,ak)P, this contradicts the assumption 
that there do not exist (a1,a2),(a2,a3),...,(ak-1,ak)P such that ak = a1.  
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 aA.  Suppose to the contrary 
that (x,x) is inconsistent with P for some xA.  This means there exist 
(a1,a2),(a2,a3),...,(ak-1,ak)P such that a1 = ak = x.  Let j = k-1.  
Since (a1,a2),(a2,a3),...,(aj-1,aj)P, (aj,a1) is inconsistent with P.  
Since (aj,a1) = (ak-1,ak) and (ak-1,ak)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 aA.

Next we prove the "if" clause:  Assume (a,a) is consistent with P for all aA.  
We must show P is internally consistent.  Suppose to the contrary P is internally 
inconsistent.  There must exist (a1,a2),(a2,a3),...,(ak-1,ak)P such that 
(ak,a
1)P.  Clearly (a1,a2),(a2,a3),...,(ak-1,ak),(ak,a1)P.  Let j = k+1 
and let aj denote a1.  Since (a1,a2),(a2,a3),...,(aj-2,aj-1),(aj-1,aj)P  
and aj = a1, (a1,a1) is inconsistent with P.  Since a1A, this contradicts 
the given assumption that (a,a) is consistent with P for all aA.  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 PPairs and all a,bA such 
that (a,b) is inconsistent with P, (b,a) is consistent with P.

Proof:  Pick any PPairs and any a,bA.  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 (x1,x2),(x2,x3),...,(xk-1,xk)P  
such that x1 = and xk = a.  Similarly, since (b,a) is inconsistent with P 
there must exist (y1,y2),(y2,y3),...,(yj-1,yj)P such that y1 = and yj = b.  
Clearly (x2,x3,),...,(xk-1,a),(a,y2),(y2,y3,),...,(yj-1,x1)P.  This implies 
(x1,x2) is inconsistent with P.  Since (x1,x2)P and (x1,x2) 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,bA and all PPairs such that (a,b) is inconsistent with P
       there exists at least one P0P such that P0 is a minimal set with 
       which (a,b) is inconsistent.
(2)  For all distinct a,bA and all PPairs 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,cA and all PPairs 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 Pab denote the set of 
all subsets of P with which (a,b) is inconsistent.  Since PPabPab is not empty.  
Thus there must exist at least one P0Pab such that #P0 ≤ #P' for all P'Pab.  
This implies no strict subset of P0 is in Pab.  Therefore P0 is a minimal set with 
which (a,b) is inconsistent.  Thus (1) has been established.

Proof of (2):  Assume ab and P is a minimal set with which (a,b) is inconsistent.  
This means there exist (a1,a2),(a2,a3,),...,(ak-1,ak)P such that a1 = b and ak = a.  
Since P is minimal, P must be {(a1,a2),(a2,a3,),...,(ak-1,ak)}.  First we show a is 
not the first alternative in any pair in P.  Suppose the contrary.  This means aj = a  
for some j ∈ {1,...,k-1}.  Since ab, it follows that a1a, so 1 < j < k.  By the 
definition of consistent
(a,b) is inconsistent with {(a1,a2),(a2,a3,),...,(aj-1,aj)}, 
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 aj = b for some j ∈ {2,...,k}.  Since ab
it follows that akb, thus 1 < j < k.  Clearly (a,b) is inconsistent with 
{(aj,aj+1),(aj+1,aj+2,),...,(ak-1,ak)}, 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 
(a1,a2),(a2,a3,),...,(ak-1,ak)such that a1 = and ak = a.  Since P is 
minimal, P must be {(a1,a2),(a2,a3,),...,(ak-1,ak)}.  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 aA and all PPairs
        let I(a,P) denote {xA\{a} such that (a,x) is inconsistent with P}.  
        For all a,bA and all PPairs, if (a,b) is inconsistent with P then #I(a,P) > #I(b,P).

Proof:  Assume a,bA and PPairs and (a,b) is inconsistent with P.  
Abbreviate Ia = I(a,P) and Ib = I(b,P).  For all x ∈ Ib there must exist 
(a1,a2),(a2,a3),...,(ak-1,ak)P such that a1 = x and ak = b (for some k 
which may vary with x).  Since (a,b) is inconsistent with P, there must exist 
(b1,b2),(b2,b3),...,(bj-1,bj)P such that b1 = b and bj = a.  Thus for all x ∈ Ib 
there must exist (x,a2),(a2,a3),...,(ak-1,b),(b,b2),(b2,b3),...,(bj-1,a)P.  
Therefore (a,x) is inconsistent with P for all x ∈ Ib.  This means x ∈ Ia 
for all x ∈ Ib.  Thus Ib ⊆ Ia.  Since (a,b) is inconsistent with P, b ∈ Ia.  
By the definition of I(), b ∉ Ib.  Since b ∈ Ia and b ∉ Ib, Ib ≠ Ia.  
Since Ib ⊆ Ia and Ib ≠ Ia, Ib must be a strict subset of Ia.  
Since A is finite, this implies #Ia > #Ib.     QED

Theorem: "Consistency Maintained":
(1)  For all internally consistent PPairs(A) and all a,bA such 
       that (a,b) is consistent with PP(a,b) is internally consistent.
(2)  For all σ ∈ L(R,A), Affirmed(A,R,σ) is internally consistent.

Proof of (1):  Assume PPairs(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 (a1,a2),(a2,a3,),...,(ak-1,ak)P' such that 
(ak,a1)P'.  There are three cases to consider:

Case 1.1:  There exists no j ∈ {1,2,...,k-1} such that (aj,aj+1) = (a,b).  
Thus, (a1,a2),(a2,a3,),...,(ak-1,ak)P.  There are two subcases to consider:  

Case 1.1.1: (ak,a1) = (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: (ak,a1)(a,b).  Since (ak,a1)P', (ak,a1)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 
(aj,aj+1) = (a,b).  Thus we can let i denote the smallest integer in 
{1,2,...,k-1} such that (ai,ai+1) = (a,b), and we can let j denote the 
largest integer in {1,2,...,k-1} such that (aj,aj+1) = (a,b).  (Possibly i = j.)  
Clearly 1 ≤ ij < k.  There are two subcases to consider:  

Case 1.2.1:  j = k-1.  Clearly (ak,a1),(a1,a2),(a2,a3),...,(ai-1,ai) ∈ P.  
Since ak = b and ai = 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:  jk-1.  This implies j < k-1.  By inspection, we see that 
(aj+1,aj+2),(aj+2,aj+3,),...,(ak-1,ak),(ak,a1),(a1,a2),(a2,a3),...,(ai-1,ai) ∈ P.  
Since aj+1 = b and ai = 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 σ ∈ L(R,A) such that 
Affirmed(A,R,σ) is internally inconsistent.  Make the following abbreviations: 

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

For all (a,b) ∈ Aff, let Affab+ denote Aff ∩ Precede(a,b).  Since the empty 
set φ 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)  Affxy+ is internally consistent. 
(2.2)  Affxy+ ∪ {(x,y)} is internally inconsistent.  

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

Theorem: "At Least One Top":
(1)  For all non-empty BA and all internally consistent PPairs(B), 
       at least one alternative in B is not second in any ordered pair in P.
(2)  For all σ ∈ L(R,A), Top(σ) is not empty.  
(3)  For all internally consistent PPairs(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 bB, let Ib denote {b'B such 
that (b,b') is inconsistent with P}.  Since A is finite, Ib must be finite for all b B
so there must exist at least one xB such that #Ix ≤ #Ib for all bB.  We 
aim to show x is not second in any ordered pair in P.  Suppose to the contrary 
there exists yB such that (y,x)P.  This implies (x,y) is inconsistent with P.  
Since P is internally consistent, by theorem "More Inconsistent" #Ix > #Iy.  
But this contradicts the definition of x, so the contrary assumption cannot hold.  
Thus xB and x is not second in any pair in P.

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

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


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

Proof:  Assume a,bA, 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 σ ∈ L(R,A).  Abbreviate RVH = RVH(A,R,σ).  
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σab does.  Since R(b,a) is empty, RσabR(a,b).  
Thus RVH ranks a over b.     QED

Theorem:  "Majorities are independent of irrelevant alternatives":  
For all non-empty BA, 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 BA and all rL(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 BA, 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 BA and all σ ∈ L(R,A), let σ|B denote the restriction of σ  
to B. (That is, σ|B = (σR|B,σA|B)L(R|B,B) where σR|B is the same as σR 
except all alternatives not in B are deleted, and σA|B is the strict ordering of B  
which is the same as σA except all alternatives not in B are deleted.)

For all non-empty BA and all σ ∈ L(R,A), RVH(A,R,σ)|B = RVH(B,R|B,σ|B).  

Proof:  Arbitrarily pick non-empty BA and σ ∈ L(R,A) and distinct a,bB.  
Thus σ|B = (σR|B,σA|B)L(R|B,B).  Abbreviate RVH = RVH(A,R,σ) and 
RVH' = RVH(B,R|B,σ|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σab does. (That is, the same as the ballot in R(ab) ranked 
highest by σ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σR|Bab does.  Clearly R|BσR|Bab = Rσab|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 σA does.  Clearly R|B(ab) is empty, implying 
RVH' ranks a relative to b the same as σA|B does, which is the same 
as σ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, σ, a and b were picked arbitrarily, the theorem has been 
established.     QED

Theorem:  "Precedence is independent of irrelevant alternatives": 
For all non-empty BA, 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 σ ∈ L(R,A) and all non-empty BA, let σ|B denote the restriction 
of σ to B. (That is, σ|B is the same as σ except all alternatives not in B are 
deleted.)  For all σ ∈ L(R,A), all non-empty BA and all a,bB
Precede(a,b,A,R,σ) ∩ Pairs(B) = Precede(a,b,B,R|B,σ|B). 

Proof:  Clearly the following statement must hold: 

(1)  For all a,bB, 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,bB, RVH(A,R,σ) ranks a over b if and only if 
       RVH(B,R|B,σ|B) ranks a over b

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

(3)  For all a,b,c,dB and all σ ∈ L(R,A), if (c,d)Precede(a,b,A,R,σ) 
       then (c,d)Precede(a,b,B,R|B,σ|B). 
(4)  For all a,b,c,dB and all σ ∈ L(R,A), if (c,d)Precede(a,b,B,R|B,σ|B
       then (c,d)Precede(a,b,A,R,σ).

First we establish 3:  Assume a,b,c,dB and σ ∈ L(R,A) and 
(c,d)Precede(a,b,A,R,σ).  We must show (c,d)Precede(a,b,B,R|B,σ|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,σ) 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,σ) 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,σ|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,σ|B) ranks c over a.

Thus, by the definition of precedence (c,d)Precede(a,b,B,R|B,σ|B), 
establishing 3.  Next we establish 4:  Assume a,b,c,dB and σ ∈ L(R,A
and (c,d)Precede(a,b,B,R|B,σ|B).  We need to show that 
(c,d)Precede(c,d,A,R,σ).  Since (c,d)Precede(a,b,B,R|B,σ|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,σ|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,σ|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,σ) 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,σ) ranks c over a.

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


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

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

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

Proof of (1):  By theorem "MAM is resolute", but substituting B for A
R|B for R and σ|B for σ, MAM(B,R|B,σ|B) is always a unique alternative 
in B for all finite non-empty A, all finite R, all non-empty BA and 
all σ ∈ L(R,A).  Therefore, by inspection of the iterative construction 
of Rsocial(A,R,σ)
, (1) is established. 

Proof of (2):  This follows immediately from 1 and the definition of Rsocial()
since the alternative atop Rsocial(A,R,σ) is Finish(A,R,σ,1) = MAM(A,R,σ).  
Thus (2) is established. 

Proof of (3):  Pick any σ ∈ L(R,A).  Make the following abbreviations: 

Rs = Rsocial(A,R,σ).  
For all k ∈ {1,2,...,#A}, 
        f(k) = Finish(A,R,σ,k). 
        B(k) = Bottom(A,R,σ,k). 
        R(k) = R|B(k)
        σ(k) = σ|B(k).
        Maj(k) = Majorities(B(k),R(k)).  
        Precede(a,b,k) = Precede(a,b,B(k),R(k),σ(k)) for all a,bB(k).
        Aff(k) = Affirmed(B(k),R(k),σ(k)). 

Pick any a,bA.  Assume (a,b) ∈ Aff(1).  We must show Rs ranks a over b.  
We prove this inductively after first establishing the following two propositions: 

Proposition 3.1:  bB(2).  
Proposition 3.2:  If aB(2) then (a,b) ∈ Aff(2). 

Proof of 3.1:  Since (a,b) ∈ Aff(1), this means b is second in at least 
one pair in Aff(1).  It follows by the definition of MAM() that f(1) ≠ b.  
This implies bB(2), establishing 3.1. 

Proof of 3.2:  Assume aB(2).  This implies f(1) ≠ a.  By 3.1, 
f(1) ≠ b.  Thus there must exist cA\{a,b} such that f(1) = c.  
Thus B(2) = A\{c}.  Suppose to the contrary (a,b) ∉ Aff(2).  
Let P denote {(x,y)Pairs(B(2)) such that (x,y) ∈ Aff(1)\Aff(2) 
or (x,y) ∈ Aff(2)\Aff(1)}.  By the contrary assumption, (a,b)P.  
Since P is not empty, by theorem "Precedence is a Strict Ordering"  
we can pick (x,y)P such that the following condition holds: 

(3.2.1)  (z,w) ∉ Precede(x,y,2) for all (z,w)P.

There are two cases to consider: 

Case 3.2.2:  (x,y) ∈ Aff(1)\Aff(2).  Since (x,y) ∈ Aff(1), this implies 
(x,y) ∈ Maj(1).  By theorem "Majorities are Independent of Irrelevant 
Alternatives"
, (x,y) ∈ Maj(2).  Since (x,y) ∈ Maj(2)\Aff(2), 
(x,y) must be inconsistent with Aff(2).  This means there exist 
(a1,a2),(a2,a3),...,(aj-1,aj) ∈ Aff(2) ∩ Precede(x,y,2) such that 
a1 = y and aj = x.  Let P2 denote {(a1,a2),(a2,a3),...,(aj-1,aj)}.  
By theorem "Consistency Maintained (2)", Aff(1) is internally 
consistent.  Therefore, since (x,y) ∈ Aff(1), at least one pair in P2  
is not in Aff(1).  Thus we can let (z,w) denote a pair in P2\Aff(1).  
Clearly (z,w)P.  But this contradicts 3.2.1, so case 3.2.2 is impossible.

Case 3.2.3:  (x,y) ∉ Aff(1)\Aff(2).  Since (x,y)P, this implies 
(x,y) ∈ Aff(2)\Aff(1).  Since (x,y) ∈ Aff(2), this implies (x,y) ∈ Maj(2).  
By theorem "Majorities are Independent of Irrelevant Alternatives"
(x,y) ∈ Maj(1).  Since (x,y) ∈ Maj(1)\Aff(1), (x,y) must be 
inconsistent with Aff(1).  Therefore, by theorem "Minimal Inconsistent 
Set (1)"
there must exist P2 ⊆ Aff(1) ∩ Precede(x,y,1) such that P2 is 
a minimal set with which (x,y) is inconsistent.  We can represent P2 as 
{(a1,a2),(a2,a3),...,(aj-1,aj)} where a1 = y and aj = x.  Since f(1) = c
it follows that c is not second in any pair in Aff(1).  Therefore, 
by theorem "Minimal Inconsistent Set (3)" no pair in P2 involves c.  
Thus P2Pairs(B(2)).  By theorem "Consistency Maintained (2)"
Aff(2) must be internally consistent.  Therefore, since (x,y) ∈ Aff(2) and 
(x,y) is inconsistent with P2, there must exist (z,w)P2\Aff(2).  Since 
(z,w) ∈ Aff(1)\Aff(2), this implies (z,w)P.  Since (z,w)Pairs(B(2)) 
and (z,w) ∈ Precede(x,y,1), by theorem "Precedence is Independent 
of Irrelevant Alternatives"
(z,w) ∈ Precede(x,y,2).  But this 
contradicts 3.2.1, so case 3.2.3 is impossible.

Since both cases are impossible, the contrary assumption cannot hold, 
establishing (a,b) ∈ Aff(2).  Thus 3.2 is established.  

It follows by induction on 3.1 and 3.2 (by relabeling A = B(k), R = R(k), etc., 
incrementing k by 1 each iteration) that (a,b) ∈ Aff(k) for all k ∈ {1,2,...,#A
such that aB(k).  This implies f(k) ≠ b for all k ∈ {2,3,...,#A} such 
that aB(k).  It follows that Rs ranks a over b.  Thus 3 is established.

Proof of (4):  Pick any σ ∈ L(R,A).  Make the same abbreviations as in the 
proof of 3.  Pick any a,bA.  Assume (a,b) ∈ Maj(1)\Aff(1).  We must 
show Rs ranks b over a.  We prove this inductively by first establishing 
the following three propositions: 

Proposition 4.1:  aB(2).  
Proposition 4.2:  If bB(2) then (a,b) ∈ Maj(2)\Aff(2).  
Proposition 4.3:  If bB(2) then a is second in at least one pair in Aff(2).  

Proof of 4.1:  Since (a,b) ∈ Maj(1)\Aff(1), (a,b) must be inconsistent 
with Aff(1).  This means there exist (a1,a2),(a2,a3),...,(aj-1,aj) ∈ Aff(1) 
such that a1 = b and aj = a.  Since (aj-1,a) ∈ Aff(1), this means a is 
second in at least one pair in Aff(1).  It follows by the definition of 
MAM() that f(1) ≠ a.  This implies aB(2).  Thus 4.1 is established. 

Proof of 4.2:  Assume bB(2).  This implies f(1) ≠ b.  By 4.1, f(1) ≠ a.  
Thus there must exist cA\{a,b} such that f(1) = c.  Thus B(2) = A\{c}.  
Suppose to the contrary (a,b) ∉ Maj(2)\Aff(2).  Since (a,b) ∈ Maj(1), 
by theorem "Majorities are Independent of Irrelevant Alternatives" 
(a,b) ∈ Maj(2).  By the contrary assumption, this implies (a,b) ∈ Aff(2).  
Let P denote {(x,y)Pairs(B(2)) such that (x,y) ∈ Aff(1)\Aff(2) or 
(x,y) ∈ Aff(2)\Aff(1)}.  Since (a,b) ∈ Aff(2)\Aff(1), (a,b)P.  
Since P is not empty, by theorem "Precedence is a Strict Ordering" 
we can pick (x,y)P such that the following condition holds: 

(4.2.1)  (z,w) ∉ Precede(x,y,2) for all (z,w)P.

There are two cases to consider: 

Case 4.2.2:  (x,y) ∈ Aff(1)\Aff(2).  By the same reasoning 
as in case 3.2.2, case 4.2.2 is impossible. 

Case 4.2.3:  (x,y) ∉ Aff(1)\Aff(2).  By the same reasoning 
as in case 3.2.3, case 4.2.3 is impossible.

Since both cases are impossible, the contrary assumption cannot hold, 
establishing (a,b) ∈ Maj(2)\Aff(2).  Thus 4.2 is established.  

Proof of 4.2:  Assume bB(2).  By 4.2, (a,b) ∈ Maj(2)\Aff(2).  By 
the definition of Affirmed(), this implies (a,b) is inconsistent with Aff(2).  
this means there exist (a1,a2),(a2,a3),...,(aj-1,aj) ∈ Aff(2) such that 
a1 = b and aj = a.  Since (aj-1,a) ∈ Aff(2), a is second in at least one 
pair in Aff(2).  Thus 4.3 is established. 

It follows by induction on 4.1 and 4.3 (by relabeling A = A(k), R = R(k), etc., 
incrementing k each iteration) that a is second in at least one pair in Aff(k
for all k ∈ {1,2,...,#A} such that bB(k).  This implies f(k) ≠ a for 
all k ∈ {2,3,...,#A} such that bB(k).  It follows that Rs ranks b over a.  
Thus 4 is established.

Proof of (5):  Pick any σ ∈ L(R,A).  Abbreviate by omitting "given (R,σ)
from the notation, and make the following abbreviations: 

Maj = Majorities(A,R).
For all a,bA, Precede(a,b) = Precede(a,b,A,R,σ).  
Aff = Affirmed(A,R,σ).  
Rs = Rsocial(σ).  
For all rL(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,σ).  

Suppose to the contrary there exists rL(A) that dominates Rs.  This means 
Distinct(r,Rs) is not empty and LDA(r,Rs) ∈ Agreed(r)\Agreed(Rs).  Let (x,y) 
denote LDA(r,Rs).  Clearly (x,y) ∈ Maj and Rs ranks y over x and r ranks x  
over y.  Since Rs ranks y over x, by (3) (x,y) ∉ Aff.  Since (x,y) ∈ Maj\Aff, 
there must exist (a1,a2),(a2,a3),...,(ak-1,ak) ∈ Aff ∩ Precede(x,y) such that 
a1 = y and ak = x.  Since (x,y) ∈ Maj, (y,x) ∉ Maj and thus k > 2.  By (3), 
Rs ranks y over a2 and a2 over a3 and ... and ak-1 over x.  Since r ranks x  
over y and k > 2, there must exist a ∈ {a2,a3,...,ak-1} such that r ranks x  
over a or r ranks a over y. (Otherwise r ranks y over all a ∈ {a2,a3,...,ak-1
and all a ∈ {a2,a3,...,ak-1} over x, implying r ranks y over x, a contradiction.)  
By induction there exists at least one pair in {(y,a2),(a2,a3),...,(ak-1,x)} that 
is not in Agreed(r), which we denote as (z,w).  Since r ranks w over z and 
Rs ranks z over w(z,w) ∈ Distinct(r,Rs).  Since (z,w) ∈ Precede(x,y), 
LDA(r,Rs) cannot be (x,y).  This contradiction means the contrary assumption 
cannot hold, so RsUndominatedRankings(σ).  Thus 5 is established.  

Proof of (6):  Arbitrarily pick σ ∈ L(R,A) and a,bA.  Since A and R  
are clear in the context, abbreviate by omitting A and R from the notation.  
Assume (a,b) is inconsistent with Affirmed(σ).  By the definition of Affirmed()
there exist (a1,a2),(a2,a3),...,(ak-1,ak)Affirmed(σ) such that a1 = b and 
ak = a.  By (3), Rsocial(σ) must rank a1 over a2, a2 over a3, ..., and ak-1 over ak.  
By 1, Rsocial(σ) is a strict ordering of A, so Rsocial(σ) ranks a1 over ak.  
Since a1 = b and ak = a, this means Rsocial(σ) ranks b over a, establishing 6. 

Proof of (7):  Pick any σ ∈ L(R,A) and any non-empty BA (strict subset) 
such that Rsocial(A,R,σ) ranks every alternative in A\B over every alternative 
in B.  Make the following abbreviations: 

Rs = Rsocial(A,R,σ).  
Maj = Majorities(A,R).  
Precede(a,b) = Precede(a,b,A,R,σ) for all a,bA.
Aff = Affirmed(A,R,σ). 

First we establish 7.1.  Make the following abbreviations:

Maj' = Majorities(B,R|B).  
Precede'(a,b) = Precede(a,b,B,R|B,σ|B) for all a,bB.
Aff' = Affirmed(B,R|B,σ|B). 

We must show Aff' = Aff ∩ Pairs(B).  Suppose the contrary.  Let P denote the 
union of Aff'\(Aff ∩ Maj') and (Aff ∩ Maj')\Aff'.  Since Aff' ⊆ Maj', P ⊆ Maj'.  
Thus every pair in P involves only alternatives in B.  By the contrary assumption, 
P is not empty.  Therefore, by theorem "Precedence is a Strict Ordering"  
we can pick (x,y)P such that the following condition holds:

(7.1.1)  For all (z,w)P, (z,w) ∉ Precede'(x,y).

There are two cases to consider: 

Case 7.1.2:  (x,y) ∈ Aff'\(Aff ∩ Maj').  Since (x,y) ∈ Aff', (x,y) ∈ Maj'.  
By theorem "Majorities are Independent of Irrelevant Alternatives", this 
implies (x,y) ∈ Maj.  Since (x,y) ∈ Maj\Aff, (x,y) must be inconsistent 
with Aff ∩ Precede(x,y).  This implies there exists P2 ⊆ Aff ∩ Precede(x,y
such that P2 = {(a1,a2),(a2,a3),...,(ak-1,ak)} and a1 = y and ak = x.  
By 1, Rs is a strict ordering.  By 3, Rs must rank y over all alternatives 
in {a2,a3,...,ak}.  Since yB, this implies {a1,a2,...,ak} ∈ B.  
Thus P2 ⊆ Maj'.  By theorem "Consistency Maintained (2)"
Aff' must be internally consistent.  Thus, since (x,y) ∈ Aff'  and (x,y) is 
inconsistent with P2, there must exist (z,w)P2 such that (z,w) ∉ Aff'.  
Since (z,w) ∈ Aff\Aff'(z,w)P.  Since (z,w) ∈ Precede(x,y), 
by theorem "Precedence is Independent of Irrelevant Alternatives" 
(z,w) ∈ Precede'(x,y).  But this contradicts 7.1.1, so case 7.1.2 is impossible.  

Case 7.1.3:  (x,y) ∉ Aff'\(Aff ∩ Maj').  This implies (x,y) ∈ (Aff ∩ Maj')\Aff'.  
Since (x,y) ∈ Maj'\Aff', (x,y) must be inconsistent with Aff' ∩ Precede'(x,y).  
This implies there exists P2 ⊆ Aff' ∩ Precede'(x,y) such that a1 = y and 
ak = x and P2 = {(a1,a2),(a2,a3),...,(ak-1,ak)}.  Since P2 ⊆ Aff', this 
implies P2 ⊆ Maj'.  By theorem "Majorities are Independent of Irrelevant 
Alternatives"
, P2 ⊆ Maj.  By theorem "Consistency Maintained (2)"
Aff' must be internally consistent.  Therefore, since (x,y) ∈ Aff 
and (x,y) is inconsistent with P2, there must exist (z,w)P2\Aff.  
Since (z,w) ∈ Aff'\Aff, (z,w)P.  But since (z,w) ∈ Precede'(x,y), 
this contradicts 7.1.1, so case 7.1.3 is impossible.

Since both cases are impossible, the contrary assumption cannot hold, 
establishing 7.1.  Next we establish 7.2.  Make the following abbreviations:

T = A\B. (The alternatives ranked over B by Rs.)
Maj" = Majorities(T,R|T).  
Precede"(a,b) = Precede(a,b,T,R|T,σ|T) for all a,bT.
Aff" = Affirmed(T,R|T,σ|T). 

We must show Aff" = Aff ∩ Pairs(T).  Suppose the contrary.  Let P denote 
the union of Aff"\(Aff ∩ Maj")  and (Aff ∩ Maj")\Aff'.  Since Aff" ⊆ Maj"
P ⊆ Maj".  Thus every pair in P involves only alternatives in T.  By the 
contrary assumption, P is not empty.  Therefore, by theorem "Precedence is 
a Strict Ordering"
we can pick (x,y)P such that the following condition holds: 

(7.2.1)  (z,w) ∉ Precede"(x,y) for all (z,w)P.

There are two cases to consider: 

Case 7.2.2:  (x,y) ∈ Aff"\(Aff ∩ Maj").  Since (x,y) ∈ Aff", (x,y) ∈ Maj".  
By theorem "Majorities are Independent of Irrelevant Alternatives", this 
implies (x,y) ∈ Maj.  Since (x,y) ∈ Maj\Aff, (x,y) must be inconsistent 
with Aff ∩ Precede(x,y).  This implies there exists P2 ⊆ Aff ∩ Precede(x,y
such that P2 = {(a1,a2),(a2,a3),...,(ak-1,ak)} and a1 = y and ak = x.  By 1, 
Rs is a strict ordering of A.  By 3, Rs ranks all alternatives in {a1,a2,...,ak-1
over x.  Since xT, this implies {a1,a2,...,ak} ∈ T.  Thus P2 ⊆ Maj".  
By theorem "Consistency Maintained (2)", Aff" must be internally 
consistent.  Thus, since (x,y) ∈ Aff" and (x,y) is inconsistent with P2
there must exist (z,w)P2\Aff".  Since (z,w) ∈ Aff\Aff"(z,w)P.  
Since (z,w) ∈ Precede(x,y), by theorem "Precedence is Independent 
of Irrelevant Alternatives"
 (z,w) ∈ Precede"(x,y).  But this 
contradicts 7.2.1, so case 7.2.2 is impossible.  

Case 7.2.3:  (x,y) ∉ Aff"\(Aff ∩ Maj").  By reasoning the same as 
in case 7.1.3 (substituting " for '), case 7.2.3 must be impossible.

Since both cases are impossible, the contrary assumption cannot hold, 
establishing 7.2.  Since both 7.1 and 7.2 are established, 7 is established. 
QED 

Theorem: "Rsocial = Rsocial2"
(1)  For all σ ∈ L(R,A), Rsocial2(A,R,σ) ∈ L(A). (That is, a strict ordering of A.) 
(2)  For all σ ∈ L(R,A), all integers k ≥ 0 and all a,bA, if (a,b) ∈ Pk(A,R,σ) 
       then (a,b) ∈ Pj(A,R,σ) for all integers jk, and (b,a) ∉ Pj for all integers j ≥ 0. 
(3)  For all σ ∈ L(R,A), all integers k ≥ 0 and all a,bA
       if (a,b) ∈ Pk(A,R,σ) then Rsocial2(A,R,σ) ranks a over b.  
(4)  For all σ ∈ L(R,A), all integers k ≥ 0 and all a,bA
       if Rsocial2(A,R,σ) ranks a over b and aTied(Pk(A,R,σ)) 
       then Next(Pk(A,R,σ),A,R,σ) ≠ {b}.
(5)  For all σ ∈ L(R,A), Rsocial(A,R,σ) = Rsocial2(A,R,σ). 

Proof of (1):  Pick any σ ∈ L(R,A) and make the following abbreviations: 

Rs = Rsocial(A,R,σ).  
Rs2 = Rsocial2(A,R,σ).  
RVH = RVH(A,R,σ). 
Aff = Affirmed(A,R,σ).  
Pk = Pk(A,R,σ) for all integers k ≥ 0. 
Tiedk = Tied(Pk) for all integers k ≥ 0. 
TTk = TopTied(Pk) for all integers k ≥ 0. 
Nextk = Next(Pk,σ) for all integers k ≥ 0. 

By inspection of the definition of Rsocial2(), 1 will follow easily 
if we establish the following five statements: 

(1.1)  Pk is a binary relation on A for all integers k ≥ 0.
(1.2)  Pk is irreflexive for all integers k ≥ 0. 
(1.3)  Pk is asymmetric for all integers k ≥ 0. 
(1.4)  Pk is transitive for all integers k ≥ 0. 
(1.5)  There exists at least one integer k ≥ 0 such that Pk is complete
(1.6)  For all integers k ≥ 0, if Pk is complete then Pk is negatively transitive.

By inspection of the definitions of P0() and Pk(), Pk is a subset of Pairs(A
for all integers k ≥ 0.  Thus, by the definition of binary relation, 1.1 clearly holds.  

Irreflexivity of P0 (that is, (a,a)P0 for all aA) follows by theorem 
"Consistency Means Acyclicity (2)"
and theorem "Consistency Maintained (2)"  
and the definition of P0().  By the definition of Pk(), it follows that Pk is irreflexive  
for all integers k ≥ 0.  Thus 1.2 is established.  

We prove 1.3 by induction:  Asymmetry of P0 follows by theorem "Consistency 
Maintained (2)"
and theorem "Reversed Inconsistent Pair is Consistent" and 
inspection of the definition of P0().  To complete the induction, pick any integer 
k > 0 and assume Pk-1 is asymmetric; we must show Pk is asymmetric.  
Assume (a,b) ∈ Pk; we must show (b,a)Pk.  There are two cases:  

Case 1.3.1:  (a,b) ∈ Pk-1.  Since Pk-1 is asymmetric(b,a)Pk-1.  
It follows by the definition of Pk(), that (b,a)Pk.

Case 1.3.2:  (a,b)Pk-1.  Since (a,b) ∈ Pk, it follows by the definition 
of Pk() that Nextk-1 = {a} and (b,a)Pk-1.  It then follows that (b,a)Pk

Since (b,a)Pk in both cases, Pk must be asymmetric.  Thus 1.3 is established. 

Next we prove 1.4 (transitivity).  First we establish the following two propositions: 

(1.4.1)  For all integers k ≥ 0 and all a,bA, if (a,b) ∈ Pk 
                and Nextk = {b}, then a ∉ Tiedk.  
(1.4.2)  For all integers k ≥ 0 and all distinct a,b,cA
                if Pk is transitive and (a,b) ∈ Pk and Nextk = {b
                and (c,b)Pk, then (a,c) ∈ Pk.  

Proof of (1.4.1):  Assume (a,b) ∈ Pk and Nextk = {b}.  Since 
Nextk = {b}, b ∈ TTk.  Since b ∈ TTk and (a,b) ∈ Pk, it follows by 
the definition of TopTied() that a ∉ Tiedk.  Thus 1.4.1 is established. 

Proof of (1.4.2):  Assume Pk is transitive and a,b,cA are distinct 
and (a,b) ∈ Pk and Nextk = {b} and (c,b)Pk.  Suppose to the 
contrary (a,c) ∉ Pk.  By 1.4.1, a ∉ Tiedk.  Since (a,c) ∉ Pk and 
a ∉ Tiedk and ac, it follows that (c,a) ∈ Pk.  Since (c,a) ∈ Pk 
and (a,b) ∈ Pk and Pk is transitive, (c,b) ∈ Pk.  This contradiction 
means the contrary assumption cannot hold.  Thus (a,c) ∈ Pk
establishing 1.4.2.  

We complete the proof of 1.4 by induction:  First we show P0 is transitive.  
Assume (a,b) ∈ P0 and (b,c) ∈ P0.  Since (a,b) ∈ P0(b,a) must be 
inconsistent with Aff.  Thus there exist (a1,a2),(a2,a3),...,(aj-1,aj) ∈ Aff 
such that a1 = a and aj = b.  Since (b,c) ∈ P0, (c,b) must be inconsistent 
with Aff.  Thus there exist (b1,b2),(b2,b3),...,(bh-1,bh) ∈ Aff such that 
b1 = b and bh = c.  Let g = j + h.  Relabel ci = ai for all i ∈ {1,2,...,j}, and 
ci = bi-j for all i ∈ {j+1,j+2,...,g}.  Since (c1,c2),(c2,c3),...,(cg-1,cg) ∈ Aff 
and c1 = a and cg = c, this means (c,a) is inconsistent with Aff.  This implies 
(a,c) ∈ P0, which means P0 is transitive.  To complete the induction, pick 
any integer k > 0 and assume Pk-1 is transitive; we must show Pk is transitive.  
Assume (a,b) ∈ Pk and (b,c) ∈ Pk; we must show (a,c) ∈ Pk.  There are four 
cases to consider: 

Case 1.4.3:  a = b.  Since (b,c) ∈ Pk, (a,c) ∈ Pk.

Case 1.4.4:  b = c.  Since (a,b) ∈ Pk, (a,c) ∈ Pk.  

Case 1.4.5:  a = c.  By 1.3 (asymmetry), this case is impossible.  

Case 1.4.6:  ab and bc and ac.  There are four subcases to consider: 

Case 1.4.6.1:  (a,b) ∈ Pk-1 and (b,c) ∈ Pk-1.  Since Pk-1 is transitive
(a,c) ∈ Pk-1.  It follows by condition 1 of the definition of Pk() 
that (a,c) ∈ Pk in case 1.4.6.1.

Case 1.4.6.2:  (a,b) ∈ Pk-1 and (b,c) ∉ Pk-1.  Since (b,c) ∈ Pk 
and (b,c) ∉ Pk-1, by the definition of Pk() Nextk-1 = {b} and 
(c,b) ∉ Pk-1.  Since Pk-1 is transitive and (a,b) ∈ Pk-1 and 
Nextk-1 = {b} and (c,b) ∉ Pk-1, by 1.4.2 (a,c) ∈ Pk-1.  By 
condition 1 of the definition of Pk(), (a,c) ∈ Pk in case 1.4.6.2.  

Case 1.4.6.3:  (a,b) ∉ Pk-1 and (b,c) ∈ Pk-1.  There are two 
subcases to consider:  

Case 1.4.6.3.1:  (c,a) ∈ Pk-1.  Since Pk-1 is transitive and 
(b,c) ∈ Pk-1 and (c,a) ∈ Pk-1, (b,a) ∈ Pk-1.  By condition 1 of 
the definition of Pk(), (b,a) ∈ Pk.  By 1.3, Pk is asymmetric
so (a,b) ∉ Pk.  But this is a contradiction, so case 1.4.6.3.1 
is impossible.

Case 1.4.6.3.2:  (c,a) ∉ Pk-1.  Since (a,b) ∈ Pk and (a,b) ∉ Pk-1
Nextk-1 must be {a}.  Since Nextk-1 = {a} and (c,a) ∉ Pk-1
it follows by condition 2 of the definition of Pk() that (a,c) ∈ Pk  
in case 1.4.6.3.2. 

Thus (a,c) ∈ Pk in case 1.4.6.3. 

Case 1.4.6.4:  (a,b) ∉ Pk-1 and (b,c) ∉ Pk-1.  Since (a,b) ∈ Pk and 
Pk is irreflexive (by 1.2), ab.  Since (a,b) ∈ Pk and (a,b) ∉ Pk-1
Nextk-1 must be {a}.  Since (b,c) ∈ Pk and (b,c) ∉ Pk-1, Nextk-1 must 
be {b}.  Thus {a} = {b}.  But this is a contradiction, so case 1.4.6.4 
is impossible. 

Thus (a,c) ∈ Pk in case 1.4.6.

Since (a,c) ∈ Pk in all possible cases, Pk is transitive, establishing 1.4. 

Next we prove 1.5 (completeness of some Pk).  By the definition 
of Tied()
, clearly the following statement must hold:  

(1.5.1)  For all integers k ≥ 0, Pk is complete if and only if Tiedk is empty.

By the definitions of Pk(), Tied(), Next(), etc., clearly the following must hold: 

(1.5.2)  For all integers k > 0, if Tiedk-1 is not empty 
             then Tiedk is a strict subset of Tiedk-1.

It follows by induction on 1.5.2 that there exists at least one integer k ≥ 0 such 
that Tiedk is empty.  Thus, by 1.5.1 there exists at least one integer k ≥ 0 such 
that Pk is complete.  Thus 1.5 is established. 

Next we prove 1.6 (negative transitivity of complete Pk).  Assume Pk is 
complete and (a,b) ∉ Pk and (b,c) ∉ Pk.  We must show (a,c) ∉ Pk-1.  
There are four cases to consider:  

Case 1.6.1:  a = b.  Since (b,c) ∉ Pk, (a,c) ∉ Pk.  
Case 1.6.2:  b = c.  Since (a,b) ∉ Pk, (a,c) ∉ Pk.  
Case 1.6.3:  a = c.  By 1.2 (irreflexivity), (a,c) ∉ Pk.  
Case 1.6.4:  ab and bc and ac.  Since Pk is complete
        (b,a) ∈ Pk and (c,b) ∈ Pk.  By 1.4 (transitivity), (c,a) ∈ Pk.  
        By 1.3 (asymmetry), (a,c) ∉ Pk

Since (a,c) ∉ Pk in all four cases, Pk is negatively transitive when it is complete
establishing 1.6. 

By 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, the definition of Rsocial2() and induction on 1.5.2, it 
follows that Rs2 is a strict ordering of A.  That is, Rs2L(A).  Thus 1 is established.  

Proof of (2):  Pick any σ ∈ L(R,A) and make the same abbreviations as in 
the proof of (1).  Pick any integer k ≥ 0.  Assume (a,b) ∈ Pk.  By inspection 
of the definitions of P0() and Pk(), clearly ab.  By induction on condition 1 
of the definition of Pk(), it follows that (a,b) ∈ Pj for all integers jk.  
Furthermore, by asymmetry (1.3) and induction on condition 1 of  the definition 
of Pk()
, it follows that (b,a) ∉ Pj  for all integers j ≥ 0.  Thus 2 is established.  

Proof of (3):  This follows immediately from 1 and 2.

Proof of (4):  Pick any σ ∈ L(R,A) and make the same abbreviations as in the 
proof of (1).  Pick any integer k ≥ 0.  Assume Rs2 ranks a over b and a ∈ Tiedk.  
Suppose to the contrary Nextk = {b}.  There are three cases to consider:  

Case 4.1:  (a,b) ∈ Pk.  By 1.2 (irreflexivity), ab.  Since (a,b) ∈ Pk  
and a ∈ Tiedk, it follows by the definition of TopTied() that b ∉ TTk.  
Thus, by the definition of Next(), Nextk cannot be {b}.  But this is 
a contradiction, so case 4.1 is impossible.

Case 4.2:  (b,a) ∈ Pk.  By 3, Rs2 ranks b over a.  By asymmetry 
(1.3), Rs2 does not rank a over b.  But this is a contradiction, 
so case 4.2 is impossible. 

Case 4.3:  (a,b) ∉ Pk and (b,a) ∉ Pk.  Since Nextk = {b}, it follows by 
the definition of Pk() that (b,a) ∈ Pk+1.  By 3, Rs2 ranks b over a.  
By asymmetry (1.3), Rs2 does not rank a over b.  But this is 
a contradiction, so case 4.3 is impossible.  

Since all three cases are impossible, the contrary assumption cannot hold, 
which implies Nextk ≠ {b}.  Thus 4 is established.

Proof of (5):  Pick any σ ∈ L(R,A) and make the same abbreviations as in 
the proof of (1).  Suppose to the contrary RsRs2.  Then we can let x denote 
the alternative ranked highest by Rs that is not ranked as high by Rs2, and we 
can let y denote the alternative ranked highest by Rs2 that is not ranked as high 
by Rs.  Let T denote the alternatives ranked over x by Rs. (T may be empty.)  
Let T2 denote the alternatives ranked over y by Rs2. (T2 may be empty.)  
By construction, and since Rs is a strict ordering of A (by theorem "Properties 
of RSocial (1)"
) and Rs2 is a strict ordering of A (by 1), clearly the following 
three statements hold: 

(5.1)  Rs ranks x over y
(5.2)  Rs2 ranks y over x
(5.3)  T = T2

By theorem "Properties of RSocial (6)" and 5.1, (x,y) must be consistent with Aff.  
Let B denote A\T.  Clearly {x,y} ⊆ B.  Make the following abbreviations: 

RVH' = RVH(B,R|B,σ|B). 
Aff' = Affirmed(B,R|B,σ|B).  
Top' = Top(B,R|B,σ|B).  
MAM' = MAM(B,R|B,σ|B).  

By inspection of the definition of Rsocial(), MAM' must be x.  Thus the following 
three statements must hold: 

(5.4)  x ∈ Top'.  
(5.5)  RVH' ranks x over all b ∈ Top'\{x}.  
(5.6)  For all bB, (b,x) ∉ Aff'.  

By 5.5 and theorem "Random Voter Hierarchy is Independent of Irrelevant 
Alternatives"
 the following statement must hold:  

(5.7)  RVH ranks x over all b ∈ Top'\{x}. 

By theorem "Properties of RSocial (7.1)", Aff' = Aff ∩ Pairs(B).  Thus, 
by 5.6 the following must hold:  

(5.8)  For all bB, (b,x) ∉ Aff.  

Since Rs2 ranks all aT over all bB, by 2 and 3 the following must hold: 

(5.9)  For all aT, all bB and all integers k ≥ 0, (b,a)Pk.  

By 5.9 and the definition of P0(), the following statement must hold: 

(5.10)  For all aT and all bB, (b,a) ∉ Aff.  

Next we establish the following proposition:  

(5.11)  For all bB, (x,b) is consistent with Aff.

Proof of (5.11):  Suppose to the contrary (x,b) is inconsistent with Aff 
for some bB.  This means there exists a sequence a1,a2,...,akA  
such that a1 = b and ak = x and (aj,aj+1) ∈ Aff for all j ∈ {1,2,...,k-1}].  
By 5.8, ak-1B, which implies ak-1T.  Thus we can let h denote 
the smallest integer in {1,2,...,k-1} such that ahT.  Since a1B
2 ≤ hk-1.  By construction, ah-1T, which implies ah-1B.  
Since ah-1B and ahT, by 5.10 (ah-1,ah) ∉ Aff.  But this is a 
contradiction, so the contrary assumption cannot hold, establishing 5.11.  

By 5.11 and the definition of P0(), the following statement must hold: 

(5.12)  For all bB, (b,x)P0.  

Since Rs2 ranks no alternative in B over y, by 3 the following must hold:  

(5.13)  For all bB, (b,y)P0.  

By 1.5 and 1.5.1, there exists at least one integer k ≥ 0 such that Tiedk is empty.  
Thus we can let j denote the smallest non-negative integer such T ∩ Tiedj is empty.  
Since Rs2 ranks all of T over all of B, by 4 the following statement must hold:  

(5.14)  For all bB and all integers k such that 0 ≤ k < j, Nextk ≠ {b}.  

By 5.14 and the definition of Pk(), the following must hold:  

(5.15)  For all b,b'B, (b,b')Pj if and only if (b,b')P0.

By 5.15, 5.12 and 5.13 the following two statements must hold: 

(5.16)  For all bB, (b,x)Pj.  
(5.17)  For all bB, (b,y)Pj.  

Since T ∩ Tiedj is empty, by 5.9 the following statement must hold:  

(5.18)  For all aT and all bB, (a,b)Pj.  

Since {x,y} ⊆ B, by 5.16 and 5.17 (x,y)Pj and (y,x)Pj.  Thus {x,y} ⊆ Tiedj.  
Since x ∈ Tiedj and T ∩ Tiedj is empty, it follows by 5.16 and the definition 
of TopTied()
that x ∈ TTj.  Since y ∈ Tiedj and T ∩ Tiedj is empty, it follows 
by 5.17 and the definition of TopTied() that y ∈ TTj.  Thus {x,y} ⊆ TTj.

Next we establish the following proposition:  

(5.19)  TTj ⊆ Top'.

Proof of (5.19):  Pick any aA\Top'.  We must show a ∉ TTj.  
There are two cases to consider:  

Case 5.19.1:  aT.  Since T ∩ Tiedj is empty, 
clearly a ∉ Tiedj.  Thus a ∉ TTj in case 5.19.1.

Case 5.19.2:  aT.  This implies aB.  Let B' denote {bB such 
that (b,a)Pj}.  Since a ∉ Top', there must exist bB such that 
(b,a) ∈ Aff'.  By theorem "Properties of RSocial (7.1)" (b,a) ∈ Aff.  
Thus (a,b) is inconsistent with Aff.  Thus (b,a)P0, and by 5.15 
(b,a)Pj.  This implies B' is not empty.  By 1, Pj is an irreflexive
asymmetrictransitive binary relation on A.  Thus we can pick zB'  
such that, for all wB', (w,z)Pj.  We aim to show z ∈ Tiedj.  
Suppose not.  There are two subcases to consider:  

Case 5.19.2.1:  (x,z)Pj.  Since Pj is transitive and (x,z)Pj 
and (z,a)Pj, (x,a)Pj.  Thus xB'.  But since (w,z)Pj 
for all wB', this is a contradiction.  Thus case 5.19.2.1 
is impossible.

Case 5.19.2.2:  (x,z)Pj.  Since x ∈ Tiedj and z ∉ Tiedjzx.  
Since z ∉ Tiedj and zx and (x,z)Pj, it follows that (z,x)Pj.  
But since zB, this contradicts 5.16, so case 5.19.2.2 is impossible.  

Since both subcases are impossible, the contrary assumption cannot 
hold, establishing z ∈ Tiedj.  Since z ∈ Tiedj and (z,a)Pj, it follows 
by the definition of TopTied() that a ∉ TTj in case 5.19.2.

Since a ∉ TTj in both cases, proposition 5.19 is established.  

By 5.7 and 5.19, RVH ranks x over all b ∈ TTj\{x}.  Thus, since x ∈ TTj
it follows by the definition of Next() that Nextj = {x}.  Since Nextj = {x
and (b,x)Pj for all bB, it follows by the definition of Pk() that (x,b)Pj+1  
for all bB.  Thus, by 3 Rs2 ranks x over all bB.  But since Rs2 is a strict 
ordering, this contradicts 5.2.  Therefore the contrary assumption cannot hold, 
which implies Rs = Rs2.  Thus 5 is established.         QED 

Theorem: "Rsocial = Rsocial3":  That is, for all σ ∈ L(R,A), 
Rsocial(A,R,σ) = Rsocial3(A,R,σ). 

Proof:  Pick any σ ∈ L(R,A).  Make the following abbreviations:  

RVH = RVH(A,R,σ).  
Maj = Majorities(A,R). 
Aff = Affirmed(A,R,σ).
Top = Top(A,R,σ). 
Rs = Rsocial(A,R,σ). 
Undom = UndominatedRankings(A,R,σ).
For all distinct r,r'L(A), 
        Distinct(r,r') = DistinctAgreed(r,r',A,R).
        TDA(r,r') = TopmostDifferentAlternative(r,r').  
Rs3 = Rsocial3(A,R,σ).  

We must show Rs = Rs3.  Suppose the contrary.  Abbreviate by omitting 
"given (R,σ)" from the notation.  By inspection of the definition of Rsocial3()
Rs3L(A). (That is, Rs3 is a strict ordering of A.)  By condition 1 of 
the definition of weak dominance, Rs3 ∈ Undom.  By theorem "Weak 
Dominance is  a Strict Ordering"
, Rs3 weakly dominates all other strict 
orderings of A, hence Rs3 weakly dominates Rs.  By theorem "Properties 
of RSocial (5)"
, Rs ∈ Undom, hence Rs3 does not dominate Rs.  Since Rs3 
weakly dominates Rs but does not dominate Rs, by condition 2 of the 
definition of weak dominance
RVH ranks TDA(Rs3,Rs) over TDA(Rs,Rs3).  
Let x denote TDA(Rs3,Rs) and let y denote TDA(Rs,Rs3). (Thus x is the 
alternative ranked highest by Rs3 that is not ranked as high by Rs, and y is 
the alternative ranked highest by Rs that is not ranked as high by Rs3.)  
Let B denote A\Over(Rs3,x).  Clearly the following statements must hold:  
        (1)  Over(Rs3,x) = Over(Rs,y). 
        (2)  {x,y} ⊆ B.
        (3)  Rs3 ranks x over all alternatives in B\{x}.   
        (4)  Rs ranks y over all alternatives in B\{y}.    
Since neither Rs nor Rs3 dominates the other, it follows by the definition of 
dominance
that Distinct(Rs,Rs3) is empty, which implies #R(x,y) = #R(y,x). 
(That is, x and y tie pairwise.)  Make the following abbreviations: 
        RVH' = RVH(B,R|B,σ|B). 
        Aff' = Affirmed(B,R|B,σ|B).
        Top' = Top(B,R|B,σ|B). 
        MAM' = MAM(B,R|B,σ|B). 
By inspection of the definition of Rsocial(), MAM'  = y.  Thus, by the 
definition of MAM()
RVH' ranks y over all other alternatives in Top'.  
Since RVH ranks x over y, by theorem "Random Voter Hierarchy 
is Independent of Irrelevant Alternatives"
RVH' ranks x over y.  
Thus x ∉ Top'.  This means there exists zB such that (z,x) ∈ Aff'.  
By theorem "Properties  of RSocial (7.1)", Aff' = Aff ∩ Pairs(B), 
so (z,x) ∈ Aff.  Thus, by theorem "Properties  of RSocial (3)" 
Rs must rank z over x.  Since Aff ⊆ Maj, (z,x) ∈ Maj.  Thus, 
since Distinct(Rs,Rs3) is empty, Rs3 must also rank z over x.  
But this contradicts 3, which means the contrary assumption 
cannot hold, establishing Rs = Rs3.          QED 

Theorem: "Undominated Rankings Consistent With Affirmed Majorities":  
For all σ ∈ L(R,A) and all rUndominatedRankings(σ), Agreed(r) = Affirmed(σ).

Proof:  Pick any σ ∈ L(R,A).  Abbreviate Rs = Rsocial(σ).  By theorem 
"Properties of RSocial (5)"
RsUndominatedRankings(σ).  
By theorem "Properties of RSocial (3 and 4)", Agreed(Rs) = Affirmed(σ).  
Pick any rUndominatedRankings(σ).  Since r does not dominate Rs  
and Rs does not dominate r, DistinctAgreed(r,Rs) must be empty.  
This implies Agreed(r) = Agreed(Rs).  Thus Agreed(r) = Affirmed(σ).  
QED

Theorem: "MAM is Reasonably Deterministic
(See also the proof that MAM is resolvable.)
(1)  For all σ ∈ L(R,A) and all a,bTop(σ), #R(a,b) = #R(b,a).  
(2)  For all σ ∈ L(R,A), all aTop(σ) and all bA ranked over a  
       by Rsocial(σ), #R(a,b) = #R(b,a).  
(3)  For all σ ∈ L(R,A), if #R(a,b) ≠ #R(b,a) for all distinct a,bA
       then Rsocial(σ) is the unique ranking in UndominatedRankings(σ).  
(4)  If [#R(a,b) ≠ #R(b,a) for all distinct a,bA] and [(a,b) is not the 
       same size as (c,d) given R for all distinct (a,b),(c,d)Majorities], 
       then MAM(σ) is independent of σ. (In other words, although σ is 
       picked randomly, chance plays no role in MAM when no two 
       alternatives tie pairwise and no two majorities are the same size.)
  
(5)  If [#R(a,b) ≠ #R(b,a) for all distinct a,bA] and [(a,b) is not the 
       same size as (c,d) given R for all distinct (a,b),(c,d)Majorities], 
       then Rsocial(σ) is independent of σ.  

Proof of (1):  Suppose to the contrary that for some σ ∈ L(R,A) there exist 
a,bTop(σ) such that #R(a,b) ≠ #R(b,a).  Clearly ab.  Abbreviate 
Top = Top(σ) and Aff = Affirmed(σ).  Without loss of generality, 
suppose #R(a,b) > #R(b,a). (We can swap labels if necessary to make 
this so.)  Thus (a,b)Majorities.  Since b ∈ Top, (a,b) cannot be in Aff.  
Since (a,b)Majorities\Aff, (a,b) must be inconsistent with Aff.  By the 
definition of inconsistent, this means a must be the second alternative in 
at least one pair  in Aff.  But this contradicts the assumption that a ∈ Top.  
The contradiction refutes the contrary assumption and establishes (1). 

Proof of (2):  Pick any σ ∈ L(R,A).  Make the following abbreviations: 

Maj = Majorities(A,R). 
Rs = Rsocial(A,R,σ). 
For all a,bA, Precede(a,b) = Precede(a,b,A,R,σ).
Aff = Affirmed(A,R,σ). 
Top = Top(A,R,σ).  

Assume a ∈ Top and b is ranked over a by Rs.  Clearly (a,b)Agreed(Rs).  
By theorem "Properties of RSocial (3)" this implies (a,b) ∉ Aff.  Suppose 
to the contrary #R(a,b) ≠ #R(b,a).  There are two cases to consider:

Case 2.1:  #R(a,b) > #R(b,a).  In this case, (a,b) ∈ Maj.  
Since (a,b) ∈ Maj\Aff, it follows by the definition of Affirmed() 
that (a,b) is inconsistent with Aff.  This means there exist 
(a1,a2),(a2,a3),...(ak-1,ak) ∈ Aff ∩ Precede(a,b) such that a1 = b  
and ak = a.  Since (ak-1,a) ∈ Aff, a cannot be in Top.  But this 
contradicts the assumption a ∈ Top, implying case 2.1 is impossible.

Case 2.2:  #R(a,b) < #R(b,a).  In this case, (b,a) ∈ Maj and 
(b,a)Agreed(Rs).  By theorem "Properties of RSocial (4)"
(b,a) ∈ Aff.  This implies a ∉ Top.  But this contradicts the 
assumption a ∈ Top, implying case 2.2 is impossible. 

Since both cases are impossible, the contrary assumption is refuted, 
establishing (2). 

Proof of (3):  Pick any σ ∈ L(R,A).  Make the following abbreviations: 

Maj = Majorities(A,R). 
Undom = UndominatedRankings(A,R,σ).  
For all r,r'L(A), Distinct(r,r') = DistinctAgreed(r,r'). 
For all r,r'L(A) such that Distinct(r,r') is not empty, 
          LDA(r,r') = LargestDistinctAgreed(r,r',A,R,σ).
Rs = Rsocial(A,R,σ). 

Assume #R(a,b) ≠ #R(b,a) for all distinct a,bA.  By theorem "Properties of 
RSocial (5)"
Rs ∈ Undom.  We must show there does not exist r distinct from Rs  
such that r ∈ Undom.  Suppose the contrary.  Since rRs and both r and Rs  
are strict orderings of A, there must exist x,yA such that Rs ranks x over y  
and r ranks y over x.  Since #R(a,b) ≠ #R(b,a) for all distinct a,bA
either (x,y) ∈ Maj or (y,x) ∈ Maj.  Thus either (x,y) ∈ Distinct(r,Rs
or (y,x) ∈ Distinct(r,Rs).  Therefore Distinct(r,Rs) is not empty.  
By theorem "Precedence is a Strict Ordering"  and the definition 
of LargestDistinctAgreed(), LDA(r,Rs) must exist and be a unique 
ordered pair in Distinct(r,Rs).  Thus either r dominates Rs or Rs dominates r.  
Since Rs is undominated, this means Rs must dominate r.  But this contradicts 
the contrary assumption that r is also undominated, establishing (3).

Proof of (4):  Assume no two distinct alternatives tie pairwise 
and no two distinct majorities are the same size.  That is, 
assume both of the following conditions hold:

(4.1)  For all distinct a,bA, #R(a,b) ≠ #R(b,a). 
(4.2)  For all distinct (a,b),(c,d)Majorities(A,R), 
          at least one of the following two conditions holds: 
          (4.2.1)  #R(a,b) ≠ #R(c,d). 
          (4.2.2)  #R(b,a) ≠ #R(d,c). 

Since no two majorities are the same size, it follows by the definition 
of precedence
that the relative precedence of any two distinct pairs 
in Majorities(A,R) is determined with certainty by which pair is larger, 
independent of σ.  It follows by the definition of Affirmed() that 
Affirmed(A,R,σ) must be independent of σ, determined with certainty 
by A and R.  Thus Top(A,R,σ) must also be independent of σ, determined 
with certainty by A and R.  Since no pairings are tied, it follows by (1) 
that Top(A,R,σ) must be a singleton.  Since Top(A,R,σ) is a singleton 
and independent of σ, MAM(A,R,σ) must be independent of σ.  
Thus (4) is established.  

Proof of (5):  Assume no two distinct alternatives tie pairwise and no two 
distinct majorities are the same size. (That is, assume 4.1 and 4.2 hold.)  
Since (4) was established for any finite non-empty A, it follows that, for 
all non-empty BAMAM(B,R|B,σ|B) must also be independent of σ, 
determined with certainty by B and R.  Thus, by inspection of the iterative 
manner in which the MAM social ordering Rsocial(A,R,σ) is constructed, 
it follows immediately that Rsocial(A,R,σ) is independent of σ, 
determined with certainty by R.  Thus (5) is established.     QED 

Theorem: "MAM2 = MAM
(1) For all σ ∈ L(R,A), Top2(σ) = Top(σ).  
(2) For all σ ∈ L(R,A), MAM2(σ) = MAM(σ).

Proof of (1):  Arbitrarily pick σ ∈ L(R,A).  Make the following abbreviations: 

Maj = Majorities(A,R). 
Aff = Affirmed(A,R,σ).  
Top = Top(A,R,σ). 
For all rL(A), Agreed(r) = Agreed(r,A,R).
For all r,r'L(A), Distinct(r,r') = DistinctAgreed(r,r',A,R).
Undom = UndominatedRankings(A,R,σ).  
Top2 = Top2(A,R,σ).  
Rs = Rsocial(A,R,σ). 

Also abbreviate by omitting "given (R,σ)" from the notation.  By theorem 
"Properties of RSocial (5)"
Rs is undominated.  First we show Top ⊆ Top2.  
Assume a ∈ Top.  We must show a ∈ Top2.  There are two cases to consider:

Case 1.1:  a tops Rs.  Since Rs is undominated, clearly a ∈ Top2

Case 1.2:  a does not top Rs.  Let r denote the ordering which is the same 
as Rs except a is raised to the top in r.  By theorem "MAM is Reasonably 
Deterministic (2)"
, #R(a,b) = #R(b,a) for all b ranked over a by Rs.  Thus 
Distinct(r,Rs) is empty, implying Rs does not dominate r.  Pick any r'L(A).  
We will show r ∈ Undom by showing r' cannot dominate r.  Suppose to 
the contrary that r' dominates r.  Since r' dominates r and Rs does not 
dominate r, by theorem "Dominance is an Ordering (4)" r' must dominate Rs.  
But since Rs is undominated, this is a contradiction.  Thus r' cannot dominate r
implying r ∈ Undom.  Since a tops r, this implies a ∈ Top2

Since a ∈ Top2 in both cases, this implies Top ⊆ Top2.  Next we show that 
Top2 ⊆ Top.  Assume a ∈ Top2.  We must show a ∈ Top.  By the definition 
of Top2() there must exist r ∈ Undom such that a tops r.  By theorem 
"Undominated Rankings Consistent with Affirmed Majorities"
, Agreed(r) = Aff.  
This implies a is not second in any pair in Aff.  By the definition of Top() this 
implies a ∈ Top.  Thus Top2 ⊆ Top. 

Since Top ⊆ Top2 and Top2 ⊆ Top, Top2 must equal Top, establishing (1). 

Proof of (2):  This follows immediately from (1) and the definitions of MAM() 
and MAM2().  Thus MAM and MAM2 are completely equivalent.    QED