Qiaochu_Yuan comments on Godel's Completeness and Incompleteness Theorems - Less Wrong

34 Post author: Eliezer_Yudkowsky 25 December 2012 01:16AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (85)

Comments (85)

Sort By: Best

You are viewing a single comment's thread.

Comment author: Qiaochu_Yuan 25 December 2012 10:50:51AM * 21 points [-]

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).

Comment author: wuncidunci 25 December 2012 01:39:45PM 8 points [-]

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.

Comment author: bryjnar 25 December 2012 02:20:46PM 3 points [-]

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!

Comment author: roystgnr 31 December 2012 02:54:09AM * 2 points [-]

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?

Comment author: Qiaochu_Yuan 31 December 2012 03:38:20AM * 4 points [-]

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!

Comment author: SilasBarta comment score below threshold [+] (12 children)

Comment author: Qiaochu_Yuan 29 December 2012 09:16:37PM * 2 points [-]

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.

Comment author: SilasBarta comment score below threshold [+] (8 children)

Comment author: Qiaochu_Yuan 30 December 2012 03:15:28AM * 2 points [-]

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?

Comment author: SilasBarta comment score below threshold [+] (6 children)

Comment author: Qiaochu_Yuan 31 December 2012 06:40:22AM 3 points [-]

I'm... not?

Comment author: SilasBarta 03 January 2013 10:01:55PM 0 points [-]

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?

Comment author: Qiaochu_Yuan 03 January 2013 10:10:01PM 0 points [-]

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.

Comment author: SilasBarta 03 January 2013 10:41:35PM * -1 points [-]

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.

continue this thread »

Comment author: nshepperd 30 December 2012 03:33:04AM 1 point [-]

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.

Comment author: SilasBarta 31 December 2012 05:40:24AM 0 points [-]

Right -- my point was just that the infinite (effective) voters would be sufficient but not necessary.

Qiaochu_Yuan comments on Godel's Completeness and Incompleteness Theorems - Less Wrong

Article Navigation

Comments (85)

Nearest Meetups

Virtual Study Room

Recent Comments

Recent Posts

Recent Rationality Quotes

Recent Wiki Edits

Top Contributors, 30 Days

Recent Karma Awards

Comments (85)

Top Contributors, 30 Days

You'll need to login or register to do that

(Don't worry, it only takes a few seconds)

Create

Login