Stack Exchange Network

Stack Exchange network consists of 175 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.

1
vote
1answer
32 views

Countable countable models

I have a proof of the following: [*] Let $A$ be a countable $\omega$-saturated model of a complete, countable theory $T$ (with infinite models). There is a bijection between the orbits under ...
3
votes
1answer
31 views

$\mathbb{Q}^{alg}[[a,b]] $ is not elementary equivalent to $\mathbb{C}[[a,b]]$, and the same for $\mathbb{Q}^{alg}[a]$ and $\mathbb{C}[a]$?

Since ACF is complete, $\mathbb{Q}^{\text{alg}}$ is elementary equivalent to $\mathbb{C}$, and by Ax-Kochen $\mathbb{Q}^{\text{alg}}[[a]]$ is elementary equivalent to $\mathbb{C}[[a]]$. But how should ...
2
votes
1answer
43 views

Enderton's sentential “tautological implication” subsumed by Enderton's first-order “logical implication”?

(My question is clearly marked at the bottom. I don't think I'm asking the same question as this math.stackexchange.com question.) I'm working in the framework of Enderton's A Mathemtical ...
0
votes
1answer
17 views

Formally deriving a vacuous truth from a definition involving conjoined implications

Definition of absolute value: $\forall x \in \mathbb{R}, (x \geq 0 \Longrightarrow |x| = x) \wedge (x < 0 \Longrightarrow |x| = -x)$ I want to use this definition in one of my proofs. So I ...
0
votes
1answer
33 views

How could I proceed in proving that a Lindenbaum algebra is atomless?

Given a $P$ infinite set of propositional variables we consider the Lindenbaum algebra generated by $P$. Then is this algebra atomless?
0
votes
0answers
46 views

Can real vector space be a model of first order logic? [on hold]

As far as I understand the linear vector algebra is first order theory, some instance of first order logic. But what about generality? Can ve construct real (or trascendental, hypercomplex or polyadic)...
0
votes
0answers
45 views

Can the cardinality of the set of all intervening cardinals between sets and their power sets be always singular?

Is the following known to be consistent relative to some large cardinal assumption? $\forall \kappa [\kappa >2 \to \kappa < \kappa^* < 2^\kappa \wedge singular(\kappa^*)]$ where $\kappa$ is ...
3
votes
1answer
49 views

Models that realize all types

Let us call a theory $T$ good if it is complete; it is formulated in a countable language $L$; it has infinite models. Suppose $T$ is good and $M \models T$, the exercise is to prove $M$ is $\...
1
vote
1answer
29 views

In FOL, can we define equality for two predicate symbols?

In FOL, I think equality is always used for two variable or constant symbols. Can we define equality for two predicate symbols? If not, why? (Do we need higher order logic to use such a concept?)
4
votes
2answers
253 views

Why constant symbols in a language?

What is the point of constant symbols in a language? For example we take the language of rings $(0,1,+,-,\cdot)$. What is so special about $0,1$ now? What is the difference between 0 and 1 besides ...
0
votes
0answers
19 views

Is this first-order sentence correct?

It is meant to express the initial conditions of a simulation: There are $N$ boxes. The boxes can store apples and pears, whose amounts are $a$ and $p$ respectively. Each box stores half of its ...
1
vote
0answers
69 views

Are the following size rules taken from the herediarily finite world consistent with ZFC?

Let $x^*$ be the set of all cardinalities that are strictly larger than the cardinality of $x$ and strictly smaller than the cardinality of $P(x)$. Formally, that is: Define: $s=x^* \iff \forall y (y ...
0
votes
1answer
30 views

First order logic without existential quantifier, does the position of the “forall” matter?

I am considering first order logic without existential quantification (i.e. with $\forall$ as the only quantifiers). Given an arbitrary formula, would moving all the $\forall$ to the "front" of the ...
2
votes
1answer
92 views

What is the consistency strength of generalized failure of the continuum hypothesis.

What is the consistency strength of $$ZFC + G \neg CH$$ where $G \neg CH$ is Generalized anti-continuum hypothesis! Formally this is: $$\forall x [|x|> 1 \to \exists y \ ( |x|<|y|<|P(x)|)]$$ ...
0
votes
1answer
25 views

What is the relationship between a requirement for consistency of a theory and what it can prove?

This is a question that I always had in mind. When it is said that the consistency of a theory $T$ requires the assumption of existence of some specified cardinal $\kappa$. Is that taken to mean ...
0
votes
1answer
19 views

First-order logic problem

I don't know how to define in the logic of the first order the following statement: "The set of natural numbers $N$ is closed with respect to the sum operation between them". For this purpose it’s ...
1
vote
1answer
24 views

Completeness Theorem for a finite domain

I take the Completeness Theorem to be saying the following: Any consistent, countable set of sentences has a model whose domain only contains natural numbers. But something feels off when I ...
2
votes
3answers
91 views

Are there paradoxical/ counter-intuitive laws in predicate logic? ( beyond the Drinker Paradox)

Preliminary remarks. (1) The term "paradoxical" is not used in a negative sense here. What is " para-doxical" is literally what disagrees with the general and uninformed " opinion": it could be argued ...
0
votes
1answer
49 views

How to state sentences for KB ∧ ¬ α given existing KB?

How do I state the sentences for KB ∧ ¬ α when I already have KB. KB: ∀xTourist(x) => Person(x): Every tourist is a person. ∀xTourist(x) ∧ visits(x, Malaysia) => walksCanopy(x): Every tourist who ...
0
votes
1answer
25 views

Show that the decision problem for implication is solvable if and only if the decision problem for validity is solvable

Having trouble with the forward direction of this proof. I assume that the decision problem for implication is solvable, so that for any set of sentences $T$, I can arrive at a yes or no answer to ...
1
vote
0answers
21 views

Is intuitionistic first-order logic with no function or relation symbols decidable?

Classical first-order logic with no function or relation symbols is decidable. If I'm not mistaken, this is essentially because any formula (with possible free variables) has truth value uniquely ...
0
votes
1answer
17 views

Maximizing a function with dependent variables

I am trying to find the maximum of a function $f(x,y)$ in which $x$ and $y$ are dependent on each other. For example, $x$ is the size and $y$ is the weight of a component. In order to find the ...
0
votes
0answers
35 views

Is it true that there is no algorithm to find the proof in the fitch proof system??

I think it probably exists. This is because the fitch proof system for propositional logic and FOL is very simple. Although it may not be effective. Can anyone tell me about such an algorithm?
0
votes
0answers
19 views

Is bare first order logic without equality an empty language?

Suppose we are considering first-order logic without equality without any relation symbols. Since there are no relation symbols, not even equality, does this mean that this language is empty?
4
votes
1answer
99 views

Conversion from Propositional Logic to Predicate Logic

I came across a proposition which I'm having a hard time converting into predicate logic. It has been a long while since I have touched the topic. The proposition reads \begin{align} &\text{...
0
votes
0answers
23 views

translate into 1st order logic

“Every Italian has an Italian lover. The father of every Italian is very protective of that person. Angelo and Antonio are Italians. If Antonio's lover is Angelo, then there is someone who is ...
1
vote
1answer
45 views

If something is provable in ZFC, can ZFC prove that ZFC proves it?

IF ZFC proves a Well-formed formula, it means, if $ZFC \vdash \phi$, then, $ZFC \vdash (ZFC \vdash \phi$) ? Generally, if an axiom system proves a wff, the axiom system can prove that it proves ...
2
votes
1answer
40 views

Consistent theories that proves their own consistence

Restrict the whole question to first order logic only. Gödel second incompleteness theorem tell us that, if, for example, we are working with Peano language, every T (recursively axiomatized, ...
1
vote
1answer
24 views

Find a first order sentence that characterizes infinite totally ordered sets

TotOrd is just the axioms of totally ordered sets I am not sure how to create a sentence that characterizes infinite sets with 2 endpoints
2
votes
1answer
53 views

Show $\neg(\forall x\phi)\vdash \exists x(\neg \phi)$ using an ND-derivation

I'm trying to show that $\neg(\forall x\phi)\vdash \exists x(\neg \phi)$ through a natural deduction (ND) derivation. I'm kind of stuck, because I don't see how I can find some $t$ such that we have $...
3
votes
0answers
34 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:
5
votes
1answer
93 views

How to tackle prime models and saturated models

We define $T$ as the theory of equivalence relations $\{R_n\}_{n\in\mathbb{N}}$ such that $R_{n+1}$ refines $R_n$. Prove that $T$ 1) has a countable prime model; but 2) no countable $\aleph_0$-...
2
votes
1answer
45 views

Proof of satisfaction given the same free variable interpretation

I am reading Enderton's A Mathematical Introduction to Logic (here a link to its second edition) and I am not sure I understand this proof, could anyone help please? What I don't understand is what ...
2
votes
1answer
39 views

First order logic: Difference between sentences

My task is to translate the following 2 sentences to first-order logic. I can't figure if my proposed solution is also correct even though it doesn't match the professor's solution. $1$. No student ...
0
votes
0answers
21 views

Solving a certain universal claim in natural deduction for predicate logic. [duplicate]

I am having a lot of trouble coming up with a solution for the following predicate Logic Natural Deduction question: $$⊢P(a) → ∀x(P(x) ∨ ¬(x = a))$$ I have spent almost all day working on it and ...
1
vote
2answers
42 views

First Order Logic to CNF for Knowledge Base

I am doing some Homework for an Artificial Intelligence Course, we are covering some First Order Logic and Conjuctive Normal Form. Here are the questions that I have to answer that I am having ...
1
vote
3answers
41 views

Ordering and comma use in predicate logic

Use of commas and ordering in notations of logic confuse the hell out of me especially when variables of different sets are concerned. What I'm trying to formalize is that $G\left(a,b,r\right)=-G\...
2
votes
2answers
45 views

Does the deduction theorem hold in Q?

The proof of the deduction theorem (for a system including Hilbert Calculus) that I am familiar with uses modus ponens to prove the result one way, and mathematical induction the other way. Robinson'...
0
votes
0answers
20 views

Proving equivalence of two statements in Smullyan, “Set Theory and the Continuum Problem”

In Smullyan and Fitting's ''Set Theory and the Continuum Problem,'' chapter 14 definition 1.4 reads as follows: Definition 1.4. Let us say a formula $\varphi(x, y)$ is function-like over a ...
2
votes
1answer
38 views

Deciding if Valid FOL Sentence

I am doing a HW assignment for First Order Logic with english sentences and this is one of the questions. Not exactly sure of how to approach it and to answer it. Q1. [10] Decide each sentence is ...
2
votes
1answer
30 views

MGU - most general unifier for skolem functions?

I have trouble understanding MGU for functions, especially skolem functions. Is it correct that in order to find MGU for 2 functions, say f(x) and g(y) then they ...
0
votes
0answers
15 views

Translating English to First Order Logic

For the following natural language sentence: No Slytherin students like any student in Gryffindor. How can it be converted to First Order Logic sentence? One possible conversion is: ...
1
vote
2answers
34 views

Variation on Lob's Theorem

Lob's theorem is, of course, if $P(y)$ is a provability predicate for $S$, $S$ diagonalisable, then if $(P(A) \rightarrow A)$ is provable in $S$ then $A$ is provable in $S$. I understand the proof of ...
2
votes
1answer
48 views

When is $X \rightarrow P(X)$ provable?

My question is: within a system $S$ where $S$ is any extension of $Q$ (Robinson's Arithmetic), and when $P(y)$ is a provability predicate for $S$, when is $(X \rightarrow P(X))$ provable? By ...
0
votes
0answers
42 views

Is there a clear inconsistency with this Lewis like Mereological foundation of set theory?

Lewis's approach to Mereological foundation of set theory, is very interesting by itself. The following shows that it can indeed provide an interpretation for Ackermann's set theory! In brief let our ...
0
votes
0answers
32 views

Express the following requirements with First Order Logic, and define terminology (predicates and functions to be used) in tables;

a) The elevator system shall accept passenger requests and provide feedback. b) The elevator system shall support all relevant fire and safety codes in effect. c) The elevator system shall have ...
3
votes
1answer
50 views

Is there a way to syntactically characterize homomorphic images and products?

Birkhoff's HSP theorem states that if a class of algebras (for a given type) is closed under products, subalgebras and homomorphic images ($\iff$ quotient), then it is actually defined by some ...
0
votes
1answer
36 views

First Order Logic Peano arithmetic Proof

I'm trying to prove: $\forall x\forall y((x=y)\longrightarrow(x\not<y)$ I tried starting off with $u=v, u+s(z) = v\vdash u = v$ $u=v, u+s(z) = v\vdash u+s(z) = v$ . . . $u=v, u+s(z) = v\vdash ...
0
votes
0answers
13 views

Why description logics are decidable but first order logics not decidable?

They say description logics are a fragment of first order logics(FOL) but description logics are decidable but FOL are not decidable. Why is that? can i have elaborated explanation with examples? ...
2
votes
1answer
53 views

Peano axioms and commutativity of addition

I'm trying to prove the commutativity of addition in Peano arithmetic in something like a natural deduction system, but am stuck halfway (I say "something like a natural deduction system" because I ...