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
1
vote
0
answers
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
0
votes
1
answer
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)∧...
-3
votes
0
answers
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).
$$
0
votes
0
answers
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
0
answers
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 ...
5
votes
1
answer
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
0
votes
0
answers
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
0
answers
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
2
votes
1
answer
34
views
$\mathcal{Z}\models \phi(13)$ if and only if $\mathcal{Z}\models\phi(-13)$
Consider the structure $\mathcal{Z}=(\mathbb{Z},0,+,-)$ in the language of abelian groups $\mathcal{L}_{ab}=(0,+,-)$. we want to show that $\mathcal{Z}\models \phi(13)$ if and only if $\mathcal{Z}\...
- 415
2
votes
1
answer
56
views
Classification of $\beth_1$-sized models of DLOWE.
The theory of Dense Linear Orders Without Endpoints (DLOWE) is countably categorical, but this is not true for other cardinalities. Let's look at $\beth_1$.
There are at least two order types our set ...
- 10.4k
2
votes
1
answer
128
views
Open source program that generate "random" theorems by exploration
With some formal systems, it's possible to enumerate all the theorems.
This is the case for instance in propositional calculus or in some first-order theories with a recursively enumerable set of ...
- 471
3
votes
1
answer
45
views
Axiomatize the class of existentially closed structures
Let $\mathcal{T}$ be a theory in a language $\mathcal{L}$. A model $M$ of $\mathcal{T}$ is existentially-closed if for every existential $\mathcal{L}$-formula $\varphi(\bar{x})$, every extension $N \...
0
votes
0
answers
34
views
How to rigorously prove that if $A\times B\neq\emptyset$ then $(A\times B\subset X\times Y)\iff(A\subset X)\land (B\subset Y)$?
I want to prove this formula as rigorous as possible.
Here is my proof.
$\Rightarrow)$
We need to prove that
$(A\not\subset X\lor B\not\subset Y)\land (A\times B\neq \emptyset)\Rightarrow A\times B\...
- 327
-4
votes
0
answers
40
views
(Q,+,-,0) elementarily equivalent but not isomorphic to (QxQ,+,-,0) [closed]
Show that (Q,+,-,0) is elementarily equivalent but not isomorphic to (QxQ,+,-,0)
- 1
1
vote
1
answer
77
views
Basic proof verification of biconditional formula
Let $\alpha \in X$. I want to prove following statement
$$
\text{Condition } A(\alpha) \text{ is satisfied} \iff \text{Condition } B \text{ is satisfied}.
$$
First I assume that $\alpha \in X$ and ...
- 23
1
vote
1
answer
76
views
Expand a model to have a well ordering. Prove that the set of all definable elements over a subset $X$ is the universe of an elementary substructure
Let $\mathcal A$ be an $\mathcal L$-structure, let $\dot{\triangleleft}$ be a new binary predicate symbol, let $\triangleleft$ be a wellordering of $A$, and let ${\mathcal A}^*$ be the expansion of $\...
- 3,331
0
votes
0
answers
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
0
votes
0
answers
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 ...
- 1
3
votes
1
answer
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
1
answer
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
2
votes
1
answer
83
views
Count the number of non-isomorphic models for a theory $T$ describing infinitely branching equivalence classes, each class infinite
Let $T$ be a theory in a language $\mathcal L = \{E_i(x,y) \mid i \in \omega \}$ expressing the following:
(1) $E_i$ is an equivalence relation with each equivalence class infinite, for each $i \in \...
- 3,331
0
votes
1
answer
54
views
Why is the cardinality of a first-order language max{$\aleph_0, k$}?
My understanding is that the cardinality is given by the cardinality of equivalence classes of formulae under the equivalence relation of being variants of each other i.e. identical up to uniform ...
- 1
2
votes
1
answer
50
views
Proof that Skolem Arithmetic is a complete theory
Skolem Arithmetic is the multiplication-flavored cousin of Presburger Arithmetic.
Presburger Arithmetic is a complete theory and listed as an example of a complete theory on the Wikipedia article. I ...
- 10.4k
-2
votes
0
answers
33
views
Prove $⊢ A → B$ implies $⊢ (∃x)A → (∃x)B$ using a Hilbert-style proof in 1st-order logic [closed]
Prove that $⊢ A → B$ implies $⊢ (∃x)A → (∃x)B$ using a Hilbert-style proof with 1st-order axioms and the theorem $⊢ A → B$ implies $⊢ (∀x)A → (∀x)B$.
Here are the list of axioms:
I have tried several ...
- 13
1
vote
2
answers
70
views
Axiomatizing ZFC+Con(ZFC) without adding a constant symbol
I think ZFC+Con(ZFC) can be axiomatized in the following way.
Suppose our language is $(\in, w)$ where $w$ is a constant symbol.
Take every axiom of ZFC.
For every axiom of ZFC with parameters in $w$ ...
- 10.4k
6
votes
2
answers
987
views
Understanding ZFC
I initially thought that ZFC was something like a collection of axioms or formation rules, defined in terms of primitive notions, which when successively combined with each other, produced all of the ...
- 329
4
votes
1
answer
98
views
Is there a first-order sentence defining a cardinal?
Being an ordinal is first-order definable, within ZFC at least.
Out of many possible first-order characterizations, one is that an ordinal is a transitive set where $\in$ is trichotomous, i.e. $w$ is ...
- 10.4k
0
votes
1
answer
48
views
How to prove these three properties about sets?
So, here is the exercise.
Here are my thoughts.
I don't like my proof of a) because it doesn't seem formal enough.
As for b), isn't what I wrote a counterexample? If not, how can one prove these ...
- 327
4
votes
0
answers
56
views
Is many-sorted logic compact?
I read this question earlier today. It contains this comment by Noah Schweber, reproduced below, as well as this answer.
"Many-sorted logic can be easily rewritten into standard (one sort) ...
- 10.4k
1
vote
2
answers
92
views
Proof of contraposition theorem using logical (semantic) entailment definition
I have been reading some older course material from Propositional Logic and I stumbled on a question, and I am unsure on how to start the proof. The question is:
Prove the following theorem (...
- 13
2
votes
1
answer
99
views
Prove that the set of nonprime numbers $>0$ is a spectrum
$\textbf{6.10 Exercise.}$ A set $M$ of natural numbers is called a $\textit{spectrum}$ if there is a symbol set $S$ and an $S$-sentence $\varphi$ such that
$$M=\{n\in\mathbb{N}\mid\varphi\text{ has a ...
- 43
1
vote
0
answers
35
views
Let $DLO$ be the theory of dense linear orders, $c_i$ be new constant symbols, and $DLO'=DLO \cup \{ c_i < c_{i+1} \}$. Then $DLO'$ is complete [duplicate]
Let ${\sf DLO}$ be the theory of dense linear orders without endpoints. Let $c_i$, for $i \in \mathbb N$, be new constant symbols, and let ${\sf DLO}'={\sf DLO}\cup \{ c_i < c_{i+1} \mid i \in \...
- 163
2
votes
1
answer
88
views
Is ZFC independent of the logic used?
I'm generally aware that there are logics beside classical predicate logic—fuzzy logic, modal logic, and paraconsistent logics, just to name a few.
I appreciate whenever I learn about how some aspect ...
- 160
12
votes
2
answers
800
views
Nonstandard infinite / hyperfinite sum in IST
TLDR:
If anyone could provide a detailed proof that a sum indexed by an unlimited hypernatural number is well-defined using the axioms of IST, I would greatly appreciate it.
I am studying Nelson's &...
- 123
-1
votes
2
answers
74
views
When we say "cardinality of first order language L" and "cardinality of a structure or model" what we are meaning? [closed]
I ask about for what set we are referring for these cardinalities?
- 11
1
vote
0
answers
50
views
Prove that there is a sentence $\phi$ such that $\cal N\models \phi$ iff $\cal N \cong \cal M$ if $\cal L$ and $\cal M$ are finite
I'm having some trouble with the following question:
Let $\cal L$ be any finite language and let $\cal M$ be a finite $\cal L$-structure. Prove that there is a sentence $\phi$ such that $\cal N\...
- 4,443
0
votes
0
answers
34
views
First order logic - finding an L-sentence satisfiable in some structure with an infinite domain but is false in every structure with a finite domain. [duplicate]
We are concerned with the language $\mathcal{L}=\{f\}$, where $f$ is a unary function symbol. I want to find a $\mathcal{L}$-sentence which is satisfiable in some structure with an infinite domain, ...
0
votes
0
answers
43
views
proving that $\mathcal{M}\models\forall x\phi\wedge\psi\implies\mathcal{M}\models\forall x(\phi\wedge\psi)$
I'm trying to prove (or disprove, although I think this is correct) that $$\mathcal{M}\models\forall x\phi\wedge\psi\implies\mathcal{M}\models\forall x(\phi\wedge\psi)$$
I think I was able to do so, ...
- 4,443
0
votes
0
answers
49
views
proof of that we can find a sentence σ s.t. σ is true in theory A but not deducible from A
I read the book of titled "a mathematical introduction to logic" written by Enderton at pp.184-185.
i don't understand thm 30A's proof procedure. i understand proof's way intended that ...
- 15
0
votes
0
answers
20
views
Herbrand Structure
Let $C$ be the clause $¬p(x) ∨ q(f(x))$. Provide two Herbrand structures $H_1$ and $H_2$ such that $[C]_{H_1}$ is true and $[C]_{H_2}$ is false.
The domain of the Herbrand's structure is $D = \{x, f(x)...
- 295
1
vote
1
answer
47
views
A question about 2.26 in Mendelson's Introduction to Logic
I am working through Mendelson's Introduction to Mathematical Logic (3rd), and in exercise 2.26 you are asked to "derive the following theorem:"
$$
\vdash (\forall x) (\mathscr{A}\Rightarrow ...
- 485
0
votes
1
answer
50
views
Any formula is logically equivalent to a formula with all terms of height ≤ 1. [closed]
i read the book of title "A First Journey Through Logic" written by Martin Hils at page 73.
the problem is i don't understand given the proof's procedures how this process shows that any ...
- 15
0
votes
1
answer
72
views
$\varphi$ is quantifier free sentence, $T$ a theory, $\vec{c} \not\in T$. $T \vdash \varphi(\vec{c})$ implies $T \vdash \forall x \varphi(\vec{x})$?
Let $\varphi$ be a quantifier free sentence and $T$ is a theory such that $\vec{c} \not\in T$. I am trying to see why the following is true: $T \vdash \varphi(\vec{c})$ implies $T \vdash \forall x \...
- 163
1
vote
2
answers
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
0
answers
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 ...
- 11
3
votes
1
answer
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 ...
- 163
0
votes
0
answers
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 ...
0
votes
1
answer
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
0
answers
81
views
Proof Explanation - Introduction to Mathematical Logic by Samuel Buss Example III.$42$
In the book Introduction to Mathematical Logic of Samuel Buss, example III.$42$ says:
Assume that $\mathfrak{A}\not\vDash C[\sigma]$. (...) since $x$ is not free in $C$, $\mathfrak{A}\not\vDash C[\...
2
votes
0
answers
38
views
Alternative formation/ notation for axiom of mathematical induction
I hope to clarify the difference between the following two statements:
$S\subset \mathbb{N}$ (set of natural numbers),
$\forall n \in \mathbb{N}, \text{ if } n\in S \text{, then } n+1\in S$
$\forall ...
- 53