Arrow's theorem for social choice functions 

Let X denote the set of alternatives.  Assume X is finite.  
For all A Í X, call A an agenda. (The "nominated" subset of alternatives.)  
Let N = {1,2,...,n} denote the set of voters.  Assume N is finite and n ³ 1.  
Let  denote all possible orderings of X.  
Let Âⁿ denote all possible profiles of votes. (Each profile contains one ordering per voter). 
For all V Î Âⁿ and all i Î N, let V_i denote the vote within profile V voted by voter i.  
For all V Î Âⁿ, all i Î N and all x,y Î X, write xV_iy if and only if V_i ranks x over y. 

Call a mapping C : 2^X ´ Âⁿ ® 2^X a social choice function. (That is, given any agenda 
and any profile of votes, a social choice function chooses a subset of the alternatives.  
Typically we desire that only one alternative be chosen, but for generality we allow more 
than one and assume that in such cases some subsequent procedure such as a coin toss 
would be used to elect one of those chosen.) 

Some desirable criteria on which to compare social choice functions:  

Prime Directive:  [A ¹ f Þ C(A,V) ¹ f] & [C(A,V) Í A]. (At least one nominee 
must be chosen if any alternatives are nominated, and only nominees may be chosen.) 

Independence from Irrelevant Alternatives (IIA):  V|_A = V'|_A Þ C(A,V) = C(A,V'), 
where V|_A is the restriction of the votes in profile V to the alternatives in agenda A. 

Unanimity:  [x Î A & xV_iy "i Î N] Þ y Ï C(A,V). 

Consistency:  [{x,y} Í A & C(A,V) Ç {x,y} = {x} & {x,y} Í A'] Þ y Ï C(A',V). 

Non-dictatorship:  There is no i Î N such that [x Î A & xV_iy Þ y Ï C(A,V)]. 

Arrow's Theorem:  If #X ³ 3 and C is a social choice function that satisfies prime directive, 
IIA, unanimity and consistency, then C violates non-dictatorship. 

Proof:  (Patterned after a proof by John Geanakoplos [2001].)  Assume #X ³ 3 and C is 
a social choice function that satisfies prime directive, IIA, unanimity and consistency.  
First we establish the following claim:  

(1)  For all x Î X, let Â(x) denote the orderings of X that rank x either strictly 
top or strictly bottom.  For all x Î X and all V Î Âⁿ, if V_i Î Â(x) "iÎN, 
then one of the following two conditions holds: 
        (1.1)  {x} = C({x,y},V) "yÎX\{x}.
        (1.2)  {y} = C({x,y},V) "yÎX\{x}. 

Proof of (1):  Pick any x Î X and any V Î Âⁿ such that V_i Î Â(x) "iÎN.  
If (1.1) holds, we are done.  Suppose (1.1) does not hold.  We must show (1.2) holds.  
Since (1.1) does not hold, there exists z Î X\{x} such that the following holds: 
        (1.3)  z Î C({x,z},V).  
Since #X ³ 3, we can pick y Î X\{x,z}.  Construct a profile V' Î Âⁿ that is the same 
as V except y is moved immediately over z in every vote in V'.  Since x is at the top 
or bottom of each V_i, the relative orderings of x and y are the same in V' as in V, 
and the relative orderings of x and z are the same in V' as in V.
Thus the following three statements hold: 
        (1.4)  V|_{x,z} = V'|_{x,z}. 
        (1.5)  V|_{x,y} = V'|_{x,y}. 
        (1.6)  yV'_iz "iÎN. 
By 1.6 and unanimity, z Ï C({x,y,z},V').                                           (1.7) 
By 1.7 and the prime directive, C({x,y,z},V') Ç {x,y} ¹ f.                (1.8)
Next we show x Ï C({x,y,z},V').  Suppose to the contrary x Î C({x,y,z},V').  
By 1.7 and consistency, z Ï C({x,z},V').  By 1.4 and IIA, z Ï C({x,z},V).  But 
this contradicts 1.3, so the contrary assumption cannot hold, so x Ï C({x,y,z},V').  
Since C({x,y,z},V') Ç {x,z} = f, by the prime directive {y} = C({x,y,z},V').  
By consistency, {y} = C({x,y},V').  By 1.5 and IIA, {y} = C({x,y},V).  
Since y was an arbitrary alternative in X\{x,z}, the following must hold:  
        (1.9)  {y} = C({x,y},V) "y Î X\{x,z}. 
Statement 1.9 is close to 1.2, which we are aiming to establish.  It remains only to 
show {z} = C({x,z},V).  Note that, by 1.9, 1.3 still holds if we swap the labels of 
y and z.  Thus, by the same reasoning that led from 1.3 to 1.9, 1.9 still holds if we 
swap the labels of y and z.  Thus {z} = C({x,z},V).                              (1.10) 
By 1.9 and 1.10, {y} = C({x,y},V) "yÎX\{x}.  
Thus 1.2 holds when 1.1 does not, establishing (1).

Next we establish the following claim:  

(2)  For all x Î X there exists a voter d Î N such that, for all V Î Âⁿ and 
all y,z Î X\{x}, if yV_dz then {y} = C({y,z},V). (In other words, for each 
alternative x some voter dictates over all pairs of alternatives distinct from x.) 

Proof of (2):  Pick any x Î X.  Pick any profile V⁰ Î Âⁿ such that each vote in V⁰  
ranks x strictly bottom.  That is, yV⁰_ix for all y Î X\{x}and all i Î N.      (2.1)
By unanimity, {y} = C({x,y},V⁰) for all y Î X\{x}.                               (2.2)  
Recall that n is the number of voters.  Construct a sequence of n admissible 
profiles V¹, V², ..., Vⁿ Î Âⁿ such that each profile V^k is the same as V⁰ except 
that voters 1 to k rank x strictly top instead of bottom.  That is, all three of the 
following conditions hold for all k Î {1,2,...,n}: 
        (2.3)  [yV^k_iz if and only if yV⁰_iz] for all y,z Î X\{x}and all i Î N. 
        (2.4)  xV^k_iy for all y Î X\{x} and all i Î {1,2,...,k}. 
        (2.5)  yV^k_ix for all y Î X\{x} and all i Î {k+1,...,n}. 
By 2.4, all votes in Vⁿ rank x strictly top. 
Thus, by unanimity, {x} = C({x,y},Vⁿ) "y Î X\{x}.                            (2.6)
By 1, for each k Î {0,1,...,n}, one of the following two conditions must hold: 
        (2.7)  {x} = C({x,y},V^k) "y Î X\{x}. 
        (2.8)  {y} = C({x,y},V^k) "y Î X\{x}.
By 2.6, 2.8 does not hold for k = n, so we can let d denote the smallest integer in 
{0,1,...,n} such that 2.8 does not hold for k = d.  This means 2.7 holds for k = d:  
        (2.9)  {x} = C({x,y},V^d) "y Î X\{x}.  
By 2.2, d ¹ 0, so d > 0.  Thus d-1 ³ 0.  By construction, 2.8 holds for k = d-1: 
        (2.10)  {y} = C({x,y},V^d-1) "y Î X\{x}. 
Since #X ³ 3, we can pick distinct y,z Î X\{x}.  Construct a profile V" Î Âⁿ  
that is the same as V^d  except V"_d moves y to the top (so x is next-to-top).  
Note that the relative orderings of x and z are the same in V" as in V^d.  That is, 
V"|_{x,z} = V^d|_{x,z}.  By 2.9 and IIA, {x} = C({x,z},V").                       (2.11) 
Also, the relative orderings of x and y are the same in V" as in V^d-1.  That is, 
V"|_{x,y} = V^d-1|_{x,y}.  By 2.10 and IIA, {y} = C({x,y},V").                  (2.12) 
By 2.11 and consistency, z Ï C({x,y,z},V").                                        (2.13) 
By 2.12 and consistency, x Ï C({x,y,z},V").                                       (2.14) 
By 2.13, 2.14 and the prime directive, {y} = C({x,y,z},V").                (2.15) 
By 2.15 and consistency, z Ï C({y,z},V").                                           (2.16) 
By 2.16 and the prime directive, {y} = C({y,z},V").                            (2.17)  
Since the relative orderings of y and z in V⁰ were arbitrary, the relative orderings 
of y and z in V" were arbitrary except for voter d, who ranks y over z in V".  
Thus, by 2.17 and IIA, {y} = C({y,z},V) for all V Î Âⁿ such that yV_dz. 
Since y and z were distinct but arbitrary alternatives distinct from x, by the same 
reasoning as above the following must hold for all distinct y,z Î X\{x}: 
        (2.18)  For all profiles V Î Âⁿ, if yV_dz then {y} = C({y,z},V). 
Since [not zV_dz] for all z Î X, 2.18 also holds (vacuously) when y = z.  
Thus, there exists a voter, voter d, who dictates over all y,z Î X\{x}.  
Since x was picked arbitrarily, (2) is established.  

Since #X ³ 3, we can pick distinct x,y,z Î X.  By 2, there are one or more voters i,j,k Î N  
(not necessarily distinct) such that i dictates over y and z, j dictates over x and z, and k  
dictates over x and y.  We will show i = j = k.  Suppose the contrary, meaning we are 
dealing with two or three "dictatorial" voters.  This means we can pick a profile V Î Âⁿ  
such that yV_iz and zV_jx and xV_ky.  Since the two or three voters dictate over their 
respective pairs, {y} = C({y,z},V) and {z} = C({x,z},V) and {x} = C({x,y},V).  
By consistency, z Ï C({x,y,z},V) and x Ï C({x,y,z},V) and y Ï C({x,y,z},V).  
Thus C({x,y,z},V) Ç {x,y,z} = f.  But this contradicts the prime directive.  
Thus the contrary assumption cannot hold, so i = j = k.  Since x, y and z were 
picked arbitrarily, it follows that this voter, i = j = k, is a dictator over all pairs of 
alternatives.  That is, xV_iy Þ {x} = C({x,y},V) for all distinct x,y Î X and all V Î Âⁿ.  
By consistency, [x Î A & xV_iy] Þ y Ï C(A,V) for all distinct x,y Î X, all A Î 2^X 
and all V Î Âⁿ.  Thus C violates non-dictatorship, as we set out to prove.