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}