# Tag Info

42

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

35

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

28

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

25

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

24

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.

22

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

13

Your impression is right, but missing the point in some sense: modal logic is strictly less powerful than first-order logic, and this is one of the reasons it is so important in various contexts (especially applications of logic in computer science)! The reason is that there is a fundamental "power-versus-tameness" tradeoff implicit in any choice of logic, ...

12

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

11

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

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

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

9

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

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

9

$\mathbb{I}$, $\mathbb{S}$, and $\mathbb{P}$ are each operators on classes of structures: $\mathbb{I}(\mathcal{K})$ is the class of structures isomorphic to a structure in $\mathcal{K}$. $\mathbb{S}(\mathcal{K})$ is the class of substructures of structures of $\mathcal{K}$. $\mathbb{P}(\mathcal{K})$ is the set of all products of structures in $\mathcal{K}$...

8

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, no one 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 ...

8

Consider $\psi = (P \lor \square \lnot P)$. $\psi$ is not valid in $S5$, since it's possible to have a world satisfying both $\lnot P$ and $\lozenge P$. But $\lozenge \psi$ is valid in $S5$. Indeed, consider any world $w$ in a Kripke model of $S5$ (actually, all we need is that the accessibility relation $R$ is reflexive). Case 1: $P$ holds at some world ...

8

A logic is stronger the more theorems it proves, and as a corollary, the fewer models it has. The more axioms there are, and the more specific an axiom is (in the sense that A is more specific than B if A entails B but B does not entail A), the more formulas will be deducible from these axioms: A logic is strong in the sense that it manages to prove many ...

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

Sorry this answer became so long. If you want the two-minute answer, just read the Terminology then skip down to the Answers to the Questions. You can then fill in the details as desired. Terminology Let $A, B, C, A_i$ denote the blue-eyed islanders. Let $A_i^*$ denote the proposition that $A_i$ has blue eyes (which does not imply that $A_i$ knows this). ...

7

The first line says "$A$ necessarily holds in wolrd $w$ iff $A$ holds in all worlds reachable from $w$". You can think of it as, $A$ necessarily holds in wolrd $w$ iff $A$ holds all around as far as one can see from $w$. If you've traveled everywhere in your reach and in all that map you see $A$, you believe that $A$ holds necessarily, it is a law for you. ...

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

6

It's just a reformulation of Gödel's theorem : if you have some intuition for Gödel's theorem then you can transfer it to Löb's theorem. Indeed if PA proves $Prov(A)\to A$ then it means that the provability of $A$ is enough to conclude the truth of $A$ : but we know that some models may believe that some things are provable while they're not : this is Gödel'...

6

You are conflating the proof theory of modal logic with the semantics of modal logic. We can approach verifying statements in two ways: 1) formal proofs from the axioms. 2) informal arguments for their validity in terms of Kripke frames. (Which is not to say these are the only two approaches, just the two relevant to this question.) The theorems of system K (...

6

The fixed-point treatment of common knowledge is not very intuitive. However, I will try to provide some explanation why it captures the properties of operators $C_G \varphi$. First, recall that intuitively $C_G \varphi := \bigwedge_{n \in \mathbb{N}} E_G^n \varphi$, where $E_G^0 \varphi:= \varphi$ and $E_G^{n+1}:= E_G E_G^n \varphi$. This is your definition ...

5

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

5

The "paradoxical" configuration is : Ann believes that Bob assumes that Ann believes that Bob’s assumption is wrong. We have here Bob's assumption : "Ann believes that Bob’s assumption is wrong". Now consider Ann's belief attitude towards Bob's assumption; we can say that if $p$ is any statement, a "reasonable" principle will ...

5

How about the following. (I will write $\bot$ instead of $F$). $\top$ is a theorem, and hence $\square \top$ is a theorem by the necessitation. Next, from $\square \top \rightarrow \lozenge \top$ (which is an instance of the axiom) by MP we have that $\lozenge \top$ is a theorem. As $\lozenge \top$ is a theorem, then $\neg p \vee \lozenge \top$ is a ...

5

Epistemic logic is a type of modal logic. The term "modal logic" is used to refer to a gigantic class of logical systems - for example, contrast epistemic logic with temporal logic. The point is that for a wide variety of logical concepts - knowledge, time, plausibility, moral obligation, ..., there is a common flavor, and syntax, which is useful to pin down....

4

This is a great, and surprisingly subtle, question! Unfortunately the answer is necessarily a bit technical, so let me state the very short version here: While validity and provability perfectly coincide "in reality," this is nontrivial, and there are non-pathological theories for whom validity logic and provability logic do not coinicide. And ...

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

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