Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [first-order-logic]

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

0
votes
0answers
26 views

A curious logical formula involving prime numbers [duplicate]

Let $S$ be a nonempty set of natural numbers. Is the following formula $$ \exists p\ \bigl(\text{$p$ is prime } \rightarrow \forall x \text{ ($x$ is prime)}\bigr) $$ true or false on $S$? I know the ...
0
votes
0answers
21 views

Dichotomy in first order logic

How to prove over first order logic that if B has free variables $\{x_1, x_2\}$ it keeps the dichotomy theorem. namely: $$if\ \Gamma, A \vDash_v B ,\Gamma, \neg A \vDash_v B$$ $$ \ then \ \Gamma, \...
1
vote
1answer
39 views

Can we enumerate finite sequences which have no halting continuation?

Note: this is a cross-post from CS.SE, since I haven't gotten an answer there. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
5
votes
1answer
31 views

First-Order Definability of finite structures (negative result)

I am trying to wrap my head around this proof sketch that we did in class: Proof: Finite structures are not first-order definable Suppose that the set $\Gamma$ of first-order sentences defines ...
0
votes
1answer
22 views

Translating Sentences into First Order Logic

My professor gave us a study guide a few days ago and the answers to it today. I did the study guide and thought I did it all right, but saw some of my answers were not the same as his. I tried ...
1
vote
1answer
24 views

For any sentence A, if M $\models$ A , then M' $\models$ A as well

Exact problem in words: Let $M$ be an interpretation, and let $M′$ be an extension of $M$. Prove that, for any sentence $A$, if $M$$\models$$A$, then M′ $\models$ $A$. I'm having trouble here ...
0
votes
0answers
19 views

Can the following idea be expressed in first order logic?

The motivation for this question came from considering the following statements in first-order logic: A. $$\forall x\ [\phi(x)] \implies P$$ B. $$\forall x\ [\ \phi(x) \implies P\ ]$$ C. $$\...
0
votes
1answer
51 views

Consistency and Gödel's Incompleteness theorem.

In Mathematical Logic, Kleene states a string of implications that are a result of Gödel's completeness theorem of predicate logic; $$\{E_1,...,E_k \vdash P\&\neg{P}\} \rightarrow \{E_1,...,E_k \...
0
votes
1answer
14 views

First order logic from computational linguistics - implication

I am reading Natural Language Understanding by James Allen. It has the following sentence That John is rich implies that he is happy. And first order logic ...
1
vote
1answer
22 views

Classifying the $n$-types over $(\mathbb{Z}, S)$

Consider the structure $(\mathbb{Z}, S)$, where $S$ is the successor function. I'm trying to work out a classification of the $n$-types over it, and would appreciate some help in how to go about it. ...
1
vote
0answers
32 views

Reference request: Would this axiom motivate a Mereological foundation of set theory?

If $\psi(s,x)$ is a formula in which symbols $``s,x"$ occur free, in which the symbol $``u"$ doesn't occur free, then all closures of: $$\forall S \ [ \forall s (s \subseteq S \exists! x (\psi(s,x))) ...
1
vote
0answers
41 views

Archimedean property in real closed fields - where's the mistake?

Let $\left<F,+,\cdot,\leq\right>$ be a real closed field. Consider the following schema: $(*)$ Let $\phi(\cdot)$ be a first-order predicate. Let there exist $x \neq y$ such that $\phi(x),\phi(y)...
1
vote
2answers
53 views

Implication or AND in First Order Logic

I've read some examples about the differences between using AND and the implication in FOL, but I have a specific example where I can't intuitively notice the difference between the two: "Every ...
0
votes
0answers
8 views

Can completeness due to adding $\omega$-rule be extended to all recursive ordinals?

Is completeness due to $\omega$-rule effected by restricting matters to what the meta-theoretic indices confer? I mean in the case of the ordinary $\omega$-rule, we can do it over the world of finite ...
0
votes
0answers
13 views

Are finite sets of standard finite sets, standard finite sets?

If we add the unary primitive $std$, denoting standard to the primitives of $ZFC$, now we add the following $\omega$-rule: From, for $n=0,1,2,3,...; \forall x (x=\{y_1,..,y_n\} \to \psi(x)) $ We ...
0
votes
0answers
39 views

First-order definability of structures of at least $n$ elements

In class, we learned that it is possible to define structures of at least $n$ elements using the following WFF $\exists^{\geq n}$: $$\exists x_1 \ldots x_n \bigwedge_{i \not= j} \neg (x_i = x_j)$$ ...
0
votes
1answer
31 views

A 7-formula deduction for $\{\forall x (Px \to Qx), \forall z P z\} \vdash Qc$. Enderton logic page 123.

Enderton claims that it is not hard to show that a deduction for $\{\forall x (Px \to Qx), \forall z P z\} \vdash Qc$ exists, and furthermore that it consists of only seven formulas. I was able to ...
1
vote
1answer
27 views

Is the “Empty String” a term in First Order Logic?

I am sitting on the couch thinking about one of my trivial and (almost!) meaningless mathematical problems. Let me explain: terms are recursively defined in First Order Logic starting from symbols for ...
0
votes
1answer
49 views

If Γ ⊢ A, then Γ ⊨ A

I'm having a difficult time differentiating between the two proofs: 1. If Γ ⊢ A, then Γ ⊨ A vs. 2. If ⊢ A, then ⊨ A Here's the question: Prove “strong soundness”: for any set of formulas, Γ, and ...
1
vote
1answer
45 views

Are definitions axioms?

I just want to ask a very elementary question. When we introduce a "definition" in a first order logical system. For example when we say Define: $Empty(x) \iff \not \exists y (y \in x) $ Isn't ...
-1
votes
1answer
59 views

What decides completability of a first order theory?

[EDIT]: To make the question (the original posting presenting it I've put in a separate section below) non trivial a definition of "inference rule" needs to be given [Noah Schweber] as clearly ...
1
vote
1answer
28 views

Classifying the $1$-types over $(\mathbb{Q}, <)$

Consider the $1$-types over $\mathbb{Q}$ as a dense linear order without endpoints. They are similar to cuts: for any $1$-type $p$ over $\mathbb{Q}$, we can define $L_p = \{a \in \mathbb{Q} \; | \; a &...
0
votes
1answer
47 views

Is “ZFC + Omega rule for finite sets” a complete theory?

Omega rule for finite sets $\omega^{fin}$: if $\phi(y), \psi(y)$ are formulas in one free variable symbol $y$, then: From: for $ n=0,1,2,3,...; \text { we have: } \forall y \ [y=\{x_1,...,x_n\} \...
2
votes
1answer
21 views

If $T$ admits quantifier elimination in $\mathcal{L}$, does it admit quantifier elimination in $\mathcal{L}(c)$?

I know this is true: If $T$ is an $\mathcal{L}$-theory and it admits quantifier elimination in $\mathcal{L}(c)=\mathcal{L}\cup\{c\}$, where $c$ is a constant symbol not in $\mathcal{L}$, then $T$ ...
2
votes
1answer
40 views

Is ZF+Omega rule for sets a complete theory?

Omega rule for sets$``\omega^{ Set}"$: if $\{\varphi_0(y),\varphi_1(y), \varphi_2(y),...\}$ is the set of all formulas in the language of $ZF$ in one free variable symbol $``y"$, and if $\psi(x)$ is a ...
2
votes
0answers
58 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
1answer
73 views

Does every standard set have a standard cardinality?

Add a new primitive one place predicate symbol $``std"$ denoting "standard" to the language of $\text{ZF}$, now iff we add an omega rule to $``\text {ZF - Infinity + every set is finite}"$ formulated ...
1
vote
1answer
26 views

Is my way of interpreting a model correct?

A model $M$ is a tuple $(O, F, P)$, where $O$ is a list of objects, $F$ is a table of function values, and $P$ is a table of predicate values. Let $O=\mathbb{Z_{\le4}}$. I use $even(x), prime(x)$ ...
1
vote
2answers
37 views

What is the difference between value and constant literal in first order logic syntax?

In FOL, there are two values true and false; In FOL, there are two constant literals : T and F; Is there any difference between the both (values and constant literals)? Can I say that true value is ...
0
votes
2answers
24 views

Determine conditions on pn such that the probability that a random graph has at least one triangle goes to zero as n increases

I'm currently struggling with an exercise about random graphs where is requested to determine the conditions on $p_n$ such that the probability that $G(n, p_n)$ has at least one triangle goes to zero ...
0
votes
0answers
18 views

Can Ackermann - Heredity + Limitation of size prove set union over $V$?

If we remove the first completeness axiom for $V$ (i.e. the axiom of Heredity), in Ackermann set theory, and add an axiom of Limitation of size on $V$, formally this is: $\forall x (x \subseteq V \...
1
vote
0answers
31 views

What is the computational complexity of Tarski's arithmetic?

Tarski proved that the first-order theory of real-closed fields is decidable. Is the exact computational complexity known? The best upper bound I could find is EXPSPACE [1], where it is also ...
0
votes
1answer
32 views

Function symbols in many sorted logic

Consider the following definition We fix an enumerable set Fun of function symbols. Each function symbol has associated to it an arity of the form $σ1 \times \...
0
votes
0answers
9 views

Why not weaken reducibility in $K_2(W)$ instead of sub-world separation?

In this theory $K_2(W)$ (page 7) Harvey Friedman argue for weakening Sub-world Separation into SS-. He did that in order to evade making $W$ transitive. But he could have done that by simply reverting ...
1
vote
1answer
23 views

A not-$\omega$-saturated model.

I'm new to $\omega$-saturated model and the likewise and although I'm aware of examples of $\omega$-saturated models $(\mathbb{Q},<)$, I can not really imagine a not-$\omega$-saturated model and ...
2
votes
1answer
162 views

Complete Theorem

Let $\mathcal{L}$ be a language with the constants ${a_1},{a_2}$ and the single parameter operation $F$. Looking at the set $\Gamma=\{ \psi,\chi,\eta \}\cup\{\phi_n|n\ge1\}$ where $\psi=\forall{x}(x\...
2
votes
1answer
24 views

Elementary equivalence and finite isomorphism

It is well known, as Fraïssé's theorem, that for a finite relational signature $\sigma$ and two $\sigma$-models $\mathfrak{A}$, $\mathfrak{B}$, $\mathfrak{A}$ and $\mathfrak{B}$ are elementary ...
1
vote
1answer
26 views

Existence of a (classical) FOL-Formula satisfiable by ONLY an uncountable model?

It's easy to find satisfiable FOL-Formulas that are satisfiable by countably finite or infinite models. If we have a formula with a countably infinite model, we can prove the existence of an ...
-2
votes
0answers
71 views

Reference request about this kind of set theory that blends Ackermann with MK set theories?

[EDIT] I'm interested the axiomatization presented below. Quesiton: Is there a known reference that tackle this subject in a detailed manner, some parts of this axiomatization is present in this ...
0
votes
1answer
23 views

Prove that structure M is not Herbrand structure

I've been trying to solve the following problem, but I get a bit confused with the solution I get. Here's the problem: Let's M be a structure with an universe all the terms with no variables. We know ...
1
vote
1answer
43 views

Prove there is no theory whose models are exactly the interpretations with finite domains [duplicate]

I'm working through Mendelson's Introduction to Mathematical Logic and I'm having trouble proving the following statement: '' There is no first-order theory $K$ whose models are exactly the ...
1
vote
0answers
83 views

First Order Logic representation of program

I have numerous records, composed of words. Each word gets translated into vectors, with a variable number of channels, provided that that word exists in a specific lookup dictionary. For n number of ...
2
votes
1answer
56 views

Two conflicting (?) versions of the Downward Löwenheim-Skolem Theorem

I found two definitions of the Downward Löwenheim-Skolem Theorem: Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or ...
0
votes
1answer
47 views

Can I apply different transformations to each side of this inequality?

Does the following hold for natural numbers: $\forall x : \mathbb{N} , \forall y : \mathbb{N} \bullet (x < (y+1)^2) \Rightarrow ((x+1) < (y + 1 +1)^2)$ (1) If (1) is valid I would like I ...
1
vote
1answer
32 views

Prove that the class of dense linear orders cannot be axiomatized by purely universal sentenes [closed]

That is, prove that there is no set $T$ of purely universal sentences such that for every structure $A$ over the signature $\{\leq\}$, $A$ is a dense linear order iff $A\models T$.
3
votes
1answer
29 views

How can I prove the following with natural deduction rules? ¬∀x∃yP(x,y) ⊢ ∃x∀y¬P(x,y)

I have been stuck with this problem for a long time, I tried reductio ad absurdum and I got the hypothesys [¬∃x∀y¬P(x,y)], then I try to eliminate the negation of the premise, but I have to prove ∀x∃...
0
votes
0answers
7 views

First order natural deduction proof [duplicate]

I have been stuck with a natural deduction proof of a first-order logic theorem, which has already been discussed here Tricky proof in Natural Deduction [¬∀x∃y¬Rxy ⊢ ∃x∀yRxy]-help ...
1
vote
0answers
75 views

Reference request: Reflection as a single axiom interpreting the whole of ZFC?

Working in first order languge $\mathcal L(\in, W)$, where $W$ is a constant symbol. Reflection: if $\varphi$ is a formula in $\mathcal L(\in)$, in which $x$ is free, and $\vec{p}$ is the string of ...
0
votes
1answer
33 views

Easy example of a herbrand structure

Can someone give me an easy example of a Herbrand structure? I can't really visualise the difference between a Herbrand and a normal structure.
1
vote
1answer
36 views

What are the completions of first-order group theory?

A completion of some theory $T$ (i.e. set of first order statements $T$) is a consistient theory $T' \supseteq T$ such that for every first order statement $\phi$, either $\phi \in T'$ or $\lnot \phi \...