4
$\begingroup$

An abstract logic satisfies the LS property for single sentences if each satisfiable sentence has a countable model. Similarly, the LS property for countable sets of sentences holds if every satisfiable countable set has a countable model.

Lindström's first theorem is usually stated in terms of the weaker LS property (for single sentences). This makes the coding of partial isomorphisms, a crucial step in the proof, more complicated. In fact, it is straightforward to codify partial isomorphisms with a countable family of predicates $I_n(\overline{x},\overline{y})$, for $n\geq 1$, and a countable set of sentences asserting that $I_n(\overline{x},\overline{y})$ holds iff the natural matching of the $n$-tuples $\overline{x}$ and $\overline{y}$ of individuals in $U$ and $V$, respectively, preserves the relevant predicates and the back-and-forth property holds:

$\forall\overline{x}\forall\overline{y}(I_n(\overline{x},\overline{y})\rightarrow \forall x(U(x)\rightarrow \exists y I_{n+1}(\overline{x},x,\overline{y},y)))$

and similarly for the "back" part.

Now, this could simplify the proof of Lindström's theorem if we could independently prove that the weaker LS property implies the strongest for an apropriate class of logics. (We know that a compact regular logic satisfying the weaker LS property also satisfies the stronger, because this logic must be equivalent to first-order logic. That would be enough if we could prove this directly, without using Lindström's theorem).

Incidentally, every logic satisfying the LS property for single sentences that I know also satisfies the property for countable sets. What is known about this?

$\endgroup$
8
  • $\begingroup$ Fix a sequence of nonisomorphic countable structures $\mathcal{A}_i$ ($i\in\omega$) and consider a logic generated by sentences $\sigma_i$ where for each $i$ the models of $\sigma_i$ are exactly the uncountable structures or the structures isomorphic to $\mathcal{A}_i$. This has dLS for single sentences but not for satisfiable countable theories. $\endgroup$ Commented Jun 6 at 22:25
  • $\begingroup$ @NoahSchweber Nice comment. If I understood correctly, this logic is not regular, for $\sigma_i\wedge\sigma_j$ has only uncountable models? $\endgroup$ Commented Jun 6 at 23:11
  • $\begingroup$ Sorry, that was a typo on my part - the countable models of $\sigma_i$ should be (up to isomorphism) the $\mathcal{A}_j$s with $j\ge i$. Unless I'm having a silly moment this does yield a regular logic; in particular, a conjunction of $\sigma$-formulas without a countable model must involve a negated $\sigma$-formula in which case it has no uncountable models either and so is unsatisfiable. $\endgroup$ Commented Jun 7 at 0:49
  • $\begingroup$ @NoahSchweber Thanks! If this extends first order logic, then it is not regular. Take the conjunction of an $\omega$-categorical sentence $\varphi$ with a $\sigma_i$, for $i$ large enough. I should add that I am mostly interested in extensions of FOL. $\endgroup$ Commented Jun 7 at 1:06
  • 1
    $\begingroup$ Nothing better than applying Lindstrom's theorem itself, sadly. I'll think about it though, it's a fun problem! $\endgroup$ Commented Jun 7 at 1:27

0

Browse other questions tagged or ask your own question.