Hacker News Reader

Comment by danbruc | Hacker News Reader

But what if there are infinitely many voters v0, v1, v2, … ? What does it mean for there to be a majority in favour? AC implies that there exists an infinitary voting scheme but supplies not a hint about how it could work.

This already leaves me confused. I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices, not that there is a way of combining a single [infinite] set of votes into a voting result. I guess it also says that there is a way to pick one of the votes from the [infinite] set of votes, but how does it imply that this choice can or must conform with the properties we want from a voting scheme?

View on HN

In this context I believe that the author is thinking of AC as Zorn's Lemma.

I will try to make a draft of a possible expansion of the reasoning.

Take the set V of functions P(N) -> {Ma,Mi,Un} that for each subset of the naturals classifies it as a majority, a minority, or undecided respecting the conditions in the article.

P(A) = Ma ⇔ P(A') = Mi

P(A) = Ma ⇔ P(A ∪ B) = Ma

P(A) = Ma ⇒ P(A \ {n}) = Ma

P(A) = Ma ∧ P(B) = Ma => P(A ∩ B) = Ma

It is easy to prove that such a function exists f_0 (A) = Mi if |A| ∈ N, f_0 (A) = Ma if |A| = ∞, and f_0 (A) = Un otherwise.

It is harder to prove that there is a such a function that also respects P(A) = Ma ∨ P(A) = Mi for subsets of the naturals.

I believe that to prove this you pretty much have to use Zorn's Lemma with the order f ≤ g ⇔ (f(A) ≤ g(A)) for all A where Un ≤ Ma, Un ≤ Mi, but Mi ≰ Ma and Ma ≰ Mi.

I feel like you can prove that the hypothesis of Zorn's Lemma are satisfied in this case.

But is is easy to see how without ZL or something similar you would have to decide one-by-one how whether each non-finite non-cofinite set maps to Mi or Ma, but there are uncountably many of them to do by simple induction.

Would the odd end even numbers not both be classified as Ma by f_0 and therefore violate the first condition?

I made a mistake in the definition of f_0, here is the correct version:

f_0(A) = Mi if and only if |A| ∈ N

f_0(A) = Ma if and only if |A'| ∈ N

f_0(A) = Un if and only if |A| = ∞ ∧ |A'| = ∞

I mixed up the concept of infinite and cofinite in my previous comment, oops.

Actually I just realized that an even simpler example of a function satisfying the conditions would be f_1(A) = Un for all A, which is also the global minimum of the entire set.

> I thought the axiom of choice says that it is possible to obtain an [infinite] set of votes from an [infinite] set of voters each with a non-empty set of choices

The axiom of choice does say this but,

1) This is not where we are applying the axiom of choice

2) You don't need the axiom of choice here: you can always just pick the "voting set" where everyone votes for choice # 1.

The axiom of choice says that the product of infinitely many non-empty sets is empty. This is needed only when you might have a different and non-computable set of choices to make at each step.

Where we are applying the axiom of choice here is: the voting scheme is just a rephrasing of an "Ultrafilter on the power set of a set": https://en.wikipedia.org/wiki/Ultrafilter#Ultrafilter_on_the... This is implied by the axiom of choice in a way that requires some working out (and is sketched in wikipedia). But you can roughly see how the axiom of choice comes about if you start trying to construct a voting scheme (the following is just intuition):

1) We know the result if the number of "Nays" or "Yays" is finite.

2) Pick any set of "Yays" so the number of "Nays" and "Yays" is both infinite. Declare this set (arbitrarily) as a victory for either "Nay" or "Yay"

3) The set in (2) implies that a bunch of other sets are either Nay or Yay by the axioms in the article (e.g. flipping all votes flips the outcome, etc)

4) While there are sets we haven't decided on, repeat steps (2) and (3).

Of course (4) is the whole tricky part, since you have to describe with this "looping forever" means rigorously... but you can see how the idea of "making infinitely distinct choices" comes up.

> The axiom of choice says that the product of infinitely many non-empty sets is empty.

You mean non-empty.

Okay, I got this, the axiom of choice is not even needed for finite sets of choices, it comes into play elsewhere. But there are quite a few more points where I can not understand the reasoning behind. Not saying that they are incorrect, only that they are not obvious to me.

Given any set of voters, either it or its complement is a majority, but not both

Why no draws, like the odd numbered voters versus the even numbered voters?

The result of removing a single voter from a majority is still a majority.

This is not true for finite sets of voters, why would we require it for infinite sets of voters? This seems more like a possible consequence of dealing with an infinite set of voters than something one would require in advance.

The intersection of two majorities is a majority

Also not true for finite sets of voters, so the same question as above.

Reply on news.ycombinator.com