Saturday, March 18, 2017

LaTeX Notation for Numerals

It is common in meta-mathematics to use the notation n to mean the numeral for the number n, that is: S...S(0), where S is a symbol for successor and there are n S's in the numeral for n. In LaTeX, one can typeset this notation using \overline{n} in math mode. Unfortunately, this does not always look very good: The height of the bar will vary with the height of the contained character(s), so the heights of the bars in \overline{n} and \overline{k} will not match.

The solution is to use a 'strut': an invisible (because 0 width) rule that functions only to set the height of the bar:
\newlength{\numheight}
\setlength{\numheight}{\fontcharht\font`0}
\newcommand\numeral[1]{\overline{\rule{0pt}{\numheight}#1}

It would perhaps be better to use the current font in \numheight, but I've never had a problem with this in practice.

Sunday, March 5, 2017

A Bound in Gödel 1931

When teaching Gödel's famous 1931 paper on the incompleteness theorems this semester, I got hung up on one of the bounds he gives in the course of the 45 definitions of primitive recursive notions. This is the case of concatenation. Recall that Gödel here codes finite sequences via prime factorization, so the sequence <a1, ..., an> is coded as: 2a1 × ... ×pnan, where pn is the nth prime. The 'star function' is then defined as follows:
x * y = μz≤Pr[l(x) + l(y)]x+y {∀n≤l(x)(n Gl z = n Gl x) &

     ∀n≤l(y)(0<n → (n + l(x)) Gl z = n Gl y)}
Here, l(x) is the length of the sequence x; n Gl x is the nth element of that sequence. So the definition says that x * y is the least number coding a sequence that agrees with x on its first l(x) elements and agrees with y on the next l(y) elements. Of course, there is such a number (and, actually, given how "Gl" works, there are infinitely many). The bound is needed to guarantee that * is primitive recursive.

The question, though, is how the bound is supposed to work. Gödel does not often discuss his bounds, which tend to be pretty loose, but he does explain one of them in footnote 35. And if one follows the sort of reasoning Gödel uses there, then it is difficult to see how to get the bound in the above.

I asked a question about this on the Foundations of Mathematics mailing list, and Alasdair Urquhart took the bait and replied with an elegant proof showing why Gödel's bound works. I thought I'd record a version of it here, in case anyone else has a similar question.

First, we show, by a straightforward induction on n, that 2a1 × ... ×pnan ≤ pna1 + ... + an.

Now let <a1, ..., an> and <b1, ..., bm> be two sequences. The code of their concatenation is:
2a1 × ... ×pnan × pn+1b1 × ... × pn+mbm ≤ pna1 + ... + an + an+1 + ... + an+m
Moreover,
a1 + ... + an ≤ 2a1 + ... + pnan ≤ 2a1 × ... × pnan = x
and similarly for y. (Note that the last inequality depends upon the fact that none of the ai = 0, but Gödel's coding of sequences only works for positive integers.) So
a1 + ... + an + an+1 + ... + an+m ≤ x + y
which gives Gödel's bound.

Wednesday, December 14, 2016

Donald Trump is Gaslighting America

"The good news about this boiling frog scenario is that we're not boiling yet. Trump is not going to stop playing with the burner until America realizes that the temperature is too high. It's on every single one of us to stop pretending it's always been so hot in here."

Read the rest at Teen Vogue. (Yes, Teen Vogue, and see this article in Slate Outward for more on the rise of Teen Vogue.)

Attorney General Loretta Lynch on Hate Crimes and our Trumpist Future

"Muslim Americans are our friends and family members, our doctors and nurses, our police officers and firefighters. They own businesses and teach in classrooms. Thousands of them have fought for the American flag. Many have died defending it. And yet, too often—especially in the last year, following a number of tragic terrorist incidents, and amidst an increase in divisive and fearful rhetoric—we have seen Muslim Americans targeted and demonized simply because of their faith. And to impose a blanket stereotype on all members of any faith because of the actions of those who pervert that faith is to go backwards in our thinking and our discourse, and to repudiate the founding ideals of this country."

Read more at Slate.

Tuesday, December 6, 2016

Abortion: An Allegory

Angelina Rosario went into Our Lady of Mercy Hospital in Santa Cristina, California, last week for a minor procedure to help with her dysmennorhea and walked out pregnant. The hospital is still trying to figure out exactly what happened. There was also another woman, Rosaria Angelino, there that day. Ms Angelino had been undergoing fertility treatment and was scheduled to have several embryos implanted in her uterus. Somehow, their charts got mixed up as they were taken into adjoining operating rooms. (There was a small earthquake about that time, and there is some evidence that the charts were knocked off the women’s gurneys.) The error was not discovered until the two women woke up in recovery. Ms Angelino was surprised to find that she had gotten an ablasion, but not nearly as shocked as Ms Rosario was to discover that she was pregnant.

Thursday, December 1, 2016

"Why Are There Lesbians?" Asks Circuit Court Judge Richard Posner

Absolutely fantastic, and really quite funny, article over at Outward about arguments yesterday at the 7th Circuit Court of Appeals concerning what may turn out to be a landmark LGBTQ discrimination case.