Adam I. Gerard

Propositional Stability and Cohen Forcing

An early draft of mine on Propositional Stability:

Read the full draft.


Refining the verbiage a tad:

Propositional stability is a two-place predicate (dyadic or arity two) P(x,y): x exhibits (or has) propositional stability with respect to y.

Remark 6.

A great paper on Cohen Forcing.

For any two (classical, deductive) models M, M* of the same theory T such that:

  1. M* is an extension of M (by Cohen Forcing).
  2. Both M, M* satisfy proposition P.

P exhibits:

  1. Truth stability under M* with respect to M. (Truth instability otherwise.)
  2. Strong propositional stability.

Proof. Obvious. Trivially, any classically-consistent, deductive proof system, model, and logic that's a model-theoretic extension of another (of the same theory T) has, by definition, the same instruction set mapping propositions to truth values (e.g. the semantics for the logical connectives). What diverges between the two models, is that the background universe assumed in M* is larger than M.

Note: a model is a background universe (roughly, a "semantics for a logic") that makes all the sentences of the theory (the grammatically valid sentences of a language) and logic (the language and proofs system) evaluate to true. By the Principle of Explosion, any contradiction in a logic entails that anything can be proven within it (e.g. - that every sentence is true). So, the above holds even when the models are inconsistent.

So, trivially, the cases of interest in many Cohen Forcing scenarios are described by Fact 2 (with models also taken into consideration) within the draft. Many of the most interesting results are those in which theories differ (Axiom of Choice versus no Axiom of Choice, etc.).

For example, cases where a background universe of sets (and say, the axioms of ZFC) has added to it some set for which the axioms of ZFC set theory fails (self-referential sets). We can, of course, define more or less rigorous notions of a model so that consistency is required of them (which further delimits the cases alluded to).

Remark 7.

Edit: I've significantly updated and revised this remark to clarify and remove some typographical errors.

Remark 7a.

The original paper

Also: Kremer and notes: and

Kripke outline several techniques in his landmark paper:

  1. The general use of fixed points from elsewhere in mathematics to sentences of paradox. Fixed points are commonly used in Number Theory.

i. A fixed point of a function F is some x such that: F(x) = x.

ii. See: the Wolfram MathWorld entry.

  1. A closed-off construction (with two-valued semantics).
  2. A three-valued construction (using Kleene 3-valued semantics and models thereof) with truth values: true, false, neither true nor false.

I'm curious about any intersections between my nascent Propositional Stability formulation and fixed point semantics.

Consider a two-valued formulation with predicate T added to it along with T-Schema constraints:

  1. Using Kripke's technique, we define an extension of T (ext(T)) corresponding to true sentences and an anti-extension of T (anti(T)) corresponding to those sentences that we don't assign truth to. We also use the same convention that coded sentences are formulated and placed into respective extensions (representing truth statements about other truth statements and attributions of truth to names of sentences or their untruth): code(T) and code(anti(T)).
  2. A fixed point here is then any model in which code(T) = ext(T) and code(anti(T)) = anti(T) (which corresponds to the T-Schema constraint in model format).
  3. If our interpretation function, I assigns primitive truth in the standard fashion (lacking any alterations) to the Liar Sentence, the Liar Sentence gets assigned to both ext(T) and anti(T) (as well as the both coded extensions). Consequently:

i. The Liar Sentence exhibits truth stability between any two fixed points (and at the same fixed point).

ii. The Liar Sentence exhibits truth instability between any two fixed points (and at the same fixed point).

iii. The Liar Sentence exhibits strong propositional stability between any two fixed points.

A proof trivially exists at every fixed point h:

  1. The Liar Sentence is true (not false).
  2. The Liar Sentence is false (not true).
  3. The instruction set remains unchanged.

So, trivially, (by the Principle of Explosion - proof following a derived contradiction - or otherwise through direct proof):

  1. One can prove the same set of truth values at each fixed point, h, relative to every other fixed point h: true, false
  2. One can prove a different truth value at each fixed point h (but not at the exclusion of the others).

Note: sentences of paradox are the only class of sentences that exhibit all the properties above.

What are differences between models of paradoxical sentences in terms of propositional stability? How do sentences of paradox differ from others in terms of propositional stability? How do consistent models differ in terms of propositional stability? Now, we have some answers.

Remark 7b.

Regarding Kripke's Three-Valued Fixed Point Construction.

If we take a weaker reading about truth-values and disallow n to count as such ({t,f,n} is the set of values that our propositions can be mapped to but count only {t,f} as truth-values proper):

  1. The Liar Sentence exhibits strong propositional stability between any two fixed points.

Proof. Obvious. Following the definitions from Kremer:

Say that a sentence A is ρ-grounded iff lfp(ρ) = t or f, and ρ-intrinsic iff gifp(ρ) = t or f.

The Liar Sentence is neither κ-grounded nor κ-intrinsic since it gets the value n at every fixed point h.

  1. The Liar Sentence receives the value n at every fixed point h.
  2. The instruction set remains unchanged.

If we take a stronger reading about truth-values and disallow n to count as such (since the spirit of the original proposal was to allow truth-value gaps):

  1. The Liar Sentence only exhibits weak propositional stability between any two fixed points (since it would lack a truth-value).
  2. The Liar Sentence could be said to exhibit truth stability between any two fixed points (since it would lack a truth-value at any fixed point).
  3. The Liar Sentence could also be said to exhibit truth instability between any two fixed points (since it would lack any truth-value at any fixed point).

This turns on how we understand a truth-value. I think the more natural reading is the one above where "truth-value gap" just means "not being true or false".

There's more to be explored here with similar systems that just don't define a total truth predicate - e.g. the Liar Sentence receives no truth-value at all (not even n) in a two-valued but non-bivalent logic. The latter scenario would above would likely describe that scenario.

Remark 8.

Propositional stability is a logical interface.

Relevant to Cross Logics (acting as "shared intermediaries" between logics) or across permanent changes in logics.

Regarding Kripke's Fixed Points

One additional insight that's relevant to Truth Grounding and Liar:

  1. Kripke's Fixed Point construction identifies the smallest fixed point.
  2. This corresponds to identifying the most minimal set of sentences to restrict the T-Schema by (when comparing the primary machinery between the two proposals).
  3. I opt to restrict the axiom itself (its still a tautology afterwards and particularly if one also accepts the analyticity of the T-Schema itself) rather than a model.

A great read about some of these observations and the applications to programming languages.