Tag Info

Hot answers tagged

33

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 ...


17

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.


14

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 ...


11

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 ...


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).


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

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 ...


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

$\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 ...


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

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

Yes. There's a strong convention that $\Box$ and $\Diamond$ are always each other's duals, even in special-purpose modal logics. When the propositional substratum is classical, this implies that $\neg\Box\equiv \Diamond\neg$ and $\Box\neg\equiv\neg\Diamond$. For example, when $\Box P \leftrightarrow \neg\Diamond\neg P$ is an axiom (or the definition of ...


6

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 ...


5

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

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 ...


4

See Epistemic Logic. If your $K$ correspond to the epistemic operator $K_c$ such that : $K_c \alpha$ reads "Agent $c$ knows $\alpha$" then $\lnot K_c \lnot$ is simply : "Agent $c$ does not know not-$\alpha$". Thus, $A := \lnot K \lnot$ is only an abbreviation. Note Like in "standard" Modal Logic, where possibility can be defined in terms as ...


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

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 ...


3

Your $Xp$ is their $Np$, for "Next, $p$." The red indicates truth along that fixed $y$-coordinate. So for instance, the semantics for $Np$ state "$Np$ is true just in case $p$ is true at the next time interval." In your first diagram, $Np$ is true at 1-2, so at the next time interval (2-3), $p$ must be true. If, for example, $p$ were true at intervals 3-5 ...


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

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

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

Preliminary comment: the interdefinability of $\square$ and $\Diamond$ using negation isn't specific to S5. Now to the question. I don't know offhand how the derivations within the system go, but if you want the claim to be "obvious" I think you want an explanation that makes it intuitive. Such an explanation can be given in terms of Kripke semantics and ...


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 ...


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 ...


2

Modalities modify propositions, predicates modify objects.


2

It appears to me that what you have is a Kripke model consisting of four worlds, and you've listed the propositions $a$ and $b$ that happen to be true in each world. You might have meant five worlds, however, since there is a transition into $S_0$, but this doesn't seem to come from any world, so let us ignore that. Let's assume that by saying that a ...



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