3

How do I "formally write" a rational number $a_i$ in a logic formula?

For example, I was taught that $x^2$ should be formally written as $F_\times(x_1,x_1)$, $1$ should be formally written as $c_1$, $2$ should be formally written as $F_+(c_1,c_1)$ and so on.

I hope my question isn't too ambiguous.

This is related to my previous question: How to show that the property of being algebraically closed is reflected by elementary extensions?

The main idea is I want to write out the formula $\phi_n$ [credit to André Nicolas who suggested it] , $$\forall w_0\forall w_1\cdots\forall w_n \exists x\left(x^{n+1}+w_nx^n+\cdots+w_0=0\right).$$

and specify that all the $w_i$ are rationals.

background information about the underlying question

If $p(x)=x^{n+1}+a_nx^n+\cdots+a_1x+a_0$ is a polynomial such that $\{a_0,\cdots,a_n\}\subset\mathbb{Q}$, then $p(x)=0$ has a solution in $F$.

Assume that the structure $(F,0,1,+,\cdot)$ is a countable elementary submodel of the complex field $(\mathbb{C},0,1,+,\cdot)$.

Sincere thanks for any help!

Community
  • 1
yoyostein
  • 19,608
  • A rational number is the quotient of two integers, with the denominator non-zero, so you can require that such integers exist. – András Salamon Apr 27 '13 at 15:38
  • 1
    Any particular rational number, and therefore any fixed $n$-tuple of rationals, can be captured by a formula. So if you care to, you can add for every specific polynomial with rational coefficients, the assertion it has a root. We cannot, however, quantify over the rationals without changing the language. Anyway, we don't need the rationals, integers will do. Any specific integer is easy to express. – André Nicolas Apr 27 '13 at 16:33

2 Answers2

2

You don't need to quantify over the coefficients to solve your original problem How to show that the property of being algebraically closed is reflected by elementary extensions? (as I have explained there).

The first-order theory of algebraically closed fields of a given characteristic is decidable. In the characteristic $0$ case, adding a predicate for the rational numbers results in an undecidable theory, so it is not a good way to go for your original problem.

Community
  • 1
Rob Arthan
  • 48,577
2

You can describe any specific rational by a formula. Let us find, for example, a formula $\psi_{2/3}(x)$ that "says" that $x=2/3$.

We use the notation implicit in your post. A formula $\psi_{2/3}(x)$ that does the job is: $$F_{\times}(F_+(F_+(c_1,c_1),c_1),x)=F_+(c_1,c_1).$$ Any rational number can be specified in this way. The negative ones require an additional trick.

Thus for any specific polynomial $P(x)$ with rational coefficients, we can write a sentence that says that this particular polynomial has a zero. And if we want to specify that every non-constant polynomial with rational coefficients has a zero, we can do so using a countably infinite set of axioms.

However, we do not really need the predicates that identify the specific rationals. For if $P(x)$ is a polynomial with rational coefficients, then $P(x)$ has a zero if and only if a certain polynomial $P^\ast(x)$ has a zero, where $P^\ast$ is obtained from $P$ by multiplying by a suitable integer, a common denominator of the coefficients of $P$.

And we do not need negative integers. For the polynomial $P(x)$ has a zero if and only if the equation $P_{+}(x)=P_{-}(x)$ has a solution, where $P_{+}$ is the polynomial whose coefficients are the positive coefficients of $P$, and $P_{-}$ is the polynomial whose coefficients are the absolute values of the negative coefficients of $P$.

Remark: As explained in the answer of Rob Arthan, introducing a new predicate symbol that says "I am rational" or "I am natural" has undesirable consequences, for decidability, and also for the model theory.

André Nicolas
  • 507,029
  • Thanks, this is an awesomely clear answer. – yoyostein Apr 28 '13 at 15:10
  • You are welcome: clarity is what one seeks. – André Nicolas Apr 28 '13 at 15:36
  • thanks, I think the key idea "multiplying by a suitable integer, a common denominator of the coefficients of P ." is really useful. This way one can avoid rationals altogether. – yoyostein May 02 '13 at 13:53
  • You are right that one can avoid individual non-intergral rationals, but it is useful to accumulate defining tricks. From my point of view, the main goal there is so that after a while, one "knows" that something complicated could be defined, so one needn't bother. A similar thing happens with recursiveness. One proves in gruesome detail that certain basic functions are recursive. After that, for functions that it is clear we could prove recursive, details can be left out. – André Nicolas May 02 '13 at 14:02