2
$\begingroup$

I am wondering something about definability : Suppose we have an infinite set of finite structures $\mathcal{A}^i$ such that $\forall i \geq 0, \mathcal{A}^i \subseteq \mathcal{A}^{i+1}$, i.e for each $i \geq 0, $ $\mathcal{A}^i$ is a substructure of $\mathcal{A}^{i+1}$. Suppose that I can define a set $S_i$ in each $\mathcal{A}^i$ by a formula of first order logic $\varphi$ such that $S_i= \{ \vec{a} \in A^i, \mathcal{A}^i \vDash \varphi(\vec{a}) \} \subseteq \{ \vec{a} \in A^{i+1}, \mathcal{A}^{i+1} \vDash \varphi(\vec{a}) \} =S_{i+1}$, then can I find a first order formula defining the set $\bigcup \{ \vec{a} \in A^i, \mathcal{A}^i \vDash \varphi(\vec{a}) \} =\bigcup S_i$ in the structure $\mathcal{A}=\bigcup \mathcal{A}^i $?

P.S: Note that $|\mathcal{A}^i| < \omega$ and $|\mathcal{A}|=\omega$.

$\endgroup$

3 Answers 3

3
$\begingroup$

No. Let $(A,\le,P)$ be the structure of a partial order consisting of countably many disjoint copies of $\omega$, and a unary predicate $P$ which is satisfied by copies of all even points. That is, $A=\omega\times\omega$, $(a,n)\le(b,m)$ iff $a=b$ and $n\le m$, and $P((a,n))$ iff $n$ is even. Let $S=\{(a,n):a\text{ even}\}$. Obviously, $S$ is not definable in $A$. However, let $A^i=\{(a,n)\in A:a+n\le2i\}$, and $S_i=S\cap A^i$. Then $S_i$ is definable in $A^i$ by the formula $\varphi(x)=\exists y\,(x\le y\land\forall z\,(y\le z\to y=z)\land P(y))$.

$\endgroup$
6
  • $\begingroup$ Thanks for the answer, this is clear .... Now, Is there any class of formulae known to have the desired property ? Giving the finite structures and the formula, Is there any general method to proof either it will possible or not ? $\endgroup$
    – Thanyon
    Apr 20, 2012 at 11:10
  • $\begingroup$ If $\varphi$ is equivalent (in all the $A^i$ as well as in $A$) to both an $\exists\forall$ formula and a $\forall\exists$ formula, then it also defines $S$ in $A$. $\endgroup$ Apr 20, 2012 at 11:43
  • $\begingroup$ Well, there is something I do not understand : Suppose I have and inductive construction of my $S_i$ in a more powerful logic that FO, meaning $S_{i+1}=S_i \cup$ {$some new elements construct from x,y \in S_i$} with the help of a powerful logic. Suppose that the construction of the $S_i$ is such that in each $\mathcal{A}^i$ and even in $\mathcal{A}$ the formula of higher logic respect the desired conservation property , If there exists a first order formula defining $S_i$ does it means that the first order formula has to be a $\forall \exists$ formula ? $\endgroup$
    – Thanyon
    Apr 20, 2012 at 12:34
  • $\begingroup$ I don’t think there is reason this should hold. $\endgroup$ Apr 20, 2012 at 13:48
  • $\begingroup$ Thank so much, last question : Is there any tricks to construct a property over finite structure such that if it is first order definable then it is a $\forall \exists$ ? $\endgroup$
    – Thanyon
    Apr 20, 2012 at 14:33
0
$\begingroup$

The fact is that I have a property that it is preserved by union of chains, but I can express it by a Higher logic than First order , now what I am wondering is if there exists a FO formula, will it be a $\forall \exists$ , I mean could I have a FO formula that defines correctly my property over finite structure but gives a different interpretation in the union of finite structure ...? It seems strange to me because then it means that the formula will not be the "good definition", since my property has to be preserved ... Well there is something I can understand , i don't If I make my problem clear ... in fact i cannot really understand if the semantic which says that the property has to be preserved implies that the Fo formula (if it exists) has to be preserved ....

$\endgroup$
0
$\begingroup$

The latest question (presented as an answer) is not very clear. In particular, it contains two entirely different questions connected by an "I mean" suggesting that thanyon didn't really intend to ask both (and might have intended something different from both). Nevertheless, here's some information that answers some of what was asked (intended or not).

If a property of (arbitrary, not necessarily finite, first-order) structures is preserved by unions of chains and is expressible by a first-order sentence $A$, then there is an $\forall\exists$ sentence $A'$ logically equivalent to $A$ (i.e., defining the same property).

It is entirely possible for a property, even a first-order definable one, to be preserved by unions of chains, to be defined on finite structures by a sentence $A$, but not to be defined by the same $A$ on infinite structures. For example, take the property of being a field and let $A$ be a sentence defining division rings. On finite structures, $A$ also defines fields, since all finite division rings are fields, but on infinite structures $A$ defines a broader class.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer, and sorry if it is a bit fuzzy, my english is not very good.Anyway that was almost what I was asking, the last thing is to precise what I mean by property. Indeed my property is just a definition of an inductive set in each $\mathcal{A}^i$, thus formally I guess it is different than a property of for example "being a field"... Now, is the last reasoning still valid ? Can we consider that the following informal sentence "the set is contruct in some technical manner",which by construction is true, is a property and then applying last reasoning conclude that if a FO $\endgroup$
    – Thanyon
    Apr 20, 2012 at 21:46
  • $\begingroup$ formula exists defining my property then there exists a $\forall \exists$ one ? $\endgroup$
    – Thanyon
    Apr 20, 2012 at 21:50
  • $\begingroup$ As an illustration if I want to define in each $\langle ${$0,...,i-1$}$,+ \rangle$ the set $S_i=$ { $a \in ${ $0,...,i-1$ }, such that $\exists x,y \in S_{i-1}$ and $a=x+y$ } $\cup S_{i-1}$ , beginning for example with $S_0=${$5,9$}. Then in the structure $\langle \mathbb{N},+ \rangle$ my inductive set will be $\bigcup S_i, \forall i \geq 0$. Does it mean that if a FO formula exists then there is a $\forall \exists $ one equivalent defining the inductive set in each $\mathcal{A}^i$ ? $\endgroup$
    – Thanyon
    Apr 20, 2012 at 22:05

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.