We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in "propositional" fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The "pure," propositional fragment FLR 0 turns out to coincide with the iteration theories of . Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.
What Gödel accomplished in the decade of the 1930s before joining the Institute changed the face of mathematical logic and continues to influence its development. As you gather from my title, I’ll be talking about the most famous of his results in that period, but first I want to indulge in some personal reminiscences. In many ways this is a sentimental journey for me. I was a member of the Institute in 1959-60, a couple of years after receiving my PhD (...) at the University of California in Berkeley, where I had worked with Alfred Tarski, another great logician. The subject of my dissertation was directly concerned with the method of arithmetization that Gödel had used to prove his theorems, and my main concern after that was to study systematic ways of overcoming incompleteness. Mathematical logic was going through a period of prodigious development in the 1950s and 1960s, and Berkeley and Princeton were two meccas for researchers in that field. For me, the prospect of meeting with Gödel and drawing on him for guidance and inspiration was particularly exciting. I didn’t know at the time what it took to get invited. Hassler Whitney commented for an obituary notice in 1978 that “it was hard to appoint a new member in logic at the Institute because Gödel could not prove to himself that a number of candidates shouldn’t be members, with the evidence at hand.” That makes it sound like the problem for Gödel was deciding who not to invite. Anyhow, I ended up being one of the lucky few. (shrink)
Charles Whitney correctly reports that I believe that the greatest problems facing humanity are the nuclear threat and overpopulation. Both situations can lead -- one directly and the other indirectly -- to massive self-destruction. But he apparently contends that these problems exist as a result of political policies, and that they require a political solution. And by this token, he thinks, the greater problem for humanity is political organization. He goes on to lament that we, as a people, have (...) been unable to work democratically to solve these problems. He writes: "I am suggesting that overpopulation and the nuclear threat are to a significant degree functions of the fact that people are prevented from associating as equals in more than local ways -- and of people's belief that they can't associate effectively.". (shrink)