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.

0
votes
1answer
21 views

Is the class of all hereditarily transitive definable sets a model of ZFC?

Is it the case that every transitive definable set is also ordinal definable? Formal definition of the former would be: $TD^M=\{u\in M: \exists \tau_1,...,\tau_n\in Trs^M, \varphi\in Formula (M\...
0
votes
1answer
24 views

Usage of (x, 1) (1) in natural deduction

When neither one of premises and conclusion includes a number like "1", like the following, I could at least proceed to some extent (although I don't know how to connect Q(y) of the first premise and ...
0
votes
0answers
37 views

Difference between 'Only' and 'Every' Keyword in Mathematical logic

Represent these two statement in first order logic: A) Only Alligators eat humans B) Every Alligator eats humans Is Every represents ≡∃ and Only represents ≡∀ ?? Can we differentiate it with ...
2
votes
2answers
73 views

When are we allowed to use the $\exists$ elimination rule in first-order natural deduction?

I don't really understand when we're allowed to use $\exists$-elimination when making first-order natural deduction proofs. I understand that the criteria are that the variable must be free in the ...
2
votes
1answer
50 views

Mekler’s construction!

I was looking at this slides by Artem Chernikov. But I did not understad what Mekler’s construction is exactly. Can one explain the idea of Mekler’s construction (in model theory) in a simple words? ...
1
vote
1answer
89 views

Axiomatisable Groups

Let A be a set of sentences (“proper axioms”) in a first-order language L with equality. Let us write Mod(A) for the class of all models of A which respect equality. We say that a class of L-...
0
votes
1answer
26 views

How do you do First order models here?

So I have a question as follow: Question 1 And I wonder if e.g. $\exists x[R(x,x)]$ means that there are things like , or does it mean that there are the same things (like twice in R) that are e.g. ...
1
vote
0answers
34 views

Using natural deduction to prove that $\forall x \lnot (P(x) \lor R(x)) \implies \exists x(\lnot P(x) \lor \lnot R(x))$

Not only do I not understand how to do this, but I don't comprehend the solution: Here, supposons means assume, and donc means thus. I'm specifically confused with line 5, for which I don't ...
0
votes
0answers
48 views

Can power set axiom be proved in a class theory of well ordered hereditarily accessible sets?

Working in a pure class theory, where sets are defined as elements of classes. That is: Define: $set(x) \iff \exists y (x \in y)$ Let's have the following known three axioms from $\text{MK}$ ...
2
votes
0answers
22 views

What is a language “expressible” in second/first-order logic?

This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated. Indeed, ...
1
vote
1answer
45 views

A (First-Order) theory T such that every embedding between T-models is elementary

I was wondering, is there a characterization for such a theory? It seems like a pretty handy property so there must be something. Would really appreciate any insight.
1
vote
1answer
35 views

Ways to show two structures are elementary equivalent

Let $\mathcal{L}$ be a finite first-order language. When we say structure we mean $\mathcal{L}$-structure. Question. Can someone lists different ways which we may use to show two given structures ...
1
vote
0answers
11 views

Using Ehrenfeucht-Fraisse games to prove elementary equivalent [duplicate]

The following theorem is Theorem 2.4.6 of Marker’s model theory book. Theorem. Let $\mathscr{L}$ be a finite a finite language without function symbols and let $\mathcal{M}$ and $\mathcal{N}$ be $\...
0
votes
1answer
25 views

Proof of the Tarski-Vaught test

The Tarski-Vaught test is a way to determine if a substructure is elementary. To my understanding, here is the theorem: Tarski-Vaught Test Let $N$ be a substructure of $M$. Then the following two ...
0
votes
0answers
34 views

Stuck in this Proof of the Completeness Theorem for Predicate Logic

I'm studying a proof of the completeness theorem for predicate logic shown in this lecture and I'm caught in an obstacle. It proceeds by showing that if a theory is consistent, then it has a model, ...
0
votes
1answer
40 views

What is the consistency strength of $ZC+\neg CH\ \forall x (|x|>1)$?

What is the consistency strength of "ZC + failure of $\text{CH}$ for all many membered sets"? I know that for the case of ZFC the failure of $\text{CH}$ for every many membered set is too strong, ...
0
votes
0answers
22 views

Proving Busy Beaver function is not recursive using Rogers's fixed point theorem

I'm trying to prove that $\operatorname{bb}(x)= \max \{U (e, 0) \mid e \leq x \text{ and } (e, 0) \in \operatorname{Dom} (U)\}$ is not recursive. ($U$ is the universal recursive function, i.e. $U$ is ...
0
votes
0answers
20 views

K-colorable map in FOL

The following claim is true in FOL: Let A be a Π1 formula over some alphabet Σ, and let M be a Σ-structure. If N |= A for all finite Σ-substructures N ⊑ M, then M |= A. A map is k-colorable, for a ...
1
vote
0answers
15 views

Equality and identity of indiscernibles

I'm considering a first-order theory where there is a given binary relation symbol "=" and these axioms (the second one is a axiom schema) : $$\forall x : x = x$$ $$\forall x, y : x=y \rightarrow (F(x)...
3
votes
1answer
43 views

$\forall x (P(x) \wedge \neg Q(x)) \equiv \forall x P(x) \wedge \neg \exists x Q(x)$

I'm supposed to determine whether or not these equivalences are valid for all predicates P and Q. I've written my assumptions but I've never done anything like this so it almost seems too simple and I ...
1
vote
0answers
46 views

First Order Logic Soundness Equivalent in Enderton An Introduction to Mathematical Logic 2001, p134.

Enderton 2001, An Introduction to Mathematical Logic, states on page 134 : Corollary 25E : If $\Gamma$ is satisfiable then $\Gamma$ is consistent and then comments "This corollary is actually ...
0
votes
1answer
32 views

How can we know whether an arbitrary sentence corresponds to a sentence in the language of arithmetic or not?

From what I came to understand from Godel's work is that a consistent effectively generated theory $T$ can have its consistency statement $Con(T)$ written in the language of $T$ itself! and that this ...
1
vote
1answer
23 views

Proving the axioms of $HFOL$ are semantic tautologies for $FOL$

We wish to construct an axiomatic system similar to $HPC$ i.e. Hilbert System for Propositional Calculus, for first order languages, denoted as $HFOL$. We wish to prove the following axioms of $HFOL$...
1
vote
1answer
32 views

Is there an arithmetic sentence for every theorem or axiom of an effectively generated set theory?

I'll quote the following from the answer to this question Gödel's work shows us how to write down an arithmetical statement that corresponds to Con(T) or ¬Con(T) for any theory T, as long as the ...
1
vote
2answers
32 views

Fitch natural deduction proof of $\forall x (P(x) \to Q(x)) \to (\forall x (P(x)) \to \forall x (Q(x))$

My logic exam is coming up and I'm pretty happy with my natural deductions, but I found this 'gem' in an old exam paper and for the life of me I cannot figure it out. You need to prove $$ \forall x (...
0
votes
1answer
21 views

FOL: Dealing with different “classes” of elements in the domain

Consider the FOL-signature: $$\Sigma = \langle\{balance\; /\; 1, spouse\; /\; 1\}, \{Rich \; / \; 1, > / \;1 \}\rangle$$ where $balance$ and $spouse$ are function symbols of arity 1 and $Rich$ ...
3
votes
1answer
36 views

Is NIP closed under $\exists$?

Definition. Let $\mathscr{L}$ be a first-order language. An $\mathscr{L}$-formula $\phi(x,y)$ has independence property (IP) if there are two sequences $(a_i)_{i<\omega}$ and $(b_I)_{i\subset \...
1
vote
1answer
57 views

Syntactical proof of universal instantiation rule

First: I am not mathematician but philosopher. I understand why the universal instantiation rule is working. $\frac{\vdash\forall xA}{\vdash A^x_t}$ But is there actually a serious proof in a ...
0
votes
1answer
29 views

Sentence satisfied by parity ordering and unsatisfied by natural ordering

Let $>_1$ be the natural ordering on $\mathbb{Z}_{>0}$ and $>_2$ be the ordering on $\mathbb{Z}_{>0}$ with $m>_1n\Leftrightarrow m>_2n$ for all $m$ and $n$ of the same parity and $m&...
0
votes
1answer
38 views

Is there a definition for free and bound variables in logic?

That makes me crazy to think about it because my book and other pages on the web talks about free and bound variables without any definition. I think everything in mathematics has a definition so ...
1
vote
2answers
65 views

Quantifier elimination exercise

Let $L$ be the language $\{c_n : n \in \mathbb{N} \}$, and $T$ the theory $\{c_i \neq c_j : i < j < \omega \}$. I want to show that $T$ has quantifier elimination (QE). It suffices to show QE ...
-1
votes
0answers
8 views

Summation in first order logic

Is there a way to express a sum of integers of a list of length n using first order logic? Say, I want the expression for sum(L)< K for any given K. How would that look using only existence and ...
0
votes
1answer
33 views

Is “PA+ω-rule” and “Zermelo-infinity+every set is finite + ω-set-rule” equi-interpretable?

We know that "PA" and "Zermelo-infinity+every set is finite" are equi-interpretable. Now is "PA+$\omega$-rule" and "Zermelo-infinity+every set is finite + $\omega$-set-rule" equi-interpretable? ...
3
votes
1answer
54 views

Given all possible k-ary relations over an n-element set, which sentences converge to a non-zero percentage as n goes to infinity?

For each relation, the sentence is either true or false. Is there a taxonomy of sentences in this regard? Many seem to converge to 0 or 1, are there some that converge to values in between?
2
votes
1answer
83 views

Are there true arithmetical statements that corresponds to inconsistency of inconsistent theories?

Lets take Naive set theory "NvST" which is the theory whose axioms are all instances of naive unrestricted comprehension, which is of course known to be inconsistent. So $\neg$ Con(NvST) is a TRUE ...
1
vote
1answer
41 views

Can $ZFC + \neg Con(ZFC)$ be interpretable in $PA + \omega$- rule?

Suppose ZFC is consistent. Then can $ZFC + \neg Con(ZFC)$ be interpretable in $PA + \omega$- rule? The idea is that "interpretability" doesn't preserve truth, so even if we hold ZFC + CH to be true, ...
0
votes
1answer
64 views

First-Order Predicate Logic on example

I have a question if First Order Predicate Logic always has to include quantifiers? E.g. in the sentence, A black dog bit a small child, would it be: Bit(dog, child) or ∀𝑥: Bit (dog, child) ? ...
0
votes
0answers
17 views

First order logic representation of permutations

First off, I'd be hugely grateful if someone commented on how to represented quantifiers in my question, or where to find documentation for using math symbols. Now for the question: I've been ...
-2
votes
1answer
92 views

What is the strongest known proxi-finite theory?

[NEWEST EDIT] This a try to salvage this method, addressing the two objections that was raised by Noah. So I'll re-exposite this approach: EXPOSITION A theory $T$ is to be labeled as "proxi-finite" ...
1
vote
0answers
19 views

Would adding abstractions over sets be inconsistent or otherwise increase the consistency strength?

Is adding abstractions (in the below mentioned manner) over $ZFC$ inconsistent? if not then does it result in increment of consistency strength? The idea is to add a new primitive binary relation "is ...
2
votes
1answer
46 views

How to show a theory eliminates quantifiers?

Definition(1). Let $\mathscr{L}$ be a first-order language. An $\mathscr{L}$-theory $T$ is said to have quantifier-elimination whenever if for all $\mathscr{L}$-formula $\phi(\bar{x})$ there exists a ...
2
votes
1answer
27 views

Is a statement with a quantified function variable considered to be of second-order logic?

Here $\mathbb{N}=\left\{n\in\mathbb{Z}:0<n\right\},$ function parameter lists are delimited as $\left[\dots\right],$ and $\underline{\exists}$ means there exists exactly one. One way to state ...
1
vote
1answer
37 views

Fitch natural deduction proof of $\forall x F(x) \lor \forall x G(x) \vdash \forall x (F(x) \lor G(x))$

I'm going through old exam papers and I found this question regarding the universal quantifier: Now this seems to be very obvious, but I just can't get it right. Doing similar proofs with the ...
0
votes
1answer
68 views

Sketches of proofs written in English that show that first-order logic is complete?

I came across the following in a textbook: $\mathcal{L}$ is a language. $\alpha \in \mathcal{L}$ is a formula. $\alpha \frac{c}{x}$ means: replace every instance of $c$ in $\alpha$ by $x$. I am ...
-1
votes
2answers
51 views

Formalizing sentences into first order logic

in regards to how can i know if a student was in the campus? edit: using first order logic(logic), which dealt with inferring, i am asking here assistance with formalizing the sentences with the ...
0
votes
0answers
6 views

Is it possible to show that this set of L-sentences in the structure $(\omega, +, \cdot, S, <, 0)$ is decidable?

Suppose that $\Sigma$ is a consistent set of L-sentences such that there is an L-formula $\phi$ such that for all L-sentences $\psi$, $\Sigma \vdash \psi \iff \phi(\ulcorner\psi\urcorner)$. Is it ...
3
votes
0answers
47 views

How to deal with second argument of implication being defined if only if the first argument is true?

Let $S$ be a set. Let $f$ be a function with $\operatorname{dom}(f)=S$. Let $P$ be a one-place property. Is the following statement well formed? $$∀x \, x∈S → P(f(x))$$ How about another one? $$\...
2
votes
2answers
33 views

How do you define least common multiple in the structure $(\mathbb{Z}, | , +, 0, 1)$

Let the relation $\text{lcm$(x,y,z)$}$ have the meaning '$|z|$ is the least common multiple of $|x|$ and $|y|$'. Show $\text{lcm$(x,y,z)$}$ is definable in $(\mathbb{Z}, | , +, 0, 1)$. My instinct is ...
0
votes
1answer
37 views

most general unifier: can a variable be substituted to a variable and a function?

i was wondering: when doing most general unifiers(MGU), can a variable be substituted to a variable and to a function? examples that illustrates my question: 1)loves(girlfriend(x),x) , loves(y,y) 2)...
4
votes
1answer
48 views

Fitch natural deduction proof of $\neg D, A \to B, B \to (C \lor D), A \lor C \vdash C$

I've been struggling with a natural deduction problem for a while now...can anyone perhaps shed some light on where I'm going wrong here? As you can see, I need to prove C from the given premises. My ...