Frege's notation is great

It gets a bad rep, and I have no idea why. Propositions are really trees, that's their essence, muddled by the fact that, due to accidents of history we never see the essence, just the suppressed form of a line. Or perhaps, in everyday speech, we are too used to compound propositions being just long sequences of conjunctions, where the potential tree-ness isn't actualized. But statements are trees, and they will resists any attempts to force them to mimic something which they are not, i.e. linear sequences, by becoming obstinately hard to understand. If you don't believe me, try using nothing but the Reverse Polish Notation for any amount of time, and let me know how long it takes for it to drive you bonkers. 

The most important Master's thesis of all time

Has been defended in 1936 by Claude Shannon, and is titled A Symbolic Analysis of Relay and Switching Circuits. In it, Shannon shows that certain electric circuits are isomorphic to Boolean algebra.

On the necessary existence of the elephant in the room

There is a philosophical view which says that mathematics is a way of evolutionary signaling, i.e. an elaborate way of demonstrating fitness (in this case, intelligence) to one's potential mates. This may very well be true but there is an elephant in the room that it does not address. Which is: while the purpose of doing mathematics may be an accident of evolution, its content cannot. It is possible to conceive of a world in which this function of doing mathematics is not plausible, or even a world in which natural selection does not exist at all; however, it is not possible to conceive of a world in which theorems of mathematics are false. Provable propositions are true in every possible world. Inasmuch as mathematics contains theorems about certain modes of reasoning, it follows that there is a realm of human thinking which cannot be an accident of evolution.

Alan Turing centennial

It could be a weird contraption made of scrap metal and wood:



It could be a "2-state 3-symbol" whatchamacallit:

Or it could be a few lines of Python code.

A Universal Turing Machine, one of the most powerful concepts ever.

Judea Pearl wins the 2011 Turing Award

Judea Pearl has won the 2011 A. M. Turing Award. The citation reads: "For fundamental contributions to artificial intelligence through the development of a calculus for probabilistic and causal reasoning." The A. M. Turing Award, given annually since 1966 by the Association for Computing Machinery, is considered the "Nobel Prize of theoretical computer science." Among the recipients are Marvin Minsky, Donald Knuth and Edsger Dijkstra.

Oftentimes, notions that seem so obvious and fundamental that we take them for granted turn out to be much more complex than we initially gave them credit for. It took philosophy and science entire millenia to come up with the first logically correct and useful definition of truth, due to Alfred Tarski. It took a few more decades for Judea Pearl to do the same for the concept of cause and effect. For those of you who don't know Pearl's work, go read his book Causality; I guarantee you it will be one of the most important pieces of prose you'll ever read. (If you would like a short and non-technical introduction, just read the book's closing part Epilogue: The Art and Science of Cause and Effect.)

The gist of Pearl's idea for defining causality is that you cannot do this without first formalizing the notion of an intervention. An intervention is an act of assigning a specific value to a variable by means that are completely independent of that variable's "natural environment". In Pearl's notation, intervention is denoted by do(X = x); think of it as of choosing treatment in a randomized experiment, or as of using the assignment operator in computer programming. Pearl defines the causal effect of a variable X on variable Y as a probability distribution of Y induced by deliberately setting the value of X to x (i.e. "doing" the do(X = x)). Or, in other words, event A causes event B if and only if the smallest possible set of do() operations performed on the whole system that brings about the realization of A, brings about the realization of B as well.

This may all sound trivial, but it actually has some non-trivial implications for probabilistic reasoning, which Pearl works out in full detail. Another interesting feature of his formalization of causality is that it provides a natural framework for mathematically rigorous thinking about the old philosophical ideas of "possible worlds" and counterfactuals. For example, it makes counterfactuals non-tautological (that is, it makes them sometimes true and sometimes false, and thus interesting, as opposed to their treatment in vanilla propositional logic in which all counterfactuals are vacuously true and therefore completely useless). Here is a truth-condition of a counterfactual implied by Pearl's theory:

The proposition "If A were true then B would be true" is true if and only if in the possible world closest to ours in which A holds, B holds as well,

where world V is closest to world W iff there does not exist any world Z such that the set of do() operations required to transform W into Z is a proper subset of the set of do() operations required to transform W into V.

Bad logic, but good game theoory

John D. Cook writes:

Ad hominem arguments are bad logic, but good (Bayesian) statistics. A statement isn’t necessarily false because it comes from an unreliable source, though it is more likely to be false. (...) Some people are much more likely to know what they’re talking about than others, depending on context. You’re more likely to get good medical advice from a doctor than from an accountant, though the former may be wrong and the latter may be right.

This is true, but I don't think it's the most important reason why ad hominem arguments persist. After all, they are used also (and perhaps mostly) against reliable sources of information. The reason is game theory. Most interactions we face are signaling games of partial conflict. We talk not just to transmit information, but also to influence other people's beliefs and actions in ways that are beneficial to us. We talk to persuade more than to inform. (Of course, communicating information is a necessary condition of persuasion. You cannot persuade anyone by talking to them if they do not understand what you're saying. Language could not evolve if all human interactions were zero-sum--there wouldn't be enough coordination to establish a common understanding of messages.) Persuasion consists of sending messages of the form "given your preferences, you should do X because Y." The logical validity of such message is of course completely independent of the sender's identity; however, the truth value of the conclusion (that doing X is good for you) is not. If someone gives you a logical argument for why it's good for you to do X, it's perfectly rational for you to wonder why they want you to believe that. Perhaps it's good for them, not so much for you. In other words, it matters who it is that's telling you this, for strategic reasons. Their preferences are relevant information in terms of assessing the likelihood of the conclusion being true.

What separates ad hominem as good game theory from ad hominem as fallacy is whether you're using information about sender's identity to update your beliefs about truth value of the conclusion or about validity of the argument. Here's an example. Suppose you are a (benevolent and completely ignorant) dictator of a medium-sized country. You wonder if establishing minimum wage requirements would help low-skilled workers and, in the process of your wondering, you ask the opinion of an expert economist. The expert comes back to you with the standard microeconomic theory argument that enforcing a minimum wage higher than the market rate increases unemployment among low-skilled workers. You then find out that your expert owns a whole bunch of enterprises that depend on low-skilled labor. It's logically valid and perfectly rational for you to use that information to postpone your decision with respect to the minimum wage (for example, until you get more opinions from experts who have no stakes in the conclusion). But, it's a fallacy if that information causes you to conclude that microeconomic theory is wrong.

Formula trees

Ever had to translate a long and complicated propositional logic formula from Polish notation into standard bracket notation or the other way around? Yeah, didn't think so. Well, I'm going to offer you some advice anyway. For whatever reason it just occurred to me that the task becomes much easier if instead of trying to translate directly you first translate your formula from whichever notation you have it in into Smullyan's tree notation, and then from that into the desired final notation. So if you have a formula in Polish notation, you do the following: Put the leftmost operator at the top of the tree (that's your highest-level node); put the second-leftmost operator (if it's there) at the level-two node starting the leftmost branch of your tree; continue that branch until you hit an atomic sentence(s); put the next operator at the level-two node starting the second-to-the-left branch of the tree; continue going down then right like than until you're done.

For example, say you have ENKpqANpNq. Your leftmost operator is E (equivalence); so that's what you'll be putting at the very top of the tree:

1.

<->

Then you've got negation at a level-two node on the left:

2.

<->

~

Then conjunction one node below:

3.

<->

~

&

And then the left node hits bottom with atoms p:

4.

<->

~

&

p

...and q:

5.

<->

~

&

pq

So you move to the right and continue:

6.

<->

~ |

&

pq

7.

<->

~ |

& ~

pq

8.

<->

~ |

& ~

pq p

9.

<->

~ |

& ~~

pq p

10.

<->

~ |

& ~~

pq pq

And that's the tree, which gives ~(p & q) <-> (~p) | (~q) (one of De Morgan's laws), which is the desired translation. The reverse procedure is equally easy.

Proofs aren't meant to convince anyone

Everyone to whom it matters knows that P does not equal NP. If so, why is P vs. NP considered to be one of the most important open questions in mathematics? Why do we need to prove something everyone is already convinced is true?

This question arises from a misconception as to what it is that math does. Gian-Carlo Rota put it best:

Saying that a mathematician's job is to "prove theorems" is like saying that a novelist's job is to "write sentences."

The job of mathematics is not to verify which mathematical statements are true and which are not, but to search for reasons why true statements are true and false ones are not. The majority of original mathematical research is done not trying to settle open questions, but trying to find new and original ways of settling problems that have already been solved. Many interesting mathematical facts have been proven tens, sometimes even hundreds of times over, each time using a different method. If all mathematicians were interested in was if a statement is true, one proof would be sufficient. But when researchers are considering a mathematical statement, they are not just interested in finding out if it's true or not. They're interested in finding out exactly why it is true. Finding a proof is a necessary, though not sufficient, condition for this. In a way, for any open mathematical problem, the Holy Grail is to find the proof: one that would show both that a statement (or its negation) is true and why it is so. For example, everyone knew long time ago that polynomials of degree five are not solvable by radicals. But no one knew why until, in the process of proving this fact, Evariste Galois came up with a theory that determines a necessary and sufficient condition for a polynomial to be thus solvable, from which it becomes obvious why equations of degree greater than four are not.

Mathematicians don't know why P does not equal NP, and they are hoping that someday, one of the proofs of this proposition will answer that question. It may be unlikely that the first proof that is discovered will provide an answer; but what's certain is that there cannot be an answer without a proof of some sort. There's also another, indirect reason why proofs are important: Proofs are fruitful. They usually lead to new insights, new techniques, new theories.

For example, Gödel proved that no consistent system of axioms whose theorems can be listed by an algorithmic procedure is capable of proving all facts about the natural numbers. By proving the same fact using a very different method, Polish logician Alfred Tarski shed some light on the reason why this is true (essentially, he showed why in formal languages that are "rich enough" to contain arithmetic of natural numbers, the set of all true statements has a higher cardinality than the set of all provable statements. Since, if the notion of provability is to make any sense at all, provable statements must be true, there must exist true statements which are not provable). And by proving the same fact by yet another method, British mathematician Alan Turing came up with a brilliant formalization of the notion of computability using a profound concept of Turing machine; his new theory turned out to have a huge impact on both theory and practice of computer science.

I deny her refutation

If you read the headlines, you might think that Rep. Maxine Waters has refuted charges brought against her by the House Ethics Committee. If you read the actual articles with said headlines, it will turn out that she hasn't really refuted those charges; she has merely denied them. It's a rather significant difference. To refute a proposition that X is to provide evidence and/or argument from which it follows that not-X. To deny a proposition that X is to stick a "not" operator to it. One takes a lot more effort than the other.

Reversing implication: you really can't do that

One of the most common fallacies is that of reversing an implication. An implication is a statement of the form 'If A then B,' where A and B can be any statements whatsoever. Now reversing implication is an incorrect belief that 'If A then B, then if B then A.' Implication is not symmetrical, and it's easy to come up with an example that would make it clear. Suppose we have the following implication: 'If Roger Federer is the best tennis player in the world, then he is the best tennis player in Europe.' Reversing this implication you'd have 'If Roger Federer is the best tennis player in Europe, then he is the best tennis player in the world,' which is clearly not true. You just can't reverse an implication; in fact, the only valid conclusion you can get from 'If A then B' is 'If not-B then not-A' ('If Roger Federer is not the best tennis player in the world, then he is not the best tennis player in Europe').

Nonetheless, reversing implications is pretty much bread and butter of political dispute. Let me give a concrete example. On August 1, 1944, Polish anti-Nazi resistance called the Home Army (Armia Krajowa) started an open battle with Nazi troops stationed in Warsaw; the battle is known as the Warsaw Uprising (Powstanie Warszawskie). I will not get into the details of the Uprising here, as I am planning a whole series of posts on this fascinating topic in the very near future. For now I'll just talk about one fact about it: when Poland succumbed to Soviet rule soon after the war was over, the official line of communist propaganda with respect to the Uprising was that it was an insanely careless endeavor that brought more harm than good. The reason that communists were saying this was purely cynical: they hated the Uprising because it was a last-ditch effort anti-communist population of Warsaw to try to prevent the city from being taken over by the Soviets. Of course, I don't share those motivations; but I do indeed believe that the Warsaw Uprising was a tragic mistake, and that, even in its terrible post-war situation, Poland would probably have been better off if it had not happened.

I cannot count the times when, after sharing this belief of mine in a face-to-face or an online discussion, I have been called a communist for having this opinion. But it should be clear that those of my critics who were using this argument were committing the fallacy of reversing an implication. We have 'If one is a communist, then one believes that Warsaw Uprising was a mistake.' From this, my critics were concluding that 'If one believes that Warsaw Uprising was a mistake, then one is a communist.' Fallacious reasoning, clear as day. And the interesting part is those were all people smart enough that, if they were presented with the Roger Federer example given above, would no doubt understand that reversing implication is invalid reasoning. Yet in this particular context they were completely unable to realize that they were making the same silly mistake.

Pet peeve: abusing the term "logic"

I love formal logic; it's one of the most beautiful things that exist. Thus, I get annoyed when the term is abused, which happens all the time. For one thing, logic is often confused with something else, such as intuition or common sense. For example, many times people will say "That's so illogical!" when they really mean "That's so counterintuitive" or "That's so unexpected." The actual formal logic is very often counterintuitive. Which should not be surprising at all: the very reason it was developed in the first place was because some thinkers noticed that relying on intuition alone leads to errors in reasoning, so they decided a formal machinery was needed to aid the brain in the reasoning process. For another thing, people tend to forget that logic is all form, no substance. Logic analyzes modes of reasoning based on their form alone, abstracting meaning away completely. How many times have you heard something like "If you only used some logic, you'd know that cutting taxes must decrease government revenue" or similar? The truth is, logic has absolutely nothing to do with it. This statement is true because of its substance, not because of its form. Logic can't tell us anything about tax cuts and deficits. Economic theory and/or empirical observation might--but not logic.