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 ...
• 111
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,777
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 ...
• 53
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$ ...
• 527
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 ...
• 101
34 views

34 views

• 3,331
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 ...
• 527
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 ...
• 3,331
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$...
• 3,331
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 ...
• 431
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 ...
83 views

Enderton's "Mathematical Introduction to Logic": Is he proving second order induction?

I am reading Enderton's "Mathematical Introduction to Logic" and I am puzzled by the following reasoning: Enderton defines the symbols of propositional logic (sentence letters and ...
• 520
1 vote