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
12 views

Are there non-linear forms of arithmetic that is logically axiomatized?

Informal idea: I'll visualize Peano arithmetic "PA" as arithmetic rising from a linear structure, we can call it in graph terms a linear directed path with a beginning and no end. The numbers are the ...
0
votes
2answers
39 views

Restrictions on Existential Introduction in first-order logic

I'm trying to understand the restrictions on Existential Introduction (EI) as defined by the Stanford introduction to logic. Three separate restrictions are mentioned: The term being replaced cannot "...
-2
votes
0answers
25 views

First order logic and conjective normal form [on hold]

Consider the following paragraph and please answer these questions below “Anyone who eats junk food or drink carbonated beverages will be a cancer victim. It is not the case that some people eat ...
0
votes
0answers
33 views

Can ZFC be interpreted in this sole class theory about ordinals?

Informally the following theory is about classes of ordinals, so only von Neumann ordinals can be elements of classes. It has a primitive partial binary function of ordered pairing over ordinals, so ...
0
votes
1answer
44 views

Can withdrawal of the Power set axiom enable absoluteness for set size statements?

If we look to models of $\small \sf ZFC$ we can have two transitive models $N,M$ such that for some formula $\phi$ in the language of $\small \sf ZFC$ we have: $\forall \mathcal M ([\mathcal M\...
1
vote
1answer
38 views

Terminology “totally transcendental” in model theory

The following is a definition of totally transcendental (a concept in model theory): Where does the terminology "totally transcendental" come from? Does it have any connection with other notions of ...
2
votes
1answer
39 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
1answer
26 views

Omega-categorical theory without quantifier elimination

Is there an $\omega$-categorical theory without quantifier elimination? The way I normally prove $\omega$-categoricity (with back-and-forth) immediately gives me QE as a corollary of the test Theorem ...
2
votes
0answers
37 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 ...
1
vote
2answers
46 views

Definition of Semantic Entailment in First-order Theory

I cannot understand the meaning of the soundness theory in first order logic. It says that if $S$ syntactically entails $p$, then $S$ semantically entails $p$. However, $p$ don't have to be a ...
-4
votes
0answers
41 views

Logical programming [closed]

“Anyone who eats junk food or drink carbonated beverages will be a cancer victim. It is not the case that some people eat junk food but they are healthy. Every cancer victims are not healthy. Bimal is ...
-1
votes
1answer
76 views

Why a language with equality in first order predicate logic has only infinite models?

I need to prove that there is no set of wff Σ of the language with equality (i.e. the language the only symbol of which is that of equality and the interpretations of this language are sets) such that:...
1
vote
1answer
57 views

Exercises involving Morley rank & degree

The definitions of Morley rank & degree I use are I understand these definitions, but I am having a hard time to use them concretely in exercises. For example, Let $L$ be a countable language ...
1
vote
1answer
50 views

Existence of a prime model for a theory

Consider the language $\mathcal{L} = \{P, f\}$ with $P$ a unary predicate and $f$ a unary function. Let $T$ be the theory: $f$ is a bijection $\forall x \, f^nx \neq x$ for all $n$ $\forall x \, (Px \...
1
vote
1answer
63 views

The theory of (Z, s) has quantifier elimination

Let $T = \text{Th}(\mathbb{Z}, s)$ where $s$ is the successor function. I want to show quantifier elimination (QE) for $T$ and construct a concrete $\omega$-saturated model. However, I am unsure ...
0
votes
1answer
26 views

Is this formula an atomic formula?

For example, the formula $\forall x.\;P(x)\wedge∃y.\;Q(y,f(x))\vee∃z.\;R(z)$ contains the atoms $$P(x),\;Q(y,f(x)),\;R(z) $$ I'm reading definition from wikipedia but I'm somehow confused if this ...
0
votes
0answers
53 views

A theorem of Skolem

I believe the following is a theorem of Skolem. How is it proved, or where may I find a proof? Suppose $\mathscr A$ is a formula of first-order logic in which no constants or function symbols occur ...
0
votes
3answers
42 views

Mistake in $A \times B \subseteq C \times D \rightarrow A \subseteq C \wedge B \subseteq D$

I am currently going through Velleman's How to prove it and I am trying to understand exercise 12 from chapter 4.1. The exercise asks to show whether the theorem in the title is correct. It is ...
0
votes
1answer
24 views

differentiable function with only positive/negative slope impies strictly increasing/decreasing

If $f:(a,b)\rightarrow\mathbf{R}$ is differentiable and 1.$f'(x)>0$ for all x $\in (a,b)$. $\ \ $then $f$ is strictly increasing on (a,b). 2.Similarly, if $f'(x)<0$ for all x $\...
2
votes
1answer
34 views

Are my logical translations correct?

I am reading Halmos’ Naive Set Theory. I attempt to translate the axioms of set theory as Halmos puts them in formal first-order logic containing equality and belonging. Please check if these are ...
0
votes
0answers
17 views

Can full Replacement be proved from replacement from sets of ordinals?

In a prior posting about "Ordinal Replacement", Joel David Hamkins had answered it, and his answer included the following statement: In fact, in this case, we needn't restrict $B$ to consist of ...
0
votes
2answers
45 views

Truth value of an open formula

I've always thought that an open formula, i.e. a formula containing free variables, has no truth value. For example, strictly speaking, I would say that for $x\in\mathbb R$, the formula "$x^2\geq0$" ...
0
votes
2answers
36 views

if $M_1,M_2$ are two structures for FOL $L$ that differ in interpretations of signs not in statement $A$, then $M_1 \vdash A$ iff $M_2 \vdash A$

Let $L$ be a first order language. Let $A$ be statement, and let $M_1,M_2$ be two structures for $L$. I want to prove that if $M_1$ and $M_2$ differ in interpretation only of signs that aren't in $A$ ...
0
votes
0answers
30 views

Infinite Conjunction vs. Compactness

How is what Quine (Methods of Logic, 1959, p. 254) called "the law of infinite conjunction" different from the compactness theorem for first order logic? The former states that if a finite or ...
0
votes
1answer
50 views

Lampert's supposed solution to the Entscheidungsproblem

Here: http://www2.cms.hu-berlin.de/newlogic/webMathematica/Logic/FOLDECISION2.pdf Timm Lampert claims to refute the Church-Turing theorem that first-order logic is undecidable. I'm wondering where the ...
-2
votes
0answers
24 views

Prove that $\Gamma$ $\vdash$ $\phi$ iff. $\Gamma$ $\vdash$ $\phi_c^x$ for any constant symbol c not occuring in $\Gamma$

i have a bit problems with this, $\Gamma$ is a set of sentences in a language, and let φ be a formula in the language. can anybody help, im pretty lost
1
vote
1answer
69 views

Ideal treatment of set theory as a meta theory for developing first-order logic

I am very familiar with the fact that when introducing model theory and the meta theorems describing a formal system, set theoretic notions are inevitably required which we include in the meta theory. ...
0
votes
1answer
16 views

FOL-Interpretation of a tableaux

Suppose I have the FOL-Formula $F := \forall x \exists y. R(x, y)$ in negation normal form. Now I want to show that $F$ is satisfiable using the tableaux calculus (TC1). By application of rules I get ...
-1
votes
0answers
28 views

Can this simplified arithmetical theory with a syntactically non reachable last natural be complete?

The following theory is coined in the language of arithmetic, however it differs in that the successor, addition and multiplication functions are not total functions. Also we add a new constant $L$ to ...
0
votes
1answer
68 views

Proof that Peano Axioms is a theory with equality (according to Mendelson book)

I'm reading Elliott Mendelson's "Introduction to Mathematical Logic". There is a statement with a proof that $S$ (Peano Arithmetic) is a first-order theory with equality. I am not sure whether I ...
2
votes
1answer
83 views

Derivative proof involving MVT and Rolle's Theorem

Suppose $f$ is a continuous and differentiable function on $[0,1]$ and $f(0) =f(1)$. Let $α∈(0,1)$. And $$∀x,y∈(0,1) ,f′(x)\neq 0\wedge f′(y)\neq 0\rightarrow f′(x) \neqαf′(y)$$ Show ...
1
vote
3answers
37 views

How to write an implication whose antecedent quantifies a variable in its consequent?

I want to write the statement $$\text{If } A^{-1} \text{ exists then } A^{-1} = \frac{\alpha-a}{\alpha^2-a^2}$$ using quantifiers. Note that $A$ and its inverse, if it exists, are taken from the set ...
0
votes
1answer
24 views

On rewriting the statement into predicate logic.

I'm interested in rewriting mathematical statement into predicate logic. Is the following correct? Normal Expression the following $x$ exists, such that $x \in R,x^2-1=0$ Predicate Logic ...
0
votes
3answers
62 views

Two definitions of exists unique

$\exists!x_0 \in S,P(x_0)$ Definitions: 1.$\exists x_0 \in S, P(x_0)\wedge(\forall x_1,x_2 \in S, P(x_1)\wedge P(x_2)\rightarrow x_1=x_2)$ 2.$\exists x_0 \in S, P(x_0)\wedge (\forall ...
3
votes
1answer
51 views

Existentially closed models of bowtie-free graphs

Setting Definition(1). $\mathcal{M} \models T$ is an existentially closed (e.c.) model of $T$ if whenever $\mathcal{N} \models T$, $\mathcal{N} \supseteq \mathcal{M}$, and $\mathcal{N}\models \exists ...
2
votes
2answers
56 views

Logical Axioms and Rules of Inference

In A Tour Through Mathematical Logic, Wolf mentions that These [logical axioms] usually include some or all tautologies, the usual equality axioms, and some simple laws involving quantifiers. ...
1
vote
0answers
31 views

Can this simple form of double extension set theory escape inconsistency?

The following theory is another way of dealing with naive comprehension. It uses the double extension principle, broadly speaking similar to what's used in Double Extension Set Theory of Andrzej ...
1
vote
0answers
55 views

Is this theory of arithmetic with a last natural that is not reachable from below complete?

This theory is a theory of arithmetic having a last natural number that is not reachable from below by syntactical recursive iteration of the successor function. So it doesn't prove all rules of ...
2
votes
1answer
48 views

Natural Deduction: Universal Introduction rule concerning free variables in Van Dalen's “Logic and Structure”

The $\forall I$ rule (forall introduction) in Dirk van Dalen's Logic and Structure (4th ed) is: $${\forall I}\, \frac{\varphi}{\forall x\, \varphi} $$ where the intended restriction is: the variable ...
3
votes
1answer
81 views

Statements vs Formulas

In A Tour Through Mathematical Logic, Wolf states that Every formula of a first-order language is a statement in the sense of Section 1.2, but not conversely. In Section 1.2, Propositional Logic,...
0
votes
1answer
48 views

every relation in a special structure $M$ which is first-order definable with parameters has cardinality $< \omega$ or $= |M|$.

Let $M$ be a special structure. I'm trying to proof that every relation in $M$ which is first-order definable with parameters has cardinality $< \omega$ or $= \lambda$. By a first-order definable ...
0
votes
0answers
30 views

Is this simple class theory equi-interpretable with ZFC?

he question here is about the consistency of a rather very simply presented theory and if it is equivalent to ZFC. The theory is a first order theory of classes, so it has its primitives being ...
-2
votes
0answers
20 views

Can potential versus actual membership evade set theoretic paradoxes?

If we informally view a set as a container, and view set membership as an invitation for entry into a container. If that invitation is fulfilled, i.e. there is an instance of entry into the container, ...
0
votes
0answers
34 views

Variable subtitution in FOL formula with nested and outer quantifiers

I am given the formula: $\Psi={{\forall}}x\exists y\left(\exists z{{\forall}}xR\left(x,z,w\right)\land\exists wP\left(w,x,z\right)\right)$ for which I'm required to determine if a given simultaneous ...
2
votes
1answer
46 views

Marker 4.5.36 - Showing elementary equivalence between two structures

This is a question about part b) of the question. Below I'll show the major 'results' in my attempt at the solution, as well as where I got stuck: 1. I defined a new $\mathcal{L}$-structure $\...
2
votes
2answers
43 views

What is the first order logic statement of “this field is of characteristic zero”?

I want to state that a field $F$ is of characteristic zero in logical notation to an audience without referring them to the meaning of the characteristic of a field. My first thought was the ...
0
votes
1answer
75 views

Is having models with ever increasing cardinality of the power set of $\omega$ is a theorem of ZFC?

I'll present this claim informally and try to write it formally as much as I can. Statement: every model of $\sf ZFC$ that statisfies the statement that the power set of $\omega$ is equal to a ...
0
votes
0answers
86 views

Had $\sf Con(ZFC)$ been explicitly written in first order language?

One always hear of $\sf Con(ZFC)$ and what is meant by that is an arithmetical sentence that is equivalent to $\sf ZFC \text { is consistent }$ that is written in the language of first order $\sf ZFC$....
1
vote
0answers
23 views

Can we have strong theories in which all sets are Dedekindian finite?

Can we have a strong class theory in which all sets are Dedekindian finite, and that has some of its sets being Tarski infinite? By strong I mean that it can interpret $\sf ZFC$ and its extensions. ...
5
votes
2answers
54 views

Quantifiers in first-order logic

The universal $(\forall)$ and existential $(\exists)$ quantifiers are the normal quantifiers which one comes across frequently. Others like uniqueness quantifier $(\exists !)$ are also there. But in ...