All Questions
1,458 questions with no upvoted or accepted answers
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 ...
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
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
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
0
answers
174
views
Centers and conjugacy classes of groups relative to a pair of group homomorphisms
$\newcommand{\defeq}{\mathbin{\overset{\mathrm{def}}{=}}}$Given a group $G$, its center $\mathrm{Z}(G)$ and set of conjugacy classes $\mathrm{Cl}(G)$ are defined by
\begin{align*}
\mathrm{Z}(G) &\...
- 11.8k
4
votes
0
answers
166
views
Consistency of definability beyond P(Ord) in ZF
Is it consistent with ZF that the satisfaction relation of $L(P(Ord))$ is $Δ^V_2$ definable? More generally, is it consistent with ZF that there is a $Δ^V_2$ formula (taking $α$ as a parameter) that ...
- 7,545
4
votes
0
answers
290
views
Which countable sets don't drastically change the definable topologies on $\mathbb{R}$?
For $\mathcal{M}$ an expansion of $\mathcal{R}=(\mathbb{R};+,\times)$ and $A\subseteq\mathbb{R}$, let $\tau^\mathcal{M}_A$ be the topology on $\mathbb{R}$ generated by the sets definable in $\mathcal{...
- 20.5k
4
votes
0
answers
135
views
Do coproducts injections of Heyting algebras have left and right adjoints?
Given two Heyting algebras $A$ and $B$, let $A+B$ be their coproduct in the category of Heyting algebras. Is it true that the inclusion $A → A+B$ always has a left and a right adjoint ? (Actually, I ...
- 135
4
votes
0
answers
162
views
Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?
(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.)
Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
- 2,912
4
votes
0
answers
214
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
- 81
4
votes
0
answers
247
views
Cantor-Bernstein phenomena for structures (and a "moderate zigzag" property)
My favorite proof of the Cantor-Bernstein theorem is the one that argues by "histories" - given injections $f:A\rightarrow B$ and $g:B\rightarrow A$, we identify each element of $A$ as ...
- 20.5k
4
votes
0
answers
145
views
On self-reference in a weak structure
Below, all structures are countable and in finite languages. This question is motivated by the following: "To what extent is self-reference possible when nothing like the diagonal lemma holds?&...
- 20.5k
4
votes
0
answers
365
views
Does $e^x$ let the reals build any new ordinal functions?
This question is closely related to this one. Belatedly, it occurred to me that I'd probably picked the wrong test question. I'm leaving that question up because I don't think it's bad per se, but I ...
- 20.5k
4
votes
0
answers
221
views
On natural examples, how much stronger is this than Löwenheim–Skolem?
Given a logic (= regular logic in the sense of Ebbinghaus/Flum/Thomas) $\mathcal{L}$, let a $\downarrow$-sentence be an $\mathcal{L}$-sentence $\varphi$ such that, whenever $\mathfrak{M}\models\varphi$...
- 20.5k
4
votes
0
answers
110
views
Coding fourth-order objects in second-order Reverse Mathematics
Reverse Mathematics (RM for short) generally takes place in the language of second-order arithmetic. Thus, higher-order objects need to be "coded" or "represented" indirectly. ...
- 4,359
4
votes
0
answers
148
views
The monochromatic principle and the axiom of choice
For any set $A\neq\emptyset$, denote by $[A]^A$ the collection of sets $B\subseteq A$ such that there is a bijection $\varphi:B\to A$. If ${\cal S}\subseteq [A]^A$, we say that $B\in[A]^A$ is ...
- 48.9k
4
votes
0
answers
139
views
Simple $(\alpha+1)$-recursive well-orders with order type $|\alpha\text{-recursive}|$
In the following, $L_\alpha$ is the $\alpha$-th level of the constructible hierarchy, $\alpha$-recursive means definable in $L_\alpha$ by a $\Delta_1$ formula. $|\alpha\text{-recursive}|$ is the ...
- 148
4
votes
0
answers
166
views
Is there any good methods for writing down basis for laws of groups?
I am wondering if there is a good method to write down a finite equational basis for a finite group.
Especially I am wondering if there is a good method in following situations:
We can write a group ...
- 93
4
votes
0
answers
154
views
Are the relations of being homeomorphic or being homotopy equivalent on the compact polyhedra definable in the structure of the natural numbers?
Let $ K(\mathbb{N}) $ denote the set of all finite simplicial complexes with vertices in $\mathbb{N}$.
Let $ f\colon \mathbb{N} \to K(\mathbb{N}) $ be a computable bijection.
Let $ R $ = { $ (m, n) $ |...
- 307
4
votes
0
answers
110
views
What logics do the transfinite length pebble games capture?
See e.g. Libkin, Elements of finite model theory for background on the usual pebble game. Below, all languages are finite and relational, and "$\uparrow$" denotes an expression being ...
- 20.5k
4
votes
0
answers
215
views
Do the transitive models of ZFC form a canonical Kripke model for the Gödel-Löb axioms?
Let $\mathcal{C}$ be the class of all transitive models of ZFC, i.e., sets $S$ such that $S$ is downward closed ($x \in S \to x \subseteq S$) and $(S, \in)$ is a model of ZFC (where $\in$ is set ...
- 328
4
votes
0
answers
122
views
Are semilinear sets piecewise periodic?
I wanted to check my understanding of semilinear sets before I give a talk on them, and I haven't been able to find this exact perspective in any of the sources I've read through. Is it correct, and ...
- 429
4
votes
0
answers
271
views
Can we have full choice prior to Reinhardt cardinals?
Working in $\sf ZF + Reinhardt \ cardinal$, can we have full choice over all stages $V_{\alpha < \kappa}$ where $\kappa$ is the Reinhardt cardinal, i.e., the critical point of the elementary ...
- 11.3k
4
votes
0
answers
247
views
Is this notion of "concrete bijection" transitive?
This question looks at the same intuition as, but expressed via a different formal notion than, a couple earlier questions of mine (1, 2). Basically, I'm playing around with using model theory to ...
- 20.5k
4
votes
0
answers
74
views
Is each TS-topologizable group TG-topologizable?
Definition 1. A topology $\tau$ on a group $X$ is called
$\bullet$ a semigroup topology if the multiplication $X\times X\to X$, $(x,y)\mapsto xy$, is continuous in the topology $\tau$;
$\bullet$ a ...
- 42k
4
votes
0
answers
157
views
On skew monoid rings and skew ordered series rings
To my knowledge (see, e.g., H.H. Brungs and G. Törner's Skew Power Series Rings and Derivations [J. Algebra 87 (1984), 368-379]), skew polynomial rings were first introduced by Ø. Ore in 1933: Given ...
- 10.5k
4
votes
0
answers
170
views
Corollaries of Kleene's Theorem (Regular Languages)
Kleene's theorem that finite automata (specifically, nondeterministic) are expressively equivalent to regular expressions seems to be a powerful and not immediately obvious tool for untangling the ...
- 429
4
votes
0
answers
283
views
Is this "finite-ish combinatorics" reflection principle consistent?
This question is an attempt to chisel away at this earlier question of mine, which in retrospect may be rather intractable. Throughout, we work in $\mathsf{ZF}$.
Briefly (see the linked question for ...
- 20.5k
4
votes
0
answers
145
views
Constructing Complicated Borel Subgroups of Polish Groups
Farah and Solecki showed the following in Borel subgroups of Polish groups:
Theorem: Every Polish group $G$ admits Borel subgroups of arbitrarily high Borel rank.
However, the construction is far from ...
- 2,146
4
votes
0
answers
163
views
Invariant Spaces of Hypergraphs
The following arose from a question in model theory (specifically in the model theory of modules).
Fix an arity $k$. Let $[\mathbb{Q}]^k$ denote the set of all subsets of $\mathbb{Q}$ of cardinality $...
- 2,146
4
votes
0
answers
180
views
Inner model theory using indiscernibles
Has an inner model theory been developed on the basis of indiscernibles rather than measures? Is there a reasonable formalization at the level of overlapping extenders?
Fine-structural models beyond $...
- 7,545
4
votes
0
answers
141
views
Adjoints on power sets and a connection to quantifiers as adjoints
While working through the Awodey book on Category Theory, we stumbled upon exercise 9.8.
The situation there is that you have $f : A \to B$ in Sets, and consider $\text{im}\, f : \mathcal P (A) \to \...
- 141
4
votes
0
answers
213
views
Is existence of this graph consistent with ZFC?
Is existence of the following graph consistent with $\sf ZFC$.
The graph is directed upwards and acyclic, children nodes can be connected to ONE parent only, and it is not the union of separate (...
- 11.3k
4
votes
0
answers
143
views
Correctness criteria for proof nets
In their paper Natural deduction and coherence for weakly distributive categories Blute, Cockett, Seely and Trimble introduce so-called proof circuits (aka two-sided proof structures) for the positive ...
- 764
4
votes
0
answers
144
views
Is the orthocenter "(roughly) equationally finitely-based"?
Let $T$ be the "almost everywhere" equational theory of the orthocenter function, "tweaked appropriately" to avoid partiality issues (see this earlier question of mine for details)....
- 20.5k
4
votes
0
answers
82
views
When do Borel propositional theories have topologically tame truth assignments?
Let $(P_r)_{r \in \mathbb{R}}$ be an $\mathbb{R}$-indexed family of propositional variables. Let $\mathcal{L}$ be the collection of all propositional sentences formed from the variables $(P_r)_{r \in \...
- 13k
4
votes
0
answers
253
views
Is this recursion theoretic analogue of a criterion of weakly compact cardinal accurate?
Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
- 1,490
4
votes
0
answers
95
views
$\omega$ incompleteness of $\lambda$ calculus
In Plotkin's 'The $\lambda$-Calculus is $\omega$-Incomplete' (The Journal of Symbolic Logic Vol. 39, No. 2 (Jun., 1974), pp. 313-317), an example is given of two (untyped) $\lambda$-terms $M$ and $N$ ...
- 358
4
votes
0
answers
58
views
Are the countable (rayless) trees with wqo labels wqo?
It has been proved by Corominas that the countable trees with vertex-labels coming from a better-quasi-ordered set are better-quasi-ordered. My question is whether this holds if we replace bqo by wqo ...
- 1,936
4
votes
0
answers
151
views
How big a "scaffold" does second-order logic need to detect its own equivalence notion?
(Previously asked and bountied at MSE:)
Let $\Sigma$ be the language consisting of a single binary relation symbol. Second-order logic can "detect" second-order-elementary-equivalence of $\...
- 20.5k
4
votes
0
answers
171
views
Can SOL characterize its own equivalence notion, without "scaffolding," for graphs?
Consider the following property $(*)_\mathcal{L}$ of a logic $\mathcal{L}$:
$(*)_\mathcal{L}:\quad$ There is no $\mathcal{L}$-sentence $\varphi$ such that for all graphs $\mathcal{A},\mathcal{B}$ we ...
- 20.5k
4
votes
0
answers
285
views
A variant of infinitary equivalence
Let $\Sigma$ be the language consisting of a single binary relation symbol, $R$ (so $\Sigma$-structures are graphs, in the model theory sense). For a logic $\mathcal{L}$, say that an $\mathcal{L}$-...
- 20.5k
4
votes
0
answers
198
views
Is there a simple proof of consistency of EA?
Let $\mathsf{EA}+\mathsf{CE}$ be elementary arithmetic with cut elimination theorem. Is there a simple (1-)consistency proof of $\mathsf{EA}$ over $\mathsf{EA}+\mathsf{CE}$? I think that a naïve ...
- 178
4
votes
0
answers
207
views
What are proofs of the consistency of the propositional calculus?
Consider the propositional calculus. For specificity I will use the sequent propositional calculus PK as developed in Cook and Nguyen's Logical Foundations of Proof Complexity (for precision the ...
- 1,974
4
votes
0
answers
172
views
Undecidability for hyperbolic Wang-tilings - pentagons, heptagons, octagons, oh my!
Berger proved that the problem of determining if a finite set of Wang tiles can tile the plane is undecidable. Robinson reproved Berger's result and raised the question of considering the ...
- 5,349
4
votes
0
answers
99
views
Minimization of second-order unifiers
We know that first-order unification is decidable.
More generally, if there exists a unifier for a first-order unification problem, then there exists a most general unifier.
I'm interested in the ...
- 186
4
votes
0
answers
368
views
Is intuitionistic predicate logic (semantically) complete or incomplete?
According to Constructivism in Mathematics: An Introduction by Troelstra A.S. and Van Dalen (https://archive.org/details/constructivismin0002troe/page/718/mode/2up) it is proven in an intuitionisitc ...
- 411
4
votes
0
answers
232
views
Is there a ${\bf 0'}$-computable linear order with "all intervals wild"?
Say that a linear order $L$ is a thicket iff $L$ is infinite, and for all elements $a,b,c_1,...,c_n\in L$ with $a<_Lb$ and $[a,b]_L$ infinite the following are equivalent:
$\{a,b\}\subseteq \...
- 20.5k
4
votes
0
answers
135
views
Can every true type be reached from the unit type in small steps?
We are playing a game where you start at the unit type and the goal is to reach a given true type.
You can go from your current location to another by writing down a (non-dependent) function of length ...
- 41
4
votes
0
answers
148
views
Can Heyting arithmetic be axiomatized by strong induction together with some disjunction-free formulas?
Consider the usual first-order language $ \mathcal L = \{ 0 , S , + , \cdot \} $ of arithmetic, and let $ y < x $ be an abbreviation for $ \exists z \ y + S z = x $. An almost negatively ...
- 346