By “voting”, I mean the following general problem: Suppose there are candidates and voters. Each voter produces a total ordering of all candidates. A voting procedure is a function which takes as input all orderings, and produces an output ranking of all candidates. Arrow’s impossibility theorem states that there is really no satisfactory voting procedure when the number of candidates is greater than 2 (majority rule is a good voting procedure when there are two candidates).
In the book Good and Real, author Gary Drescher, who received his PhD from MIT’s AI lab, defends the view that determinism is a consistent and coherent view of the world. In doing so, he enters many different arenas: ethics, decision theory, and physics.
In his chapter on quantum mechanics, he defends the “many-worlds” interpretation (although he doesn’t think the term accurately describes the concept) versus the Copenhagen interpretation. In the process of doing so, he does something I thought was extraordinary: he comes up with a simple model of quantum mechanics in which all of the standard concepts you read about: the two-slit experiment, the Heisenberg uncertainty principle, etc., are represented. This model requires no prerequisites from physics and actually uses almost totally discrete mathematics!
(Edit: I somehow missed this when originally writing this post, but Drescher also outlines quantish physics in an online paper.)
I’ll sketch it below.
A function from to is called even if for all , . We might call it even about the point if, for all , .
Conversely, we can call a function strongly non-even if for all , , .
Finding strongly non-even functions is easy, as any injective function provides a trivial example. We can make things harder for ourselves by considering only functions from to . But now, it is just as easy to show that there are no strongly non-even functions.
Therefore, let’s make the following definition: Let a function be non-even of order if, for all , . Thus, a strongly non-even function is non-even of order , and a function being non-even of order implies that it’s non-even of order for all .
In this paper, the set theorists Peter Komjáth and Saharon Shelah proved:
The existence of a non-even function of order 1 is equivalent to the Continuum Hypothesis (i.e., the statement that ).
Thus, if we assume that there is a non-even function of order 1, then we can conclude that . Can we weaken the hypothesis and still conclude something interesting? We can, as they also proved:
For any , if there is a non-even function of order , then .
You may have heard about the Tarski-Seidenberg theorem, which says that the first-order theory of the reals is decidable, that the first-order theory of the complex numbers is similarly decidable, or that the first order theory of the integers without multiplication is decidable.
In the course of John Harrison‘s logic textbook Handbook of Practical Logic and Automated Reasoning, all three of these algorithms (and many more) are implemented. Furthermore, you can download and play with them for free. (However, I still recommend checking out the book: especially if you are looking for a good textbook for a course on logic with a concrete, computational bent.)
Below, I’ll describe how to install the programs and try them out. There are many more interesting functions in this suite that I haven’t described.
Suppose that you’re translating an ancient text, and in this text you come across three words whose meaning you are unsure of: , , and . So, you head down to the ancient language department of your local university.
The first professor you come across, , knows what means, the second professor you come across, , knows what means, and the third professor you come across, , knows what means. So you have fortunately solved your problem.
But you’re now curious and decide to meet some other professors in the department. The next professor you come across is named . He doesn’t know what means or what means, but if you told him what meant, he would be able to tell you what means (for example, maybe he knows that is the noun form of ).
The next professor you meet is named . If you told him what meant and what meant, he would be able to tell you what means.
The next professor you meet is named . If you told him a method for finding out the meaning of given the meaning of , he would be able to tell you the meaning of .
In general, for any two professors and , there is a professor with the property that if you told him what knew, he would be able to tell you what knows (but doesn’t know any more than that).
Notice that some professors have essentially the same state of knowledge. For example, and have essentially the same knowledge, since to get the meaning of out of you only have to tell him a method for finding out the meaning of given the meaning of , which is something that you can do without any particular special knowledge concerning , and .
A more nontrivial example is that has the same state of knowledge as . This is because each can “simulate” the other. In one direction, suppose somebody told the meaning of . He therefore knows a trivial “method” for getting the meaning of given any inputs, and so he knows the meaning of . In the other direction, suppose we told a method for turning (methods for turning the meaning of into the meaning of ) into the meaning of . Well, knows a method for turning the meaning of into the meaning of , so he can use that find the meaning of . He can then use his method a second time to turn that into the meaning of .
The puzzle is then to prove that there are only finitely many professors with different states of knowledge.
This puzzle is equivalent to showing that intuitionistic implicational propositional logic over three variables has only finitely many logically inequivalent formulas. Another formulation is: Let be the free cartesian closed category over objects. Given objects and , say that and are equivalent if there is an arrow from to and an arrow from to . Then there are only finitely many equivalence classes in . (The corresponding statements are also true with replaced by .)
Let be Peano Arithmetic. Gödel’s Second Incompleteness Theorem says that no consistent theory extending can prove its own consistency. (I’ll write for the statement asserting ‘s consistency; more on this later.)
In particular, is stronger than . But certainly, given that we believe that everything proves is true, we believe that does not prove a contradiction, and hence is consistent. Thus, we believe that everything that proves is true. But by a similar argument, we believe that everything that proves is true. Where does this stop? Once we believe that everything proves is true, what, exactly, are we committed to believing?
Let be a -periodic function. It may or may not have a representation as a trigonometric series
A natural question to ask is whether or not the representation of as a trigonometric series is unique, if it has one. It was the consideration of this question that led Cantor to the invention of set theory.
There is a nice writeup of this story in the first part of this article by Alexander Kechris. I’ll give part of the story below.