# Tag Info

38

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

22

The modal operator $\square$ refers to necessity; its dual, $\lozenge$, refers to possibility. (A sentence is necessarily true iff it isn't possible for it to be false, and vice versa.) $P(\varphi)$ means that $\varphi$ is a positive (in the sense of "good") property; I'll just transcribe it as "$\varphi$ is good". I'll write out the argument ...

21

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.

20

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

19

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

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

This is Gödel's ontological proof, which is fully explained on Wikipedia (see the link). I find this to be an incredible easter egg, since the proof is something which Sheldon says he doesn't understand. And Sheldon has expressed more than once that he doesn't believe in the existence of god. (Originally I thought this would be something pertaining to the ...

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

10

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

10

The box is a modal operator (it is necessarily true that ...), with the diamond its dual (it is possibly true that ...). '$P(\varphi)$' holds when the property expressed by $\varphi$ is 'positive' (maybe better, is a perfection). Other novelties are defined. $G(x)$ says $x$ has all perfections (so is God). $\varphi$ ess $x$ says the property $\varphi$ is ...

9

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

9

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

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

8

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

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

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

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

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

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

1.) The quantified piece of new information that the Guru provides is not 'at least one person has blue eyes' (except in the $n=1$ case), since everyone knew that already. In fact, this quantified piece of information is rather complicated. If there is one islander, then the new information is exactly 'there is at least one person on the island with blue ...

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

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

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

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

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

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

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

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

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