All Questions
1,458 questions with no upvoted or accepted answers
6
votes
0
answers
117
views
Closedness of the partial order in complete Hausdorff semitopological semilattices
First some definitions.
A semilattice is a commutative semigroup consisting of idempotents (i.e., elements such that $xx=x$). A typical example of a semilattice is the unit interval endowed with the ...
- 42k
6
votes
0
answers
484
views
Infinite-time Turing machines and the formal Church's thesis
Infinite-time Turing machines are known to either halt or loop in countable time.
In the spirit of double-negation translation, is there a statement which is: classically equivalent to this; ...
- 3,612
6
votes
0
answers
134
views
weak square and tower forcing
Suppose $\delta$ is a Woodin cardinal and $\kappa < \delta$. If $G$ is generic for the stationary tower $\mathbb Q^\kappa_{<\delta}$, then there is an elementary embedding $j : V \to M \...
- 18.6k
6
votes
0
answers
81
views
Representing meet-semilattices with vector spaces of specified dimensions
Take $K$ to be a field and take $L$ to be a finite meet-semilattice. I'm interested in the set of functions $n: L \rightarrow \mathbb{Z}^{\ge 0}$ such that there is some function $V$ from $L$ to ...
6
votes
0
answers
148
views
Linear logic with storage preserving positives
Has anyone studied a version of linear logic in which the storage modality $!$ preserves the positive connectives and quantifiers $\otimes,\oplus,\exists$? That is, such that we have $!(A\otimes B) = ...
- 66.8k
6
votes
0
answers
170
views
Katetov ordering on ideals on $\omega$
Recall that a nonempty set ${\cal I}\subseteq {\cal P}(\omega)$ is a (set) ideal if
$B\in{\cal I}$ and $A\subseteq B$ imply $A\in{\cal I}$, and
$A,B \in {\cal I}$ implies $A\cup B\in {\cal I}$.
By $\...
- 48.9k
6
votes
0
answers
237
views
A specific model of Z
Short version: there is a natural, very "thin" (but probably not minimal) model of Zeremelo set theory; I'm curious what is known about it.
Zermelo set theory (= ZF without the Replacement scheme) is ...
- 20.5k
6
votes
0
answers
406
views
Mildly destroying all worldly cardinals below an inaccessible by forcing
We call a cardinal $\theta$ worldly if $V_\theta \models \mathsf{ZFC}$. If $\kappa$ is an inaccessible cardinal, then we have an unbounded set of worldly cardinals below $\kappa$, in fact even a club ...
- 325
6
votes
0
answers
132
views
Recursive enumeration of totally categorical structures
A theorem of Hrushovski [1] says that every totally categorical theory admits a finite axiomatization which may include certain "infinity axioms", called a quasi-finite axiomatization. In particular, ...
- 618
6
votes
0
answers
554
views
Is this property a new large cardinal notion?
Given a cardinal $\kappa$, $\kappa$-complete lattices are lattices that have joins and meets of less than $\kappa$ elements (in particular they are bounded). In what follows we shall restrict to the ...
- 5,902
6
votes
0
answers
176
views
Breaking determinacy with forcing, and then fixing it
While forcing is usually presented over models of ZFC, it works equally well over models of ZF (or even less). However, the general theory of forcing becomes much stranger (much like the general ...
- 20.5k
6
votes
0
answers
215
views
Matrix semigroups in which a weighted average of eigenvalues is multiplicative
A problem in fractal geometry requires me to consider matrix semigroups with the following curious property. For a $d \times d$ real matrix $A$ let $\lambda_1(A) \geq \lambda_2(A) \geq \cdots \geq \...
- 6,206
6
votes
0
answers
223
views
Compactness beyond extendibility
By a result of Magidor, $\kappa$ is extendible if and only if the infinitary $n$th-order logic over the language $L_{\kappa,\kappa}$ is compact for every $n < \omega$, where by compact, we mean ...
- 490
6
votes
0
answers
294
views
Laurent and power series over the field with one element?
Question. Is there a suitable notion of the Laurent series ring $\mathbb{F}_1((t))$ and power series ring $\mathbb{F}_1[[t]]$ in some framework for the field with one element $\mathbb{F}_1$?
For ...
user1437
6
votes
0
answers
311
views
Reference for "if the set $A$ is Suslin, then every $\Sigma^1_1(A)$ set is Suslin"
Does anyone know of a reference for one or both of the following facts (in $\mathsf{ZF}$)?
If the set of reals $A$ is Suslin, then every $\Sigma^1_1(A)$ set of reals is Suslin.
If $T$ is a tree on $\...
- 5,471
6
votes
0
answers
404
views
$\infty$-Borel Determinacy?
An $\infty$-Borel set is a set $X\subseteq\mathbb{R}$ which has an $\infty$-Borel code - a set $r$ coding the construction of $X$ via open sets, complementation, and well-ordered unions (see http://en....
- 20.5k
6
votes
0
answers
572
views
Computing the pro-solvable closure of a finitely generated subgroup of a free group
The pro-solvable topology on a group $G$ is the unique group topology such that the set of normal subgroups $N\lhd G$ with $G/N$ a finite solvable group is a fundamental system of neighborhoods of the ...
- 38.6k
6
votes
0
answers
261
views
Stability of analytic Zariski structures
Noetherian Zariski structures are introduced by Hrushovski and Zilber(1996).
An analytic Zariski structure is a generalization of Noetherian Zariski structures, introduced by Zilber and Peatfield.
...
- 1,872
6
votes
0
answers
382
views
Saturated Ehrenfeucht-Mostowski models
Inspired by this question on MSE I tried to prove the following:
Let $T$ be a complete theory in a first order language and $\kappa$ a cardinal. If $T$ is $\kappa$-stable, then there exists a $\...
6
votes
0
answers
613
views
A question about Paraconsistent Set Theory and the Continuum Hypothesis
In question No.134351 it is asserted that there exists a Paraconsistent Set Theory in which the
Continuum Hypothesis (CH) is disproved. I would like to know more about this theory, which I will
call ...
- 6,215
6
votes
0
answers
248
views
$\omega$-models of $\mathbf{\Sigma^1_1}-DC$ and $\mathbf{\Delta^1_1}-CA$
So what is needed to demonstrate something (say like $L_{\omega_1^{CK}}[a]$ is a $\omega$-models of $\mathbf{\Sigma^1_1}$-$DC$ or $\mathbf{\Delta^1_1}$-$CA$? It's not like I don't understand what the ...
- 3,029
6
votes
0
answers
587
views
How to prove a $\Pi_2$ statement properly?
Consider the following situation. In a parallel world (let's hope not in this one),
in 2020 a clever guy proved $P\neq NP$ in a theory $T_1=\{ZFC+some\, reasonable\, new\, axioms\}$.
Then, in 2021 a ...
- 6,891
6
votes
0
answers
619
views
Duality between conjugacy classes and irreducible characters for finite monoids?
Qiaochu's answer to this question suggests that the proper way to view the bijection between conjugacy classes and irreducible complex representations of a finite group is via a duality. My question ...
- 38.6k
6
votes
0
answers
340
views
Free CCC or topos on a cartesian category
$\def\sC{\mathcal{C}}\def\sD{\mathcal{D}}\def\Set{\mathbf{\mathrm{Set}}}\DeclareMathOperator{\Sub}{Sub}\def\op{\circ}$I have a Cartesian category $\sC$. I would like to embed $\sC$ into a cartesian ...
user13113
6
votes
0
answers
300
views
What are these sets in Freyd's model?
Recall Freyd's model of $ZF +\neg AC$ (as recounted in MacLane and Moerdijk's book Sheaves in Geometry and Logic): it arises as the Fourman interpretation of the topos of sheaves on a particular ...
- 35.5k
6
votes
0
answers
516
views
Are advanced number-theoretic techniques related to undecidability?
Is there any evidence for or against the idea that some of the important statements of number theory that have only been proved using infinite sets, are in fact undecidable in Peano arithmetic?
Most ...
- 149k
6
votes
1
answer
368
views
Time functions of non-deterministic Turing machines
Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$. The smallest ...
user6976
5
votes
0
answers
67
views
Definable pseudo-standard predicates in Internal Set Theory
Consider the usual language $\mathcal{L}=(\in, \mathrm{st})$ of Nelson's Internal Set Theory, and a unary $\mathcal{L}$-predicate $P$. For an $\mathcal{L}$-formula $\varphi$, let $\varphi^P$ denote ...
- 756
5
votes
0
answers
159
views
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
In his wonderfully titled paper Can you take Solovay's inaccessible away? Shelah showed that if every $\mathbf{\Sigma}^1_3$ set of reals is Lebesgue measurable, then $\omega_1$ is an inaccessible ...
- 13k
5
votes
0
answers
138
views
Cone avoidance and $\Pi^0_1$-classes
Suppose $X \subseteq 2^{\omega}$ is nonempty and $\Pi^0_1$ relative to $a$. Assume $c_0 \nleq_T b_0 \oplus a$ and $c_1 \nleq_T b_1 \oplus a$. Must there exist some $y \in X$ such that $c_i \nleq_T ...
- 51
5
votes
0
answers
192
views
Do most semigroups have a zero?
It is widely believed in finite semigroup theory that asymptotically almost all finite semigroups $S$, up to isomorphism, are 3-nilpotent, i.e., they satisfy $\#\{abc\,:\,a,b,c\in S\} = 1$. My ...
- 151
5
votes
0
answers
81
views
Which pseudovarieties have (Eilenberg/Schutzenberger) minimal descriptions?
Suppose $\mathscr{V}$ is a pseudovariety in a countable language $\Sigma$. Say that a minimal description of $\mathscr{V}$ (in the sense of Eilenberg/Schutzenberger rather than Reiterman) is a pair $(...
- 20.5k
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
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
5
votes
0
answers
199
views
In finite model theory, is "invariant FOL with $\varepsilon$-operator" unavoidably second-order?
Throughout, all structures are finite.
Say that a class of finite structures $\mathbb{K}$ is $\mathsf{FOL}_\varepsilon^\text{inv}$-elementary iff it is the class of finite models of a sentence in the ...
- 20.5k
5
votes
0
answers
187
views
Isbell duality for monoids and groups
Isbell Duality
$\newcommand{\IsbellSpec}{\mathsf{Spec}}\newcommand{\IsbellO}{\mathsf{O}}\newcommand{\Sets}{\mathsf{Sets}}\newcommand{\rmL}{\mathrm{L}}\newcommand{\rmR}{\mathrm{R}}\newcommand{\B}{\...
- 11.8k
5
votes
0
answers
108
views
Structure of well-ordered commutative monoids
Let $(M,+)$ be a commutative monoid. Let $<$ be a well-ordering on $M$, where
$\forall a\in M,\ 0\leq a$
$\forall a,b,c\in M,\ a<b\Rightarrow a+c<b+c$
The first condition means $M$ will be ...
- 18.7k
5
votes
0
answers
213
views
Friedman's proof of covering lemma for $L$
There is a two-page proof of the covering lemma for $L$ using $\Sigma_n$ substructures (Theorem 3.10) in Sy Friedman's Fine Structure and Class Forcing, compared to the proof that spans about twenty ...
- 333
5
votes
0
answers
191
views
Higher-order equivalence of ordinals
I wonder which ordinals are second-order equivalent, and similarly for other logical equivalences. Let the signature be fixed and include only <. For concreteness, let us first ask for the first ...
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
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
5
votes
0
answers
153
views
What is known about propositional realizability for the second Kleene algebra and related PCAs?
Short version: Various things are known about realizability of propositional formulas for Kleene's “first algebra” (i.e., $\mathbb{N}$), like examples of realizable but unprovable formulas, and some ...
- 32.5k
5
votes
0
answers
249
views
Classical first-order model theory via hyperdoctrines
I have been reading this discussion by John Baez and Michael Weiss and I find this approach to model theory using boolean hyper-doctrines very interesting. One of their goal was to arrive at a proof ...
- 3,446
5
votes
0
answers
136
views
When does an iteration not add functions $\eta\to V$ at the final stage?
I am interested in better understanding the following property:
Let us say that an iteration of forcings $\langle\mathbb{P}_\alpha,\dot{\mathbb{Q}}_\beta\mid\alpha\leq\gamma,\beta<\gamma\rangle$ is ...
- 2,206
5
votes
0
answers
192
views
Complexity implications on computability
Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or ...
- 3,029
5
votes
0
answers
160
views
$S$ and $T$ globally isomorphic semigroups, with $S$ (commutative and) cancellative, iff $S$ is isomorphic to $T$?
Denote by $\mathcal P(S)$ the semigroup obtained by equipping the non-empty subsets of a "ground semigroup" $S$ (written multiplicatively) with the operation of setwise multiplication ...
- 10.5k
5
votes
0
answers
131
views
Is the opposite of the category of $\kappa$-Lindelöf Hausdorff spaces locally presentable?
Gelfand duality tells us that the category of compact Hausdorff spaces (with continuous maps as morphisms) is contravariantly equivalent to the category of commutative, unital $C^\ast$-algebras (with $...
- 64k
5
votes
0
answers
215
views
Status of Problems in 102 problems in mathematical logic
Is there any location that records the current status of the problems in 102 problems in mathematical logic? Or, better yet, serves as a status board for open problems in mathematical logic? ...
- 3,029
5
votes
0
answers
241
views
A possible characterization of weakly compact cardinals
Aside from the well-known characterization of weakly compact cardinals in terms of the usual partition calculus, I've been wondering if there are other characterizations that are variants of the ...
- 3,038
5
votes
0
answers
249
views
Natural combinatorial properties of $\omega_1$ and weakly compact cardinals
One of the magnificent theorems of $\sf ZFC$ is that there exists an Aronszajn tree on $\omega_1$. Namely, a tree of height $\omega_1$ in which every level is countable, but no branch is cofinal.
On ...
- 39.8k