Re: interpolation theorem of propositional logic

BTW: Often the interpolation theorem is
not only formulated for formulas, but
rather for sequents.

That is alfa and beta are sequents,
i.e. lists or multisets of formulas.
And if alfa |- beta, then there is
another sequent gamma such that:

alfa |- gamma and (i)
gamma |- beta and (ii)
S(gamma) subset S(alfa) intersect S(beta) (iii)

Whereby S has to be defined. You can
also take into account the polarity of
predicates. So if a predicate P occurs
possitively the P+ is in S. If it
occurs negatively then P- is in S.

When you allow sequents you don't
run into the true/p v ~p problem
with condition (iii).

Bye


David C. Ullrich wrote:
On Thu, 13 Apr 2006 13:24:15 +0200, Jan Burse <janburse@xxxxxxxxxxx>
wrote:



David C. Ullrich wrote:

On Wed, 12 Apr 2006 13:29:30 +0200, Jan Burse <janburse@xxxxxxxxxxx>
wrote:



Hi

David C. Ullrich wrote:


On 11 Apr 2006 03:36:16 -0700, "Li Yi" <liyi.cn@xxxxxxxxx> wrote:


If alpha |= beta, then there is some gamma all of whose sentence
symbols occur in both alpha and beta and such that alpha |= gamma |=
beta.

This is obviously false.
Hint: The weaker statement "If alpha |= beta, then there is some gamma all of whose sentence symbols occur in both alpha and beta"
is obviously false.

Depends on what one understands by sentence symbols.


The subject line specifies _propositional_ logic.
There's a perfectly standard notion of "sentence
symbol" in propositional logic



If for example sentence symbols means variables, function
symbols and predicate symbols,


and none of these exist in propositional logic.

If you restrict FOL to 0-ary predicate symbols,
even not allowing equality, you arrive a propositional
logic.


Supposing that's so, it's hard to see what your
point could be. Second, _if_ we restrict FOL as you
say, and _if_ we say that the resulting theory _is_
propositional logic (instead of saying more correctly
that it's isomorphic to propositional logic) then
variables and function symbols do not exist in
propositional logic.

First, and more to the point: _If_ we do that
we arrive at a situation where the statement
I made that you disputed is obviously correct:
Say P and Q are unary predicates. Let alpha be
P -> P and let beta be Q -> Q. Then alpha |- beta, although there does not exist
a gamma including only sentence symbols common
to alpha and beta.


These things do of course exist in predicate logic.
Calling them "sentence symbols" seems like maximally
strange terminology; the things that they "represent"
are not sentences.

A propositional variable is a sentence symbol.


I wasn't disputing that. A propositional variable
is indeed a sentence symbol. It doesn't follow that
"variables, function symbols and predicate symbols"
are sentence symbols.


Because a propositional variable in essence can
represent a full propositional formula. This
can be done either by using biimplication, i.e.
for example:

p <-> q & ~r.

Now p stands for q & ~r. Or by explicit substitutional
rules and/or lemmas.

For example many natural deduction systems
come with the rule, that if A is an axiom,
the one can use A[S] where S is a substition

from propositional variables to propositional

formulas.

Also there are lifting lemmas, that say for
example if A is a tautology then A[S] is
also a tautology.

Etc..



************************

David C. Ullrich
.

Relevant Pages