# Tag Info

32

Here's the story of one blue-eyed islander. The Guru said she saw someone with blue eyes. He looked around and thought "Hey, I don't see anyone with blue eyes. I guess she means me." And so he left right away. Here's the story of two blue-eyed islanders. The Guru said she saw someone with blue eyes. They looked around and thought "OK, I see someone with ...

19

Simply put, modal logics are useful any time that you want to reason about truths that are, well, modal. The example you gave contrasts first order logic and modal logic, but a more common starting point is to build modal logics upon propositional logics. One of the characteristics of modal logics is that the modal operator, often written $\Box$, is not ...

15

I think the answer to Question 1 is that after the Guru has spoken they all know that they all know that they all know that they all know that (repeat as many times as you like) someone has blue eyes. Previously they did not know that, and the statement is only true when it contains at most 99 "they all know that"s.

10

In modal logic we use the term "possible worlds" to describe some set of "vertices" with an accessibility relation defining "edges". Possible worlds are just a term for some set $W$ which we wish to identify as our frame in the context of Kripke semantics. When we define a valuation on that frame we obtain a model which has certain modal formulas being ...

9

Another interpretation would be temporal logic: If you interpret $\Diamond$ as "eventually" and $\square$ as "always", this allows you to describe the properties of systems with evolving state. See http://en.wikipedia.org/wiki/Temporal_logic; this kind of logic is used in some areas of computer science (model checking in particular).

9

The guru starts the doomsday clock. Before the guru speaks, there is no "day 1". Without the common reference time, every blue eyed person (BEP) lives happily with the knowledge that there must be either 99 or 100 BEPS. But there is no way to decide which is true. The common reference time is the key to the apparent paradox. Without it, there is no ...

8

I'll take up the challenge in nbubis's comment (even though there are not yet $99$ answers), and try to give a precise answer. And since this is a mathematics rather than a philosophy site, I'll try to use some formulas to describe what is going on. As has been noted, the technical notion of common knowledge is important here. Clearly there is in this ...

8

Just work out the case where there are 2 people, then 3 people, then 4 people. It's the same principle, just more mind-boggling, for higher $n$. When there are just 2 people the situation is pretty much clear. When there are 3 people, does each know that everybody knows that everybody knows that there are people with blue-eyes? (there was no typo in what I ...

7

While "it is possible that" and "it is necessary that" are the common interpretation of the $\Diamond$ and $\Box$ operators of modal logic, these are by no means the only interpretations. From a mathematical point of view, provability logic (see also the Stanford Encyclopedia of Philosophy) is quite important in the analysis of sufficiently strong formal ...

7

Yes, there is also a set-theoretic formulation of common knowledge as a fixed point. Common knowledge of an event $E$ is the greatest fixed point of the function $f_E(X)=K^1(E\cap X)$, where $K^1(Y)$ denotes first-order mutual knowledge of $Y$, i.e., that everyone knows $Y$. The existence of a greatest fixed point is guaranteed by the Knaster–Tarski theorem. ...

6

$\def\diamond{\diamondsuit}$ Modal logic is concerned with the logic of so-called "modal operators", often "necessarily true" and "possibly true", which are symbolized with $\square$ and $\diamond$ respectively. The idea is that while it is true that George Bush was the 43rd president of the United States, it is not necessarily true, because one can easily ...

6

With more than one blue-eyed islander, the guru's statement on its one is obvious to everyone, so in isolation it provides no information. As a result, noone heads for the ferry that night. However, without any more words being spoken, each passing day results in more information. On day one, the guru's statement alone says "There is at least one blue-eyed ...

6

The question doesn't ask for the solution to the puzzle, which it already linked to. The first paragraph of the linked puzzle ends with: [...] Everyone on the island knows all the rules in this paragraph. The whole paragraph is crucial, but two strongly interacting aspects may be overlooked. First, "[t]hey are all perfect logicians -- if a ...

5

In classical modal logic, □ and ◊ are defined to be De Morgan duals, and so the relation necessarily holds for all classical modal logics, even non-normal modal logics. In intuitionistic modal logic, the duality between the modalities is generally looser and the relation generally does not hold. Typically in intuitionistic modal logics, the meaning of one ...

4

Consider following structure: $U=\{ w_{1},w_{2},w_{3}\}$, $R$ is transitive, reflexive plus $(w_{3},w_{2}) \in R$ and following valuation $v(w_{1},A)=0, v(w_{2},A)=1, v(w_{3},A)=0$. It's easy to check that Grz axiom is false in this structure with respect to given valuation. In general this http://en.wikipedia.org/wiki/Method_of_analytic_tableaux method is ...

4

The rule is that if $\varphi$ is provable from no assumptions [other than logical axioms], i.e. if $\varphi$ is a theorem, then $\Box\varphi$ is also a theorem. That's a plausible rule to have in the modal logic of necessity: it formally echoes the idea that if something is demonstrable by logical reflection alone it is necessarily true. Thus, the following ...

4

"$\phi$ is provably equivalent to $\psi$" in some logical system $K$ means that $\phi \vdash_K \psi$ and $\psi \vdash_K \phi$. If $K$ comes equipped with the usual notion of bi-implication ($\leftrightarrow$), then this will be the same as $\vdash_K \phi \leftrightarrow \psi$. I would write this as "$\phi \mathrel{\dashv\vdash}_K \psi$" (and rather ...

4

This answers the question as it was before it was edited to ask something completely different! If those are all the axioms you have, then no. The axioms are all true in an interpretation where $\Diamond p$ is false for all $p$, and in such an interpretation $p\to\Diamond(p\land q)$ will be false whenever $p$ is true. On the other hand, it looks rather ...

3

The passage of time is important input because an event happens every night, and that event provides information to every islander what the others know or do not know. Whether or not anyone leaves on a given night, the information content changes. By not leaving, everyone has communicated clearly, "I do not know my eye color". When the guru speaks, he ...

3

The reason it's not "common knowledge" beforehand that there is someone with blue eyes is: Let's simplify the case to four people other than the guru: Two (Alice and Bob) with blue eyes, and two (Carol and Dave). It is true that everyone can, in fact, see at least one person with blue eyes. Alice can see Bob, Bob can see Alice, and Carol and Dave can see ...

3

I personally learned modal logic from Chellas's Modal Logic: An Introduction, but a more modern treatment in-line with current interests in modal logic is van Benthem's Modal Logic for Open Minds. Other good introductions include Modal Logic: An Introduction to its Syntax and Semantics, Cresswell & Hughes's A New Introduction to Modal Logic, and Beall ...

3

Check that in your frame you can describe in first order language that there are three types elements: Those that do not contain any elements (first type), those that contain elements that do not contain elements (second type) and a unique element that contains all the elements of the second type (third type). Next check that via first order language you ...

3

Many (most?) modal logics can indeed be translated into non-modal predicate logics, such as by replacing the modalities by quantification over a "time" variable and giving every existing predicate an extra argument, meaning intuitively "at time $t$ it holds that such-and-such". One reason not to do this is that the quantification over "time" that modalities ...

3

If the full payoff matrix for everyone was part of the common knowledge, then of course everyone will be able to observe that a given position is a Nash equilibrium, by observing that no-one will be able to improve their position by changing individually, and this calculation would also be part of the common knowledge (provided it was common knowledge that ...

2

This is an area where it is very easy to get oneself confused from lack of precision. You write ${\it Bew}(\ulcorner p\urcorner)$ without specifying which axioms $p$ is to be proved from, and that makes an important difference. Let's first consider $$T_0(p) \equiv {\it Bew}_{PA}(\ulcorner p \urcorner)\to p$$ There's nothing wrong with this; if we believe ...

2

As Zhen Lin indicates, this cannot be a "complete characterization of all modal logics." It seems to be close to a characterization of one particular modal logic. The simplest non-trivial system is arguably the one called S5, in which iterations of modal operators are equivalent to single ones. You may be close to a characterization of this one system, ...

2

Something is perhaps amiss, as the third is certainly a modal validity (in normal alethic modal logics which aim to regiment the notion of necessary truth). Which modal logic are you working in? (1) holds in any normal modal logic, as any tautology like $(P \to P)$ is a theorem, and necessitations of theorems are theorems. (2) is an instance of a tautology ...

2

Yes -- model theory with Kripke structures is the standard way to exhibit a semantics of the usual first-order connectives for which intuitionistic logic is a sound and complete proof system. The Wikipedia article has some details.

2

There are four kinds of possible distributivity between binary operators $\triangle$ and $\otimes$. Left-distributivity of $\triangle$ over $\otimes$ is: $x \triangle (y \otimes z) = (x \triangle y) \otimes (x \triangle z)$ Right-distributivity of $\triangle$ over $\otimes$ is: $(x \otimes y) \triangle z = (x \triangle z) \otimes (y \triangle z)$ ...

Only top voted, non community-wiki answers of a minimum length are eligible