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
(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