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,250
questions
0
votes
0
answers
50
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.1k
4
votes
1
answer
333
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. ...
- 988
5
votes
0
answers
86
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
212
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
4
votes
0
answers
76
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, ...
- 41
0
votes
0
answers
95
views
What is the minimal length of an undecidable sentence in those ZFC related theories?
If we measure the length of a sentence by the number of occurrences of atomic subformulas in it. So, for example in set theory written in $\sf FOL(\in)$, the length of a sentence is the number of ...
- 10.1k
4
votes
0
answers
145
views
+150
Bounding proofs of transfinite induction
Let $\phi$ be a "reasonable" formula in the language of first-order arithmetic expressing some amount of transfinite induction along a given (index for a) computable linear order; my default ...
- 20.6k
0
votes
1
answer
105
views
How can we define non-finitely axiomatizable extensions of set theories?
Suppose we have a first order set theory $T$ that is finitely axiomatizable. Is there a general way to formalize a set theory $T^+$ that extends $T$ and that is slightly stronger than $T$ and that is ...
- 10.1k
1
vote
0
answers
119
views
Constructively, when do functions that agree on $[a, b] \cup [b, c]$ also agree on $[a,c]$?
Let $a, b, c \in \mathbb R$ such that $a \le b \le c$. Let $S$ be some set and $f, g : [a, c] \to S$ be functions. As a follow up to When can a function defined on $[a, b] \cup [b, c]$ be ...
- 6,160
11
votes
2
answers
1k
views
Am I doing a forcing argument here?
I have an argument of the following form:
Executive Summary:
We have a $\mathbb R$-valued function $L$ which we want to show is $\mathbb Z$-valued. We approximate it by $\mathbb Q$-valued functions $\...
- 62.5k
16
votes
2
answers
1k
views
Is it consistent with ZFC that the real line is approachable by sets with no accumulation points?
Let $P$ denote the following proposition:
There exists a set $S$ of subsets of $\mathbb{R}$ such that
$S$ is totally ordered by inclusion;
each member of $S$ has no accumulation points;
the union of ...
- 988
9
votes
1
answer
828
views
What gets to be called a "proper class?"
ZFC has no formal notion of "proper class," but informally, everyone uses the term anyway. $V$, $Ord$, etc are said to be proper classes. Similarly, although in ZFC, one can only take the &...
- 4,837
9
votes
0
answers
230
views
Open problems in complete theories
It is well-known that every complete recursively enumerable first-order theory is decidable. Does that mean that such theories are "trivial", or are there still interesting open problems ...
user507115
2
votes
0
answers
42
views
Chromatic number of the dual hypergraph [duplicate]
Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
If $\kappa>0$ is a cardinal, a map $...
- 46.9k
4
votes
1
answer
179
views
Axiomatic strength of the cumulative hierarchy
In the 2021 paper Level Theory Part I: Axiomatizing the Bare Idea of a Cumulative Hierarchy of Sets by Tim Button, a first order theory of the cumulative hierarchy is explored. Initially no axioms ...
- 9,189