# An Uncountable language , A Model of $\mathbb{N}$, A Problem.

Edit 1: I messed up my original question, but Arthur Fischer answered my question anyway.

Edit 2: We can actually restrict $L$ to the language in arithmetic with the prdicate $P_{\mathbb{P}}$. Everything I actually care about is definable in that language.

Let $\mathbb{P}$ be the set of primes viewed as a subset of the natural numbers. Let $L=\{\leq,0,1,+,\times\} \cup \{P_i :i\in 2^{\mathbb{P}}\}$ and consider the standard natural numbers, $\mathbb{N}$. Before I go any further, note that this is an uncountable language. Each $i$ corresponds to some $i\in 2^{\mathbb{P}}$. We interpret $P_i(x)$ as "$x$ is divisible by the set of primes in $i$". Hence, $\mathbb{N} \models P_{\{2\}}(2)\wedge P_{\{2\}}(4) \wedge P_{\{2,3,5\}}(30)$, so on and so forth. We let $T = Th_L(\mathbb{N})$.

$\mathbf{Observation}$ $\mathbf{1}:$ $\mathbb{N}\models(\forall x) \neg P_i(x)$ for any infinite set $i\subset \mathbb{N}$.

$\mathbf{Observation}$ $\mathbf{2}:$ $\mathbb{N}\models(\exists x) P_i(x)$ for any finite set $i\subset \mathbb{N}$.

$\mathbf{Observation}$ $\mathbf{3}:$ For any two finite subsets of $\mathbb{P}$, say $i,j$ we have that $$\mathbb{N} \models (\forall x) ([P_i(x)\wedge P_j(x)]\to P_{i\cup j}(x))$$

$\mathbf{Problem}$: We consider the theory $T$. $T$ is trivially consistent. We define the following set of sentences in the expanded language $L'=L\cup\{c\}$:

$$\phi_n=\bigwedge_{j<n}_{j\in \mathbb{P}} P_{\{j\}}(c)$$

Let $\Phi=\bigcup_{n < \omega}\{\phi_n\}$. Clearly, $T\cup \Phi$ is finitely satisfiable. Then, by compactness $T \cup \Phi$ has a model.

However, This is where I believe we have a problem. $\Phi$ asserts that there exists an element with infinitely many prime divisors. Hence, (This is probably where I go wrong) $\Phi \vdash (\exists x)(P_{\mathbb{P}}(x))$ $\mathbb{P} \in 2^{\mathbb{P}}.$ However, $T \vdash (\forall x) (\neg P_{\mathbb{P}} (x))$ since $\mathbb{P}$ is an infinite subset of $2^{\mathbb{P}}$. And so we have a contradiction.

I believe I have gone wrong somewhere in my argument, but I'm not sure where. I assume what happened is that the new model (Let's say $\mathbb{M}\models T\cup \Phi$) essentially lies to us. It does not believe that there are any elements which have infinitely many (finite) prime divisor because it can't understand $\bigcup_{n\in \mathbb{P}}\{n\}$. Hence, the logician can understand that if $P_{\{n\}}(x)$ for all $n \in \mathbb{P}$, then $P_{\mathbb{P}}(x)$ holds, but $\mathbb{M}$ cannot. Any help would be much appreciated.

• But $\Phi \subseteq T$ (by Observation 2). Don't mix up $\bigcup_{n < \omega} \{\phi_n\} = \{\phi_n \mid n < \omega\}$ which asserts that for any $n$ there is some $x$ such that $x$ is divisible by the primes less than $x$ and the assertion $\exists x\, P_{\mathbb P}(x)$ which wants the same $x$ for all $n$. Commented Jul 16, 2014 at 12:50
• Indexing-wise, you should have used $A$ to index the elements of $2^\Bbb P$. Using $i$ hints the reader this might be a natural number (especially in this context). Commented Jul 16, 2014 at 13:00
• @martini: That you for the comment. I was wrong and should have realized what I was writing sooner. Commented Jul 16, 2014 at 13:39
• @AsafKaragila: Sorry about the notation. I took it from a similar problem from a homework assignment last year. Commented Jul 16, 2014 at 13:39
• Observation 3 holds without the restriction to finite index sets. For example if $i$ is infinite, $i\cup j$ will be infinite too, so by Observation 1, it simply reduces to $\forall x(\bot \land P_j(x) \to \bot)$, which is trivially true. Commented Jul 16, 2014 at 13:43

$\Phi$ does not assert (or prove) that there is an element with infinitely many prime divisors. It only asserts that there are elements whose prime divisors constitute an arbitrarily large initial segment of the primes. In particular, for each $n$ the witness to $\phi_n$ may be different, and so there is no justification for $\Phi \vdash ( \exists x ) ( P_{\mathbb{P}} (x) )$.

(Aside. Note that your Observation 3 cannot be formally extended to infinite unions of subsets of $\mathbb{P}$, since there is no formula of the form, e.g., $$P_{\{2\}} (x) \wedge P_{\{3\}} (x) \wedge P_{\{5\}} (x) \wedge \cdots.$$ Semantically you can still wean meaning from it (and see that it is true), but this is outside of first-order logic proper (and gets pretty darn close to the nasty beautiful business of infinitary logic). From another point of view, you're also getting close to the nature of $\omega$-consistency. But I digress.)

However, what happens if you introduce a new constant symbol $c$ to your language, and instead of the $\phi_n$ introduce of the $\psi_n$ defined by $$\psi_n = \bigwedge_{j < n\text{ prime}} P_{\{j\}}(c)$$ as new axioms? By essentially the same reasoning, $T + \Psi$ (where $\Psi = \{ \psi_n : n \}$) is consistent. And in a model of this theory you have an element which has every (standard) prime number as a divisor. But there is nothing wrong with this: we just get a non-standard model of arithmetic.

• I messed up. That's what I was attempting to build, but I forgot about adding in the constant symbol. Thank you. Commented Jul 16, 2014 at 13:02
• This is where the we would have an element where $P_i(x)$ holds for ever $i \in \mathbb{P}$, but $P_\mathbb{P} (x)$ does not hold for any element of our model, correct? Commented Jul 16, 2014 at 13:05
• @Kyle: Right. The meaning of each of the $P_A(x)$s is fixed by $Th_L(\mathbb N)$ -- when $A$ is finite, the theory will assert that $P_A(x)$ is equivalent to its usual arithmetic definition, and when $A$ is infinite the theory contains the sentence $\forall x.\neg P_A(x)$. Commented Jul 16, 2014 at 13:23

The set of infinitely many sentences $\{P_{\{j\}}(x):j\in\mathbb P\}$ says, intuitively, that $x$ is divisible by all the prime numbers. So does the single sentence $P_{\mathbb P}(x)$. So the latter sentence and the (infinite) conjunction of the former set of sentences are equivalent in the standard model of arithmetic. They need not, however, be equivalent in nonstandard models, such as the one you obtain by applying the compactness theorem. Such a nonstandard model retains those properties of the standard model that are expressible in first-order logic, but the equivalence in question is not so expressible. It involves an infinite conjunction, and first-order logic allows only finitely big formulas. In the situation you describe, the value of $c$ will satisfy all of $\{P_{\{j\}}(x):j\in\mathbb P\}$ but not $P_{\mathbb P}(x)$.

• Thank you. I guess the intuitive question to ask is "So is $c$ divisible by all standard primes or not?". However, as FOL goes, this is not really well-defined. Commented Jul 16, 2014 at 20:21
• I think that this argument would have worked better using Los theorem, where it's clear that you reinterpret $P_\Bbb P$, rather than just keeping it as the same predicate as before. Commented Jul 16, 2014 at 20:33