The EPL Theorem, Part 4

Outline of Proof

Let’s sketch out the proof of the EPL Theorem.

Some notation

We’ll write ⟨𝑠₁, …, 𝑠ₙ⟩ as an abbreviation for the following propositional formula meaning “exactly one of 𝑠₁, …, 𝑠ₙ is true”:

\(\langle s_1, \ldots, s_n\rangle \triangleq \left(\bigvee_{i=1}^n s_i\right) \wedge \left( \bigwedge_{i=1}^{n-1}\bigwedge_{j=i+1}^n \neg(s_i\wedge s_j) \right).\)

(The first conjunct says that at least one of the 𝑠ᵢ is true, and the second says that no two of them are both true.)

The proof steps

The proof has these steps:

1. Using R1 (invariance from logical equivalence) and R2 (invariance under definition of new symbols), show that

   \(\begin{eqnarray*} (A\mid X) &=& (s_1\vee\cdots \vee s_k \mid \langle s_1,\ldots,s_n\rangle) \\ &\triangleq& \Upsilon_2(k, n) \end{eqnarray*}\)

   where 𝑛 is the number of truth assignments that satisfy 𝑋, 𝑘 is the number of these truth assignments that also satisfy 𝐴, and 𝑠₁, …, 𝑠ₙ are are any 𝑛 distinct propositional symbols. This means that (𝐴 | 𝑋) is a function of 𝑘 and 𝑛. We will call this function 𝛶₂.

2. Using R1 and R3 (invariance under addition of irrelevant information), show that for all 𝑚 > 0, 𝑛 > 0, and 0 ≤ 𝑘 ≤ 𝑛,

   \(\Upsilon_2(m k, m n) = \Upsilon_2(k, n) \)

   and therefore (𝐴 | 𝑋) is a function of 𝑘 / 𝑛. We will call this function 𝛶₁. Hence

   \((A\mid X) = \Upsilon_1\left(\frac{k}{n}\right) \triangleq \Upsilon_2(k, n).\)

3. Using R4 (preservation of existing distinctions in plausibility), show that 𝛶₁ is a strictly increasing function: if 𝑥 and 𝑦 are rational numbers between 0 and 1 inclusive, with 𝑥 < 𝑦, then 𝛶₁(𝑥) is a plausibility value that is strictly less than 𝛶₁(𝑦).

Therefore 𝛶₁ is an order isomorphism between ℚ₀₁ (the rational numbers between 0 and 1 inclusive) and ℙ (the set of all plausibility values.) This means that 𝛶₁ defines a one-to-one correspondence between the elements of ℚ₀₁ and the elements of ℙ, as well as being strictly increasing.

Since 𝛶₁ is an order isomorphism, it has an inverse 𝑃 that is also a strictly increasing function, and we have

\(P(A \mid X) = P\left(\Upsilon_1\left(\frac{k}{n}\right)\right) = \frac{k}{n}.\)

Detail on step 1

We’ll save this for a follow-on post, as it is rather involved.

Detail on step 2

Define 𝑌 = ⟨𝑡₁, …, 𝑡ₘ⟩, where the 𝑡ᵢ are any 𝑚 propositional symbols disjoint from 𝑠₁, …, 𝑠ₙ. Then by R3, invariance under addition of irrelevant information, we have

\(\begin{eqnarray*} \Upsilon_1(k,n) &=& (s_1\vee\cdots\vee s_k \mid \langle s_1, \ldots, s_n\rangle) \\ &=& (s_1\vee\cdots\vee s_k \mid Y \wedge \langle s_1, \ldots, s_n\rangle) \\ &=& \Upsilon_1(m k, m n). \end{eqnarray*}\)

The last equality follows from the fact that 𝑌 has 𝑚 satisfying truth assignments on { 𝑡₁, …, 𝑡ₘ }, and so conjoining 𝑌 expands each satisfying truth assignment into 𝑚 distinct satisfying truth assignments.

Detail on step 3

Give rational numbers 𝑥 and 𝑦, with 0 ≤ 𝑥 < 𝑦 ≤ 1, express them as fractions with a common denominator 𝑛 > 0: 𝑥 = 𝑘 / 𝑛, 𝑦 = 𝑙 / 𝑛, with 0 ≤ 𝑘 < 𝑙 ≤ 𝑛. Then since

\(\begin{eqnarray*} \langle s_1, \ldots, s_n\rangle &\models& (s_1\vee\cdots\vee s_k) \rightarrow (s_1 \vee \cdots \vee s_l) \\ \text{but} && \\ \langle s_1, \ldots, s_n \rangle &\not\models& (s_1 \vee \cdots \vee s_l) \rightarrow (s_1 \vee \cdots \vee s_k) \end{eqnarray*}\)

we have

\(\begin{eqnarray*} \Upsilon_1\left(\frac{k}{n}\right) &=& \left(s_1\vee\cdots\vee s_k \mid \langle s_1,\ldots,s_n\rangle\right) \\ &\prec& \left(s_1\vee\cdots\vee s_l \mid \langle s_1,\ldots,s_n\rangle\right) \\ &=& \Upsilon_1\left(\frac{l}{n}\right). \end{eqnarray*} \)

where 𝑝 ≺ 𝑞 means that 𝑝 is a plausibility value strictly less than 𝑞.

Final comments

Note that requirements R1, R2, and R3 are all invariance requirements, specifying ways in which we can jointly change 𝐴 and 𝑋 without changing (𝐴 | 𝑋). This is what turns the partial plausibility order inherent in propositional logic into a total order. But if all you have are invariance requirements, you can satisfy them by collapsing all plausibility values down to one single value, making the plausibility function a constant function. Requirement R4 prevents this collapse.