7
$\begingroup$

In retrospect the original version of this question was impossibly bloated. Here's a better version:

There are many results about when first-order sentences are preserved by algebraic operations on model classes; for example, in first-order logic the sentences preserved by taking substructures are those semantically equivalent to (= having the same models as) universal sentences.

I'm broadly interested in preservation results beyond first-order logic. In particular, I'd like to know if preservation under taking (arbitrary) Cartesian products nicely characterizable in second-order logic (preservation under taking substructures is actually simpler for $\mathsf{SOL}$ than $\mathsf{FOL}$ since the former can directly quantify over substructures).

To pose this precisely:

Is there a computable set of $\mathsf{SOL}$-sentences $X$ such that the $\mathsf{SOL}$-sentences preserved by Cartesian products ("productive sentences") are exactly those semantically equivalent to elements of $X$?

Note that the productivity of a given $\mathsf{SOL}$-sentence is not set-theoretically absolute. However, neither is semantic equivalence between even individual $\mathsf{SOL}$-sentences, so this doesn't immediately give a negative answer to the question.

I'm also interested in what happens if we weaken "semantically equivalent to elements of $X$" to "semantically equivalent to possibly infinite conjunctions of elements of $X$."

$\endgroup$
6
  • $\begingroup$ How do you define the Cartesian product of two models (without reducing mod an ultrafilter)? (In particular, if the language has relation symbols, while there are ways one might define the products of the relations, it's unclear to me that there's any obvious canonical way.) $\endgroup$
    – Farmer S
    Sep 20, 2021 at 6:15
  • $\begingroup$ Actually I think I found a reference for that. But another question: what does „semantically equivalent“ mean? $\endgroup$
    – Farmer S
    Sep 21, 2021 at 9:44
  • $\begingroup$ @FarmerS "Semantically equivalent" just means "has the same models." And I had in mind arbitrary products. (I've added each of these points to the question.) $\endgroup$ Sep 24, 2021 at 4:08
  • $\begingroup$ Prof. Keisler must know everything there is to know about preservation properties in logic. Have you asked him? $\endgroup$
    – bof
    Sep 24, 2021 at 7:25
  • $\begingroup$ @FarmerS Yes, I think that is the case. $\endgroup$ Sep 24, 2021 at 15:16

1 Answer 1

2
+100
$\begingroup$

EDIT: Now understanding "semantically equivalent", I change my answer (my previous answer, to a different question, is further below)...I'm working in ZFC.

Yes, there is such a computable set $X$; that is, $X$ is a set of productive second order sentences, and for every productive second order $\mathcal{L}$-sentence $\psi$, there is a semantically equivalent sentence $\varphi\in X$ (having the same models). Here we can take "productive" either to mean w.r.t finite products or set-sized products, and we fix countably many constant/function/relation symbols that we deal with.

Proof: The plan is to (i) give a recursive procedure to pass from sentences $\varphi$ to sentences $\psi_\varphi$ such that $M\models\psi_\varphi$ iff $M$ is a product $\Pi_{i\in I}M_i$ such that $I\neq\emptyset$ and each $M_i\models\varphi$, and (ii) then use $X=\{\psi_\varphi\bigm|\varphi\text{ is an second order }\mathcal{L}\text{-sentence}\}$.

First let's consider the set-product version, so $I$ can be whatever set above.

Note that if we can do (i), then $X$ as in (ii) works: Each $\psi_\varphi$ is easily productive, and if $\varphi$ is productive then $\varphi$ is semantically equivalent to $\psi_\varphi\in X$. (If $M\models\varphi$ then $M\models\psi_\varphi$ (take the product of only $M_0=M$, with $I=\{0\}$), and if $M\models\psi_\varphi$ then because $\varphi$ is productive, $M\models\varphi$.)

So it suffices to do (i). A slightly annoying thing to deal with here are empty models and models of cardinality 1, because they contribute less to the cardinality of a product. Let $M$ be the model in question. Then $\psi_\varphi$ says: if $M\models\neg\varphi$ then $M$ is isomorphic to a product $\Pi_{i\in I}M_i\times\Pi_{i\in J}M_i$ where $I\cup J$ has cardinality $>1$ and each $M_i\models\varphi$, and for each $i\in I$, $M_i$ has cardinality 1, and for each $i\in J$, $M_i$ has cardinality $\neq 1$. Note that we can now ignore the case that some $M_i$ is empty, because this just makes the product empty (hence isomorphic to $M_i$).

Note that we can identify (in SOL) whether $M$ is infinite.

Case 1: $M$ is infinite.

Note that in order to be a product as above, $M$ must have cardinality $\Pi_{i\in J}\lambda_i$ where $\lambda_i=\mathrm{card}(M_i)$. Since $M$ is infinite, and $\mathrm{card}(M_i)>1$ for $i\in J$, we have $0<|J|<2^{|J|}\leq\mathrm{card}(M)$, so we can find a subset of $J'\subseteq M$ of cardinality $|J|$. Similarly, each $\lambda_i\leq\mathrm{card}(M)$, so we can find a subset $N'_i\subseteq M$ with $\mathrm{card}(N'_i)=\lambda_i$, and a structure $M'_i$ on $N'_i$ such that $M'_i\equiv M_i$ (note these are all structures in the same finite language that $\varphi$ uses). Fixing bijections $\pi:J'\to J$ and $\sigma_i:N'_i\to M_i$, let $M'_i$ be the structure on $N'_i$ isomorphic to $M_i$ via $\sigma_i$. We can find some (finitely many) relations describing these things; e.g. we have a binary relation $R$ where $R(x,y)$ iff $x\in J'$ and $y\in N'_{\pi(x)}$.

Suppose for the moment that $I=\emptyset$; we just want to assert that $M$ is isomorphic to the product $\Pi_{i\in J}M_i$. For this, we want to assert (using SOL) that there is a binary relation $R$ (on the universe of $M$) and some other relations $R^P$ etc for the symbols $P$ etc used in $\varphi$, coding a set $J'$ and models $M'_i$ as above, each $M'_i$ models $\varphi$, and $M$ is isomorphic to their product. So it just remains to assert the isomorphism. But this is just done by coding an isomorphism through another relation: Code an isomorphism $\tau:M\to\Pi_{i\in J}M_i$ via the ternary relation $R_\tau$ where $R_\tau(a,x,y)$ iff $a\in M$ and $x\in J'$ and $R(x,y)$ and $\tau(a)(\pi(x))=\sigma_i(y)$. (That is, $\tau(a)$ is an element of the product, i.e. a function $\tau(a):J\to\bigcup_{i\in J}M_i$ with $\tau(a)(i)\in M_i$ for each $i\in J$. And $\pi:J'\to J$ is the bijection above. So $\tau(a)(\pi(x))=\tau(a)(i)\in M_i$, so this is of the form $\sigma_i(y)$ for some $y\in N'_i$.) Thus, we just have to assert that there is a binary relation $R$ on $M$, and various relations $R^{P_1},\ldots,R^{P_n}$ for the symbols $P_1,\ldots,P_n$ in $\varphi$, such that $R,R^{P_1},\ldots,R^{P_n}$ code a collection of models, indexed by $\mathrm{dom}(R)$, each modelling $\varphi$, and there is a ternary relation $R'$ on $M$, such that $R'$ codes an isomorphism between $M$ and the product of the models just mentioned, as coded above.

This deals with the $I=\emptyset$ case. Now suppose $I\neq\emptyset$. The slight irritation here is that these factors of the product don't add to the cardinality of $M$, so it might be that $I$ has cardinality bigger than $M$. However, note that this case is irrelevant, and in fact, we can assume that $I$ is finite. This is because there are only finitely many non-isomorphic models with 1 element and in the symbols used in $\varphi$, and the if $M_i,M_{i'}$ are isomorphic 1-element models, then note that their product is still isomorphic to the same model; likewise for infinite products of the same 1-element model. So we may assume $I$ is finite. That being the case, it is easy to modify the preceding paragraph to incorporate the full product $\Pi_{i\in I}M_i\times\Pi_{i\in J}M_i$.

Case 2: $M$ is finite.

We deal with $J$ just as before. For $I$, in case $M$ has too small cardinality, we can just hard code all of the (finitely many) possible products of 1-element models, in the language of $\varphi$, into a disjunction of possibilities. That is, first compute a list $A_1,\ldots,A_k$ of all such products (up to isomorphism). Then when writing $\psi_\varphi$, just say "There is $i\leq k$ such that $M$ is isomorphic to $A_i\times\Pi_{i\in J}M_i$ (where $J,M_i$ are as before)".

This completes the description of $\psi_\varphi$, and note that $\varphi\mapsto\psi_\varphi$ is recursive.

That was the case for arbitrary products. For finite products it is the same, except that we must also assert that $I,J$ are both finite. But since we have SOL, this is no problem.


REMARK: It's important above that "false" is productive, so that we can (and must) have sentences in $X$ which have no models. Suppose one modified the question and demanded that all the sentences in $X$ be true. Then (1) it is no longer possible. Similarly, (2) there is no computable set $X$ of true SOL sentences such that for each true SOL sentence $\varphi$, there is some $\psi\in X$ which is semantically equivalent to $\varphi$. For (2): Let $\delta$ be the least ordinal such that $V_\delta\equiv_{\Sigma_2}V$. Then $V_\delta$ is also the least set containing models of all consistent SOL sentences. But this means that using $X$, we can define $\delta$ in a $\Sigma_2$ way, and since $X$ is computable, therefore $\{\delta\}$ is $\Sigma_2$, which contradicts the definition of $\delta$. Note that this shows that in fact no such $X$ can be $\Sigma_1$-definable. For (1) it is similar, because the true productive SOL sentences are still cofinal in the true SOL sentences. (Given $\varphi$ true productive, $\psi_\varphi$ (as above) is "above" $\varphi$.)


Original answer (actually to another question): I think the answer to the first question is no, but I'm not totally sure what "semantically equivalent" should mean.

As a warm-up, first consider the version of the question for finite products (I'm not sure whether you meant finite or arbitrary products).

And avoiding the question of "semantically equivalent", let's restrict attention to the second order language $\mathcal{L}=(0,1,+,\times)$ of arithmetic (without $<$), and show that the set $X$ of productive sentences of $\mathcal{L}$ is itself not computable.

(Also, I'm taking the product $P$ of two $\mathcal{L}$-models $M,N$ to have $c^P=(c^M,c^N)$ for constants $c=0,1$, and $+/\times$ are likewise defined component-wise. Likewise for arbitrary products.)

To show $X$ (the finite product version) is not computable, we just identify a computable sequence $\left<\psi_n\right>_{n\in\mathbb{N}}$ of sentences such that $\psi_n$ is finitely productive iff $n\in 0$-jump.

Observe first that there is a finitely productive sentence $\psi$ of second order $\mathcal{L}$ which asserts "The model is a product of finitely many, but at least 1, copies of $\mathbb{N}$". For this, say (i) The sub-model generated by $(0,1,+)$, extended with the restriction of $\times$, is isomorphic to $\mathbb{N}$, and (ii) there is some $n\in\mathbb{N}$ and an isomorphism between the $n$-fold product of $\mathbb{N}$ and the full model.

Now for $n\in\mathbb{N}$ let $\psi_n$ be the sentence $\psi$+"if the model is not isomorphic to $\mathbb{N}$ then $n\in 0$-jump", where $0$-jump is defined using the copy of $\mathbb{N}$ found as in (i) above (note that because it models $\psi$, we can indeed find a copy of $\mathbb{N}$ in this way to start with).

Then $\psi_n$ is finitely productive iff $n\in 0$-jump: If $n\in 0$-jump this is clear; if $n\notin 0$-jump then note that $\mathbb{N}\models\psi_n$ but $\mathbb{N}^2\models\neg\psi_n$ (it's easy to see that $\mathbb{N}$ and $\mathbb{N}^2$ are not isomorphic).


Edit: generalization for arbitrary products. The new thing here is to appropriately adapt $\psi$. But for this, I want to work instead with the language $\mathcal{L}'=(0,1,+,\times,\leq)$. I am taking products of relations to be defined using the "for all" quantifier, i.e. in our case, for the product $P$ of a sequence $\left<M_i\right>_{i\in I}$ of models, $f\leq^Pg$ iff $f(i)\leq^{M_i}g(i)$ for all $i\in I$. I'll write $<^*$ for the strict part of $\leq^P$ below (note this need not be the same as the product of the strict parts of respective $\leq$s).

So we want a sentence $\psi$ which says "the model is the product of set-many, but at least 1-many, copies of $\mathbb{N}$". Let $P$ be the product of $I$-many copies of $\mathbb{N}$. Given $j\in I$, let $f_j\in P$ be the function $f_j:I\to\mathbb{N}$ where $f_j(j)=1$ and $f_j(i)=0$ for $i\neq j$. Note that the set $A=\{f_j\bigm|j\in I\}$ is definable over $P$: given $f\in P$, we have $$ f\in A\iff [f\neq 0^P\text{ and for all }g\text{, if }g<^*f \text{ then }g=0^P],$$ where $<^*$ is the strict part of $\leq^P$. Then from $A$, we can uniformly identify the models $\mathbb{N}_f$, for $f\in A$, generated by $\{f\}$ by adjoining $0^P$ and closing under $+$, interpreting $1$ as $f$ and restricting $\times,\leq$ from $P$. And then $P$ is isomorphic to $\Pi_{f\in A}\mathbb{N}_f$.

So to assert that a given model $M$ (in the language above) is some product of set-many (at least 1) copies of $\mathbb{N}$, just define the set $A^M$ in the same manner, assert that every $f\in A^M$ generates (by adjoining $0$, closing under $+$, and interpreting $1$ as $f$) a model $\mathbb{N}_f$ which together with the restriction of $\times^M,\leq^M$, is isomorphic to $\mathbb{N}$, and $\mathbb{N}_f\cap\mathbb{N}_g=\{0^M\}$ when $f\neq g\in A$, and that $M$ is isomorphic to the product $\Pi_{f\in A}\mathbb{N}_f$. To say the latter, just say that there is a binary relation $R\subseteq M^2$ which codes an isomorphism $\pi:M\to\Pi_{f\in A}\mathbb{N}_f$, via $R(x,y)$ iff $y\in\mathrm{rg}(\pi(x))$. It is easy enough to write down the properties that $R$ needs in order to code an isomorphism in this way.

This $\psi$ is (set-)productive, and has the right meaning. Now define $\psi_n$ as before, and we get the same result as before.

$\endgroup$
1
  • $\begingroup$ Quite nice, I'm surprised by this result! $\endgroup$ Sep 25, 2021 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.