The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
46 views

Model complete theories without quantifier elimination

As we know, if a theory $T$ admits quantifier elimination, then $T$ is model complete. What are the simplest examples that show that the converse is not true?
1
vote
1answer
31 views

How is quantifier elimination accomplished in second and higher order logic?

In first order logic we can eliminate existential quantifiers using a second order equivalence relation: $\forall$x$\exists$y P(x, y) $\iff$ $\exists$f$\forall$x P(x, f(x)) Dropping the existential ...
3
votes
0answers
43 views

Ordering of $\mathbb{R}$ not quantifier-free definable in $L_{R}$

I'm reading David Marker's book "Model Theory: An Introduction" and I'm trying to solve Exercise 3.4.24 which is stated as follows: Let $x$ and $y$ be algebraically independent over $\mathbb{R}$. a) ...
1
vote
1answer
41 views

Why is Skolem normal form equisatisfiable while the second order form equivalent?

I asked in another question when is it appropriate to de-Skolemize a statement. The answer, I'm not sure I'm satisfied with yet, relies on a second order logical equivelance, but Skolem normal form ...
0
votes
2answers
54 views

Trying to understand negation of quantifiers

Trying to understand the negation of the following: For this: ∀x~P(x) I have this as negation: ~∃xP(x) For this: ~∃x(∀yP(y) Λ Q(x)) I have this: ∀x(~∃yP(y) V ~Q(x)) Are these correct? If not please ...
4
votes
2answers
83 views

Proper definition of quantifier elimination

I study Marker book "Model Theory, An Introduction". Definition 3.1.1 on page 72 defines "theory T has quantifier elimination". A theory $T$ has quantifier elimination if for every formula $\phi$ ...
0
votes
0answers
38 views

proof of quantifier elimination in theory of real closed field/reals and existential quantifier over atomic formula

Standard proof of quantifier elimination for theory of real closed field/reals uses induction, as in Wikipedia article (http://en.wikipedia.org/wiki/Quantifier_elimination#Basic_ideas). However, it ...
2
votes
2answers
94 views

How is a quantifier-free formula actually interpreted?

My understanding is that a quantifier-free formula in FOL is simply a formula that contains no quantifiers, just possibly free variables. How is such a formula interpreted? My understanding is that if ...
2
votes
1answer
74 views

Why Quantifier Free Formulas define Linear Functions.

How do you prove that functions definable by quantifier-free formulas must be linear? I am interested for the structure $\langle Q,+,0\rangle$.
0
votes
2answers
31 views

Resultant$(f,g)$ says when there exist $\phi,\psi$ such that $\psi f + \phi g = 0$. How do I actually find them?

If $f$ and $g \in k[X]$ are two polynomials such that $\textrm{Res }(f,g)=0$ how do I find $\phi$ and $\psi$ with $\deg \phi < \deg f$ and $\deg \psi < \deg g$ such that $$\psi f +\phi g =0$$
6
votes
0answers
206 views

Characterization of the First Order Theory of Ordered Abelian Groups via Quantifier Elimination

In the paper "Elimination of Quantifiers in Algebraic Structures" Macintyre, McKenna and van den Dries, proved that every field (ordered field) whose theory admits quantifier elimination in the ...
1
vote
2answers
228 views

Herbrand Logic-Fitch System

Given $$\forall x.(p(x) \implies q(x))\quad and \quad p(a)$$ use the Fitch system to prove q(a) I have started: $$\\$$ $$1) \forall X.(p(X) \implies q(X)) \qquad (Premise)$$ $$2) p(a) \qquad ...
1
vote
1answer
134 views

Proof of Robinson's test

I have been working with Tent and Ziegler's Model Theory. I am on the Quantifier elimination chapter, and there they mention Robinson's test. It says that, for an $L$-theory $T$ three statements ...
3
votes
1answer
110 views

Quantifier Elimintion of $(\Bbb{Q},+,0)$

I want to prove that the structure $(\Bbb{Q},+,0)$ has Quantifier Elimination. I can prove it for some simple basic formulas, but what if i get a formula which says that i have a linear combination, ...
2
votes
1answer
447 views

How to prove that something is definable or not definable in a given structure?!

Hello friends of mathematics :) I have some problems with the topic "Is something definable in a structure". I can solve some problems for example the following questions: Is the relation definable ...
4
votes
3answers
181 views

Want to show Quantifier elimination and completeness of this set of axioms…

Let $\Sigma_\infty$ be a set of axioms in the language $\{\sim\}$ (where $\sim$ is a binary relation symbol) that states: (i) $\sim$ is an equivalence relation; (ii) every equivalence ...
3
votes
2answers
84 views

Need a FOL derivation validated. Unclear on universal generalization restriction.

I'm currently working through Suppes' Introduction to Logic, and while the text is excellent, the lack of solutions to the exercises can be frustrating at times. This is one of those times. I've ...
2
votes
1answer
158 views

Reducing quantification to probability

I was thinking about some problem involving quantifiers (the existencial and universal quantifiers) and I noticed how it might resemble probability in a sense. They both assume a variable and its ...
11
votes
2answers
875 views

Software for solving geometry questions

When I used to compete in Olympiad Competitions back in high school, a decent number of the easier geometry questions were solvable by what we called a geometry bash. Basically, you'd label every ...