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.

4
votes
1answer
27 views

Taking an unproven but “seemingly true” statement as an axiom

I'm sorry for this uneducated question, but I've been thinking of this for a few hours and I couldn't find anything on the topic. Perhaps it is just a failure on my part and a limitation of my ...
0
votes
0answers
19 views

Find non-isomorphic models of $(Q,<,c_{n \in N})$

This is a problem in Basic Model Theory by Kees Doets: Let $X=(Q,<,n)_{n \in N}$ $Y=(Q,<,\frac{-1}{n+1})_{n \in N}$ $Z=(Q,<,q_n)_{n \in N}$ where $\{q_n\}_{n \in N}$ is an ascending ...
0
votes
0answers
5 views

Is the collection of all partial isomorphisms between finitely generated substructures from Z nonempty?

given : L := {<}, L-Structure Z' = (Z, <) with the usual order. Is the collection of all partial isomorphisms between finitely generated substructures from Z non-empty?
0
votes
1answer
29 views

First-order logic formula(prime numbers)

How to write into a first-order logic formula: 1) $m$ is prime number, which consists in $[\sqrt{n},n]$ 2) $n$ is number of second power of prime number. $\textbf{My work:}$ Prime number can be ...
1
vote
0answers
53 views

What is the consistency strength of Ackermann + the following cardinals to ordinals isomorphism?

This is a try to salvage the attempt written in the posting: "Can we derive a large cardinal axiom by a principle of isomorphism between cardinals and ordinals?" Here we change the base theory to ...
-1
votes
1answer
60 views

Can we derive a large cardinal axiom by a principle of isomorphism between cardinals and ordinals

[EDIT, this posting had been answered to the negative, However it couldn't be deleted, so I've written a salvage for it in the posting titled "What is the consistency strength of Ackermann + the ...
-1
votes
1answer
82 views

Intuition behind Unprovable Truths: Godel

Godel's Incompleteness Theorem says there are statements in an axiomatic system which are TRUE but UNPROVABLE. I have read other answers here, but none of them captures the essence of such statements. ...
0
votes
0answers
33 views

What do sentences in the theory of the structure $A=(Q,<,n)_{n \in N}$ look like?

I'm working on a problem from Kees Doets, and he mentions the following structures: $X=(Q,<,n)_{n \in N}$ $Y=(Q,<,\frac{-1}{n+1})_{n \in N}$ $Z=(Q,<,q_n)_{n \in N}$ where $\{q_n\}_{n \in ...
1
vote
1answer
33 views

proof by finding suitable instances and resolution

I am trying to proof by resolution the following: 1) Given a language with the binary relation symbols $<, <<, <<<$ and the binary function symbols $+, *$ and the constant symbols ...
2
votes
1answer
34 views

First Order Logic: how to prove the formula?

How to show this formula using axioms of First Order Logic: $\forall x_{0}, \forall x_{1}, \forall x_2 ((x_{0}=x_{1})\wedge (P(x_1,x_2) \rightarrow Q(x_1,x_2) )\rightarrow (P(x_0,x_2) \rightarrow Q(...
1
vote
3answers
48 views

If $\Sigma \models \phi$, then for some finite $\Delta \subset\Sigma$, $\Delta \models \phi$.

This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory: Let $\Sigma$ a set of sentences and $\phi$ a sentence. If $\Sigma \models \phi$, then ...
1
vote
1answer
43 views

Proving $\forall x \forall y Rxy \therefore \forall x \forall y Ryx$.

I have been having a hard time trying to understand how to prove the following proof: $\forall x \forall y Rxy \therefore \forall x \forall y Ryx$ What I have done so far is opened the 2 sub-proofs ...
1
vote
1answer
33 views

Is there a standard quantifier notation for an exact number of true values?

When working with SAT Solvers, I need to write quantifiers that give the total number of true values. The usual quantitiers $\forall$ and $\exists$ do not suffice. Is there a standard notation for ...
1
vote
2answers
39 views

Craig interpolants for inifinite set of implications

Suppose we have an infinite set of first-order sentences $\{\alpha_i\}_{i=1}^{\omega}$ and first-order sentence $\beta$ such that for all $i$, \begin{align*} \alpha_i \vDash \beta \end{align*} I ...
-1
votes
1answer
59 views

A well-formed-proof by (or in) the propositional calculus is also a well-formed-proof of set theory? [closed]

In the set theory that J. Barkley Rosser presents in Logic for Mathematicians (1973) it is suggested as a method of proof for set theoretical formulas(p.p.230-235)that if one wants to prove a theorem ...
1
vote
2answers
83 views

What exactly is a formula in set theory?

I've taken a look at this: Set theory formula But I'm still a little confused. Is the formula supposed to take x, y, z as input and produce "TRUE" as an output? Are all set theory formula's TRUE?
1
vote
1answer
34 views

Prove that the topological closure of a set is definable if the set is definable

Let $L$ be the language $L=\{<,=,+,-,\cdot, 0,1\}$, with standard interpretations, and let $\mathcal{A}=\langle\mathbb{R}, <,=,+,-,\cdot,0,1\rangle$. Let $S\subseteq\mathbb{R}^n$. Show that if $...
0
votes
0answers
11 views

Double universal quantifiers at skolemization step of first-order logic to CNF conversion

I am trying to convert the following formula $$ (\forall_{X}\forall_{Y}((\forall_{Z}p(X,Y,Z))\rightarrow (\exists_{P}q(Y,P))))\wedge\exists_{S}r(S) $$ to CNF. After eliminating the implication, ...
0
votes
0answers
28 views

Show that first order Peano's axioms capture the natural numbers regarding satisfiablity

Denote be $\mathcal P_{MO}$ the set of the monadic second order axioms of Peano. Then as shown by Dedekind any two model are isomorphic to $\mathbb N$. Hence for a monadic second order sentence we ...
0
votes
3answers
32 views

Axiom of extensionality inconsistent with empty set?

Axiom of extensionality looks like this: $\forall{A,B}:(\forall{X}:(X \in A \iff X \in B) \implies A=B)$ Now set $A= \emptyset=\{\forall{Y}:\lnot(Y \in A)\}$ (axiom of the empty set) Now look at ...
1
vote
1answer
14 views

Prove formula using skolemization and resolution

I have the following formula that I am trying to prove is valid: $$\exists x \forall y q(x,y) \rightarrow \forall y \exists x q(x,y)$$ By following the Skolemization algorithm in the book "...
0
votes
0answers
24 views

FOL: substitution of open formulas and the Substitution Theorem in Van Dalen's “Logic and Structure”

Theorem 3.5.8 (Substitution Theorem), p. 72 in Van Dalen's Logic and Structure (5th ed.) states that $$\models(\varphi \leftrightarrow \psi) \rightarrow(\sigma[\varphi/P] \leftrightarrow \sigma[\psi/...
0
votes
0answers
33 views

How can I define Propositional Expansion precisely?

Suppose that our universe of discourse is $X=\{ x_1, x_2, \cdots , x_n \}$ Then, intuitively, the following seems to be truth. $$(\exists x\in X) (P(x)) := (P(x_1) \lor P(x_2) \lor \cdots \lor P(x_n)...
0
votes
1answer
32 views

Are these logic statements equivalent?

I understand logical statements #1 and #2 to be equivalent. I have been told that logical statement #3 is not equivalent to #2, but I do not understand how or why (assuming what I have been told is ...
2
votes
1answer
47 views

$T \vdash \forall x (f(x)=x \vee \dots \vee f^{n}(x)=x)$ for $\omega$-categorical theories

Let $T$ a $L$-theory $\omega$-categorical such that $f \in L$ is a symbol unary of function. I want to show \begin{equation} T \vdash \forall x (f(x)=x \vee \dots \vee f^{n}(x)=x) \end{equation} for ...
2
votes
0answers
59 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-...
1
vote
1answer
48 views

consistent Henkin theory with language that has only one constant symbol

as the title says, I am looking for a consistent Henking theory (either a complete or an incomplete one, or both of them) whose language has only one constant symbol (but may have more predicate- and/...
0
votes
1answer
60 views

infinite and uncountable structures in specific classes of structures

I'd appreciate your help with proofing one or both of the following statements: 1) let $M$ be an infinite countable structure. We want to show that there's an uncountable structure in $Mod(Th(M))$, ...
0
votes
1answer
27 views

Formalisation of a given sentence using quantiifiers

The question is: Minesweeper is a single-player computer game invented by Robert Donner in 1989. A unary predicate mine is defined, where $mine(x)$ means that the cell $x$ contains a mine ...
0
votes
1answer
25 views

Equivalence of tuple relational calculus expression

A. $\forall t \in r \left(P\left(t\right)\right)$ B. $\exists t \notin r \left(\neg P\left(t\right)\right)$ solving B, $\neg\forall t\in r \left(\neg P\left(t\right)\right)$ $\neg\forall t\notin r ...
0
votes
0answers
36 views

How does one show that the Godel number of $L-$terms are computable?

I was reading these (page 100 paper pdf) notes and was trying to show the Godel number of $L-$terms are computable. The structural recursion they have for this: I will use the symbol $g(t) = \...
4
votes
1answer
27 views

Nonisomorphism of real numbers and reals without 0 (the only symbol is the < symbol)

Why are $(\mathbb{R}, <)$ and $(\{ x \in \mathbb{R} | x \neq 0\}, <)$ not isomorphic? My approach is to assume that there is an isomorphism and attempt to derive a contradiction by showing that ...
1
vote
1answer
17 views

Why is $Th(\Sigma) := \{ \sigma : \Sigma \vdash \sigma \}$ an L-theory?

I was told that: $$ Th(\Sigma) := \{ \sigma : \Sigma \vdash \sigma \} $$ is an L-theory (i.e. its closed under provability i.e. $if T \vdash \sigma \implies \sigma \in T$). I feel it should be a ...
0
votes
1answer
26 views

Why is a relation that is $\Sigma-$representable not an IFF condition?

I was reading these notes and the definition of $\Sigma-$representability of a relation. It's as followings. $R$ is $\Sigma$ representable if $\forall a \in \mathbf N^m$ (where $a_i = S^{a_i} 0$ and $...
2
votes
4answers
51 views

Evaluating a proposition that is empty

Here is a silly example to illustrate my question: Definition We call a function zeroed-at-one if $f(1)=0$. If $1$ is not in the domain of $f$, is the statement "$f$ is zeroed-at-one" true or false? ...
2
votes
1answer
38 views

Example of incomplete, but decidable theory, and of complete and undecidable theory, question

On wikipedia it is written that Decidability should not be confused with completeness. For example, the theory of algebraically closed fields is decidable but incomplete, whereas the set of all ...
0
votes
1answer
26 views

$T \models \phi(c_1,\ldots,c_n)$ implies $T \models \forall x_1,\ldots,x_n\ \phi(x_1,\ldots,x_n)$?

Let $L$ be a language and $T$ be an $L$-theory. Let $L'=L \cup C$ where $C$ is a set of new constant symbols. Suppose $\phi(x_1,\ldots,x_n)$ is an $L$-formula and $(c_1,\ldots,c_n) \in C^n$. (1) ...
3
votes
1answer
67 views

How to know if the class of theories can be axiomatisable?

Let $L =${ $E$ } where $E$ is a symbol for a binary relation. If $K$ is a class of $L$ structures and $T$ an $L$ theory, we say $T$ auxiomatize $K$ if for every $L$ structure $M$, $M$ in $K$ if and ...
2
votes
3answers
67 views

Show that $\Sigma \vdash\varphi$ if and only if $\Sigma\,\cup \{\neg\varphi\}$ is inconsistent.

I am stuck at the following problem: Let $\varphi$ be a sentence in a predicate calculus $T$ and $\Sigma$ a set of sentences in $T$. Show that $\Sigma \vdash\varphi$ if and only if $\Sigma\,\cup \{\...
0
votes
0answers
38 views

If $\mathcal{M} \equiv \mathcal{N}$ then there is some $L$-structure $\mathcal{R}$ and elementary embeddings between them.

Let $L$ be a language and $\mathcal{M},\mathcal{N}$ be $L$-structures. Suppose $\mathcal{M}$ and $\mathcal{N}$ are elementarily equivalent. Prove that there is some $L$-structure $\mathcal{R}$ and ...
0
votes
0answers
32 views

Parentheses for quantifiers in First-Order Logic affect logical operators normally?

I'm sure this is a very simple question, but I cannot manage to find it explictly answered anywhere. Do parentheses used for quantifiers also affect logical operators normally? For example, if ...
0
votes
1answer
57 views

show that for every consistent theory there is a complete consistent theory

Let $\mathcal{L}$ be any language of predicate logic, $\Sigma_0$ a consistent theory in $\mathcal{L}$. Let P be the set of all consistent theories $\Sigma \supseteq \Sigma_0$ in $\mathcal{L}$. With ...
0
votes
0answers
41 views

What is the reason for the specific assumption on the nature of the variables?

In Angelo Margaris's book First Order Mathematical Logic we have the following theorem (see pp. 84), The equivalence theorem. Let $U$ and $V$ be two formulas (of First Order Predicate Calculus). ...
2
votes
0answers
29 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)$ ?
-4
votes
1answer
37 views

Natural deduction proof - is this correct?

I don't know of any means to check my work, can anyone point out if they're any mistakes?
-1
votes
0answers
25 views

Identifying Syntax and Semantics [duplicate]

Let us take a universally known statement: 2+2=4 Syntax refers to symbols, so we are probably talking about stuff like '2', '+', '=', '4'. We can classify them. Syntax is probably also about ...
0
votes
1answer
49 views

Proving ∀x(A(x) ∨ B) → ∀xA(x) ∨ B, with x is not in B, by natural deduction

how can prove ∀x(A(x) ∨ B) → ∀xA(x) ∨ B where x is not in B using natural deduction. i am not sure how should use for all introduction rule here. any help wpuld be highly appreciate. Cheers
1
vote
2answers
83 views

What is the meaning of ∀x∃x?

Say we are in first-order logic, $x$ is a variable and its values are from a set of values, doesn't matter what. $∀x∃x$ means for every $x$ (from the set of values) there exist at least one x (from ...
0
votes
1answer
26 views

How to prove ~($\forall$x Q(x)) is logically equivalent to $\exists$x(~Q(x)) using natural deduction for first order logic

I am thinking of assuming Q(x1) and then deriving to reach to a contradiction but I have not been able to do so.
1
vote
0answers
15 views

beta reduction: order of substitution

Do we always apply our input to the left most term in a lamda expression? For instance, take the expressions: $λP λQ. ∀x P(x)→Q(x)$ which we can rewrite as $[λP λQ[ ∀x P(x)→Q(x)]]$ $λP. λQ. ∀x P(x)→...