All Questions
6,026 questions
18
votes
3
answers
3k
views
What's the earliest result (outside of logic) that cannot be proven constructively?
Although mathematicians usually do not work in constructive mathematics per se, their results often are constructively valid (even if the original proof isn't).
An obvious counter-example is the law ...
- 82.7k
3
votes
1
answer
271
views
A possible ${\sf (ZF)}$-theorem in the spirit of the $3$-set-lemma
The number $3$ plays an interesting role in the following statement:
$\newcommand{\S}{\sf(S_3)}\S$ Let $X$ be a non-empty set and let $f:X \to X$ be fixpoint-free (that is $f(x) \neq x$ for all $x\in ...
- 13.4k
4
votes
1
answer
214
views
Weak Power Hypothesis and Dependent Choice
Consider in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$ the following statement:
Weak Power Hypothesis (WPH): if $X,Y$ are sets and there is a bijection between $\newcommand{\P}{{\cal P}}\P(X)$ and $\P(Y)$, ...
- 39.8k
4
votes
2
answers
151
views
Are there outer models $V \subset W$ of $L$ such that $V$ is "far" from $L$ but $W$ is "not too far" from $V$?
In the following, whenever I say "$V_1$ is an outer model of $V_2$", I mean
$V_1, V_2$ are transitive models of $\mathsf{ZFC}$,
$V_2 \subset V_1$,and
$ORD^{V_1} = ORD^{V_2}$.
I am curious ...
- 236k
7
votes
0
answers
177
views
Is the positive fragment of second-order logic compact?
This is a crosspost of this question that I posted on the math stack exchange a year and a half ago.
There are two slightly different versions of compactness in the FOL setting:
If $\Delta$ is ...
- 20.5k
4
votes
1
answer
208
views
Generic absoluteness
In Theorem 14 of "On The Question Of Absolute Undecidability" Peter Koellner describes a generic absoluteness result which could be summed up as $\Sigma^2_1(\Gamma^\infty)$-generic ...
- 8,099
6
votes
1
answer
315
views
In HoTT with LEM, are sets and pointed sets the same thing?
The operations of adding and removing a point (where removing is a consideration of a subset of elements x such that $(x = *) \to 0$) implements the equivalence of these 1-types, as far as I can see. ...
- 989
6
votes
1
answer
318
views
Is univalence equivalent to every type function being a functor over equivalence?
Introduce a rule in type theory that if $\Gamma \vdash f : \text{Type} \to \text{Type}$ and $\Gamma \vdash e : A \simeq B$ then $\Gamma \vdash f[e] : f(A) \simeq f(B)$.
It may seem like such a rule is ...
- 48.8k
8
votes
2
answers
1k
views
Is there one binary operation foundational for set theory?
The membership relationship "$\in$" is foundational for set theory, in the sense that the axioms of any set theory are formulated in the language of "$\in$". Naturally, the ...
- 48.8k
110
votes
10
answers
26k
views
Set theories without "junk" theorems?
Clearly I first need to formally define what I mean by "junk" theorem. In the usual construction of natural numbers in set theory, a side-effect of that construction is that we get such theorems as $...
- 6,353
12
votes
0
answers
211
views
Are there times when replacement is "more natural" than collection?
There are a couple examples I'm aware of where choosing to axiomatize $\mathsf{ZF(C)}$ using collection instead of replacement results in a much nicer (or at least less surprising) picture:
Let $\...
- 20.5k
15
votes
1
answer
615
views
Changing the cofinality of a regular cardinal without collapsing any cardinals?
I have a short but hopefully interesting question on cardinal arithmetic and collapsing cardinals:
Is it possible to change the cofinality of a regular cardinal without collapsing any cardinals?
Is ...
- 1,799
5
votes
0
answers
230
views
Are there Dedekind-infinite amorphous sets?
An amorphous set is an infinite set (i.e. cannot be put into bijection with any finite set $\{ 1, \dots, n \}$ for any $n$) that cannot be partitioned into two mutually disjoint infinite subsets. ...
- 51
2
votes
0
answers
91
views
A recursive description of the smallest divisor-closed subsemigroup containing a set
Let $S$ be a semigroup and $\widehat{S}$ be its unitization, i.e., the monoid obtained from $S$ by adjoining an identity element if necessary (so that $\widehat{S} = S$ when $S$ is already a monoid).
...
- 10.5k
2
votes
0
answers
119
views
Adding partitions of one but not the other kind
Say that two partitions $(P_i)_{i\in I}, (Q_j)_{j\in J}$ are isomorphic iff there is a bijection $f: I\rightarrow J$ such that $\vert P_i\vert=\vert Q_{f(i)}\vert$ for all $i\in I$. (Note that in the ...
- 20.5k
7
votes
1
answer
433
views
How much choice is needed to prove the completeness of equational logic?
All the proofs of the completeness of (Birkhoff's) equational logic I have read seem to pick representatives for equivalence classes of terms and hence require the axiom of choice. Is AC (or a weak ...
- 48.8k
9
votes
2
answers
2k
views
Truth in a different universe of sets?
I understand that provability and truth as different concepts.
Provability is syntactic, it only concerns whether the given
sentence can be derived by reiterating the inference rules over a
collection ...
- 18.6k
48
votes
5
answers
7k
views
What axioms are used to prove Gödel's Incompleteness Theorems?
I understand Gödel's Incompleteness Theorems to be statements about effectively generated formal systems, which basically makes them theorems about algorithms. This is cool, because despite being ...
- 11.3k
1
vote
0
answers
63
views
Can the proper/whole domain relationship in bi-interpretations be reversed for non-synonymous theories?
Suppose we have theories $T$ and $H$ that are bi-interpretable, now suppose that the relevant interpretations achieving that bi-interpretability are: $\tau: T \to H$, and $\pi: H \to T$. Now suppose ...
- 11.3k
0
votes
0
answers
135
views
Provability predicates
We know that there are provability predicates, that is, predicates derived from the recursive relation "x is a demonstration of y", with which Godel's second incompleteness theorem would not ...
- 265
3
votes
1
answer
304
views
When does $\Pi_2$-reflection on $X$ fail to imply iterated $\Pi_1$-reflection on $X$?
Let lowercase Greek letters denote ordinals. Recall from Richter and Aczel's "Inductive definitions and reflecting properties of admissible ordinals", for a set of formulae $\Gamma$ and a ...
- 3,065
11
votes
2
answers
817
views
Undefinable inner model
What are some examples of a pair $M\subseteq N$ of transitive set models of $\mathsf{ZFC}$ with the same ordinals, such that $M$ is not a definable class (with parameters) in $N$? Is it possible that $...
- 236k
13
votes
3
answers
978
views
Model Structure/Homotopy Pushouts in topological monoids?
Let $\mathsf C$ be the category of topological monoids, that is, the category of monoids in $(\textsf{Top}, \times)$.
Can the model category structure on $\textsf{Top}$ (Serre fibrations, ...
- 4,713
3
votes
1
answer
171
views
Every homomorphism between (rational) Puiseux monoids is multiplication by a non-negative rational
Let a (rational) Puiseux monoid be a non-trivial submonoid of the non-negative rational numbers under (the usual operation of) addition. It is not difficult to show that, if $f \colon H \to K$ is a (...
- 38.6k
4
votes
1
answer
515
views
Truth Values of Statements in non-standard models
Excuse me, if the question sounds too naive.
Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...
- 2,167
0
votes
1
answer
222
views
Is it consistent that $2^{(\cdot)}$ is "surjective" on the class of uncountable ordinals?
$\newcommand{\Z}{{\sf (ZFC)}}$
It is consistent in $\Z$ that there is an uncountable cardinal $\kappa$ such that for no cardinal $\lambda$ we have $2^\lambda = \kappa$: Take any model in which $2^{\...
- 32.2k
11
votes
1
answer
756
views
On the classification of second-countable Stone spaces
Let $X$ be a Stone space (i.e. totally disconnected compact Hausdorff). Then the following are equivalent:
$X$ is second countable
$X$ is metrizable
$X$ has countably many clopen subsets
$X$ is an ...
- 35.5k
2
votes
0
answers
145
views
Is it consistent to have these kinds of acyclic hereditarily size sets?
Working in $\sf ZFC-Reg. {}+ Acyclicity$. Where :
Acyclicity: $\neg \exists x_1, \cdots, \exists x_n: x_1 \in x_2 \in\cdots\in x_n \in x_1$
We add the following kind of weird non-well founded sets.
$\...
- 11.3k
3
votes
0
answers
143
views
Lindström's theorem part 2 for non-relativizing logics
By "logic" I mean the definition gotten by removing the relativization property from "regular logic" — see e.g. Ebbinghaus/Flum/Thomas — and adding the condition that for every ...
- 20.5k
3
votes
2
answers
990
views
Theory interpreted in non-set domain of discourse may be consistent?
Following the blow. I will try to ask question in order to check if I well understand what was pointed. I decide to ask another question, because mathoverflow is not projected to be good environment ...
- 1,446
3
votes
1
answer
310
views
When is an upper bound on the longest irreducible program outputting something computable?
Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program is irreducible if no subsequence of it has the ...
- 3,319
4
votes
1
answer
161
views
Which of the known variants of Replacement can survive DeExtensionality?
Starting with $\sf ZF$. If we replace the power set axiom by the axiom stating that for any set $A$ there exists a set $x$ such that for every $y \subseteq A$ we have a set $y' \in x$ such that $\...
- 11.3k
3
votes
0
answers
95
views
What does the computation of irrationality and transcendentality via a fancy implementation of analytic Markov's property look like?
Proofs that various real numbers are not rational or not algebraic tend to be constructively valid as is. Examples include the proofs that $\sqrt 2$ and $\log_2(3)$ are not rational and that $e$ is ...
- 6,353
6
votes
1
answer
267
views
Borel / Wadge hierarchies on subsets closed under prepending a finite prefix
I'm interested in subsets $X$ of the Cantor space ($2^\omega$) or the Baire space ($\omega^\omega$) that are closed under prepending an arbitrary finite prefix:
$$
(x_1, x_2, \dots) \in X \implies (...
CommunityBot
- 1
14
votes
1
answer
520
views
Is there a theory between HA and PA that doesn't have Markov's rule?
A theory $T$ admits Markov's rule when
For every formula $\phi(n)$, if $$T \vdash \forall n \in \mathbb N. \phi(n) \lor \lnot \phi(n)$$ and $$T \vdash \lnot \lnot \exists n \in \mathbb N. \phi(n)$$ ...
- 47.4k
18
votes
1
answer
829
views
Convergence rate of Fagin's 0-1 law for first-order properties of random graphs
Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the ...
- 47.4k
3
votes
0
answers
181
views
Are all "reasonable" Gödel encodings isomorphic in some sense?
It is clear that many different Gödel numberings can work in Gödel's proof. Yet for the proof one just needs a few properties of how the numberings of related sentences are related, and I'm wondering ...
- 3,230
13
votes
1
answer
943
views
Cantor-Bernstein with "weakly injective" functions
Let us call a map $f: X \to Y$ between non-empty sets a "weak injection" if $f^{-1}(\{y\})\subseteq X$ is finite for every $y \in Y$.
Recall that the (Schroeder-)Cantor-Bernstein-Theorem (...
CommunityBot
- 1
-1
votes
1
answer
750
views
Is theory with domain of interpretation in second order objects a First Order Theory?
Thank everybody for answering my previous questions: first, and second.
Here I would like to ask about some important thing which I do not understand clearly.
Is it necessary for theory to have given ...
- 1,446
5
votes
2
answers
433
views
Models of second-order arithmetic closed under relative constructibility
I know little to nothing about second-order arithmetic and its subsystems. However, I would like to understand when a model of (a subsystem of) second-order arithmetic ($\mathsf{Z}_2$) is downward ...
- 20.5k
6
votes
0
answers
182
views
Iterated $\Pi^1_1$-reflection and non-Gandiness underrepresented in ordinal analyses?
This is a copy of Math StackExchange question #4395977, which I felt was more appropriate for MathOverflow.
Note on terminology: "admissible", "$(^+)$-stable", and "$\Pi^1_1$-...
- 2,031
1
vote
0
answers
73
views
EF-games with scrambling
This question is motivated both by the notion of zero-knowledge proofs and by general curiosity about versions of the infinitely-long Ehrenfeucht-Fraisse game which don't trivialize (= Duplicator win ...
- 20.5k
9
votes
3
answers
602
views
Admissibility of Harrop's rule, computationally
It is obvious that the following formula is not a theorem of
intuitionistic propositional calculus (IPC).
$$
(\neg A \; \to \; B \vee C) \;\; \to \;\;
((\neg A \; \to \; B) \vee (\neg A \; \to \; ...
- 6,353
5
votes
0
answers
191
views
Reference-Request: Had this replacement principle been investigated before?
Replacement$^*$: If $\varphi$ is a formula with at least two variables occuring free, in which $``x,y"$ do not occur free, then:
$$\forall a \forall b \forall c \forall d \ ( \varphi(a,b) \land \...
- 11.3k
2
votes
0
answers
97
views
Which of these non-well founded set theories is synonymous with ZFC?
Lets add a constant $\mathcal A$ to the language of $\sf ZFC$.
Let "Foundation$_{\mathcal A}$" denote the following sentence:
$$ \forall x: \forall y \in x \exists z \in y \cap x \to \exists ...
- 11.3k
2
votes
0
answers
144
views
The strongest reflection principle that does not violate covering lemmas
#-generated reflection, or Indiscernible-generation, is considered to be the strongest reflection principle that does not violate the covering lemma in L. [1]
Is there a way to extend this success to ...
- 6,367
1
vote
0
answers
182
views
Can this Mereological system be synonymous with $\sf ZF(C)$?
This question is about synonymy of $\sf ZFC$ set theory with the following Mereological theory:
Language: first order logic with equality. Extra-logical primitives: $\subseteq$ standing for the binary ...
- 11.3k
6
votes
0
answers
109
views
Is PA interpretable in PRA + TI(<epsilon_0)?
By Gentzen's consistency proof, we know that PA has the same consistency strength as PRA + TI(<epsilon_0). Question: is PA interpretable in PRA + TI(<epsilon_0)?
For simplicity, let us assume ...
1
vote
1
answer
213
views
Minimal models in strong set theories - pt. 2
This is a follow-up to this question.
So, as Noah elucidated (thanks Noah!), whenever $T$ is r.e., $M(T) < \sigma$ ($\sigma$ is the least stable ordinal, i.e. $L_\sigma\prec_{\Sigma_1}L$).
In ...
- 2,031
32
votes
11
answers
11k
views
Is PA consistent? do we know it?
1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please).
2) There are proofs (...
- 2,031