Mathematical comment that might amuse LWers: the compactness theorem is equivalent to the ultrafilter lemma, which in turn is essentially equivalent to the statement that Arrow’s impossibility theorem is false if the number of voters is allowed to be infinite. More precisely, non-principal ultrafilters are the same as methods for determining elections based on votes from infinitely many voters in a way that satisfies all of the conditions in Arrow’s theorem.
Mathematical comment that some LWers might find relevant: the compactness theorem is independent of ZF, which roughly speaking one should take as meaning that it is not possible to write down a non-principal ultrafilter explicitly. If you’re sufficiently ultrafinitist, you might not trust a line of reasoning that involved the compactness theorem but purported to be related to a practical real-world problem (e.g. FAI).
The reason why compactness is not provable from ZF is that you need choice for some kinds of infinite sets. You don’t need choice for countable sets (if you have a way of mapping them into the integers that is). You can get a proof of compactness for any countable set of axioms by proving completeness for any countable set of axioms, which can be done by construction of a model as in Johnstone’s Notes on Logic and Set Theory p. 25.
the compactness theorem is equivalent to the ultrafilter lemma, which in turn is essentially equivalent to the statement that Arrow’s impossibility theorem is false if the number of voters is allowed to be infinite.
Well, I can confirm that I think that that’s super cool!
the compactness theorem is independent of ZF
As wuncidunci says, that’s only true if you allow uncountable languages. I can’t think of many cases off the top of my head where you would really want that… countable is usually enough.
Also: more evidence that the higher model theory of first-order logic is highly dependent on set theory!
I’m fascinated by but completely failing to grasp your first comment. Specifically:
Suppose we:
Take a finite set FS of N voters
Define an infinite set IS of hypothetical voters, fully indexed by the positive integers, such that hypothetical vote n+1 is the same as real vote (n mod N)+1
Use a “non-principal ultrafilter” to resolve the result
Which of Arrow’s criteria is violated when considering this to be a result of the votes in FS but not violated when considering this to be a result of the votes in IS?
Good question! It’s dictatorship. In such a situation, any non-principal ultrafilter picks out one of the congruence classes and only listens to that one.
More generally, given any partition of an infinite set of voters into a finite disjoint union of sets, a non-principal ultrafilter picks out one member of the partition and only listens to that one. In other words, a non-principal ultrafilter disenfranchises arbitrarily large portions of the population. This is another reason it’s not very useful for actually conducting elections!
which in turn is essentially equivalent to the statement that Arrow’s impossibility theorem is false if the number of voters is allowed to be infinite.
And you can achieve that, in effect, by permitting (finite) voters to express preferences using the full spectrum of real numbers, right? Since that’s equivalent to having infinite voters?
Thus, why systems like range voting avoid its consequences. (Though range voting typically limits the precision in practice.)
No, the details are very different from range voting. You still only allow each voter to pick one candidate, and the ultrafilter provides a (highly nonconstructive) way of distilling all of these votes into a winner of the election. You can get a feel for how this works by reading about what Terence Tao calls an adaptive oracle. Roughly speaking, you can arbitrarily choose winners subject to consistency with your previous choices and with the conditions in Arrow’s theorem, and the freedom of having infinitely many voters ensures that this process won’t lead to a contradiction.
In a certain sense, “ultrafilter voting” is still controlled by a sort of “virtual dictator,” so even conceptually this isn’t a strong blow to Arrow’s theorem, and in practice “ultrafilter voting” is useless because you can’t write down (non-principal) ultrafilters explicitly.
I admit I don’t know a lot about these intersecting topics, but I also don’t see the relevant difference that you’re asserting between infinite voters and infinite precision of (finite) range-voters, especially given that range voting does not, as you say, “only allow each voter to pick one candidate”
Okay, then I don’t understand what you’re saying. What do you mean by “permitting (finite) voters to express preferences using the full spectrum of real numbers” when, as I’ve said, in “ultrafilter voting” each voter is still only allowed to pick one candidate instead of expressing a degree of preference between candidates?
The voting on this thread is bizarre, but I think I know where some of my confusion comes from. I misread this comment:
No, the details are very different from range voting. You still only allow each voter to pick one candidate, and the ultrafilter provides a (highly nonconstructive) way of distilling all of these votes into a winner of the election.
I thought the bit about “you still only allow … one candidate” was about range voting, and the ultrafilter clause was referring to theorem.
Nevertheless, while you make a lot of points that are interesting in isolation, I don’t see how any of it is responsive to the question I asked, which was whether the range voting (and other systems like it) avoids the Arrow Theorem problems by allowing infinite (effective, virtual) voters.
To anyone still reading: I understand that I’ve made some logical errors in this thread, but why the severe downvoting for some honest questions? Is there a nicer way to tell someone it looks like they’re changing the topic?
I don’t see how any of it is responsive to the question I asked, which was whether the range voting (and other systems like it) avoids the Arrow Theorem problems by allowing infinite (effective, virtual) voters.
The answer is still no. Again, the details are very different. If you studied them, it would be clear to you that the details are very different. I don’t know what else there is to say. If you asked me “is an apple tasty because it behaves like an orange?” my answer would be “no, apples behave very differently from oranges” and I don’t understand what would constitute a better answer than that.
Actually, what happened here would be more like this exchange:
You: Red produce is exempt from the produce tariffs. Me: Oh! Is that why they don’t make you pay a tax on red carrots? You: The details are different there. Apples have long been used in making cider, and cider has to be taxed, but it can’t be double-taxed, and you can read about why [here]. Apples have a significantly different shape from carrots, and the necessity of certain infrastructure has led to shape influencing taxation. Me: Well, I don’t know about all those issues, but on the matter of whether red carrots being red gets them out of the produce tariffs, is my suggestion correct? You: I don’t even know what you’re saying now. What do you mean by “red carrots being red” when, as I’ve said, apples can be used for cider? Look, just study tax law, I can’t conceive of how I can provide any other kind of reply.
That’s a simple substitution of what happened here:
You: Infinite-voter systems avoid the consequences of Arrow’s Theorem. Me: Oh, is that why range voting avoids it? You: The details are different there. Ultrafilter voting provides a way to select a winner, similar to how an adaptive oracle works. It allows you to choose winners in a way that satisfies the Arrow constraints. Me: Well, I don’t know about all those issues, but on the matter of whether range voting being effectively infinite-voter (via infinite precision), and infinite-voter systems avoiding the consequences of Arrow’s Theorem, am I right? You: What do you mean “being effectively infinite voter … infinite precision”, when ultrafilter voting has you just vote for one candidate? Look, just study the topic, I can’t conceive of how I could reply differently.
No, it really isn’t. A closer analogy is that produce that is either red or orange is exempt from the produce tariffs, ultrafilter voting is red, and range voting is orange. If you aren’t willing to study the details then I am not going to respond any further. I’ve paid 10 karma to respond now entirely because I think ultrafilters are great and people should learn about them, but they have nothing to do with range voting.
So were you wrong to say that all “infinite voter systems avoid the consequences of Arrow’s Theorem” (“both red and orange are exempt”), or were you wrong to reject my point about range voting’s infinite effective voters being proof that it avoids the consequences of Arrow’s Theorem?
On the one hand, you want to say that the broad principle is true (“apples and oranges are exempt”/”all infinite voter systems are exempt”), but on the other hand, you don’t want to agree that the broad principle has the implications I suggested (“Navals are oranges and thus exempt”/”Range voting has infinite voters as is thus exempt”).
And a resolution of that inconsistency really does not require a thorough review of the cited sources.
There’s a superficial similarity, in that both situations (infinite voters, and real-number range voting) have an uncountable ballot space. Where by ballot space I mean the set of all possible combinations of votes for all voters. But otherwise, it’s not really equivalent at all. For one thing, range voting doesn’t actually require infinite precision. Even if the only values allowed are {0, 1, 2, …, 10} it still gets around Arrow’s theorem, right? Even though you actually have a finite ballot space in this case.
Mathematical comment that might amuse LWers: the compactness theorem is equivalent to the ultrafilter lemma, which in turn is essentially equivalent to the statement that Arrow’s impossibility theorem is false if the number of voters is allowed to be infinite. More precisely, non-principal ultrafilters are the same as methods for determining elections based on votes from infinitely many voters in a way that satisfies all of the conditions in Arrow’s theorem.
Mathematical comment that some LWers might find relevant: the compactness theorem is independent of ZF, which roughly speaking one should take as meaning that it is not possible to write down a non-principal ultrafilter explicitly. If you’re sufficiently ultrafinitist, you might not trust a line of reasoning that involved the compactness theorem but purported to be related to a practical real-world problem (e.g. FAI).
The reason why compactness is not provable from ZF is that you need choice for some kinds of infinite sets. You don’t need choice for countable sets (if you have a way of mapping them into the integers that is). You can get a proof of compactness for any countable set of axioms by proving completeness for any countable set of axioms, which can be done by construction of a model as in Johnstone’s Notes on Logic and Set Theory p. 25.
Well, I can confirm that I think that that’s super cool!
As wuncidunci says, that’s only true if you allow uncountable languages. I can’t think of many cases off the top of my head where you would really want that… countable is usually enough.
Also: more evidence that the higher model theory of first-order logic is highly dependent on set theory!
I’m fascinated by but completely failing to grasp your first comment. Specifically:
Suppose we:
Take a finite set FS of N voters
Define an infinite set IS of hypothetical voters, fully indexed by the positive integers, such that hypothetical vote n+1 is the same as real vote (n mod N)+1
Use a “non-principal ultrafilter” to resolve the result
Which of Arrow’s criteria is violated when considering this to be a result of the votes in FS but not violated when considering this to be a result of the votes in IS?
Good question! It’s dictatorship. In such a situation, any non-principal ultrafilter picks out one of the congruence classes and only listens to that one.
More generally, given any partition of an infinite set of voters into a finite disjoint union of sets, a non-principal ultrafilter picks out one member of the partition and only listens to that one. In other words, a non-principal ultrafilter disenfranchises arbitrarily large portions of the population. This is another reason it’s not very useful for actually conducting elections!
And you can achieve that, in effect, by permitting (finite) voters to express preferences using the full spectrum of real numbers, right? Since that’s equivalent to having infinite voters?
Thus, why systems like range voting avoid its consequences. (Though range voting typically limits the precision in practice.)
No, the details are very different from range voting. You still only allow each voter to pick one candidate, and the ultrafilter provides a (highly nonconstructive) way of distilling all of these votes into a winner of the election. You can get a feel for how this works by reading about what Terence Tao calls an adaptive oracle. Roughly speaking, you can arbitrarily choose winners subject to consistency with your previous choices and with the conditions in Arrow’s theorem, and the freedom of having infinitely many voters ensures that this process won’t lead to a contradiction.
In a certain sense, “ultrafilter voting” is still controlled by a sort of “virtual dictator,” so even conceptually this isn’t a strong blow to Arrow’s theorem, and in practice “ultrafilter voting” is useless because you can’t write down (non-principal) ultrafilters explicitly.
I admit I don’t know a lot about these intersecting topics, but I also don’t see the relevant difference that you’re asserting between infinite voters and infinite precision of (finite) range-voters, especially given that range voting does not, as you say, “only allow each voter to pick one candidate”
Okay, then I don’t understand what you’re saying. What do you mean by “permitting (finite) voters to express preferences using the full spectrum of real numbers” when, as I’ve said, in “ultrafilter voting” each voter is still only allowed to pick one candidate instead of expressing a degree of preference between candidates?
Well, then I don’t understand why you’re refuting claims about range voting by making claims about ultrafilter voting.
Edit: It turns out that this was the result of misreading the first two sentences of this comment.
I’m… not?
The voting on this thread is bizarre, but I think I know where some of my confusion comes from. I misread this comment:
I thought the bit about “you still only allow … one candidate” was about range voting, and the ultrafilter clause was referring to theorem.
Nevertheless, while you make a lot of points that are interesting in isolation, I don’t see how any of it is responsive to the question I asked, which was whether the range voting (and other systems like it) avoids the Arrow Theorem problems by allowing infinite (effective, virtual) voters.
To anyone still reading: I understand that I’ve made some logical errors in this thread, but why the severe downvoting for some honest questions? Is there a nicer way to tell someone it looks like they’re changing the topic?
The answer is still no. Again, the details are very different. If you studied them, it would be clear to you that the details are very different. I don’t know what else there is to say. If you asked me “is an apple tasty because it behaves like an orange?” my answer would be “no, apples behave very differently from oranges” and I don’t understand what would constitute a better answer than that.
Actually, what happened here would be more like this exchange:
You: Red produce is exempt from the produce tariffs.
Me: Oh! Is that why they don’t make you pay a tax on red carrots?
You: The details are different there. Apples have long been used in making cider, and cider has to be taxed, but it can’t be double-taxed, and you can read about why [here]. Apples have a significantly different shape from carrots, and the necessity of certain infrastructure has led to shape influencing taxation.
Me: Well, I don’t know about all those issues, but on the matter of whether red carrots being red gets them out of the produce tariffs, is my suggestion correct?
You: I don’t even know what you’re saying now. What do you mean by “red carrots being red” when, as I’ve said, apples can be used for cider? Look, just study tax law, I can’t conceive of how I can provide any other kind of reply.
That’s a simple substitution of what happened here:
You: Infinite-voter systems avoid the consequences of Arrow’s Theorem.
Me: Oh, is that why range voting avoids it?
You: The details are different there. Ultrafilter voting provides a way to select a winner, similar to how an adaptive oracle works. It allows you to choose winners in a way that satisfies the Arrow constraints.
Me: Well, I don’t know about all those issues, but on the matter of whether range voting being effectively infinite-voter (via infinite precision), and infinite-voter systems avoiding the consequences of Arrow’s Theorem, am I right?
You: What do you mean “being effectively infinite voter … infinite precision”, when ultrafilter voting has you just vote for one candidate? Look, just study the topic, I can’t conceive of how I could reply differently.
No, it really isn’t. A closer analogy is that produce that is either red or orange is exempt from the produce tariffs, ultrafilter voting is red, and range voting is orange. If you aren’t willing to study the details then I am not going to respond any further. I’ve paid 10 karma to respond now entirely because I think ultrafilters are great and people should learn about them, but they have nothing to do with range voting.
So were you wrong to say that all “infinite voter systems avoid the consequences of Arrow’s Theorem” (“both red and orange are exempt”), or were you wrong to reject my point about range voting’s infinite effective voters being proof that it avoids the consequences of Arrow’s Theorem?
On the one hand, you want to say that the broad principle is true (“apples and oranges are exempt”/”all infinite voter systems are exempt”), but on the other hand, you don’t want to agree that the broad principle has the implications I suggested (“Navals are oranges and thus exempt”/”Range voting has infinite voters as is thus exempt”).
And a resolution of that inconsistency really does not require a thorough review of the cited sources.
There’s a superficial similarity, in that both situations (infinite voters, and real-number range voting) have an uncountable ballot space. Where by ballot space I mean the set of all possible combinations of votes for all voters. But otherwise, it’s not really equivalent at all. For one thing, range voting doesn’t actually require infinite precision. Even if the only values allowed are {0, 1, 2, …, 10} it still gets around Arrow’s theorem, right? Even though you actually have a finite ballot space in this case.
Right—my point was just that the infinite (effective) voters would be sufficient but not necessary.