User:Chriswig
From Wikipedia, the free encyclopedia
This is a Wikipedia user page.
This is not an encyclopedia article. If you find this page on any site other than Wikipedia, you are viewing a mirror site. Be aware that the page may be outdated and that the user to whom this page belongs may have no personal affiliation with any site other than Wikipedia itself. The original page is located at http://en.wikipedia.org/wiki/User:Chriswig. |
I'm only creating a user page so I can have a sandbox to experiment around in. I'm working on this with user Rubysargasso, so please don't reverse any work she's done on here. Thank you.
Epistemic logic is a subfield of modal logic that is concerned with reasoning about knowledge. While epistemology has a long philosophical tradition dating back to Ancient Greece, epistemic logic is a much more recent development with applications in many fields, including philosophy, theoretical computer science, artificial intelligence, economics and linguistics. While philosophers since Aristotle have discussed modal logic, and Medieval philosophers such as Ockham and Duns Scotus developed many of their observations, it was C.I. Lewis who created the first symbolic and systematic approach to the topic, in 1912. It continued to mature as a field, reaching its modern form in 1963 with the work of Kripke.
Many papers were written in the fifties that spoke of a logic of knowledge in passing, but it was von Right's paper An Essay in Modal Logic from 1951 that is seen as a founding document. It was not until 1962 that another Finn, Hintikka, would write Knowledge and Belief, the first book-length work to suggest using modalities to capture the semantics of knowledge rather than the alethic statements typically discussed in modal logic. This work laid much of the groundwork for the subject, but a great deal of research since that time has taken place. For example, epistemic logic has been combined recently with some ideas from dynamic logic to create public announcement logic and product update logic, which attempt to model the epistemic subtleties of conversations. The seminal works in this field are by Plaza, van Benthem, and Baltag, Moss, and Solecki.
[edit] Standard Possible Worlds Model
Most attempts at modeling knowledge have been based on the possible worlds model. In order to do this, we must divide the set of possible worlds between those that are compatible with an agent's knowledge, and those that are not. While we will primarily be discussing the logic-based approach to accomplishing this task, it is worthwhile to mention here the other primary method in use, the event-based approach. In this particular usage, events are sets of possible worlds, and knowledge is an operator on events. Though the strategies are closely related, there are two important distinctions to be made between them:
- The underlying mathematical model of the logic-based approach are Kripke structures, while the event-based approach employs the related Aumann structures.
- In the event-based approach logical formulas are done away with completely, while the logic-based approach uses the system of modal logic.
Typically, the logic-based approach has been used in fields such as philosophy, logic and AI, while the event-based approach is more often used in fields such as game theory and mathematical economics. In the logic-based approach, a syntax and semantics have been built using the language of modal logic, which we will now describe.
[edit] Syntax
The basic modal operator of epistemic logic, usually written K, can be read as "it is known that", "it is epistemically necessary that", or "it is inconsistent with what is known that not". If there is more than one agent whose knowledge is to be represented, subscripts can be attached to the operator (K1, K2, etc.) to indicate which agent one is talking about. So Kiφ can be read as "Agent i knows that ψ." The dual of K, which would be in the same relationship to K as is to , was introduced by Hintikka as P. This is not normally used, however, and it can be represented by , which can be read as "does not know whether or not φ".
In order to accommodate notions of common knowledge and distributed knowledge, three other modal operators can be added to the language. These are EG, which reads "every agent in group G knows"; CG, which reads "it is common knowledge to every agent in G"; and DG, which reads "it is distributed knowledge to every agent in G". If φ is a formula of our language, then so are EGφ, CGφ, and DGφ. Just as the subscript after K can be omitted when there is only one agent, the subscript after the modal operators E, C, and D can be omitted when the group is the set of all agents.
[edit] Semantics
As we mentioned above, the logic-based approach is built upon the possible worlds model, the semantics of which are often given definite form in Kripke structures, also known as Kripke models. A Kripke structure M for n agents over Φ is a tuple , where S is a nonempty set of states or possible worlds, π is an interpretation which associates with each state in S a truth assignment to the primitive propositions in Φ, and are binary relations on S for n numbers of agents. It is important here not to confuse Ki, our modal operator, and , our accessibility relation.
The truth assignment tells us whether or not a proposition p is true or false in a certain state. So π(s)(p) tells us whether p is true in state s in model . It is important to remember that truth depends not only on the structure, but on the current world as well. Just because something is true in one world does not mean it is true in another. To show that a formula φ is true at a certain world, we write , which is usually read as "φ is true at (M,s)," or "(M,s) satisfies φ".
It is useful to think of our binary relation as a possibility relation, because it is meant to capture what worlds or states agent i considers to be possible. It also usually makes sense for to be an equivalence relation, since this is the strongest form and is the most appropriate for the greatest number of applications. An equivalence relation is a binary relation that is reflexive, symmetric, and transitive. It is important to note that our accessibility relation does not have to have these qualities; there are certainly other choices possible, such as those used when we are modeling belief rather than knowledge.
[edit] The Properties of Knowledge and Related Axiom Systems
Assuming that is an equivalence relation, as we detailed above, and that our agents are perfect reasoners, we can derive a few properties of knowledge as we've defined it. The following will list a few of those, detailing informally how they come about, and then give a proof for each property. The properties listed here are often known as the "S5 Properties," for reasons described in the Axiom Systems section below.
[edit] The Distribution Axiom
This axiom is traditionally known as K. In epistemic terms, it states that if an agent knows φ and knows that , then the agent must also know ψ. So you can say
[edit] The Knowledge Generalization Rule
Another property we can derive is that if φ is valid, then Kiφ. It is an easy mistake to think that this implies that if φ is true, that agent i knows φ, but that is not the case. What it means is that if φ is true in every world that an agent considers to be a possible world, then the agent must know φ at every possible world.
- if then
[edit] The Knowledge or Truth Axiom
This axiom is also known as T. It says that if an agent knows facts, the facts must be true. This has often been taken as the major distinguishing feature between knowledge and belief. This is because while you can believe something that is false, you cannot know something that is false.
[edit] The Positive Introspection Axiom
This property and the next state that an agent has introspection about its own knowledge, and are traditionally known as 4 and 5, respectively. The Positive Introspection Axiom, also known as the KK Axiom, says specifically that agents know what they know. This axiom may seem less obvious than the ones listed previously, and Timothy Williamson has argued against its inclusion forcefully in his recent book, Knowledge and Its Limits.
[edit] The Negative Introspection Axiom
The Negative Introspection Axiom says that agents know what they do not know.
[edit] Axiom Systems
Different modal logics can be derived from taking different subsets of these axioms, and these logics are normally named after the important axioms being employed. However, this is not always the case. KT45, the modal logic that results from the combining of K, T, 4, 5, and the Knowledge Generalization Rule, is primarily known as S5. This is why the properties of knowledge described above are often called the S5 Properties.
It is important to note that epistemic logic also deals with belief, not just knowledge. The basic modal operator is usually written B instead of K. In this case though, the knowledge axiom no longer seems right -- agents only sometimes believe the truth -- so it is usually replaced with the Consistency Axiom, traditionally called D:
which states that the agent does not believe a contradiction, or that which is false. When D replaces T in S5, the resulting system is known as KD45. This results in different properties for as well. For example, in a system where an agent "believes" something to be true, but it is not actually true, the accessibility relation would be non-reflexive. The logic of belief is called doxastic logic.
[edit] Completeness and Decidability
[edit] Completeness
Let be the set of formulas that can be built up starting from the primitive propositions in Φ using conjunction, negation, and the modal operators K1,...K2. Let be the class of all Kripke structures for n agents over Φ, with NO restrictions on the relation. If we want to discuss a subclass of with certain restrictions on it, we can add superscripts indicating properties of the accessibility relation after . So for an accessibility relation that is an equivalence relation, for example, as the one described in the Semantics and Properties of Knowledge sections above, we can write , with the r standing for reflexive, the s for symmetrical, and the t for transitive.
In order to prove that Kn is a sound and complete axiomatization with respect to for formulas in the language , it suffices to prove that every Kn-consistent formula in is satisfiable with respect to . If we can prove that, and φ is a valid formula in , that means that if φ is not provable in Kn, neither is . So we can prove that is Kn-consistent. It follows from there that is satisfiable with respect to , contradicting the validity of φ with respect to .
In order to prove that every Kn-consistent formula in is satisfiable with respect to , we need to construct a special structure Mc, usually called the canonical structure or canonical model. Mc has a state sV corresponding to every maximal Kn-consistent set V. Then we show that
- iff .
This means that a formula is true at a state sV just in the case that it is one of the formulas in V. This is enough to prove what we were after, since if φ is Kn-consistent, then φ is contained in some maximal Kn-consistent set V. So , and so φ is satisfiable in Mc. Hence, φ is satisfiable with respect to .
[edit] Incorporating Common Knowledge
The modal operator for common knowledge, CG, is defined as an infinite conjunction, meaning it is "infinitary." The formula CGφ is true when everyone in G knows φ, everyone in G knows that everyone in G knows φ, and so on, ad infinitum. However, the axioms for common knowledge are complete, as we are able to characterize the operator CG with a finite set of axioms. Along with all of the axioms mentioned above, we can add two more specifically for common knowledge:
Together with the Induction Rule,
- ,
these two axioms completely characterize common knowledge.
[edit] Alternatives to Standard Kripke Structures (SKSs)
[edit] Introduction
The knowledge operator K is closed under logical consequence in standard Kripke structures (SKS), so SKSs model "logically omniscient" agents. That is, if the formulas Kaφ and Kaψ are true at world w, where φ and ψ are true in every world epistemically accessible to an agent a, then a knows , , , and at w.
In the actual world, agents commonly do not know formulas entailed by their knowledge -- sometimes because they possess a sound but incomplete set of inference rules, sometimes because they are unwilling or unable to do the requisite derivations. Defeaters abound.
The alternative structures introduced here provide logical apparatuses for modeling such "resource-bounded" agents. They also provide ways of reasoning about single agent systems, in which an agent's knowledge is intuitively implicit rather than attributed explicitly by the modeler to the agent.
It is useful to keep in mind the following concepts for the purposes of our introduction:
A. Types of Logical Omniscience
Full logical omniscience, which exists in SKS, requires that an agent knows all of the formulas logically implied by the formulas he knows. The following weaker forms of logical omniscience may or may not exist in alternative structures:
(1) Knowledge of Valid Formulas: Agent knows all valid (i.e. necessarily true) formulas.
(2) Closure Under Logical Implication: Agent knows ψ if and only if (i) agent knows φ, and (ii) .
(3) Closure Under Logical Equivalence: Agent knows ψ if and only if (i) agent knows φ, and (ii) φ and ψ are logically equivalent.
(4) Closure Under Material Implication: Agent knows ψ if and only if (i) agent knows , and (ii) agent knows φ.
(5) Closure Under Conjunction: Agent knows φ and ψ if and only if (i) agent knows φ, and (ii) agent knows ψ.
B. Locality of Knowledge
In SKSs, we can define classes of worlds which are indistinguishable to an agent. Worlds w and v are indistinguishable to an agent if, when she knows p in state w, she also knows φ in state v, in cases in which w is related to an v by an equivalence relation (reflexivity, symmetry, and transitivity). Because some alternative structures abandon the use of equivalence relations, we are not able to discuss the locality of knowledge in their models.
C. Standard Propositional Semantics
Standard propositional semantics allows us to reduce the number of cases in proofs by induction by allowing equivalencies between logical connectives. Under standard propositional semantics, ; . These equivalencies hold in SKSs but not in some alternative structures.
[edit] Alternative Structures
A. Explicit Representations of Truth
1. Syntactic Structures
a. The Model
SKSs consist of a frame F = (W,K1,...,Kn) and a valuation function π which assigns truth values to the primitive propositions in each world. The syntactic approach replaces the standard valuation function pi with Σ, a valuation which "explicitly represents truth", as it is not constrained by standard propositional semantics in its assignment of truth values. So Σ may assign true to both φ and in world w.
It is important to note that standard propositional semantics, perhaps counterintuitively, does hold in syntactic structures. As a result, the true formula p or q is equivalent to in world w, despite the fact that may be false in w.
It is also important to note that we can engineer Σ to force our model to approximate the standard definition of knowledge, which is one source of flexibility in this approach.
b. Properties of Knowledge on Syntactic Structures
Given valid, logically equivalent formulas φ and ψ, Σ may assign false to the formula Kaφ and true to the formula Kaψ. In other words, the K operator is not an equivalence relation under this model, and thus knowledge is not defined as truth in all possible worlds. As a result, no form of logical omniscience, including knowledge of valid formulas, necessarily holds in syntactic structures.
c. Agents Modeled by Syntactic Structures
A model in a syntactic structure could neatly capture intuitions about knowledge in the following scenario: A child cannot determine that p = q, where p = x * 0, q = y * 0, , x and y are integers, because she has not learned that multiplying an integer by 0 results in the product 0. In such a case, the child has a consistent set of base knowledge and a sound set of arithmetic inference rules, but she is resource-bound by the fact that her set of inference rules is incomplete, i.e. it does not allow her to prove all of the truths in the arithmetic.
d. Weaknesses of Syntactic Structures
Because the K operator is not an equivalence relation, syntactic structures do not have possibility relations between their worlds, and consequently syntactic assignments cannot capture the notion of the locality of an agent's knowledge. Moreover, the structure is not negation complete, which means that we cannot prove the compactness of its models.
Because they explicitly represent knowledge, syntactic structures may violate our intuitions concerning reasoning about knowledge. Due to this lack of expressive power, syntactic structures have been dubbed a means of representing knowledge rather than a means of modeling it.
2. Semantic Structures
a. The Model
A semantic structure, or a Montague-Scott structure (MS), is a tuple (W,π,C1,...,Cn) where W is a set of worlds, π(w) is a truth assignment to the primitive propositions for each world w in W, and Ci(w) is a set of subsets of W, for i = 1, . . . , n. MSs explicitly represent the truth values of propositions by defining the valuation π as a function mapping propositions to worlds, rather than propositions to truth values. Accordingly, the semantics of these structures is specified in terms of sets of worlds in which given propositions in the model are true, i.e. in terms of the "intensions" of its propositions. As a result, to an agent, φ is indistinguishable from ψ just in case φ and ψ have the same intension, or are true in exactly the same worlds. Unlike syntactic structures, MSs explicitly fix the semantics of propositions while retaining the notion of possible worlds.
Because the semantic approach reduces the semantic content of known formulas to sets of worlds, we can capture an agent's knowledge by listing the set of worlds in which the propositions he knows hold true. We refer to this set with the notation (Ca(w)), where a is an agent and w is a world, and C is the set of worlds containing only those propositions that a knows at w.
Standard propositional semantics holds for atomic propositions, conjunctions, and negations, but the semantics of the knowledge operator is specified in terms of (Ca(w)). We say that a world logically implies knowledge of a proposition if and only if that world is in the set of worlds in which the proposition is true.
b. Properties of Knowledge on MSs
Because the knowledge operator is given meaning in terms of its membership in a class of models that make a proposition true, we have closure under logical equivalence in semantic structures. That is, where p=q, the axiom holds because, by definition, formulas with the same truth values in all possible worlds are indistinguishable to an agent.
Although there is a failure of all other forms of logical omniscience in MSs, we can accommodate other properties of knowledge by constraining the intensions of propositions. Knowledge of valid formulas, for example, is secured when we stipulate that all worlds are in the intension of K[a]p. Similarly, we get closure under conjunction by stipulating that the intensions of the propositions p and q are equivalent to the worlds in the intersection of Caφ and Caψ.
c. Weaknesses of MSs
MSs are able to model types of logical omniscience other than closure under conjunction without increasing the complexity of reasoning required to make the appropriate derivations in the structure. However, once we modify the structure to allow for closure under conjunction, semantic structures become PSPACE-complete rather than NP-complete, and this is undesirable for reasons beyond the scope of this entry.
B. Nonstandard Structures
Nonstandard Structures leave the SKS knowledge operator K in tact but change the semantics of epistemically available propositions. In other words, these structures have the expressive power provided by equivalence relations, but they are restricted from expressing certain types of logical omniscience because of the nature of the propositions able to be known by agents in the structures.
Nonstandard structures utilize aspects of the syntactic approach in their free assignment of truth values, and they also define propositional semantics in terms of worlds as in the semantic approach.
In nonstandard models we say that an agent has logical omniscience "with respect to" the nonstandard semantics of the formulas in the model. There are several ways to make propositional semantics nonstandard; here we present an approach which modifies the standard semantics of negation.
1. The Model
A nonstandard Kripke structure M is a tuple (W,π,K1,...,Kn, * ), where the tuple (W,π,K1,...,Kn) is a Kripke structure, and * is a unary function from the set of worlds W to itself (where we write w* for the result of applying the function * to the world w) such that w** = w for every w in W. Though we retain the notion of possible worlds, we redefine each world w as a set of databases, one containing the formulas that are true in the world and one containing those that are false. Without loss of generalization, we say that φ is true if it belongs to the "database" of true formulas, such that φ can belong to both the true and false databases at any given point in time. Furthermore, every world w has a counterpart world w* which contains the set of databases that are compliments of those in the "source" world w.
Talk of membership in databases allows φ to have "an independent truth value": a truth value that is not defined semanticaly in terms of its negation. The propositional semantics of negation is correspondingly modified: is true in w not if φ is not logically implied by w, but rather only if has membership in the compliment class of false formulas in w*. If w=w*, then we secure the standard propositional semantics of negation.
If φ and are in neither database, then neither proposition is true or false, hence nonstandard models do not presuppose monotonicity. We refer to a world in which φ and hold as incoherent, and one in which neither φ nor hold as incomplete.
2. Properties of Knowledge in Nonstandard Structures
One interesting feature of nonstandard structures is that logical implication is not synonymous with material implication. In order for to hold, whenever Kaψ holds, Kaφ must hold as well. This is on account of the independence of the truth values of propositions in nonstandard structures, which prevents from being logically equivalent to . Nonstandard structures therefore define a new logical connective which allows them to express material implication which has the meaning specified above.
There are no valid formulas in nonstandard structures in part on account of its treatment of negation. It is not the case that a world makes φ true if and only if the world does not logically imply . Thus, another interesting feature of nonstandard structures is that, while knowledge of valid formulas holds, there are no valid formulas in nonstandard structures, this property of knowledge has an idiosyncratic meaning.
3. Agents Modeled by Nonstandard Structures
Because nonstandard models can represent worlds in which both φ and are true, they provide a means of modeling situations in which, for example, witnesses provide conflicting information about a crime without our logic suffering from the disadvantages of the explicit representation approaches.
4. Advantages of Nonstandard Structures
Some find standard propositional semantics unintuitive or otherwise problematic. For instance, it is far from obvious that any formula is logically implied by an invalid statement. So it is sometimes appealing to provide propositions with nonstandard semantics. Indeed, as opposed to the syntactic structure outlined above, the semantics of nonstandard models actually provides these structures with comparatively intuitive and instructive means of reasoning about knowledge.
C. Impossible Worlds Structures
While logicians consider worlds in which agents have knowledge of contradictions impossible, such impossible worlds are often epistemically available to agents for reasons outlined in the introduction, and we want to model them when they figure into agent's reasoning processes.
1. The Model
Impossible world structures augment a set of standard possible worlds with a set of worlds in which the standard rules of propositional logic do not apply. For example, we may have true in a world in which neither φ nor ψ is true. Such worlds are referred to as impossible worlds, and they serve only as epistemically accessible, but not metaphysically possible, states of affairs. Logical implication and validity are determined solely with respect to the standard worlds. Thus, while standard propositional semantics holds in possible worlds, the semantics in impossible worlds can functions in fanciful ways.
2. Properties of Knowledge in Impossible World Structures
The primary feature of impossible world structures that allows us to avoid logical omniscience is that logical implication is evaluated with respect to only possible worlds, while an agent’s knowledge is evaluated with respect to all of the worlds she considers possible, impossible and possible worlds alike. Because validity of a proposition is considered with respect to only possible worlds, and because agents consider impossible worlds, knowledge of valid formulas fails. For example, an agent may consider an impossible world in which φ or is false alongside a possible world in which φ or is true. Since one of the conjuncts in the proposition is false on account of the worlds epistemically accessible to the agent, the proposition is false. Closure under logical implication also fails in impossible world structures.
[edit] Other Alternatives to SKSs
A. Awareness Structures
An awareness structure is a tuple M = (S,π,K1,...,Kn,A1],...,An), where the tuple (W,π,K1,...,Kn) is a Kripke structure and A1 is a function associating a set of formulas with each world, for i = 1, . . . , n. By preserving the standard definition of the K operator, referred to in the structure as the "explicit knowledge" operator, awareness structures model agents who are in some sense logically omniscient. But by including an "implicit knowledge" (X) operator and an "awareness" (A) operator, they more accurately reflect the phenomenology of some epistemological states of affairs. Implicit knowledge is knowledge of a proposition in all worlds that an agent considers possible. Explicit knowledge is awareness of implicit knowledge. While all logical consequences of an agent's explicit knowledge are included in the set of his implicit knowledge, definitionally, an agent does not know the logical consequences of his implicit knowledge. The explicit-knowledge operator Ka may behave differently. Agents do not explicitly know all valid formulas.
By placing restrictions on the awareness operator we can capture some interesting properties of knowledge. For instance, if we stipulate that the following axiom holds in our model: Aaφ, then AaAaφ, then the agents in our model who are aware of the set of formulas in Aa are also aware that they are aware of these formulas. To require that agents who are aware of formulas of which they do and do not know, we stipulate that Aax then KaAax and .
By definition, the implicit-knowledge operator Ka behaves just as it does in a Kripke structure, it is closed under material implication, and Kix is valid for every valid formula x.
The explicit-knowledge operator Ka may behave differently. Agents do not explicitly know all valid formulas. An agent's explicit knowledge is not necessarily closed under material implication.
B. Local Reasoning Structures
SKSs capture agents who have a single "frame of mind," that is, those who consider a set of worlds to be possible depending on their location with respect to other states of affairs. It is also useful to model agents who have multiple frames of mind, however. An example of such an agent is a politician whose agenda is determined by rapidly changing current events. Local reasoning structures, which enable an agent to consider different sets of worlds possible depending on her knowledge at a given time, are appropriate for this task.
The knowledge an agent has in a frame of mind is referred to as local knowledge. One interesting property of local reasoning structures follows from the failure of closure under conjunction in them: because the formulas an agent knows are relativized to his position with respect to sets of possible worlds, it is possible for a to know both φ and , to have inconsistent knowledge, while still forbidding the model from allowing the agent to know a contradiction. An agent does have knowledge of all valid formulas, however, because no matter where he is situated in the model with respect to other possible worlds, he will see the value of the valid formula as “true”.
[edit] References
- Fagin, Ronald et al. Reasoning about Knowledge. Cambridge: MIT Press, 2003.
- Meyer, J-J C., 2001, "Epistemic Logic," in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.
- Anderson, A. and N. D. Belnap. Entailment: The Logic of Relevance and Necessity. Princeton: Princeton University Press, 1975.
- Fagin et al. "A nonstandard approach to the logical omniscience problem." Artificial Intelligence, Volume 74, Number 2, 1995, p. 203-40.
- Hintikka, J. Knowledge and Belief. Ithaca: Cornell University Press, 1962.
- Montague, R. "Universal Grammar". Theoretica, Volume 36, 1970, p. 373-398.
[edit] See also
[edit] External links
- Stanford Encyclopedia of Philosophy:
- "Epistemic Logic" -- Hendricks, Vincent.
- "Modal logic" -- by James Garson.
- "Common Knowledge"- Vanderschraaf, Peter.
- Ho Ngoc Duc's Home Page:
- "Epistemic modal logic" -- Ho Ngoc Duc.
[[Category:Modal logic]]