All Questions
6,026 questions
0
votes
0
answers
179
views
the (indirect) deduction theorem
$\DeclareMathOperator\Cn{Cn}\DeclareMathOperator\Sb{Sb}$I would like to ask about the Deduction Theorem for an inconsistent system. This is a very well-known fact that for the classical propositional ...
- 19
7
votes
1
answer
556
views
Does this ZFC+V=L like theory, have a limit on large cardinal properties?
Let $\sf T$ be a theory that has as axioms every axiom of $\sf ZFC$, and every theorem of $\sf ZFC + [V=L]$ that is neither provable nor disprovable by $\sf ZFC$, whose addition or addition of its ...
- 11.3k
7
votes
1
answer
716
views
What is the flaw in Cooper's argument?
Lately I have been studying in the subject of degree theory, specifically definability results related to $\mathcal{D}$. A famous conjecture in the field due to Slaman and Woodin is that the only ...
- 893
4
votes
1
answer
154
views
Minimal dominating sets in thin hypergraphs
Let $H=(V,E)$ be a hypergraph. We say that $H$ is thin if for every $v\in V$ the set $E_v=\{e\in E:v\in e\}$ is finite.
A subset $D\subseteq V$ is dominating if
$\bigcup \{e\in E:e\cap D \neq \...
- 48.9k
1
vote
0
answers
75
views
How many constant symbols can a set of intuitionistic formulas have for completeness to hold?
Fitting proves a version of the completeness theorem for intuitionistic FOL in his book on intuitionistic model theory and forcing.
Let $U$ be any set of formulas without parameters (i.e. constant ...
- 139
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
4
votes
0
answers
103
views
Unstable structures with unstable $\aleph_0$-categorical reducts
Suppose $M$ is a first-order structure which is unstable. If necessary, assume it is $\aleph_0$-saturated (or more, but I don't think it matters beyond that).
Are there any interesting criteria for ...
- 1,338
3
votes
0
answers
97
views
Can the differential field of d.c.e. reals be nicely construed as a field of functions?
This question is basically a special case of this older question of mine, which is still unanswered.
Let $\mathcal{D}$ be the field of d.c.e. reals; these turn out to be exactly the reals $\alpha$ for ...
- 20.9k
4
votes
1
answer
238
views
AD and simultaneous well-orderability principle
Is the axiom of determinacy (AD) consistent with the following choice principle, and if yes, does it hold in $L(ℝ)$ under AD:
Simultaneous well-orderability: For every function $f:P(Ord)→\text{...
- 7,545
3
votes
2
answers
390
views
Can there exists a model of ZFC with permutation that sends successor infinite stages to their predecessors?
Can there exist a model $M$ of $\sf ZFC$ and an external permutation $j$ on $M$ such that $j[(V_{\alpha+1})^M]=(V_\alpha)^M$ for each infinite $\alpha$?
- 11.3k
3
votes
0
answers
76
views
Why does the following test for protoalgebraicity work?
Remark. Crossposted from Math SE due to lack of responses.
The following text appears in Janusz Czelakowski's "Protoalgebraic Logics":
Suppose there exists a class $\mathbf{K}$ of matrices ...
- 31
14
votes
1
answer
642
views
Example of a forcing notion with finite-predecessor condition that does not add reals
This question seems very basic but I cannot seem to find any literature on it.
Let $\mathbb{P}$ be a forcing notion. If $p$ is a condition of $\mathbb{P}$, define the predecessor set of $p$ to be $$\{...
- 1,328
7
votes
0
answers
166
views
Examples of finitary problems/theorems of high logical complexity? [duplicate]
Generally, number theoretic conjectures which are well-known and easy to explain are either obviously $\Pi^0_1$ or $\Pi^0_2$, which is to say, their truth can be decided by a single membership query ...
- 1,452
-3
votes
1
answer
117
views
Can stratification be used to internalize functions on models of $\sf Z$?
Suppose $M$ is a model of $\sf Z +\neg AC$ that is externally bijective to an element $k \in M$. Obviously if $j$ denotes such an external bijection, then it cannot be used in Separation within $M$, ...
- 11.3k
-1
votes
1
answer
141
views
Can stratification be used to internalize external functions inside models of $\sf ZF$?
Suppose $M$ is a model of $\sf ZF+\neg AC$ that is externally bijective to an element $k \in M$. Obviously if $j$ denotes such an external bijection, then it cannot be used in Separation and ...
- 11.3k
3
votes
0
answers
183
views
Can we have a theory that interpret $\sf ZFC$, proves existence of an infinite set, and yet prove all of its sets being Dedekind finite?
If we start with axioms of $\sf ZF$ replace the axiom of Infinity with an axiom stating the existence of a set that doesn't have an injection to a von Neumann natural, and replace the axiom of Power ...
- 11.3k
7
votes
0
answers
196
views
Infinite cardinals and learnability of probability distributions
Two players play as follows. Player one chooses a secret finitely supported probability distribution $P$ on $ω_k$ (or another known set with $\aleph_k$ elements), and randomly takes $n+1$ samples ...
- 7,545
3
votes
0
answers
89
views
Ordering the elements of a semigroup by $a \le b$ iff $a=b$ or $b=ab=ba$
Let $S$ be a semigroup, written multiplicatively. The binary relation $\le$ on (the underlying set of) $S$, whose graph consists of all pairs $(a,b) \in S \times S$ such that $a = b$ or $b = ab = ba$, ...
- 10.5k
10
votes
1
answer
499
views
What is the least $\alpha$ such that $L_\alpha$ contains a non-measurable set
What is the least level of the constructable hierarchy that contains a non-measurable (Lebesgue) subset of $2^\omega$. If it makes a difference assume we are working inside L (V=L).
I'm pretty sure it ...
- 3,029
4
votes
1
answer
186
views
Logical relationship between supercompact and rank-into-rank cardinals
It is well known that the large cardinals are ordered by logical consistency. In many cases, the logical consistency is, in fact, a direct implication - for example, Mahlo $\Rightarrow$ Inaccessible ...
- 463
3
votes
1
answer
161
views
Stone-Čech compactification of a Boolean subalgebra of $\{0,1\}^S$
Setup: Let $S$ be a set. Let $B$ be a Boolean subalgebra of $\{0,1\}^S$; i.e., just to be clear $B$ contains the constant $0$ and $1$ functions, and is stable under binary pointwise $\land$, $\lor$ ...
- 32.5k
3
votes
0
answers
130
views
Is Quine's Mathematical Logic "ML" consistent with Azcel's Extensionality?
Now that Holmes had proven the consistency of adding Extensionality to Stratified Comprehension (i.e. $\sf NF$), a question along the same vein presents itself:
Is Aczel's Extensionality axiom ...
- 11.3k
1
vote
0
answers
122
views
How could I formally express: System F cannot express universal quantification over things that are not types? [closed]
I'm trying to understand exactly why it is that https://ncatlab.org/nlab/show/computational+trilogy states that quantification requires dependent types, and why this wouldn't be possible to achieve ...
- 113
9
votes
1
answer
366
views
Can the canonical Eudoxus-real representatives be defined easily?
(See e.g. here for background on the Eudoxus reals, which motivates this question.)
Let $\mathcal{Z}=(\mathbb{Z};+,<)$. Say that a Eudoxus function is an $f:\mathbb{Z}\rightarrow\mathbb{Z}$ such ...
- 20.9k
9
votes
0
answers
274
views
Has a computer search for inconsistency of large cardinals been carried out before?
In discussion about the consistency of large cardinals, a justification which occasionally appears is that despite years of work, no inconsistency has currently been discovered. For example, here are ...
- 2,031
1
vote
0
answers
71
views
Can we have partitions on powersets of infinite cardinals that preserve natural arithmetical operators?
There exists an infinite cardinal $\zeta$ such that there exists a set $P$ such that $P$ is a partition on $\mathcal P(\zeta) \setminus \{\varnothing\}$ such that each element $h$ of $P$ is an ...
- 11.3k
2
votes
1
answer
150
views
Weakly compact characterization
In Theorem 9.26 of Jech, it is shown that if $\kappa$ is inaccessible and has the tree property, then $\kappa \rightarrow (\kappa)^2_\lambda$ for every $\lambda<\kappa$. Jech remarks after the ...
- 41
6
votes
0
answers
120
views
Is there a syntactic proof that first-order positive inductive definitions are conservative?
Every first-order positive inductive definition has a fixed point. It follows that, if the biconditional is thought of as an axiom in the language obtained from the background language by adding a new ...
- 61
16
votes
0
answers
218
views
If a map between unital rings preserves multiplication and successor, does it preserve addition?
Welcome to my first MathOverflow posting!
This is a question about rings, all of them assumed to be both unital and associative.
Let $f\colon R\to S$ be a map between rings such that $f(xy)=f(x)f(y)$ ...
- 161
20
votes
1
answer
557
views
Almost orthogonal maps $f:\omega \to \{-1,1\}$
Let $\omega$ denote the set of non-negative integers. For sets $A,B$, let $B^A$ denote the set of maps $f:A\to B$. For $f,g\in\{-1,1\}^\omega$ we say that $f,g$ are almost orthogonal if there is $C_0\...
- 48.9k
11
votes
3
answers
779
views
Is every recursively axiomatizable and consistent theory interpretable in the true arithmetic (TA)?
I am looking for a scholarly text that discusses this issue in detail.
- 307
-2
votes
1
answer
181
views
What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]
As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
- 3,094
20
votes
1
answer
694
views
Is the theory of ordinals in Cantor normal form with just addition decidable?
This seems like it should be a pretty well-studied question but I can't seem to find an easy answer:
Is the theory $(\varepsilon_0, +, \omega^{\ \cdot}, 0, 1)$ decidable?
From Is the theory of $(\...
- 1,452
4
votes
0
answers
261
views
Läuchli's "intermediate thing"
On page 230 of An abstract notion of realizability ..., Läuchli writes the following:
If we drop the restrictions put on $\Theta$, then we get classical logic in one case and an intermediate thing in ...
- 20.9k
3
votes
1
answer
199
views
Mutually equal Hamming distance of members of ${\cal P}(\mathbb{N})$
This is inspired by an older, as of yet unanswered question.
If $X$ is a set and $A,B\subseteq X$, we let the Hamming distance of $A, B$ be defined as $d_H:=\text{card}\big((A\setminus B)\cup (B\...
- 48.9k
0
votes
0
answers
114
views
Clarifications sought on the paper on the semigroup associated with a free polynomial by Ali Abbas and Abdallah Assi
I have three questions regarding the proof of Proposition 4 on page 4 of this paper here. For those interested in addressing these questions, please refer to some definitions in the first two or three ...
8
votes
1
answer
280
views
What is the consistency strength of "Singular worldly that is inaccessible in an inner model"?
In short, what can we say about the consistency strength of "$\kappa$ is a singular worldly and inaccessible in an inner model"?
Clearly, $0^\#$ exists since we have a singular cardinal ...
- 39.8k
3
votes
0
answers
211
views
Intuitionistic set-theoretic geology
Work in ZF, if there are proper class many supercompact cardinals, then all grounds are uniformly definable. Hence under reasonable assumption, we can have choiceless set-theoretic geology.
But can we ...
- 695
1
vote
1
answer
308
views
Is reflection on Grothendieck universes equivalent to TG set theory?
Let take the first order set theory whose axioms are Extensionality, Separation and Universal reflection.
By $\operatorname {unv}(x)$, denoting "$x$ is a universe", we'll take it to mean ...
- 11.3k
13
votes
1
answer
933
views
Consistency strength of HoTT
What is the consistency strength of Homotopy type theory (HoTT) relative to various set theories (e.g., are there any known set theories that it can interpret)? Does this question even make sense?
- 4,985
3
votes
0
answers
161
views
On generators of the multiplicative semigroup $\{r\in\mathbb Q:\ r>1\}$
The set $M=\{r\in\mathbb Q:\ r>1\}$ is a commutative semigroup with respect to the multiplication. For any integers $a>b\ge1$, we clearly have
$$\frac ab=\prod_{n=b}^{a-1}\frac{n+1}n.$$
So the ...
- 15.6k
3
votes
0
answers
92
views
Reference for the monoidal category structure $X \otimes Y = X + Y + X \times Y$ on a distributive category
Given a distributive category $\mathscr C$ (more generally a rig category), we can define a (semicocartesian) monoidal category structure on $\mathscr C$ with tensor product given by $X \otimes Y := X ...
- 10.7k
15
votes
0
answers
244
views
Natural examples of Borel surjections without right inverse
As discussed in this question, in general a Borel surjection $f:\mathbb{R}\rightarrow\mathbb{R}$ may not have a Borel right inverse, namely a $g$ such that $f\circ g=id$, although there is always a ...
- 623
4
votes
0
answers
143
views
Part II to Ketonen's "Set Theory for a Small Universe I. The Paris-Harrington Axiom"
There is an unpublished manuscript "Set Theory for a Small Universe I. The Paris-Harrington Axiom" by Ketonen which appeared early in the study of the Paris-Harrington theorem, around 1979. ...
- 2,031
8
votes
0
answers
157
views
How to define Dedekind reals and Eudoxus reals such that they are equivalent to unmodulated Cauchy reals
In constructive mathematics without choice, we have three different versions of the real numbers (each embedding into the next).
Regular Cauchy reals (functions $f : \mathbb N \to \mathbb Q$ such ...
- 6,353
6
votes
1
answer
197
views
Is there a 1-generic degree g such that Th(D(< g)) is more complicated than true arithmetic?
I am currently reading an article titled "Embedding and Coding Below a 1-Generic Degree" by Greenberg and Montalbán(link to a free source:https://pi.math.cornell.edu/~erlkonig/Papers/...
- 893
5
votes
1
answer
167
views
Cardinality of separating families on an infinite cardinal $\kappa$
Let $\kappa$ be an infinite cardinal. We say ${\cal S}\subseteq {\cal P}(\kappa)$ is separating if whenever $a\neq b\in \kappa$ there is $T\in {\cal S}$ such that $|T\cap\{a,b\}| = 1$. Let $\...
- 48.9k
4
votes
1
answer
394
views
How many variations can be derived from Gödel's fixed-point lemma?
Recently, I attempted to generalize the fixed-point lemma and proved the following:
Let $ F_n $ be the set of all formulas with $ n $ free variables in $L_{PA}$.
Let us define the unary function $ f $ ...
- 127
2
votes
0
answers
142
views
Can a path in Kleene's $\mathcal{O}$ enumerate all of the computable reals via uniform diagonalization?
It's a well-known fact that there are computable diagonalization functions on Baire space $\mathbb{B} = \mathbb{N}^\mathbb{N}$ (i.e., functions which take a sequence $(r_i)_{i\in \mathbb{N}}$ of ...
- 12.5k
2
votes
0
answers
100
views
Realizing arithmetic hierarchy in algebraic number theory
Is it possible to realize arithmetic hierarchy in algebraic number theory?
For example, consider a $\Pi^0_4$ statement of the form $\forall x \exists y \forall z \exists w \phi(x,y,z,w)=0$ where $\phi$...
- 593