# Questions tagged [first-order-logic]

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

5,297 questions
Filter by
Sorted by
Tagged with
1 vote
50 views

### Un-definability of graphs with bounded out-degree

I want to solve the following question but has some difficulties: Given a language L = ⟨R( , )⟩ where R is a two-place relation symbol. Prove that the set of graphs of bounded out-degree (graphs whose ...
37 views

### Forms of ambiguous sentences

The sentence "Every artist is friendlier to some pianist than to some master sewer" is ambiguous. One reading is given by ∀x(A(x)→∃y∃z((P(y)∧M(z))∧F(x,y,z))) Another reading is ∃x∃y((P(x)∧...
41 views

### math logic 9th grade highscool Romaniaprove [closed]

Prove that whatever $p(x,y)$ then this is true: $$(\exists x)(\forall y)p(x,y)\to(\forall y)(\exists x) p(x,y).$$
23 views

### Do Fagin's zero-one laws hold on stochastic block model?

Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...
1 vote
27 views

### Predicate Logic - How Specific to Be When Converting From English Sentence

I'm learning predicate logic, and one of the tasks is to translate English statements into predicate logic. I'm struggling with understanding how specific you have to be. Suppose you have a statement ...
126 views

### What exactly is the unique union of a family of sets?

It's quite an elementary question, but I couldn't find anything relevant to the query online. In Velleman's book "How To Prove It", 3.6.5, this excerpt can be found 1. It defines "a new ...
68 views

### Definition of linear and renaming substitution

Wikipedia's article on substitution defines linear substitution as follows: A substitution $σ$ is called a linear substitution if $tσ$ is a linear term for some (and hence every) linear term $t$ ...
1 vote
34 views

### Uniform continuity and the order of quantifiers

I’m taking my first course in real analysis, and I’m trying to prove the following proposition. Proposition: If $f:S\to\mathbb{R}$ is uniformly continuous, then $f$ is continuous. In comparing ...
34 views

34 views

35 views

### Question on substitution [duplicate]

The Wikipedia article on substitution states: In first-order logic, a substitution is a total mapping $σ: V → T$ from variables to terms; many, but not all authors additionally require $σ(x) = x$ for ...
23 views

### How to prove equal cardinality of arbitrary subset and its closure, in this proof of downward Löwenheim-Skolem theorem?

From this wikipedia article: For each first-order $\sigma$-formula $\varphi(y,x_{1}, \ldots, > x_{n}) \,,$ the axiom of choice implies the existence of a function :$f_{\varphi}: M^n\to M$ such ...
58 views

### $tp^\mathbb{Q}(a/\mathbb N) = tp^\mathbb{Q}(b/\mathbb N)$ iff there is an automorphism $\sigma$ of $\mathbb Q$ fixing $\mathbb N$ and $\sigma(a)=b$

If $a, b \in \mathbb Q$, then $\text{tp}^{\mathbb Q}(a/\mathbb N) = \text{tp}^{\mathbb Q}(b/\mathbb N)$ if and only if there is an automorphism $\sigma$ of $\mathbb Q$ fixing $\mathbb N$ pointwise ...
1 vote
111 views

### Prove that divisibility between two natural numbers is not definable in arithmetic [duplicate]

Prove that there is no formula $\varphi(v,u)$ so that $(\mathbb N; 0, 1, +) \models \varphi[x,y]$ iff $x$ divides $y$. Here is what I have so far: assume on the contrary that we do have such $\varphi$...
83 views

1 vote
83 views

### Is $x$ a free variable in sentences like "$x\lt 7\Rightarrow x\lt 5$"?

Is $x$ a free variable in sentences like "$x\lt 7\Rightarrow x\lt 5$"? I consulted an advanced calculus book and it says that this is a false sentence, which indicates that $x$ is a bound ...
1 vote
61 views

### Connection of axioms of first order logic and axioms of first order theory

If we have a set of sentences S in first order logic. We know that we can create a first order theory Th(S) from S, which is the "set S" union "the sentences which we can prove them ...
105 views

### If A is a substructure of B and A is isomorphic to B then A is an elementary substructure of B

If $\mathcal A$ is a substructure of $\mathcal B$ and $\mathcal A$ is isomorphic to $\mathcal B$, then is it true that $\mathcal A$ is an elementary substructure of $\mathcal B$? This question arose ...
62 views

### Why does the reverse of Existential Generalisation not hold? [duplicate]

This question was prompted by this one: If $\Delta \vDash \exists x.p(x)$, then $\Delta \vDash p(\tau)$ for some ground term $\tau$. Why is this false?, but is a proof-theoretic inquiry into why does ...