12. A modal logic of a truth definition for finite models, pdf
\begin{abstract}
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.
\end{abstract}
12. Lower bounds for the unprovability of
Herbrand consistency
in weak arithmetics, pdf
\begin{abstract}
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.
\end{abstract}
11. On a question of Andreas Weiermann, pdf
\begin{abstract}
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}$.
\end{abstract}
10. On the second order intuitionistic
propositional logic
without a universal quantifier, pdf
\begin{abstract}
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$.
\end{abstract}
9. Undecidability and concatenation, pdf,
published
version
\begin{abstract}
We consider the
problem stated by Andrzej
Grzegorczyk in
``Undecidability without arithmetization''
(Studia Logica 79(2005))
whether
certain weak theory of concatenation is essentially
undecidable.
We give a positive answer for this
problem.
\end{abstract}
8. Finite arithmetics, pdf,
published
version
\begin{abstract}
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.
\end{abstract}
7. The Intended Model of Arithmetic.
An Argument from Tennenbaum's Theorem,
pdf
\begin{abstract}
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.
\end{abstract}
6. Coprimality in finite models, pdf,
published
version
\begin{abstract}
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.
\end{abstract}
5. FM-representability and beyond, pdf,
published
version
\begin{abstract}
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.
\end{abstract}
4. Theories of arithmetics in finite models, pdf,
published
version
\begin{abstract}
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
operation.
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.
\end{abstract},
3. Degrees of logics with Henkin Quantifier
in poor vocabularies, pdf,
published
version
\begin{abstract}
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].
\end{abstract}
1. Arithmetics in finite but potentially
infinite worlds,
pdf
\begin{abstract}
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))$.
\end{abstract}