A modal logic of a truth definition for finite models, pdf

 The property of being true in almost all finite, initial segments of the standard
model for arithmetic is a $\Sigma^0_2$--complete property. Thus, it admits
a kind of a weak truth definition. We define such an arithmetical predicate.
Then we define its modal logic $\mathrm{SL}$ and prove a completeness
theorem with respect to finite models semantics. The proof that $\mathrm{SL}$
is the modal logic of a weak truth definition for finite arithmetical models
is based on an extension of $\mathrm{SL}$ by a fixpoint construction.

12. Lower bounds for the unprovability of Herbrand consistency
in weak arithmetics

 We prove that for $i\geq 1$, the arithmetic $I\Delta_0 + \Omega_i$
does not prove its own Herbrand consistency restricted to
the terms of the depth in $(1+\varepsilon)\log^{i+2}$,
where $\varepsilon$ is an arbitrary small constant greater than zero.

11. On a question of Andreas Weiermann, pdf
We answer positively the following question posed by Andreas Weiermann (private communication). Is it true that for every $\beta,\gamma<\varepsilon_0$ there exist $\alpha$ so that whenever $A$ is $\alpha$--large, $A$ satisfies some inessential assumption, say $\min(A) \geq 2$, and $G:A\rightarrow\beta$ is such that $\forall a\in A \psn(G(a)) \leq a$ 
there must exist $\gamma$--large $C\subseteq A$ on which $G$ is nondecreasing.
We give also some upper bounds on $\alpha$ for $\beta\leq \omega^{\omega^\omega}$.

10. On the  second order intuitionistic propositional logic
without a universal quantifier
, pdf

We examine second order intuitionistic propositional logic,
${\rm IPC}^2$. Let $\Fexst$ be the set of  formulas
with no universal quantification.

We prove Glivenko's theorem for formulas in $\Fexst$ that is,
for $\vp\in\Fexst$, $\vp$ is a classical tautology
if and only if
$\neg\neg\vp$ is a tautology of ${\rm IPC}^2$.

We show that for each sentence $\vp\in\Fexst$ (without free variables),
$\vp$ is a classical tautology
if and only if $\vp$ is an intuitionistic tautology.
As a corollary we obtain a semantic argument that  the quantifier $\forall$
is not definable in ${\rm IPC}^2$
from $\bot, \disj, \conj, \rightarrow, \exists$.

9. Undecidability and concatenationpdf, published version

We consider the problem stated by Andrzej Grzegorczyk in
``Undecidability without
 arithmetization'' (Studia Logica 79(2005))
certain weak theory of concatenation is essentially undecidable.
We give a positive
answer for this problem.

8. Finite arithmeticspdf, published version

The paper presents the current state of knowledge in the field of logical investigations of finite arithmetics. This is an attempt to summarize the ideas and results in this area. Some new results are presented - these are mainly generalilzations of the earlier results related to properties of sl-theories and some nontrivial cases of FM-representability theorem.


7. The Intended Model of Arithmetic.
An Argument from Tennenbaum's Theorem
, pdf

We present an argument that allows to determine the intended model of arithmetic
using some cognitive assumptions and the assumptions on the structure of natural numbers.
Those assumptions are as follows: the psychological version of the Church thesis,
computability of addition and multiplication and first order induction.
We justify the thesis that the notion of natural number is determined by
any recursive $\omega$-model of $\PA$ up to recursive isomorphism.


6. Coprimality in finite models, pdf, published version

We investigate  properties of the coprimality relation within
the family of finite models being initial segments of the standard
model for coprimality, denoted by $\FM((\omega,\bot))$.

Within $\FM((\omega,\bot))$ we construct an interpretation
of addition and multiplication on indices of prime numbers.
Consequently, the first order theory of $\FM((\omega,\bot))$
is $\Pi^0_1$--complete (in contrast to the decidability of the theory
of multiplication in the standard model). This result strengthens
an analogous theorem of Marcin Mostowski and Anna Wasilewska, 2004,
for the divisibility relation.

As a byproduct we obtain definitions of addition and multiplication
on indices of primes in the model $(\omega,\bot,\leq_{P_2})$,
where $P_2$ is the set of primes and products of two different primes
and  $\leq_X$ is the ordering relation restricted to the set $X$. This can
be compared to the de\-ci\-da\-bi\-lity of the first order theory  
of $(\omega,\bot,\leq_P)$, for $P$ being the set of primes (Maurin, 1997)
and to the interpretation of addition and multiplication in $(\omega,\bot,\leq_{P^2})$,
for $P^2$ being the set of primes and squares of primes, given
by B\`{e}s and Richard, 1998.

5. FM-representability and beyond, pdf, published version

This work concerns representability of arithmetical notions in finite models. It follows
the paper by Marcin Mostowski \cite{MM00a},  where the notion of {\em $\FM$--representability}
has been defined. We discuss how far this notion captures the methodological idea of representing
infinite sets in finite but potentially infinite domains.

We consider mainly some weakenings of the notion of $\FM$--representability.
We prove that relations {\em weakly $\FM$--representable} are exactly those
being $\Sigma^0_2$--definable. Another weakening  of the notion, namely
{\em statistical representability}, turns out to be equivalent to the original one.

Additionally, we consider the complexity of sets of  formulae naturally defined
in finite models. We state that the set of sentences true in almost all finite arithmetical
models is $\Sigma^0_2$--complete and that the set  of formulae $\FM$--representing
some relations is $\Pi^0_3$--complete.

4. Theories of arithmetics in finite models, pdf, published version

We investigate theories of initial segments of the standard models
for  arithmetics. It is easy to see that if the ordering relation
is definable in the standard model then the decidability results
can be transferred from the infinite model into the finite models.
On the contrary we show that the $\Sigma_2$--theory of
multiplication is undecidable in finite models. We show that this
result is optimal by proving that the $\Sigma_1$--theory of
multiplication and order is decidable in finite models as well as
in the standard model. We show also that the exponentiation
function is definable in finite models by a formula of arithmetic
with multiplication and that one can  define in finite models the
arithmetic of addition and multiplication with the concatenation

We consider also the spectrum problem. We show   that the spectrum
of arithmetic with multiplication and arithmetic with
exponentiation is strictly contained in the spectrum of arithmetic
with addition and multiplication.

3. Degrees of logics with Henkin Quantifier
in poor vocabularies
, pdf, published version

We investigate some logics with Henkin quantifiers.
For a given logic $L$, we consider questions of the form:
what is the degree of the set of
$L$--tautologies in a poor vocabulary (monadic or empty)?
We prove that the set of tautologies of the logic with all
Henkin quantifiers in empty vocabulary $L^*_\emptyset$ is of
degree $\bf{0'}$. We show that the same holds also
for some weaker logics like  $L_\emptyset({\sf{H}}_\omega)$
and $L_\emptyset({\sf{E}}_\omega)$.

We show that each logic of the form $L_{\emptyset}^{(k)}(Q)$
with the  number of variables restricted to $k$ is decidable.
Nevertheless -- following the argument of M.~Mostowski
from [Mos89] -- for each reasonable set theory no concrete
algorithm can provably decide $L^{(k)}(Q)$, for some $Q$.
We improve also some results related to undecidability and
expressibility for logics $L(\sf{H}_4)$ and $L(\sf{F}_2)$ of
Krynicki and M.~Mostowski from [KM92].

1. Arithmetics in finite but potentially infinite worlds, pdf

Let $\FMA$, for $\cA=(\omega,\bar{R})$, be the family of finite models being
initial segments of $\cA$. The thesis investigates logical properties of families
of  the form $\FMA$ for various arithmetics like arithmetic of
addition and multiplication, Skolem arithmetic of multiplication,
arithmetic of coprimality, of expo\-nen\-tia\-tion and
arithmetic of concatenation. We concentrate on  questions such as
decidability of various theories of $\FMA$; definability and interpretability of
one arithmetic, $\FMA$ in another, $\FMB$; the problem of representing
infinite relations in such families of models and on the spectrum problem
for such arithmetics.

Following M.~Mostowski (\cite{MM01, MM0?a}), we define some methods 
which one can use to represent infinite relations in finite models and some
natural theories of families $\FMA$, such as the set of sentences true in almost
all finite models from $\FMA$, $\sli(\FMA)$, or the set of sentences which are almost
surely true in $\FMA$ (in a probabilistic sense).
We show that for $\cA=(\omega,+,\cart)$, the first set is $\Sigma_2$--complete
and the second one is \mbox{$\Pi_3$--complete}. We also characterize  relations which can
be represented in both theories as exactly $\Delta_2$ relations (for the first
theory such a characterization was obtained in \cite{MM01}).  We show that the above
remains true even in the relatively weak  arithmetic of multiplication.

We also consider various  notions of definability and interpretability between arithmetics
of finite models. We give the definition of $\FM((\omega,+,\cart))$ in the finite models
of arithmetic of concatenation. This is an analogous to the situation in the infinite models
for these arithmetics but one should use a different method to give a suitable definition.

We show that, contrary to the infinite  case, arithmetic of expo\-nen\-tiation, $\FM((\omega,\exp))$,
is definable from arithmetic of multiplication only, $\FM((\omega,\cart))$.
We also give  interpretations of  $\FM((\omega, +,\cart))$ in arithmetic of coprimality,
$\FM((\omega,\bot))$, and in $\FM((\omega,\exp))$. The  interpretations reveal that in finite models
co\-pri\-ma\-lity or expo\-nen\-tiation are as hard as the full arithmetic of addition and multiplication,
which is especially surprising in the case of coprimality. We also describe the decidability border
for finite model arithmetic of multiplication showing that the $\Sigma_1$--theory of
$\FM((\omega,\cart,\leq))$ is decidable while the $\Sigma_2$--theory of $\FM((\omega,\cart))$ is undecidable.
We close the thesis with a partial characterization of families of spectra for $\FM((\omega,\cart))$
and $\FM((\omega,\exp))$.