4
$\begingroup$

I wonder if there is a notion like the limit of formulas (and structures) because I believe it is important in describing countable structures (from finite structures). (For more detail, see this paper.) Now I give an excellent example illustrating it. The example is the so-called Quine atom. Let $$ I_n=\{I_{n-1}\},\quad\text{for } n\geqslant1, \:\text{and } I_0=G_0. $$ Where $G_0\neq\{G_0\}$. By repeatedly applying the axiom of extensionality, we get \begin{align} \phi_n&\iff\exists !\:y_n\in I_n \\ &\iff \exists !y_n(y_n=I_{n-1}) \\ &\iff\exists !y_n((\exists !y_{n-1}\in y_n)(y_{n-1}\in I_{n-1})\land (\exists !y_{n-1}\in I_{n-1})(y_{n-1}\in y_n)) \\ &\iff\exists !y_n \exists !y_{n-1}(y_{n-1}\in y_n\land y_{n-1}\in I_{n-1}) \\ &\iff\exists !y_n \exists !y_{n-1}(y_{n-1}\in y_n)\land \exists !y_{n-1}(y_{n-1}=I_{n-2}) \\ &\iff\exists !y_n \exists !y_{n-1}(y_{n-1}\in y_n)\land\exists !y_{n-1}((\exists !y_{n-2}\in y_{n-1})(y_{n-2}\in I_{n-2})\land(\exists !y_{n-2}\in I_{n-2})(y_{n-2}\in y_{n-1})) \\ &\iff\exists !y_n \exists !y_{n-1}(y_{n-1}\in y_n)\land \exists !y_{n-1}\exists !y_{n-2}(y_{n-2}\in y_{n-1}\land y_{n-2}\in I_{n-2}) \\ &\quad\:\vdots \\ &\iff \exists !y_n \exists !y_{n-1}(y_{n-1}\in y_n)\land \bigwedge_{1\leqslant j\leqslant n-1}\exists !y_j\exists !y_{j-1}(y_{j-1}\in y_{j})\quad\quad\quad\quad\text{(1)} \end{align} Clearly, for any $n<\omega$, $I_{n}\models \phi_n$. This suggests that we can define the limit of formulas as follows.

Edit: As pointed out in @Goldstern's example, formulas for limit can not be too general. So we limit them to a $\aleph_0$-categorical theory. (It could be extended to the theory of a countably saturated structure though.)

Definition 1: Suppose for any $n<\omega$, $\varphi_{n}$ is in a $\aleph_0$-categorical theory $T$ in $L$ (an infinitary language of $L_{\omega_1, \omega}$) and $M_{n}\models \varphi_{n}$. If for any $n$, there is a $N_n$ that for any $k>N_n,\:M_{k}\models \varphi_{n}$, then $\lim_\limits{n\to\omega}\varphi_{n}$ is a (unique) formula (up to equivalence) in $L$, and $\lim_\limits{n\to\omega}M_{n}$ is a (unique) $L$-structure. Let $\lim_\limits{n\to\omega}\varphi_{n}=\varphi_{\omega}$ and $\lim_\limits{n\to\omega}M_{n}=I_{\omega}$. Then $M_{\omega}\models \varphi_{\omega}$.

Also the follow axioms hold for the limit of formulas.

  1. $\lim_\limits{n\to\omega}(\phi_{n}\land\varphi_n)=\lim_\limits{n\to\omega}\phi_{n}\land\lim_\limits{n\to\omega}\varphi_n$
  2. $\lim_\limits{n\to\omega}\neg\phi_{n}=\neg\lim_\limits{n\to\omega}\phi_{n}$
  3. $\lim_\limits{n\to\omega}\exists x\phi_{n}=\exists x\lim_\limits{n\to\omega}\phi_{n}$
  4. $\lim_\limits{n\to\omega}\bigwedge_\limits{1\leqslant j\leqslant n}\phi_j=\bigwedge_\limits{ n<\omega}\phi_n$

We can prove from the above axioms that

  1. $\lim_\limits{n\to\omega}(M_{n-1}\in M_n)=\lim_\limits{n\to\omega}M_{n-1}\in \lim_\limits{n\to\omega}M_{n}$

  2. $\lim_\limits{n\to\omega}\exists x_n(M_{n-1}\in M_n)=\exists\lim_\limits{n\to\omega} x_n(\lim_\limits{n\to\omega}M_{n-1}\in \lim_\limits{n\to\omega}M_{n})$

(For detailed proofs, see this paper.)

$\operatorname{Th}(I_n)$ is $\aleph_0$-categorical because any $I_i$ can be mapped one-on-one to $I_j$, and so is homogeneous. Since the language of set theory is finite relational, $\operatorname{Th}(I_n)$ is $\aleph_0$-categorical. By definition 1 and (1), we can see that $\lim_\limits{n\to\omega}\phi_{n}$ and $\lim_\limits{n\to\omega}I_{n}$ both are unique. Let $\lim_\limits{n\to\omega}\phi_{n}=\phi_{\omega}$ and $\lim_\limits{n\to\omega}I_{n}=I_{\omega}$. Then $I_{\omega}\models \varphi_{\omega}$. Furthermore \begin{align} \phi_{\omega}&=\lim_\limits{n\to\omega}\phi_{n} \\ &=\lim_\limits{n\to\omega}\exists !y_n \exists !y_{n-1}(y_{n-1}\in y_n)\land \lim_\limits{n\to\omega}\bigwedge_{1\leqslant j\leqslant n-1}\exists !y_j\exists !y_{j-1}(y_{j-1}\in y_{j}) \\ &=\exists !I_{\omega}(I_{\omega}\in I_{\omega})\land \bigwedge_{n<\omega}\exists !y_n\exists !y_{n-1}(y_{n-1}\in y_{n})\quad\quad\quad(\lim_\limits{n\to\omega}y_n=I_{\omega}) \end{align}

Thus $I_{\omega}=\{I_{\omega}\}$, i.e. $I_{\omega}$ is a Quine atom.

Since the limit of formulas (for finite structures) can completely describe the Quine atom, I believe that it (will) play a significant role in the investigation of countable structures. I'd like to confirm that the above notion of limit of formulas and reasoning are not available in current model theory and so belong to a new field of research.

Edit: Next I will give two examples on how to apply the limit of formulas to studying some known results in model theory.

Example 1: There is arbitrary large number in nonstandard number theory.

Let $\phi_n=\exists x\bigwedge_\limits{m\leqslant n}(x>m)$ and $M_n\models \phi_n$. Since for any $k>n, \:x>k\to x>n, \:M_k\models \phi_n$. So the limit of $\phi_n$ exists and $$ \lim_\limits{n\to\omega}\exists x\bigwedge_\limits{m\leqslant n}(x>m)=\exists x\bigwedge_\limits{n<\omega}(x>n) $$ And there is a $M\models \exists x\bigwedge_\limits{n<\omega}(x>n)$.

The second example shows that theory of DLO without endpoints is the limit of union of integers shifts.

Example 2: Suppose $T$ is the theory of DLO without endpoints and $M_n=\bigcup_\limits{1\leqslant j<n}(\Bbb{Z}+j/n)$. Then $\lim_\limits{n\to\omega}\bigcup_\limits{n<\omega}M_n=\Bbb{Q}$ and $T = Th(\Bbb{Q})$.

Suppose $\varphi_n,\phi_n,\delta_n$ are sentences specifying the properties of linear ordering, a dense subset and set without endpoints for $M_n$. Then

\begin{align} \varphi_n &= (∀x,y,z∈M_n)(x≤x∧(x≤y∧y≤x⇒x=y)∧(x≤y∧y≤z⇒x≤z)) \\ \phi_n &= (∀x,y∈M_n)(x<y⇒(∃z∈M_{l})(l>n∧x<z<y)) \\ \delta_n &= (∀x∈M_n)((∃y∈M_n)(y<x)∧(∃y∈M_{n})(x<y)) \end{align} For any $x,y∈M_{n}\:(x<y)$, set $N_{n}=2n$. Then $∀k>N_{n},\:∃z∈M_{k}$ that $x<z<y$, i.e. $M_{k}\models φ_{n}$. Since $ℤ\modelsϕ_{n}∧δ_{n},\:M_{k}\models ϕ_{n}∧φ_{n}∧δ_{n}$ and $T$ is $ℵ_0$-categorical, $\lim_\limits{n\to\omega}M_n$ is unique. And \begin{align} \lim_\limits{n\to\omega}ϕ_{n} &=(∀x,y,z∈\lim_\limits{n\to\omega}M_n)(x≤x∧(x≤y∧y≤x⇒x=y)∧(x≤y∧y≤z⇒x≤z)) \\ \lim_\limits{n\to\omega}\phi_{n} &=(∀x,y∈\lim_\limits{n\to\omega}M_n)(x<y⇒(∃z∈\lim_\limits{n\to\omega}M_n)(x<z<y)) \\ \lim_\limits{n\to\omega}δ_{n} &=(∀x∈\lim_\limits{n\to\omega}M_n)((∃y∈\lim_\limits{n\to\omega}M_n)(y<x)∧(∃y∈\lim_\limits{n\to\omega}M_n)(x<y)) \end{align} Since $\lim_\limits{n\to\omega}ϕ_{n},\lim_\limits{n\to\omega}φ_{n}, \lim_\limits{n\to\omega}δ_{n}$ are axioms of $Th(\Bbb{Q}),\: \lim_\limits{n\to\omega}M_n=\Bbb{Q}$ and $T = Th(\Bbb{Q})$.

$\endgroup$
  • 6
    $\begingroup$ Your "Definition 1" does not define what "$\lim_n \varphi_n$" is, it just claims that this limit has a certain property. Please clarify. $\endgroup$ – Goldstern Sep 8 at 20:06
  • 3
    $\begingroup$ @hermes If you don't give a definition of "limit of a sequence of formulas", your question might be closed as "unclear what you are asking". $\endgroup$ – Goldstern Sep 10 at 7:51
  • 5
    $\begingroup$ Your use of standard notation is so peculiar that it is almost impossible to tell what you are saying. $\endgroup$ – Andrés E. Caicedo Sep 11 at 0:21
  • 4
    $\begingroup$ @hermes Saying that your paper is “available upon request” is a bit odd, like you want someone to beg you for it — if the paper is relevant to the question, it’s customary to simply post the arxiv link somewhere in the body. Then inquiring minds can simply click the link to check out your paper if they desire, rather than having to waste time asking for a copy and waiting for a reply. (not a downvoter or upvoter yet here, just mildly interested and following along. if experts in the field agree that it’s a well-posed question i’ll upvote, and they could decide more quickly with a link) $\endgroup$ – Alec Rhea Sep 11 at 1:24
  • 3
    $\begingroup$ @There is a natural compactification of the set of formulas (over some fixed set of variables) in first-order logic. It's the collection of partial types (i.e. closed subsets of type space) with the Vietoris topology. $\endgroup$ – James Hanson Sep 16 at 2:32
12
$\begingroup$

I am not sure which set-theoretic axioms you want to use. Certainly not foundation, but I guess that at least the singleton axiom is allowed.

Consider $M_0:= \{x\}$, where $x$ is any element satisfying $x\not=\{x\}$. $M_{n+1}:=\{M_n\}$. Let $\varphi_n$ be $\phi_n \wedge \psi$, where $\phi_n$ is your formula, and $\psi$ says the unique element is not an element of itself. Then by your arguments the limit $M_\omega$ must satisfy $M_\omega = \{M_\omega\}$, but it must also satisfy $\psi$, which is a contradiction.

So your axioms and rules lead to a proof of $x=\{x\}$ for all $x$.

It may be that I missed something. As a matter of fact, I am only guessing at what formal language you are using.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @ Goldstern, thanks. This example is right which means that formulas for limit can not be too general. So I modified definition 1 to limit them to a $\aleph_0$-categorical theory, which is atomic and exists a complete formula. Since $\psi$ in your example does not follow from the complete formula, the problem is avoided. $\endgroup$ – hermes Sep 9 at 0:46
  • 3
    $\begingroup$ The structures $M_i$ in my example all have exactly one element, so their theory is $\aleph_0$-categorical (in the first order sense). The limit of my formulas is (following your rules) $\phi_\omega\wedge \psi$. $\endgroup$ – Goldstern Sep 10 at 7:41
  • $\begingroup$ Your structure is the same as $I_n$. Since $Th(I_n)$ is $ℵ_0$-categorical, it is atomic and has a complete formula $ϕ_ω$. If $ψ=∃x(x≠\{x\})$, then $ϕ_ω∧ψ$ has no contradiction. However, if $ψ=∀x(x≠\{x\})$, then $ψ∉Th(I_n)$ because $ϕ_ω→¬ψ$. $\endgroup$ – hermes Sep 10 at 15:51
  • $\begingroup$ The formal language used here is the infinitary language of set theory ($L'_{\omega_1,\omega}$). However, it can be extended to a general language of $L_{\omega_1,\omega}$. $\endgroup$ – hermes Sep 11 at 0:20
  • $\begingroup$ Also the axioms of this set theory is basically ZF minus the axiom of regularity, where the axiom of extensionality in ZF needs be modified to accommodate NWF sets like Quine atoms. The axiom of union needs change too. The axiom of regularity is dropped and replaced by a new axiom stating that there are NWF sets. The rest axioms (pairing, power set, infinity, replacement, separation) remain the same as those of ZF. See the file listed in the post for more details. $\endgroup$ – hermes Sep 11 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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