Questions tagged [first-order-logic]

For questions about formal deduction of first-order logic formula or metamathematical properties of first-order logic.

19
votes
0answers
238 views

Does “every” first-order theory have a finitely axiomatizable conservative extension?

I've now asked this question on mathoverflow here. There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. However $\sf NBG$ ...
12
votes
0answers
686 views

Why can't we formalize the lambda calculus in first order logic?

I'm reading through Hindley and Seldin's book about the lambda calculus and combinatory logic. In the book, the authors express that, though combinatory logic can be expressed as an equational theory ...
6
votes
0answers
45 views

First-order definability sums of squares

Let $K$ be a field. I am interested in when there can exist a first-order definition of the set $$ \Sigma K^2 := \lbrace \sum_{i=1}^n x_i^2 \mid n \in \mathbb{N}, x_1, \ldots, x_n \in K \rbrace $$ in $...
5
votes
0answers
257 views

A “formalistic” variant of the Gödel completeness theorem

I think, the following variant of the Gödel completeness theorem must be true, but I can't find the necessary references. I would be grateful if specialists in logic could give me them (or enlighten ...
5
votes
0answers
147 views

Elimination of the quantifier “there are infinitely many”

Is there a back-and-forth condition equivalent to elimination of the $\exists^\infty$ quantifier? (The question may not have much of a sense. Then, please, argue why.) Background. For instance, the ...
5
votes
0answers
180 views

bi-interpretability and automorphism groups

Let $M$ and $N$ be two first order structures, say they are countable and $\aleph_0$-categorical. Then $M$ and $N$ are bi-interpretable if and only if their automorphism groups $Aut(M)$ and $Aut(N)$ ...
5
votes
0answers
100 views

Proving $\square(\forall v_1\neg\psi(v_1))\rightarrow\forall v_1\neg\psi(v_1)$ for a particular $\psi$.

I have a formula $\psi(v_1)$ that is equivalent in $\mathrm{PA}$ to $$\exists a\exists b\exists c\left[\neg\exists x\overline{\mathrm{Prf}}(x,c)\wedge\mathrm{Neg}(b,c)\wedge\mathrm{Sub}\left(a,\...
4
votes
0answers
42 views

Examples of undefinable predicates in continuous logic

Definability of predicates in Continuous first order logic is (usually) defined as follow: A predicate $P:M^n \to [0,1]$ is called definable over $\mathcal{M}$ iff there exists a sequence $(\phi_k(x)|...
4
votes
0answers
104 views

Questions about the statement “Every number can be specified by less than twenty words.”

This is really an interesting question, though I do not know how to word it in a mathematical way. I am glad if one can help me to reword it mathematically. A friend of mine comes up with this ...
4
votes
0answers
95 views

Can first-order logic be recognized by a pushdown automaton?

I have the belief that first-order logic cannot be recognized by a pushdown automaton because the automaton will have no way to keep track of the variables that are currently in scope. More precisely, ...
4
votes
0answers
82 views

Domain with positive-existential subset that is not diophantine

Let $R$ be a ring. Call a subset $A$ of $R$ diophantine if it is of the form $$ \lbrace x \in R \mid \exists z_1, \ldots, z_n \in R : f(x, z_1, \ldots, z_n) = 0 \rbrace $$ for some $n \in \mathbb{N}$ ...
4
votes
0answers
92 views

Show that there are only $\aleph_0$ many countable models of the following theory.

Consider a language $L$ with $<0,1,S>$, where $S$ is the successor function. Show that there are only $\aleph_0$ many countable models of Th$(\mathbb{N})$, under $L$. This is one of the ...
4
votes
0answers
52 views

Decidability of real closed field with predicate

Tarski's theorem shows that the theory of real closed fields is decidable. In section 1.3 of this presentation http://mat.msgsu.edu.tr/~aad/2012/Slides/tressl.pdf, it says that Abraham Robinson ...
4
votes
0answers
159 views

Is there a name for this principle of logic? From $\exists a P(a), !bQ(b), \forall a(P(a) \rightarrow Q(a)),$ infer $\forall a(Q(a) \rightarrow P(a))$

In set theory, we have the following: Observation 0. Let $X$ denote a set. Let $A$ and $B$ denote subsets of $X$. Then if $A$ has at least one element, $B$ has at most one element, and $A \...
3
votes
0answers
48 views

How to deal with second argument of implication being defined if only if the first argument is true?

Let $S$ be a set. Let $f$ be a function with $\operatorname{dom}(f)=S$. Let $P$ be a one-place property. Is the following statement well formed? $$∀x \, x∈S → P(f(x))$$ How about another one? $$\...
3
votes
0answers
43 views

Th(A) is omega-categorical iff Th(A; a) is omega-categorical.

Consider the following theorem: I do not understand how to arrive at the claim underlined in red in the picture. Why is that true? We use the following definition of type:
3
votes
0answers
41 views

Why can't the sequent calculus for First-Order Classical Logic be used for proving decidability via Proof-search?

I understand that Turing reduced the halting problem to the satisfiability problem of first-order logic thus proving first-order logic undecidable. However, when thinking about the sequent calculus ...
3
votes
0answers
97 views

Recursion Theory/Incompleteness Theorems: Computability of sets of formulas in first order logic

I am struggling with the following two problems: Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas $\{\varphi$ $\mid$ for every $M$-assignment $\...
3
votes
0answers
90 views

Formal proof of $\exists x (\exists y P(y) \rightarrow P(x))$ and $(\forall x \exists y R(x,y))\rightarrow (\forall y \exists x R(y,x))$

within the following axiomatic system I've beeb trying to proof the formulas (1) $\forall x \exists y R(x,y) \rightarrow \forall y \exists x R(y,x) \\$ and (2) $\\ \exists x (\exists y P(y) \...
3
votes
0answers
149 views

Can first-order logic compactness theorem be used to prove extensibility of every partial ordering to a linear ordering?

So, assume there is a set $X$ with some partial ordering on it. Surely, we can consider a signature $\sigma$ that has $=, <$ and a constant $c_x$ for every $x \in X$. We can then consider a theory ...
3
votes
0answers
136 views

Are $\mathbb C$ , $\mathbb C[X]$ definable in $\mathbb C[[X]]$?

Let $L$ be a first-order language and $M$ be an $L$-structure. Let $D \subseteq M^n$ . Let us say $D$ is definable in $M$ if for some finite set (possibly empty) $A=\{a_1,...,a_m\} \subseteq M$ and ...
3
votes
0answers
89 views

Isomorphism between finite structures which is not elementary

in the book by Katrin Tent and Martin Ziegler, "A course in model theory", it says that a complete theory in a finite relational language has quantifier eliminiation iff any isomorphism between finite ...
3
votes
0answers
138 views

Inference rules for quantifiers in natural deduction - are all the conditions correct?

Because I am getting quite confused with the definition of the four inference rules for quantifiers, and all of their conditions, I would like to write them down here as I understand it. My questions ...
3
votes
0answers
37 views

How much time to find satisfying values of $\Pi_2$ theorems of Robinson arithmetic?

As far as I can tell, for any $\Pi_2$ theorem of Robinson arithmetic $\forall_{x_1,\dots,x_m} \exists_{y_1,\dots,y_n} P(x_1,\dots,x_m,y_1,\dots,y_n)$ where $P$ is quantifier-free, there is a ...
3
votes
0answers
90 views

Is it possible that a theory A is not interpretable in a theory B, and B is not interpretable in A too?

Suppose A and B are first order theories(probably, the restriction to first order theory is not essential, but for simplicity). When one theory has finite model,the question is easy. If one has the ...
3
votes
0answers
91 views

What is the importance of first order language in logic?

I do not know much about logic but I was wondering if someone could explain to me the importance of first order language in logic. In particular, what different does it make if something is ...
3
votes
0answers
54 views

Model theory of the naturals with a multiplication by an irrational factor

It is well-known that the theory of the structure $(\mathbb{N},<)$ is not stable, but is NIP and has quantifier elimination in the language $L=\{<,0,S,S^{-1}\}$ where $S,S^{-1}$ are function ...
3
votes
0answers
117 views

Some boys in the class are taller than all the girls?

"Some boys in the class are taller than all the girls" I tried in the following way : As it says that some boys are there, means that atleast 1 boy is there who ...
3
votes
0answers
73 views

Software for solving first-order logic

Is there any class of software that can help me with the following problem in first order logic: given $\phi$ a formula with a "hole" in it (a subformula which is undetermined) and a particular set of ...
3
votes
0answers
93 views

Is Leibnizian calculus embeddable in first order logic?

We just published an article making what we feel is a plausible case in favor of an affirmative answer in Foundations of Science, see preprint here. The basic argument is that while such a requirement ...
3
votes
0answers
93 views

Describe a set with FOL formula

This is a problem from Introduction to Mathematical Logic course A structure $\mathscr{A}$ with domain $\mathbb{N}^k$ is for FOL language $\mathscr{L}$ with $k$ predicate symbols $p_1, \ldots, p_k$ ...
3
votes
0answers
154 views

how to determine if a semi-algebraic function has a semi-algebraic anti-derivative

Is there an algorithm for determining if a semi-algebraic function has a semi-algebraic anti-derivative? By semi-algebraic function, I mean a function that can be defined in a real closed field. For ...
3
votes
0answers
58 views

complex numbers from real closed fields

I am very interested in first order axiomatizations of the complex numbers, but I have never actually seen one laid out. Algebraically closed fields of characteristic zero are a start, but they don't ...
3
votes
0answers
101 views

Expressing quantifier free $\mathcal{L}_{PA}$-formulae $\varphi(y,\vec{x})$ with polynomials

I'm stuck at the following exercise: I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all $\vec{n}...
2
votes
0answers
29 views

Intuition of Morley rank

One way to understand the Morley rank of a unary formula $\varphi(x)$ with $\text{RM}(\varphi(x)) < \omega$ is to imagine it as the height of an $\omega$-branching tree, where each node is mapped ...
2
votes
0answers
36 views

Replacing Constants with Unary Functions

Suppose I have a first order theory over some signature $\Sigma$ with constant symbols. Is there a name for the theory I obtain by replacing the constant symbols with unary function symbols along ...
2
votes
0answers
27 views

Is it possible to have a single axiom that subsumes axioms 8-10 in this list?

Think of a totally ordered set as an “order-theoretic line”. Similarly, cyclic orders are “order-theoretic circles”. I want to find the right axioms for an “order-theoretic plane”. My ultimate goal ...
2
votes
0answers
79 views

Are there any good books on propositional, first order, and second order logic that don't require me to be a supergenius?

I am trying to learn mathematical logic but every textbook I come across is so hard to read and understand, and assumes I'm already an expert in everything. Is there anything aimed at beginners that ...
2
votes
0answers
66 views

A property of representable functions?

Recall that a function $f:\mathbb{N}^k\rightarrow\mathbb{N}$ is representable in Peano arithmetic if there exists a formula $\varphi(x_1,\dots ,x_k,y)$ such that for every $n_1,\dots,n_k,m\in\mathbb{N}...
2
votes
0answers
66 views

Is every theory meeting Gödels incompleteness, also incomplete below its consistency level?

Is it always the case that for any theory $T$ that meets Godel's criteria for incompleteness, there is a sentence $P$ such that neither $T \vdash P$, nor $T\vdash \neg P$; and such that $T+P$ is equi-...
2
votes
0answers
38 views

What is the definition of a strong type?

I know the definition of a type over a set of parameters but can not find any definition for strong type. For example what does it mean to write $stp(a/A)$ ?
2
votes
0answers
59 views

What are the existing constructive proofs for Craig's Interpolation Theorem

Can anyone help me assemble a list of the constructive proofs of Craig's Interpolation Theorem for classical first order logic? A constructive proof means that a method is provided for producing the ...
2
votes
0answers
37 views

Metric on the space of complete theories of a countable language

If I'm not mistaken, the space $\mathcal{T}$ of all complete theories of a countable language is a compact Hausdorff space, and moreover it is second-countable, since it has as its base the sets of ...
2
votes
0answers
73 views

Are all prop logic wffs sentences? Why aren't there any free variables?

In propositional logic is it correct to say that all wffs are also sentences/statements? Are sentences and statements the same thing? I also read that sentences are wffs that lack free variables, but ...
2
votes
0answers
43 views

Translation of infinite-valued QBF to first order logic

Quantified Boolean Formulas with infinite values are distinct from their usual 2-valued version (proof). Is there a known way to express such formulas in standard first order logic notation (so that ...
2
votes
0answers
33 views

Illegal Herbrand Logic sentence

I am studying the Stanford Introduction to Logic course. There was a problem about whether an expression is legal sentence of Herbrand Logic or not. It asks: Say whether $p(f(p(a))$ is a ...
2
votes
0answers
152 views

How many axioms does first-order logic need?

I am confused about the nature of first-order logic's axioms. I want every line of a proof to be a valid sentence, and I want the only rule of inference employed to be modus ponens. What axioms do I ...
2
votes
0answers
49 views

$((0,1), <) \preceq (\mathbb{R}, <)$ in $\mathcal{L}=\left\{<\right\}$

I want to prove that ((0,1), <) is an elementary substructure of $(\mathbb{R}, <)$ i.e. $((0,1), <) \preceq (\mathbb{R}, <)$ The first hint is to prove that there exists an automorphism $...
2
votes
0answers
33 views

SAT preserving conversion of statement to existential one

For me, a formula $\psi$ is existential if and only if it is of the form $\psi=\exists x_1\cdots\exists x_n \varphi$ such that $\varphi$ has no quantifiers. Prove or Disprove: There exists an ...
2
votes
0answers
83 views

Tensor rank as a first order formula

I heard in a talk today that the problem of tensor rank over $\mathbb{Q}$ is not even known to be decidable and it is equivalent to the existential theory of over that field. Did not interrupt the ...