## Parameterization in monadic logic

### Grigori Mints

Dept. of Philosophy
and CSLI

Stanford University

Monday, 22 December 2008, 14:00 (note the unusual weekday)

Cybernetica Bldg (Akadeemia tee 21), room B126

**Abstract**: A logical formula *F(X,P)* is
treated here as an equation to be satisfied by solution
*X*_{0}(P) for unknown predicate symbols
*X* (with parametric predicate symbols *P)*. We find
general solution for monadic predicate logic with
equality. Elimination of quantifiers provides necessary and
sufficient solvability conditions of the form *∨*_{i≤ m}
R_{i}(P) with *R*_{i}(P) =
∧_{s} Q_{i,s}x P_{s}(x). Here
*s* ranges over all possible
*states*
*P*_{1}^{σ1}(x)∧...∧
P_{n}^{σn}(x) and
*Q*_{i,s} is *∃*_{=is} or
*∃*_{≥ is}. The general solution
consists of the components *X*_{0}^{i}(P),
*i≤ m*, such that *R*_{i}(P) →
F(X_{0}^{i}(P),P) (*)
is valid. *X*_{0}^{i}(P) contains ε-terms for
*∃*-quantifiers in *K*_{i}. This solves a
parameterization problem stated by J. McCarthy (see this
page).

The components are glued together in a standard way:
*
X*_{0}:= (R_{1}∧
X_{0}^{1})∨(R_{2}∧ &neg;
R_{1}∧ X_{0}^{2})∨ ... ∨
(R_{m}∧∧_{i < m}&neg; R_{i}∧
X_{0}^{m})
.
*X*_{0} is a solution: *∨*_{i}
R_{i} → F(X_{0},P), since
*R*_{i}→ (X_{0} ↔
X_{0}^{i}) and (*) holds.

*X*_{0} is a general solution: for every state
*s* and *i ≤ m* there is a substitution
*σ*_{i} for the predicates occurring in
*X*_{0} but not in *P* (arbitrary constants)
that turns *X*_{0} into
*X*_{0}^{i} in state
*P*_{s} provided *R*_{i} holds. This implies
*
∨*_{i} R_{i}→ ∨_{i} (σ_{i}( X_{0})↔ X_{0}^{i})
since *∨*_{s} P_{s} is valid.

(Joint work with Tomohiro Hoshi.)

Tarmo Uustalu

Last update 9.12.2008