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 σ ∈ L(R,A) and all alternatives a ∈ A, 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,b ∈ A, 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,b ∈ A, 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,c ∈ A, 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,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 σ_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^σab ≠ R^σ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 p ∈ Pairs, 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 p ∈ Pairs.  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), 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,σ), 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 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,σ) 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 σ ∈ 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 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,σ).

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 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 σ ∈ 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 r ∈ L(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 
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 σ ∈ 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 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 σ ∈ 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 σ ∈ L(R,A), Affirmed(A,R,σ) 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 σ ∈ 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 Aff_ab+ 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)  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,σ) is internally consistent for all σ ∈ 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 σ ∈ L(R,A), Top(σ) 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 σ ∈ 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 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 σ ∈ 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,σ) 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 σ ∈ 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^σab ∈ 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 σ ∈ 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 B ⊆ A and all σ ∈ L(R,A), RVH(A,R,σ)|_B = RVH(B,R|_B,σ|_B).  

Proof:  Arbitrarily pick non-empty B ⊆ A and σ ∈ L(R,A) and distinct a,b ∈ B.  
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^|B^ab does.  Clearly R|_B^σR^|B^ab = 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 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 σ ∈ L(R,A) and all non-empty B ⊆ A, 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 B ⊆ A and all a,b ∈ B, 
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,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,σ) 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,d ∈ B 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,d ∈ B 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,d ∈ B 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,d ∈ B 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 x ∈ Top(A,R,σ) 
such that, for all y ∈ Top(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 R_social":  (See the section "The MAM social 
ordering" in the document "MAM Formal Definition" for definitions.)
(1)  For all σ ∈ L(R,A), R_social(A,R,σ) is a strict ordering of A. (That is, R_social() 
       is irreflexive, complete, asymmetric, transitive and negatively transitive.)  
(2)  For all σ ∈ L(R,A), R_social(A,R,σ) ranks MAM(A,R,σ) over all other alternatives.  
(3)  For all σ ∈ L(R,A) and all (a,b) ∈ Affirmed(A,R,σ), 
       R_social(A,R,σ) ranks a over b.  
(4)  For all σ ∈ L(R,A) and all (a,b) ∈ Majorities(A,R)\Affirmed(A,R,σ), 
       R_social(A,R,σ) ranks b over a. 
       (Note that 3 and 4 imply Affirmed(A,R,σ) = Agreed(R_social(A,R,σ)).)
(5)  For all σ ∈ L(R,A), R_social(A,R,σ) ∈ UndominatedRankings(A,R,σ).  
(6)  For all σ ∈ L(R,A) and all a,b ∈ A, if (a,b) is inconsistent 
       with Affirmed(A,R,σ) then R_social(A,R,σ) ranks b over a.  
(7)  For all σ ∈ L(R,A) and all non-empty B ⊂ A such that 
       R_social(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 B ⊆ A and 
all σ ∈ L(R,A).  Therefore, by inspection of the iterative construction 
of R_social(A,R,σ), (1) is established. 

Proof of (2):  This follows immediately from 1 and the definition of R_social(), 
since the alternative atop R_social(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: 

R_s = R_social(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,b ∈ B(k).
        Aff(k) = Affirmed(B(k),R(k),σ(k)). 

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

Proposition 3.1:  b ∈ B(2).  
Proposition 3.2:  If a ∈ B(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 b ∈ B(2), establishing 3.1. 

Proof of 3.2:  Assume a ∈ B(2).  This implies f(1) ≠ a.  By 3.1, 
f(1) ≠ b.  Thus there must exist c ∈ A\{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 
(a₁,a₂),(a₂,a₃),...,(a_j-1,a_j) ∈ Aff(2) ∩ Precede(x,y,2) such that 
a₁ = y and a_j = x.  Let P₂ denote {(a₁,a₂),(a₂,a₃),...,(a_j-1,a_j)}.  
By theorem "Consistency Maintained (2)", Aff(1) is internally 
consistent.  Therefore, since (x,y) ∈ Aff(1), at least one pair in P₂  
is not in Aff(1).  Thus we can let (z,w) denote a pair in P₂\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 P₂ ⊆ Aff(1) ∩ Precede(x,y,1) such that P₂ is 
a minimal set with which (x,y) is inconsistent.  We can represent P₂ as 
{(a₁,a₂),(a₂,a₃),...,(a_j-1,a_j)} where a₁ = y and a_j = 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 P₂ involves c.  
Thus P₂ ⊆ Pairs(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 P₂, there must exist (z,w) ∈ P₂\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 a ∈ B(k).  This implies f(k) ≠ b for all k ∈ {2,3,...,#A} such 
that a ∈ B(k).  It follows that R_s 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,b ∈ A.  Assume (a,b) ∈ Maj(1)\Aff(1).  We must 
show R_s ranks b over a.  We prove this inductively by first establishing 
the following three propositions: 

Proposition 4.1:  a ∈ B(2).  
Proposition 4.2:  If b ∈ B(2) then (a,b) ∈ Maj(2)\Aff(2).  
Proposition 4.3:  If b ∈ B(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 (a₁,a₂),(a₂,a₃),...,(a_j-1,a_j) ∈ Aff(1) 
such that a₁ = b and a_j = a.  Since (a_j-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 a ∈ B(2).  Thus 4.1 is established. 

Proof of 4.2:  Assume b ∈ B(2).  This implies f(1) ≠ b.  By 4.1, f(1) ≠ a.  
Thus there must exist c ∈ A\{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 b ∈ B(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 (a₁,a₂),(a₂,a₃),...,(a_j-1,a_j) ∈ Aff(2) such that 
a₁ = b and a_j = a.  Since (a_j-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 b ∈ B(k).  This implies f(k) ≠ a for 
all k ∈ {2,3,...,#A} such that b ∈ B(k).  It follows that R_s 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,b ∈ A, Precede(a,b) = Precede(a,b,A,R,σ).  
Aff = Affirmed(A,R,σ).  
R_s = R_social(σ).  
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,σ).  

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

Proof of (6):  Arbitrarily pick σ ∈ L(R,A) and a,b ∈ A.  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 (a₁,a₂),(a₂,a₃),...,(a_k-1,a_k) ∈ Affirmed(σ) such that a₁ = b and 
a_k = a.  By (3), R_social(σ) must rank a₁ over a₂, a₂ over a₃, ..., and a_k-1 over a_k.  
By 1, R_social(σ) is a strict ordering of A, so R_social(σ) ranks a₁ over a_k.  
Since a₁ = b and a_k = a, this means R_social(σ) ranks b over a, establishing 6. 

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

R_s = R_social(A,R,σ).  
Maj = Majorities(A,R).  
Precede(a,b) = Precede(a,b,A,R,σ) for all a,b ∈ A.
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,b ∈ B.
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 P₂ ⊆ Aff ∩ Precede(x,y) 
such that P₂ = {(a₁,a₂),(a₂,a₃),...,(a_k-1,a_k)} and a₁ = y and a_k = x.  
By 1, R_s is a strict ordering.  By 3, R_s must rank y over all alternatives 
in {a₂,a₃,...,a_k}.  Since y ∈ B, this implies {a₁,a₂,...,a_k} ∈ B.  
Thus P₂ ⊆ Maj'.  By theorem "Consistency Maintained (2)", 
Aff' must be internally consistent.  Thus, since (x,y) ∈ Aff'  and (x,y) is 
inconsistent with P₂, there must exist (z,w) ∈ P₂ 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 P₂ ⊆ Aff' ∩ Precede'(x,y) such that a₁ = y and 
a_k = x and P₂ = {(a₁,a₂),(a₂,a₃),...,(a_k-1,a_k)}.  Since P₂ ⊆ Aff', this 
implies P₂ ⊆ Maj'.  By theorem "Majorities are Independent of Irrelevant 
Alternatives", P₂ ⊆ Maj.  By theorem "Consistency Maintained (2)", 
Aff' must be internally consistent.  Therefore, since (x,y) ∈ Aff 
and (x,y) is inconsistent with P₂, there must exist (z,w) ∈ P₂\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 R_s.)
Maj" = Majorities(T,R|_T).  
Precede"(a,b) = Precede(a,b,T,R|_T,σ|_T) for all a,b ∈ T.
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 P₂ ⊆ Aff ∩ Precede(x,y) 
such that P₂ = {(a₁,a₂),(a₂,a₃),...,(a_k-1,a_k)} and a₁ = y and a_k = x.  By 1, 
R_s is a strict ordering of A.  By 3, R_s ranks all alternatives in {a₁,a₂,...,a_k-1} 
over x.  Since x ∈ T, this implies {a₁,a₂,...,a_k} ∈ T.  Thus P₂ ⊆ Maj".  
By theorem "Consistency Maintained (2)", Aff" must be internally 
consistent.  Thus, since (x,y) ∈ Aff" and (x,y) is inconsistent with P₂, 
there must exist (z,w) ∈ P₂\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: "R_social = R_social2": 
(1)  For all σ ∈ L(R,A), R_social2(A,R,σ) ∈ L(A). (That is, a strict ordering of A.) 
(2)  For all σ ∈ L(R,A), all integers k ≥ 0 and all a,b ∈ A, if (a,b) ∈ P_k(A,R,σ) 
       then (a,b) ∈ P_j(A,R,σ) for all integers j ≥ k, and (b,a) ∉ P_j for all integers j ≥ 0. 
(3)  For all σ ∈ L(R,A), all integers k ≥ 0 and all a,b ∈ A, 
       if (a,b) ∈ P_k(A,R,σ) then R_social2(A,R,σ) ranks a over b.  
(4)  For all σ ∈ L(R,A), all integers k ≥ 0 and all a,b ∈ A, 
       if R_social2(A,R,σ) ranks a over b and a ∈ Tied(P_k(A,R,σ)) 
       then Next(P_k(A,R,σ),A,R,σ) ≠ {b}.
(5)  For all σ ∈ L(R,A), R_social(A,R,σ) = R_social2(A,R,σ). 

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

R_s = R_social(A,R,σ).  
R_s2 = R_social2(A,R,σ).  
RVH = RVH(A,R,σ). 
Aff = Affirmed(A,R,σ).  
P_k = P_k(A,R,σ) for all integers k ≥ 0. 
Tied_k = Tied(P_k) for all integers k ≥ 0. 
TT_k = TopTied(P_k) for all integers k ≥ 0. 
Next_k = Next(P_k,σ) for all integers k ≥ 0. 

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

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

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

Irreflexivity of P₀ (that is, (a,a) ∉ P₀ for all a ∈ A) follows by theorem 
"Consistency Means Acyclicity (2)" and theorem "Consistency Maintained (2)"  
and the definition of P₀().  By the definition of P_k(), it follows that P_k is irreflexive  
for all integers k ≥ 0.  Thus 1.2 is established.  

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

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

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

Since (b,a) ∉ P_k in both cases, P_k 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,b ∈ A, if (a,b) ∈ P_k 
                and Next_k = {b}, then a ∉ Tied_k.  
(1.4.2)  For all integers k ≥ 0 and all distinct a,b,c ∈ A, 
                if P_k is transitive and (a,b) ∈ P_k and Next_k = {b} 
                and (c,b) ∉ P_k, then (a,c) ∈ P_k.  

Proof of (1.4.1):  Assume (a,b) ∈ P_k and Next_k = {b}.  Since 
Next_k = {b}, b ∈ TT_k.  Since b ∈ TT_k and (a,b) ∈ P_k, it follows by 
the definition of TopTied() that a ∉ Tied_k.  Thus 1.4.1 is established. 

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

We complete the proof of 1.4 by induction:  First we show P₀ is transitive.  
Assume (a,b) ∈ P₀ and (b,c) ∈ P₀.  Since (a,b) ∈ P₀, (b,a) must be 
inconsistent with Aff.  Thus there exist (a₁,a₂),(a₂,a₃),...,(a_j-1,a_j) ∈ Aff 
such that a₁ = a and a_j = b.  Since (b,c) ∈ P₀, (c,b) must be inconsistent 
with Aff.  Thus there exist (b₁,b₂),(b₂,b₃),...,(b_h-1,b_h) ∈ Aff such that 
b₁ = b and b_h = c.  Let g = j + h.  Relabel c_i = a_i for all i ∈ {1,2,...,j}, and 
c_i = b_i-j for all i ∈ {j+1,j+2,...,g}.  Since (c₁,c₂),(c₂,c₃),...,(c_g-1,c_g) ∈ Aff 
and c₁ = a and c_g = c, this means (c,a) is inconsistent with Aff.  This implies 
(a,c) ∈ P₀, which means P₀ is transitive.  To complete the induction, pick 
any integer k > 0 and assume P_k-1 is transitive; we must show P_k is transitive.  
Assume (a,b) ∈ P_k and (b,c) ∈ P_k; we must show (a,c) ∈ P_k.  There are four 
cases to consider: 

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

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

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

Case 1.4.6:  a ≠ b and b ≠ c and a ≠ c.  There are four subcases to consider: 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Since (a,c) ∉ P_k in all four cases, P_k 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 R_social2() and induction on 1.5.2, it 
follows that R_s2 is a strict ordering of A.  That is, R_s2 ∈ L(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) ∈ P_k.  By inspection 
of the definitions of P₀() and P_k(), clearly a ≠ b.  By induction on condition 1 
of the definition of P_k(), it follows that (a,b) ∈ P_j for all integers j ≥ k.  
Furthermore, by asymmetry (1.3) and induction on condition 1 of  the definition 
of P_k(), it follows that (b,a) ∉ P_j  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 R_s2 ranks a over b and a ∈ Tied_k.  
Suppose to the contrary Next_k = {b}.  There are three cases to consider:  

Case 4.1:  (a,b) ∈ P_k.  By 1.2 (irreflexivity), a ≠ b.  Since (a,b) ∈ P_k  
and a ∈ Tied_k, it follows by the definition of TopTied() that b ∉ TT_k.  
Thus, by the definition of Next(), Next_k cannot be {b}.  But this is 
a contradiction, so case 4.1 is impossible.

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

Case 4.3:  (a,b) ∉ P_k and (b,a) ∉ P_k.  Since Next_k = {b}, it follows by 
the definition of P_k() that (b,a) ∈ P_k+1.  By 3, R_s2 ranks b over a.  
By asymmetry (1.3), R_s2 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 Next_k ≠ {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 R_s ≠ R_s2.  Then we can let x denote 
the alternative ranked highest by R_s that is not ranked as high by R_s2, and we 
can let y denote the alternative ranked highest by R_s2 that is not ranked as high 
by R_s.  Let T denote the alternatives ranked over x by R_s. (T may be empty.)  
Let T₂ denote the alternatives ranked over y by R_s2. (T₂ may be empty.)  
By construction, and since R_s is a strict ordering of A (by theorem "Properties 
of RSocial (1)") and R_s2 is a strict ordering of A (by 1), clearly the following 
three statements hold: 

(5.1)  R_s ranks x over y. 
(5.2)  R_s2 ranks y over x. 
(5.3)  T = T₂. 

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 R_social(), 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 b ∈ B, (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 b ∈ B, (b,x) ∉ Aff.  

Since R_s2 ranks all a ∈ T over all b ∈ B, by 2 and 3 the following must hold: 

(5.9)  For all a ∈ T, all b ∈ B and all integers k ≥ 0, (b,a) ∉ P_k.  

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

(5.10)  For all a ∈ T and all b ∈ B, (b,a) ∉ Aff.  

Next we establish the following proposition:  

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

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

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

(5.12)  For all b ∈ B, (b,x) ∉ P₀.  

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

(5.13)  For all b ∈ B, (b,y) ∉ P₀.  

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

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

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

(5.15)  For all b,b' ∈ B, (b,b') ∈ P_j if and only if (b,b') ∈ P₀.

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

(5.16)  For all b ∈ B, (b,x) ∉ P_j.  
(5.17)  For all b ∈ B, (b,y) ∉ P_j.  

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