All Questions
1,458 questions with no upvoted or accepted answers
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
3
votes
0
answers
99
views
Counting Eilenberg/Schutzenberger-type definitions of pseudovarieties
See Eilenberg/Schutzenberger, On pseudovarieties for background on pseudovarieties. I've phrased things in terms of pairs-of-sets to avoid some annoying language about multisets. Also, I'm aware that ...
- 20.5k
3
votes
0
answers
115
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.5k
3
votes
0
answers
171
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
3
votes
0
answers
154
views
How the cardinalities of $\mathcal H^*_x$ and $\mathcal P(x)$ compare?
Working in $\sf ZF$, regarding an arbitrary Dedekind infinite set $x$, what's the relationship between the cardinality of $\mathcal P(x)$ and $\mathcal H^*_x$? The latter is the set of all sets ...
- 11.3k
3
votes
0
answers
133
views
Comparing two fragments of SOL with the downward Lowenheim-Skolem property
For $S$ a set of (parameter-free) second-order formulas and $\mathfrak{A},\mathfrak{B}$ structures, write $\mathfrak{A}\trianglelefteq^S\mathfrak{B}$ iff $\mathfrak{A}$ is a substructure of $\mathfrak{...
- 20.5k
3
votes
0
answers
164
views
Can we have an inverted iterative hierarchy?
Let stratified $\sf Z$ have all axioms of $\sf Z$-$\sf Reg.$ with Infinity stipulated by existence of a Dedekind infinite set, and with Separation restricted to use only stratified formulas, where ...
- 11.3k
3
votes
0
answers
212
views
Periodicity in the cumulative hierarchy
Under Reinhardt cardinals in ZF, the cumulative hierarchy exhibits a periodicity in that for large enough $λ$, certain properties of $V_λ$ depend on whether $λ$ is even vs odd. See Periodicity in the ...
- 7,545
3
votes
0
answers
200
views
Weak extender models for supercompactness without choice
Assume ZFC and a supercompact cardinal $κ$. Is it consistent that there is a weak extender model $N⊨\text{ZF}$ for supercompactness of $κ$ such that the axiom of choice and well-ordering of $P_κ(λ)^N$...
- 7,545
3
votes
0
answers
255
views
Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?
If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not.
But ...
- 31
3
votes
0
answers
209
views
Homotopy type theory for semantics
It looks like I have been building up a theory that might require looking closely at Homotopy Type Theory vs. Category Theory with respect to semantics. I am considering two types of semantics that ...
- 1,313
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
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
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
0
answers
125
views
Positive boolean satisfiability problem : finding minimal solutions
Consider, over a finite set of boolean variables $X$, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals.
For every assignment of the variables which ...
3
votes
0
answers
186
views
In constructive set theory, is it consistent for there to be a ring that models smooth infinitesimal analysis?
In a constructive set theory such as CZF, it is consistent to assume that every function $f : \mathbb R \to \mathbb R$ is continuous. However, it is not consistent to assume that every such function ...
- 6,353
3
votes
0
answers
54
views
A new(?) kind of 2-adjunction for relating cartesian closed functors using dinatural hexagons
$\newcommand{\A}{\operatorname{A}}
\newcommand{\B}{\operatorname{B}}
\newcommand{\Cat}{\mathcal{Cat}}
\newcommand{\Cart}{\mathcal{Cart}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\F}{\operatorname{F}}
\...
3
votes
0
answers
75
views
Are the automorphisms of the power semigroup of a cancellative semigroup cardinality-preserving?
Let $S$ be a semigroup (written multiplicatively) and $f$ be an automorphism of the power semigroup $\mathcal P(S)$ of $S$, that is, a bijective function on the family of all non-empty subsets of $S$ ...
- 10.5k
3
votes
0
answers
203
views
Reverse-mathematical strength of Banach-Tarski
What is the reverse mathematical strength of the Banach-Tarski paradox?
The usual proof of Banach-Tarski should carry out in $\mathrm{ZF}+\mathrm{AC}_\kappa$, where $\kappa$ is the supremum of the ...
- 2,031
3
votes
0
answers
176
views
Can the set of parafinite congruences be descriptive-set-theoretically complicated?
Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...
- 20.5k
3
votes
0
answers
103
views
An isomorphism problem for semigroups of ideals
An ideal of a semigroup $S$ (written multiplicatively) is a set $I \subseteq S$ such that $IS$ and $SI$ are both contained in $I$ (here, $XY$ means, for all $X, Y \subseteq S$, the setwise product of $...
- 10.5k
3
votes
0
answers
148
views
Can well-ordering of the universe due to global choice survive extensive failure of Extensionality?
That axiom of global choice leads to the well-ordering of the universe given the other axioms of Zermelo set theory is a famous result.
Now, if we weaken the power set axiom to the axiom stating that ...
- 11.3k
3
votes
0
answers
206
views
Independence and truth in PA
By $\textbf{PA}$ I will mean the usual first-order Peano Arithmetic. I will denote an element of $\mathbb{N}$ by $n$, and by $[n]$ I will denote the corresponding term in the language of $\textbf{PA}$:...
- 3,318
3
votes
0
answers
99
views
Comparing computable structures via Kleene and Skolem
Below, by "structure" I mean "computable structure in a finite language with domain $\omega$," and by "sentence" I mean "finitary first-order sentence containing no ...
- 20.5k
3
votes
0
answers
240
views
The most powerful inner model and a $\Delta^2_1$ well-ordering of the reals
With the current research, it seems that we are in a position to get extremely powerful absoluteness theorems (like $\Sigma^2_0$-absoluteness, $\Sigma^2_1$-absoluteness, $\Sigma^2_2$, $\diamondsuit_G$,...
- 695
3
votes
0
answers
119
views
Is it consistent to have an infinite antitone sequence of elementary embeddings such that the involved models include iterated sharps?
$\DeclareMathOperator\crit{crit}$Background essays (the material I've tried to understand in leading up to this question):
Daghighi, et. al. [2014], "The foundation axiom and elementary self-...
3
votes
0
answers
176
views
The monoid of stably-free modules over integral group rings
Fix a torsion-free group G, let $M_G$ be the monoid of stably-free $\mathbb{Z}G$-modules under operation $\oplus$, the direct sum of modules.
In studying objects related to Wall’s D2 problem on CW-...
- 187
3
votes
0
answers
90
views
Realizing continuum many types and omitting one
I have a theory with finitely many relations, and would like to find a model of it with continuum-many 1-types realized, and one 2-type omitted. Is there a version of the Omitting Types Theorem that ...
- 429
3
votes
0
answers
52
views
Closely related definitions with and without approximation built-in
Let us say that a (real) function class $A$ has 'approximation built-in' in case for every $f:\mathbb{R}\rightarrow\mathbb{R}$ in $A$ and any $x\in \mathbb{R}$, we can approximate $f(x)$ using only $f(...
- 4,359
3
votes
0
answers
127
views
A class of Kripke frames which preserves validity
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $1\leq s\leq n-2$, the frame $\mathcal{C}_n(s)$ denotes the frame which is ...
- 53
3
votes
0
answers
179
views
Lifting Wilkie's theorem from $\mathbb{N}$ to other structures
Let $\models,\models_2,\models_d$ be the satisfaction relations for first-order logic, second-order logic with full semantics, and second-order logic with set quantifiers ranging over definable-with-...
- 20.5k
3
votes
0
answers
72
views
What are all the order types of maximal chains of $\Delta^0_2$ sets?
A set of natural numbers is $\Delta^0_2$ if it’s computable from the halting set. Consider the quasi-order/pre-order of all $\Delta_0^2$ sets ordered by $m$-reduction, or equivalently consider the ...
- 4,597
3
votes
0
answers
223
views
Basic cardinal arithmetic without choice
Do we know everything about addition and multiplication of cardinalities in choiceless set theory?
For example, let $M$ be a model of $\textsf{ZF}+\textsf{AD}+V=L(\mathbb{R})$, consider the sets $\...
- 877
3
votes
0
answers
107
views
Logical strength of the pigeon-hole principle for measure spaces
In his book on measure theory, Tao discuss the pigeon-hole principle for measure spaces, which expresses that the union of measure zero sets is again measure zero.
I am interested in the logical ...
- 4,359
3
votes
0
answers
180
views
Are "very conservative" connectives already definable?
I'm sadly an outsider to nonclassical propositional logics. All terminology below comes from Humberstone's book The Connectives, specifically section 4.2.
A new connective - a bit more precisely, a ...
- 20.5k
3
votes
0
answers
283
views
What is the meaning and proof of Harvey Friedman’s ultrafinite incompleteness sentence?
On page 7 of his paper “Adventures in Incompleteness”, Harvey Friedman states the following:
IN ANY LONG ENOUGH SEQUENCE $x_1,...,x_n$ FROM $\{1,2,3\}$, SOME $(x_i,...,x_{2i})$ IS A SUBSEQUENCE OF ...
- 4,597
3
votes
0
answers
133
views
Is there an ordered algebra analogue of the HSP theorem?
For an algebraic signature (= set of function symbols) $\Sigma$, say that an ordered $\Sigma$-algebra is a pair $\mathfrak{A}=(\mathcal{A};\le)$ where $\mathcal{A}$ is a $\Sigma$-algebra in the sense ...
- 20.5k
3
votes
0
answers
161
views
Making the powerset into a topological monoid
Every monoid $X$ induces a monoid structure $\circledast$ on $\mathcal{P}(X)$ via
$$U\circledast V := \{uv\ |\ u\in U,v\in V\}.$$
Moreover, a morphism of monoids $f\colon X\to Y$ induces a morphism of ...
- 11.8k
3
votes
0
answers
120
views
Does the "iterated definability" closure always fall short of standard (Boolean) infinitarization?
Given a (set-sized) logic $\mathcal{L}$, let $\mathcal{L}'$ be gotten from $\mathcal{L}$ by adding the ability to quantify over $\mathcal{L}$-definable relations. (I'm being a bit vague here, since e....
- 20.5k
3
votes
0
answers
77
views
Relation algebras and quantifier rank
I had originally posted the following questions on math stack exchange but feel they are better suited for mathoverflow (original post$-$updated & reorganized for clarity).
On the Wikipedia page ...
- 201
3
votes
0
answers
157
views
Systems of elementary embeddings
Recently I've been thinking about elementary embeddings, partition cardinals, etc. as part of my never-ending quest for understanding of consistency strength :p
I came up with this idea, called I* ...
- 704
3
votes
0
answers
91
views
Algebraic logical structure
Let $M=(W,R)$ be a Kripke frame, $A=(f_1,...,f_m)$ is a tuple of operations $f_i:W^{n_i}\to W$, and $\Phi=(\varphi_1,...,\varphi_m )$ is a tuple of first-order logic formulas in vocabulary $\sigma=\{=...
- 107
3
votes
0
answers
203
views
Which arxiv-category should computability theory be submitted to?
There are two categories on the arXiv that seem like a potential fit for computability research to me, although none of them explicitly lists it in the description. These would be:
cs.LO
Covers all ...
- 4,727
3
votes
0
answers
225
views
Has an uncomputable variant of the Cantor staircase ever been used in constructive logic?
An open problem in choiceless constructivism is to prove that if a function $f:\mathbb R \to \mathbb R$ is pointwise differentiable everywhere, with $f'=0$, then $f$ is constant. See In choiceless ...
- 4,943
3
votes
0
answers
233
views
Is $\sf ZFC + Classes$ finitely axiomatizable?
$\sf ZFC + Classes$ is a bi-sorted theory with lower cases standing for sets and upper cases for Classes; axioms include all $\sf ZFC - Extensionality$ axioms written in lower case, and the following ...
- 11.3k
3
votes
0
answers
152
views
Recursive axiomatizability over non-recursive base theory
This is a somewhat open-ended question — I’m curious whether there are any known results which are able to prove that one theory is not recursively axiomatizable over another, despite both having the ...
- 111
3
votes
0
answers
210
views
Weak Power Hypothesis with injections instead of bijections
Let $x,y$ be sets. We use the following notation:
$x\simeq y$ means that there is a bijection $\varphi:x\to y$, and
$x\leq y$ means that there is an injection $\iota:x\to y$.
The Weak Power ...
- 48.9k
3
votes
0
answers
110
views
What is the $E$-r.e. part of $L$?
See Sacks' paper $E$-recursive inuitions or his book for background on $E$-recursion. Throughout, work in $\mathsf{ZFC+V\not=L}$. I'll use $\varphi_e$ in place of $\{e\}$ for the $e$th partial $E$-...
- 20.5k
3
votes
0
answers
157
views
Closure of the inverse image under the projection map
Let $S$ be a subsemigroup of a semitopological semigroup $(T,+)$, let $e$ be an idempotent in $T\setminus S$ such that $e\in cl_T(S)$, let $\mathcal{E}$ be a subsemigroup of $S\times S$ such that $(e,...
- 85