Questions tagged [first-order-logic]
For questions about formal deduction of first-order logic formula or metamathematical properties of first-order logic.
9,908 questions
0
votes
2
answers
97
views
How to transform a First-order logic + Peano sentence into a Turing machine?
I know that every Turing machine can be represented by a unique number and similarly every First-order logic + Peano sentence can be coded into a unique number as well.
Similarly I have read that ...
- 31
1
vote
0
answers
108
views
Is a statement of first-order logic valid if and only if you can find "witnesses" for it?
Let $\phi(\alpha,\beta,\gamma,\delta)$ be a quantifier-free, first-order formula having free variables only amongst $\alpha,\beta,\gamma,$ and $\delta$. Let $\mathcal{F}$ denote the set of functions ...
- 2,766
4
votes
2
answers
453
views
Keisler's definition of limit
Keisler's Elementary Calculus. An Infinitesimal Approach defines
$L$ is the limit of $f(x)$ as $x$ approaches $c$ if whenever $x$ is infinitely close to but not equal to $c$, $f(x)$ is infinitely ...
4
votes
1
answer
178
views
First order theories for teaching abstract mathematics
I will preface this question by stating that, although it concerns mathematics education, I think it is more suited for this platform than, for example the Mathematics Educators Stack Exchange, as it ...
- 4,413
3
votes
1
answer
84
views
Can an infinite field have an $\omega$-categorical theory?
Let $F$ be a field and let $T$ be its complete, first order theory in the language of rings. I'm pretty sure $T$ can never be $\omega$-categorical, but I have not been able to find a proof.
If char$(F)...
- 815
1
vote
1
answer
146
views
Writing a result in logic
I would like to see if I am translating correctly from natural language into logic with symbols.
Let's say I have the following result:
Let $m,n\in\mathbb{N}$, $A\in\mathbb{Q}^{m\times n}$, $b\in\...
- 425
5
votes
0
answers
212
views
Are two continuum-sized structures that are "the same at all sub-continuum levels" necessarily isomorphic? (Counterexample in ZFC)
Now cross-posted to MO.
This is a follow up to my previous question:
Let $\mathcal{L}$ be a countable language and $M, N$ be two structures over $\mathcal{L}$. Suppose $|M| = |N| = 2^{\aleph_0}$ and ...
- 26.5k
0
votes
0
answers
48
views
I can't figure out how to directly prove cut-elimination for Herbrand style proof system
I should clarify the proof system I am talking about. In this system we prove things in the following way: given a set $\{\Gamma_1,\Gamma_2,...\}$ of closed statements in first order logic, $\Gamma$ ...
- 2,766
2
votes
1
answer
117
views
In the empty theory, if something satisfies a predicate then everything does?
It is an established fact that with a non-empty universe we have $\forall x\phi(x)\implies\exists x\phi(x)$.
But suppose we prove $\exists x\phi(x)$ is a tautology. Then we have shown the negation $\...
- 2,766
4
votes
3
answers
140
views
Translate "Some fragile items are transparent only if they are glass"
What is the predicate expression for statement :
"Some fragile items are transparent only if they are glass."
Let:
$Fx = x$ is fragile item
$Tx = x$ is transparent item
$Gx = x$ is glass ...
- 87
1
vote
2
answers
176
views
Why is this statement not inferable?
Premises:
All managers are employees.
Some employees are contractors.
No contractors are full-time workers.
Only full-time workers receive benefits.
To infer:
Some employees receive benefits only if ...
- 87
-1
votes
1
answer
46
views
How do I best interpret beta existential graphs into symbolic first-order logic formulas and into English and is that even a good approach
Proof that anything unique also has at most 2 instances (since it has at most 1 instance)
The graph in question is a cut with a line of identity crossing the cut's boundary (sort of like a power ...
8
votes
1
answer
350
views
Are two structures that are "the same at the countable level" necessarily isomorphic?
Let $\mathcal{L}$ be a countable language and $M, N$ be two (not necessarily countable) structures over $\mathcal{L}$. Suppose $|M| = |N|$ and they furthermore satisfy the following condition:
For ...
- 26.5k
0
votes
2
answers
91
views
Predicate Logic: Why does this formula fail to express "Lynh loves exactly two people"? (Variable Scope)
Problem Statement: I am working on a problem from my Discrete Mathematics course regarding translating natural language into predicate logic. Let $L(x, y)$ be the predicate "$x$ loves $y$" ...
11
votes
5
answers
1k
views
Why is the formal semantic definition of quantifiers so complex?
In the book "Logic: The Laws of Truth" by Smith, N., the author has the following definition:
"$\exists x\alpha(x)$ is true in $M$ if, and only if, there is at least one object $o$ in ...
- 119