7
$\begingroup$

I am not a logician, so this is just kind of curiosity. Suppose you have a axiomatic system (?) like ZFC. Take $X$ to be the set of possible sentences, and set $x \sim y$ whenever one can prove the other. Let $X'$ be the set $X$ modulo this equivalence. This is an ordered set via $x \le y$ if $x$ can show $y$.

What I ask is the following: suppose that $x,y \in X'$ have the "same consequences", i.e. for every $z \in X'$

$$ x < z \Leftrightarrow y < z$$

Is it true that $x=y$?

EDIT: this is not true of course for general posets. Take for example $\{0 < 1\}^2$: the objects $(0,1), (1,0)$ are different but have the above property.

$\endgroup$

1 Answer 1

3
$\begingroup$

Incidentally, this poset is called the Lindenbaum(-Tarski) algebra. Below I'll conflate Boolean operations with their induced operation on $\sim$-classes.

The answer is yes - two distinct equivalence classes cannot lie strictly above the same things. Of course, as you say this is not true in arbitrary posets. What makes Lindenbaum algebras special is their additional algebraic structure coming from the logical connectives.

First, a general point. In a poset $\mathbb{P}$, let the strict lower cone below $p\in\mathbb{P}$ be the set $\{q\in\mathbb{P}: q<p\}$. Then in any poset at all, we know that two distinct elements with the same strict lower cones must be incomparable. So we just need to prove:

In a (non-silly) Lindenbaum algebra $L$, if $a,b$ are incomparable then they have different strict lower cones.


As a warm-up, let's look at the case of propositional logic:

  • If there are finitely many propositional atoms $a_1,...,a_n$, then the sentences $(a_1\vee...\vee a_n)$ and $(\neg a_1\vee...\vee\neg a_n)$ are distinct but have the same strict lower cones: the only sentence strictly weaker than either (up to $\sim$) is the tautology $\top$.

  • If there are infinitely many propositional atoms, however, things are nicer: for $\psi\not\ge\varphi$, fixing some propositional atom $c$ not occurring in either (which exists since there are infinitely many propositional atoms but sentences are only finitely long) we have $\varphi>\varphi\vee c$ but $\psi\not\ge\varphi\vee c$.

In fact, all we really needed in that last bulletpoint is that $\psi\wedge\neg c\not\ge \varphi$ and $c\not\ge\varphi$. So in a setting like the Lindenbaum algebra of ZFC, we'll want to find sufficiently independent statements, which in this case means:

Suppose $ZFC+\psi\not\vdash\varphi$. Then there is some $\theta$ such that $ZFC+\psi\wedge\neg\theta\not\vdash\varphi$ and $ZFC+\theta\not\vdash\varphi$.

This is harder to show, but is still true - it's a consequence of Godel's incompleteness theorem for ZFC. Specifically, we'll prove something a bit stronger: letting $T=ZFC+\psi$ and assuming $T\not\vdash\varphi$ we'll show that there is some $\theta$ such that $T+\theta\not\vdash\varphi$ and $T+\neg\theta\not\vdash\varphi$.

Suppose no such $\theta$ exists. Then for each $\gamma$, exactly one of the following hold:

  • $T+\gamma\vdash\varphi$.

  • $T+\neg\gamma\vdash\varphi$.

We can't have both, since then we would have $T\vdash\varphi$ outright; and if neither were to hold, we would have our desired $\theta$. Since an inconsistent theory proves everything, this means we can use $\varphi$ as a "consistency detector:" given a sentence $\gamma$, we search simultaneously for a proof of $\varphi$ from $T+\gamma$ and for a proof of $\varphi$ from $T+\neg\gamma$, concluding that $T+\neg\gamma$ is consistent if we find the former first and concluding that $T+\gamma$ is consistent if we find the latter first.

That is, assuming no such $\theta$ exists, we have a computable procedure $\Pi$ for picking - for any sentence $\gamma$ - one of $\gamma$ or $\neg\gamma$ which we are then certain is consistent with $T$. But since computable processes are representable in ZFC - indeed much less - we can write a sentence $\rho$ which intuitively says "$\Pi$ applied to me chooses my negation," and this yields a contradiction. (See the second half of this answer of mine for a bit more detail on this point.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.