All Questions
6,026 questions
1
vote
2
answers
335
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 ...
- 708
9
votes
2
answers
473
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,353
1
vote
1
answer
143
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 ...
- 11.3k
6
votes
1
answer
742
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. ...
- 708
9
votes
0
answers
168
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 ...
- 18.6k
5
votes
1
answer
415
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 ...
- 225
5
votes
0
answers
101
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
1
vote
0
answers
119
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 ...
- 11.3k
6
votes
0
answers
290
views
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.5k
1
vote
1
answer
131
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 ...
- 11.3k
2
votes
0
answers
143
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,353
12
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 $\...
- 63.9k
17
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 ...
- 708
10
votes
1
answer
1k
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,907
10
votes
0
answers
274
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
46
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 $...
- 48.9k
6
votes
2
answers
406
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 ...
- 10.1k
15
votes
2
answers
1k
views
Proof/Reference to a claim about AC and definable real numbers
I’ve read somewhere on this site (I believe from a JDH comment) that an argument in favor of AC (I believe from Asaf Karagila) is that without AC, there exists a real number which is not definable ...
- 293
13
votes
4
answers
843
views
What is a "general" relation algebra?
I'm trying to understand why (or if) the axioms of relation algebras are "the right ones." For example, we can back up the idea that the group axioms exactly capture the notion of "...
- 20.5k
15
votes
2
answers
918
views
Which are the hereditarily computably enumerable sets?
My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a hereditarily computably enumerable (h.c.e.) set is ...
- 236k
3
votes
0
answers
170
views
Is the Tarski–Seidenberg theorem constructively provable?
The Tarski–Seidenberg theorem asserts that the projection of a semialgebraic set is also a semialgebraic set. My question is whether this is provable in constructive mathematics.
First, let me ...
- 6,353
10
votes
0
answers
159
views
Closed sets versus closed sublocales in general topology in constructive math
This question is set in constructive mathematics (without Choice), such as in the internal logic of a topos with natural numbers object, or in IZF.
Short version of the question: if $X$ is a sober ...
- 32.5k
2
votes
1
answer
57
views
Are simplicial commutative inverse semigroups fibrant?
Let $X$ be a simplicial object in the category of commutative inverse semigroups (or monoids, if needed). Is the underlying simplicial set of $X$ always a Kan complex? If so, are there some nice ...
- 742
10
votes
1
answer
644
views
Infinitary logics and the axiom of choice
Suppose we want to enhance ZF by allowing for infinitary formulas instead of just first-order ones in our axiom schema of separation and/or replacement. It seems that we don't need much power in our ...
- 4,907
4
votes
0
answers
193
views
Examples of Grothendieck ($\infty$-)topoi which do / do not satisfy the law of excluded middle
I would like to create a big list of Grothendieck topoi (or Grothendieck $\infty$-topoi) which do / do not satisfy the law of excluded middle. That is, let’s list some examples of topoi whose internal ...
2
votes
0
answers
48
views
Is the class of strongly Kripke complete normal modal logics closed under sums?
Given an arbitrary set of normal modal logics $\mathcal{L}$, one can define their sum $\bigoplus \mathcal{L}$ (or $\bigoplus_{L \in \mathcal{L}} L$ if you prefer) to be the least normal modal logic ...
- 21
3
votes
1
answer
125
views
Is existence of this function on nonempty sets of Quine atoms consistent with ZF-Regularity?
Working in $\sf ZF \text { - Regularity}$
Let $A $ be the set of all Quine atoms.
Let $f$ be a partial injective function from $\mathcal P(A)\setminus \{\emptyset\}$ to $A$.
Lets postulate the ...
- 11.3k
8
votes
0
answers
152
views
Which sentences are "strategically preserved"?
Below, everything is first-order.
Say that a sentence $\varphi$ is strategically preserved iff player 2 has a winning strategy in the following game:
Players 1 and 2 alternately build a sequence of ...
- 20.5k
0
votes
0
answers
245
views
Is this mereotopology theory consistent?
$ \newcommand{\Pt}{ \ \mathbb P \ }
\newcommand {\cz}{\ C_z \ }
\newcommand {\eps}{\ \varepsilon \ }$Logic: first order logic with equality
Extra-logical primitives:
"$\varepsilon$" ...
- 11.3k
3
votes
1
answer
174
views
Is it consistent to have $\kappa$-Kurepa trees for some $\kappa$, but no Kurepa trees of other heights?
Definitions A tree means a set-theoretic tree, that is a poset $(T,<)$ so that for each $x\in T$, the set $\{y\in T\mid y<x\}$ is well-ordered.
A $\kappa$-Kurepa tree is a tree of height $\kappa$...
2
votes
0
answers
235
views
Is there a computable model of HoTT?
Among the various models of homotopy type theory (simplicial sets, cubical sets, etc.), is there a computable one?
Can the negative follow from the Gödel-Rosser incompleteness theorem?
If there is no ...
user507115
5
votes
0
answers
109
views
Computational complexity of arithmetic sentences over classical theories
Below, I use the term "tracker" rather than "realizer" since I'm not requiring the relevant objects to be computable.
Define the relation "$f$ tracks $\varphi$" for $f:\...
- 20.5k
7
votes
1
answer
561
views
How are real numbers defined in elementary recursive arithmetic?
I am currently reading about elementary function arithmetic and Harvey Friedman's grand conjecture.
In Number theory and elementary arithmetic, Jeremy Avigad expressed Fermat's last theorem, ...
user507115
-2
votes
1
answer
169
views
Is discriminative choice provable in ZFC?
Let $\phi$ be a formula defining an equivalence relation.
Definitions:
The $\phi$-cardinality of a set $X$ be the cardinality of $X/\phi$. That is, the cardinality of the set of all equivalence ...
- 11.3k
4
votes
1
answer
269
views
Does Peano's axioms prove $\alpha$-induction for primitive recursive sequences for every concrete $\alpha < \varepsilon_0$?
It is well-known that Peano's axioms (PA) cannot prove $\varepsilon_0$-induction for primitive recursive sequences (PRWO($\varepsilon_0$)), because PA + PRWO($\varepsilon_0$) proves the consistency of ...
0
votes
0
answers
70
views
Is Acyclic ZF consistent with downshifting automorphisms?
Recall the criterion of acyclic comprehension. This is shown to be equivalent to stratified comprehension for language $\sf FOL(=, \in)$, given minimal assumptions. [See here, and here].
Let Acyclic ...
- 11.3k
4
votes
0
answers
177
views
Recording of 2009 lecture on Harvey Friedman's work
On December 13--20 2009 at Bristol, there was a meeting devoted to thorough dissection of Harvey Friedman's work on the foundations of mathematics and his statements claimed to be equivalent to ...
- 2,031
19
votes
6
answers
2k
views
Book recommendation introduction to model theory
Next semester I will be teaching model theory to master students. The course is designed to be "soft", with no ambition of getting to the very hardcore stuff. Currently, this is the syllabus....
- 9,111
4
votes
0
answers
115
views
Is there an abstract logic satisfying the Löwenhein-Skolem property for single sentences but not for countable sets of sentences?
An abstract logic satisfies the LS property for single sentences if each satisfiable sentence has a countable model. Similarly, the LS property for countable sets of sentences holds if every ...
- 2,467
1
vote
1
answer
112
views
Constructible cardinality downslides and their consistency strengths?
Posting "Large cardinals and constructible universe" mentions that $\omega_1^L < \omega_1$ if we assume Ramsey cardinal.
My question can we have more downslides like for example $\omega_2^...
- 11.3k
10
votes
1
answer
501
views
Must strange sequences wear Russellian socks?
This is an attempt to make more precise a vague guess at the end of this answer of mine. We work in $\mathsf{ZF}$ throughout.
Say that a sequence $\mathcal{A}=(A_i)_{i\in\omega}$ of disjoint sets is ...
- 20.5k
6
votes
0
answers
145
views
Alternative proofs of the countable chain condition in forcing
Advance warning: This question is more about history and pedagogy than "hard" mathematics.
I am studying Cohen forcing with the forcing poset $(\operatorname{Fin}(E,2),\supseteq,0)$, and I ...
4
votes
0
answers
150
views
Does this rule imply axiom of choice?
if $\kappa; \lambda$ are infinite Scott cardinals, then: $$2^\kappa = 2^\lambda \leftrightarrow
\kappa \leq \lambda < 2^\kappa \lor \lambda \leq \kappa < 2^\lambda $$
Would adding the ...
- 11.3k
4
votes
1
answer
312
views
What determines internalization of graph-structures into the set world?
Can we add to $\sf MK$ a cardinality function that is indexed by sets?
That is, add a new primitive total unary function symbol $C$, then axiomatize: $$C(X) = C(Y) \leftrightarrow X \cong Y \\ \forall ...
- 11.3k
1
vote
0
answers
230
views
Can the Collatz conjecture be independent of ZFC? [closed]
It is known that the Continuum Hypothesis is independent of ZFC.
The formulation of the Collatz conjecture looks somehow more simple than that of the Continuum Hypothesis.
Is it possible that the ...
- 654
1
vote
0
answers
67
views
How $n$-set -like functions are constructed?
if for every $f$ we define a relation $R_f$ as follows: $$ x \ R_f \ y \iff \exists z \in x : y=f(z)$$
So, the binary relation $R_f$ sends a set to each image under $f$ of an element of it.
Define $R \...
- 11.3k
1
vote
0
answers
62
views
Can this theory interpret TG? Would its Reinhardt's extension be equivalent to the usual one?
Language: FOL
Primitives: $=, \in$
Axioms:
Extensionality: as in Z
Define: $\operatorname {set}(y) \iff \exists x: y \in x$
Comprehension: $$n=0,1,2, \ldots \\ \forall \operatorname {set} x_1, \cdots, ...
- 11.3k
6
votes
1
answer
447
views
Why should I believe Martin's Maximum++?
$\sf MM^{++}$ is a 'good' set-theoretic axiom because it is 'Maximum'. Of course, bigger is better. But I'd like to know exactly how the argument works.
Let me be clear about the question posed:
What ...
- 695
5
votes
1
answer
220
views
What is the theory of computably saturated models of ZFC with an *externally well-founded* predicate?
For any model of $M$ of ZFC, we can extend it to a model $M_{ew}$ with an "externally well-founded" predicate $ew$. For $x \in M$, We say that $M_{ew} \vDash ew(x)$ when there is no infinite ...
- 6,353
6
votes
2
answers
470
views
Does Well-Ordered Interval Power Set "WOIPS" principle , prove $\sf AC$ in $\sf ZFA$?
Does $\sf ZFA + WOIPS$ prove $\sf AC$?
Where $\sf WOIPS$ is phrased as: for every infinite set $X$ the set of intervening cardinals between $|X|$ and $|\mathcal P(X)|$ is well-ordered.
In $\sf ZF$, I ...
- 11.3k