By “voting”, I mean the following general problem:  Suppose there are $n$ candidates and $m$ voters.  Each voter produces a total ordering of all $n$ candidates.  A voting procedure is a function which takes as input all $m$ orderings, and produces an output ranking of all $n$ 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).

Filed under Uncategorized

## Quantish Physics: A Discrete Model of Quantum Physics

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.

Filed under Uncategorized

## Functions with Very Low Symmetry and the Continuum Hypothesis

A function from $\mathbb{R}$ to $\mathbb{R}$ is called even if for all $h\in\mathbb{R}$, $f(-h) = f(h)$.  We might call it even about the point $x$ if, for all $h\in\mathbb{R}$, $f(x-h) = f(x +h)$.

Conversely, we can call a function strongly non-even if for all $x\in\mathbb{R}$, $h>0$, $f(x-h)\ne f(x+h)$.

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 $\mathbb{R}$ to $\mathbb{N}$.  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 $f\colon \mathbb{R}\to\mathbb{N}$ be non-even of order $n$ if, for all $x$, $|\{h>0\mid f(x-h) = f(x + h)\}|\leq n$.  Thus, a strongly non-even function is non-even of order $0$, and a function being non-even of order $n$ implies that it’s non-even of order $m$ for all $m\geq n$.

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 $2^{\aleph_0} = \aleph_1$).

Thus, if we assume that there is a non-even function of order 1, then we can conclude that $2^{\aleph_0} = \aleph_1$.  Can we weaken the hypothesis and still conclude something interesting?  We can, as they also proved:

For any $n$, if there is a non-even function of order $n$, then $2^{\aleph_0}\leq \aleph_{\lceil\log_2{(n+1)}\rceil}$.

Filed under Uncategorized

## A Suite of Cool Logic Programs

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.

Filed under Uncategorized

## An Interesting Puzzle in Propositional Logic

Suppose that you’re translating an ancient text, and in this text you come across three words whose meaning you are unsure of: $\mathit{bal}$, $\mathit{kat}$, and $\mathit{lot}$.  So, you head down to the ancient language department of your local university.

The first professor you come across, $\hbox{Prof. Bal}$, knows what $\mathit{bal}$ means, the second professor you come across, $\hbox{Prof. Kat}$, knows what $\mathit{kat}$ means, and the third professor you come across, $\hbox{Prof. Lot}$, knows what $\mathit{lot}$ 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 $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$.  He doesn’t know what $\mathit{bal}$ means or what $\mathit{kat}$ means, but if you told him what $\mathit{bal}$ meant, he would be able to tell you what $\mathit{kat}$ means (for example, maybe he knows that $\mathit{kat}$ is the noun form of $\mathit{bal}$).

The next professor you meet is named $\hbox{Prof. }(\mathrm{Bal}\rightarrow(\mathrm{Kat}\rightarrow\mathrm{Lot}))$.  If you told him what $\mathit{bal}$ meant and what $\mathit{kat}$ meant, he would be able to tell you what $\mathit{lot}$ means.

The next professor you meet is named $\hbox{Prof. }((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Lot})$.  If you told him a method for finding out the meaning of $\mathit{kat}$ given the meaning of $\mathit{bal}$, he would be able to tell you the meaning of $\mathit{lot}$.

In general, for any two professors $\hbox{Prof. }P$ and $\hbox{Prof. }Q$, there is a professor $\hbox{Prof. }P\rightarrow Q$ with the property that if you told him what $\hbox{Prof. }P$ knew, he would be able to tell you what $\hbox{Prof. }Q$ knows (but $\hbox{Prof. }P\rightarrow Q$ doesn’t know any more than that).

Notice that some professors have essentially the same state of knowledge.  For example, $\hbox{Prof. Bal}$ and $\hbox{Prof. }((\mathrm{Kat}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})$ have essentially the same knowledge, since to get the meaning of $\mathit{bal}$ out of $\hbox{Prof. }((\mathrm{Kat}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})$ you only have to tell him a method for finding out the meaning of $\mathit{kat}$ given the meaning of $\mathit{kat}$, which is something that you can do without any particular special knowledge concerning $\mathit{bal}$, $\mathit{kat}$ and $\mathit{lot}$.

A more nontrivial example is that $\hbox{Prof. }(((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})\rightarrow\mathrm{Kat})$ has the same state of knowledge as $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$.  This is because each can “simulate” the other.  In one direction, suppose somebody told $\hbox{Prof. }(((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})\rightarrow\mathrm{Kat})$ the meaning of $\mathit{bal}$.  He therefore knows a trivial “method” for getting the meaning of $\mathit{bal}$ given any inputs, and so he knows the meaning of $\mathit{kat}$.  In the other direction, suppose we told $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$ a method for turning (methods for turning the meaning of $\mathit{bal}$ into the meaning of $\mathit{kat}$) into the meaning of $\mathit{bal}$.  Well, $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$ knows a method for turning the meaning of $\mathit{bal}$ into the meaning of $\mathit{kat}$, so he can use that find the meaning of $\mathit{bal}$.  He can then use his method a second time to turn that into the meaning of $\mathit{kat}$.

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 $\mathbb{C}_n$ be the free cartesian closed category over $n$ objects.  Given objects $A$ and $B\in \mathbb{C}_n$, say that $A$ and $B$ are equivalent if there is an arrow from $A$ to $B$ and an arrow from $B$ to $A$.  Then there are only finitely many equivalence classes in $\mathbb{C}_3$.  (The corresponding statements are also true with $3$ replaced by $n$.)

1 Comment

Filed under Uncategorized

## What Happens When You Iterate Gödel’s Theorem?

Let $\mathrm{PA}$ be Peano Arithmetic.  Gödel’s Second Incompleteness Theorem says that no consistent theory $T$ extending $\mathrm{PA}$ can prove its own consistency. (I’ll write $\mathrm{Con}(T)$ for the statement asserting $T$‘s consistency; more on this later.)

In particular, $\mathrm{PA} + \mathrm{Con}(\mathrm{PA})$ is stronger than $\mathrm{PA}$.  But certainly, given that we believe that everything $\mathrm{PA}$ proves is true, we believe that $\mathrm{PA}$ does not prove a contradiction, and hence is consistent.  Thus, we believe that everything that $(\mathrm{PA} + \mathrm{Con}(\mathrm{PA}))$ proves is true.  But by a similar argument, we believe that everything that $(\mathrm{PA} + \mathrm{Con}(\mathrm{PA} + \mathrm{Con}(\mathrm{PA})))$ proves is true.  Where does this stop?  Once we believe that everything $\mathrm{PA}$ proves is true, what, exactly, are we committed to believing?

Filed under Uncategorized

## Trigonometric Series and the Beginnings of Set Theory

Let $f\colon\mathbb{R}\to\mathbb{R}$ be a $2\pi$-periodic function. It may or may not have a representation as a trigonometric series

$\displaystyle{a_0+\sum_{n=1}^\infty a_n\sin(nx) + b_n\cos(nx)}$

A natural question to ask is whether or not the representation of $f$ 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.