# F[t] has undecidable positive existential theory in the language {+,⋅,0,1,t}

Watch
Announcements
Thread starter 5 years ago
#1
Hello!!

I am reading the following part of a paper but I got stuck at some points...

Consider the ring (the polynomials in and with coefficients in the field ).

Theorem 1.
Assume that the characteristic of is zero. Then the existential theory of in the language is undecidable.

Theorem 2.
Assume that has characteristic . Then the existential theory of is undecidable.

We have that even the positive existential theory of is undecidable.

Now we give a Lemma that, together with the preceding results, allows us to conclude the undecidability of the positive existential theory of in the language .

Lemma.
If the characteristic of is other than , then the solutions of with and in are given by where for in .

Theorem 3.
If the characteristic of is other than , then has undecidable positive existential theory in the language .

Proof.
Write .
Then and .
We interpret the positive existential theory of in in the following way:
an element of is represented as a pair with in being the components of with repsect to the base considering as a module over ; addition and multiplication of elements of is defined accordingly. So, we see that the positive existential theory of is interpretable in with only one problem: we do not have constants for and but only for .
So, the positive existential theory of is undecidable provided that the theory of is undecidable in the language .
It is only a matter of routine checking to see that our undecidability result for holds true in this language as well:
simply substitute , write all equations involved in the form , where and have coefficients in (the quantity , wherever it appears, is replaced by which is in ) and substitute the equations of this last form by the corresponding equations .
Of course, it is necessary to check that the new solutions that come onto the scene through the squaring do not do any harm to the stated equivalences. Hence, the theorem follows.

The trick in the last theorem was to interpret the theory of an algebraic extension of a ring into the theory of the base ring.
Suppose that is an integral domain and is an extension ring of so that the quotient field of is algebraic over the quotient field of and is a finite dimensional free module over with base, say .
Suppse that is a set of constants each of which represents an individual element of and define .
For each , let be an irreducible polynomial over the quotient field of , with coefficents in , which has as a zero in .
Let be the set of coefficients of all the 's, and define and , where is a predicate for the relation " is an element of ". Let be the subring of which is generated by the elements of which are representable by constants in (so each element of is representable in as a polynomial in the constants in with coefficients in ), and let be the subring of which is generated by the elements of that are representable by constants in (so each element of can be represented as a polynomial in the constants of with coefficents in ).

Techical Lemma.
Assume that there is an effective procedure to write each element of the subring in the form with in (it is easy to see that there is always such a representation of elements of but its effective nature has to be assumed).
Then the existential theory of in the language is decidable if and only if the existential theory of in is decidable.

I have some questions about the proof of the theorem .

At the beginning of the proof we take .
Which is the reason that we take this ?

"we see that the positive existential theory of is interpretable in with only one problem: we do not have constants for and but only for "

We have that each element of can be represented as an element of , besides and , because the language does not consist of a square root. Is this correct?
0
reply
5 years ago
#2
I have no idea but let me just say that this is scariest thing I have ever seen in my life
0
reply
5 years ago
#3
(Original post by driftawaay)
I have no idea but let me just say that this is scariest thing I have ever seen in my life
Amen to that. And I'm applying to Cambridge Maths in a couple of months...
0
reply
X

Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### Should there be a new university admissions system that ditches predicted grades?

No, I think predicted grades should still be used to make offers (563)
34.12%
Yes, I like the idea of applying to uni after I received my grades (PQA) (680)
41.21%
Yes, I like the idea of receiving offers only after I receive my grades (PQO) (332)
20.12%
I think there is a better option than the ones suggested (let us know in the thread!) (75)
4.55%

View All
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.