2. A union of the agent's possibilities, that evaluate L, and the impossible worlds that evaluate N,
is *fixed* and *independent* of e, and is the set of all *conceivable* states. Formally, in **ON L**, Lα is evaluated *wrt.* worlds w ∈ e, and Nα is evaluated *wrt.* worlds w **∈ W −** e; the union of which is W. The intuition is that the exact complement of an agent's possibilities is used in evaluating N.

3. Given any set of possibilities, there is always a model where *precisely* this set is the epistemic state. Formally, in **ON L**, any subset of W can be defined as the epistemic state.
Although these notions seem clear enough in the single agent case, generalizing them to the many agent case is non-trivial [Halpern & Lakemeyer 2001]. We shall return to analyze the features shortly. Let us begin by extending the language. Let **ON L**n be a first-order modal language that enriches the nonmodal subset of **ON L** with modal operators Li and Ni for i = **a, b**. For ease of exposition, we only have two agents a (Alice) and b (Bob). Extensions to more agents is straightforward. We freely use Oi, such that Oiα is an abbreviation for Liα ∧ Ni¬α, and is read as "all that i knows is α". Objective and subjective formulas are understood as follows.

Definition 2.1: The i-depth of a formula α, denoted |α|i, is defined inductively as (i denotes Li or Ni):
1. |α|i = 1 for atoms, 2. |¬α|i = |α|i, 3. |∀**x. α**|i = |α|i, 4. |α ∨ β|i = max(|α|i, |β|i),
5. |iα|i = |α|i, 6. |jα|i = |α|j + 1, for j 6= i A formula has a depth k if max(a-depth,b-depth) = k. A formula is called i-objective if all epistemic operators which do not occur within the scope of another epistemic operator are of the form j for i 6= j. A formula is called i-subjective if every atom is in the scope of an epistemic operator and all epistemic operators which do not occur within the scope of another epistemic operator are of the form i.

For example, a formula of the form LaLbLap ∨ Lbq has a depth of 4, a a-depth of 3 and a b-depth of 4. Lbq is both b-subjective and a-objective. A formula is called *objective* if it does not mention any modal operators. A formula is called *basic* if it does not mention any Ni for i = **a, b**. We now define a notion of epistemic states using k-*structures*. The main intuition is that we keep separate the worlds Alice believes from the worlds she considers Bob to believe, to depth k.

Definition 2.2: A k-structure (k ≥ 1), say e k, for an agent is defined inductively as:
− e 1 **⊆ W × {{}}**,
− e k **⊆ W ×** E
k−1, where E
m is the set of all m-structures.