Questions tagged [lo.logic]
first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.
5,260
questions
1
vote
0
answers
43
views
Are "equi-expressivity" relations always congruences on Post's lattice?
Given a clone $\mathcal{C}$ over the set $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with (symbols corresponding to) elements of $\mathcal{C}$ replacing the ...
- 20.8k
0
votes
2
answers
292
views
Negating fundamental axioms
It is commonplace to consider standard axiomatic systems (e.g. $ZF$) with one of the 'less essential' axioms negated, like infinity, 'less essential' here having some ambiguous definition related to ...
- 9,229
-3
votes
1
answer
216
views
Two equivalent statements about formulas projected onto an Ultrafilter
Question 1:
In the same language, let $ X $ be a nonempty set, and let $ \{ (\forall x_{x(i)} f(i)) \ | \ i \in X \} $ be a set of formulas. We use $ x(i) $ to denote the index of the variable on ...
- 45
1
vote
0
answers
72
views
Whence compactness of automorphism quantifiers?
The following question arose while trying to read Shelah's papers Models with second-order properties I-V. For simplicity, I'm assuming a much stronger theory here than Shelah: throughout, we work in $...
- 20.8k
6
votes
0
answers
70
views
Is there a substructure-preservation result for FOL in finite model theory?
It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
- 20.8k
5
votes
1
answer
219
views
Equivalence of omniscience principles for natural numbers and analytic omniscience principles for Cauchy real numbers
In constructive mathematics, a proposition $P$ is decidable if $P \vee \neg P$, and a proposition is stable if $\neg \neg P \implies P$. We have the following principles of omniscience for the natural ...
- 2,554
0
votes
1
answer
221
views
About having one axiom schema for ZFC motivated after the iterative conception of sets?
This posting is related to this posting, and builds its motivation from this answer to it.
Define: $\operatorname {History}(x) \iff \\\forall y \in x: y=\{c \mid \exists z : z \in y \cap x \land (c \...
- 10.2k
1
vote
0
answers
69
views
Defining fields of characteristic zero in existential second-order logic
Is it possible to define in existential second-order logic (ESO) the class of fields of characteristic zero? An easy compactness argument shows that the class of fields of positive characteristic is ...
- 125
-1
votes
2
answers
237
views
Heuristic interpretations of the PA-unprovability of Goodstein's Theorem
I've relatively recently learned about Goodstein's Theorem and its unprovability in Peano arithmetic (the Kirby-Paris Theorem). I do not have any real knowledge of formal logic; but I think I've seen ...
- 1,026
6
votes
0
answers
168
views
Completing half of Hilbert's program: Foundations that are conservative over Peano Arithmetic
The goal of the Hilbert program was to find a complete and consistent formalization of mathematics. Gödel's first incompleteness theorem establishes that completeness is impossible with first-order ...
- 6,230
0
votes
1
answer
118
views
What determines non-finite axiomatizability of a class extension of a set theory?
Suppose $T$ is a set theory, i.e. doesn't have proper classes. And $T$ can interpret $\sf PA$, and $T$ is an effectively generated consistent first order set theory. Now, let $T^+$ be a class theory ...
- 10.2k
5
votes
1
answer
658
views
Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?
EDIT: Noah Schweber helpfully points out that $\mathsf{ACA}_0$ is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
- 1,026
7
votes
0
answers
131
views
Algebraic structures on spaces of ultrafilters
The space of ultrafilters on $\omega$ has a natural semigroup structure, and ultrafilters that are idempotent in that algebra have seen applications in combinatorics on the natural numbers, for ...
- 18k
2
votes
0
answers
260
views
Intuition for the "internal logic" of a cotopos
Let $\mathcal{E}$ be an elementary topos. By definition, $\mathcal{E}$ is a category that has finite limits, is Cartesian closed, and has a subobject classifier $\Omega$. This subobject classifier can ...
- 173
5
votes
0
answers
89
views
Computational view of subsystems of second-order arithmetic
If System T "corresponds" to full first-order arithmetic, and System F (λ2) corresponds to full second-order arithmetic, what type systems would be associated with weaker fragments, ...
user531171