15 March 2016

A canary in a coal mine for contagious dancing

Nice blog post about logic here:
dancing (sic) around a weird looking tautology — I had never heard of it before, but I guess it's well known in the circles.
After a first moment of concern I eventually got the meaning of the proposition.
Their post starts from such a tautology in order to deal with a few deep features of logic (formal proofs, terms and references, classical and non-classical logic, sequent calculus, etc...).
Here I just would like to recount in my own words how it turns out that such proposition is a tautology and make some comments along the way. But before continuing please take your time to read their piece because what follows is a not-self-contained reply indeed to it.
Let's first briefly recall a few properties of a logical implication from propositional calculus (which is logic without variables or quantifiers).
It all boils down to the "ex falso quodlibet" property, which says that the (truth table of the) implication "A ⇒ B" is true (not only in these cases but for sure) whenever the premise A is false, whatever the truth of B.
By the same token, the implication "A ⇒ B" is completely equivalent to "B ∨ ¬A" (see for example their truth tables).
Well, no need to recall anything more, so let's start. And in contrast with the starting statement of their post, here we are going to start with a statement which I think everybody would agree it is manifestly a tautology, namely:
"Everybody dances or there's someone who doesn't".
And it's a tautology not only in ordinary language, but also in its transposition into logical form:
"∀y Dy ∨ ∃x ¬Dx".
Just to be precise, it's a tautology due to the rules of inference of classical predicate calculus directly related to the meaning itself of the universal and existential quantifiers.
I hope everything is fine and dandy so far, because here comes the tricky point. To wit: let's bring the existential quantifier outside the whole statement:
"∃x (∀y Dy ∨ ¬Dx)".
This operation is logically valid since we are not breaking the scope of the existential quantifier. Quite the opposite, in fact: we are bringing the clause "∀y Dy" within the scope of the existential quantifier even if the occurrence of y is actually free. The trickery is clear if we try to render such a new statement into ordinary language:
"There is someone such that (either) everybody dances or she does not dance".
The translation seems to reflect the logical proposition but as a matter of fact in ordinary language we are somehow suggesting that there is someone, well chosen, which has the property that she's dancing only if *everybody else* is dancing too. In other words, the sentence in ordinary language seems to allow for many different situations concerning who's dancing and who's not — while keeping fixed the well chosen someone which we are saying something about! Instead, of course, the meaning of the logical proposition is that, given in the first place an arbitrary and fixed state of dancing people conditions, we can *then* choose a specific somebody in order to make the statement true.
Ok, so, please keep in mind such a difference between what goes without saying in the ordinary language transliteration with respect to what is the bare logical content of the sentence, and let me further play with it.
Now let's focus on the part of the statement within brackets: "∀y Dy ∨ ¬Dx". Guess what? Yep, it has just the structure "B ∨ ¬A" recalled above! Therefore we can rewrite it as "A ⇒ B", namely "Dx ⇒ ∀y Dy", the whole sentence resulting in:
"∃x (Dx ⇒ ∀y Dy)"
which is exactly the weird looking tautology they where talking about in their post!
All right, we actually were just able to derive such a statement from a pretty clear tautology, but with a tricky step which should clarify the weirdness of sentence. Their ordinary language conversion reads:
"There is someone such that, if she dances, then everybody dances"
and if we bring here what we found was going without saying in our transliteration above, we find again that the ordinary language sentence is suggesting that there is someone, well chosen, which has the property that, if she's dancing, then everybody else would al least *start* dancing if he wasn't yet. Instead, again, the content of the logical statement is that, given in the first place an arbitrary and fixed state of dancing people conditions, we can *then* choose a specific somebody in order to make the statement true.
Notice how, now that the structure "B ∨ ¬A" is recast into the form "A ⇒ B", we are not allowed to bring the existential quantifiers inside the brackets any more!
Well, I think the next question is: how could you differently translate the stronger sentence implied by the ordinary language clause into a logic form? — avoiding any tautology and instead keeping all its falseness?
Otherwise, or in addition: how could you differently translate into ordinary language the weaker sentence implied by the logical tautology? — keeping all its empty trueness?
The problem with the first question seems to be that logic deals with sets, which are a-temporal collections of elements given once and for all. So there's no way to render in set theory the fact that you can keep an element fixed and consider different arrangements of a property among the (other) elements of the set. Or... wait: maybe this is not actually true and instead we can just try this way! Namely let's try to render the idea of different arrangements of a property, which could be done via subsets. I'm aware that the correspondence between predicates and subset could open deep questions on the principles of logic, but let me use such a correspondence in a somehow naif way. So, given a universe set X, let's assume that any property, such D, can be seen as defining a (possible improper) subset of X — whose elements are just the ones for which Dx is true). Hence the "real" logical transposition of the sentence "There is someone such that, if she dances, then everybody dances" should sound like the following:
"∃x: ∀D, x∈D ⇒ ∀y y∈D".
In fact such logic statement seems to keep all the falseness of our ordinary language sentence! — if the property D is "is dancing", or the subset D is "those who are dancing".
In this approach the tautology reads instead:
"∀D, ∃x: x∈D ⇒ ∀y y∈D"
since its triviality lies just in the fact that the you can always find the x, once a specific subset D is provided. A close comparison of such two propositions makes it clear how they differ just by the switching of the quantifiers: the universal one over the subsets D and existential one over the element of D.
So in principle this last proposition could be the first step for answering to our second question too. In order to stress the fact the we are choosing the subset D *before* the choice of the element x which we are saying something about, the tautology could be recast as:
"Given a (possible improper) subset D of the universe set X, there exists an x such that if x belongs to D then every y belongs to D".
But in sharp contrast with the answer for the first question, here we're extremely dissatisfied with such result. What's happening here is that the use of the implication "if A then B" seems to suggest some sort of causal relation between the x (hiding the fact that you can always find one of it) and the universality ("for every y") of the D property. Even if you choose which is x after having inspected the property/subset D, the proposition seems to suggest that such element x could act like a canary in a coal mine, like an evidence for learning something about every y, knowing something about a single x only. Rather, the derivation itself follows a (double) path in which the consequence B ("everybody dances") is alternately assumed as true or false in the first place and only then, based on this evidence on B, one is able to "learn" something about the truth of A ("you can find an x which does or doesn't dance").
So in the end I think the proper way to convey in ordinary language the content of the logic tautology is to avoid the if-then clause and use the equivalent "or-not" formulation, namely:
"Given a (possible improper) subset D of the universe set X, every y belongs to D or there exists an x such that x does not belong to D"
which of course clearly shows the full empty meaning of a tautology and in fact can be cleaned of all the scaffolding of set theory:
"Everybody dances or there's someone who doesn't"
which in turn is just the plain tautology I started this post from.