Questions tagged [first-order-logic]

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

594 questions
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$ ...
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 ...
45 views

90 views

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 ...
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 ...
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 ...
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 ...
66 views

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}... 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-... 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)$? 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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$...
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 ...
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 ...