All Questions
1,141 questions
6
votes
1
answer
756
views
Lawvere's 'Categories of space and of quantity" - the projection formula
I'm trying to read bits and pieces of W. Lawvere's Categories of Space and of Quantity, and, as usual have lots of questions. Page numbers will refer to the number printed on the corners of the pages.
...
- 10.5k
6
votes
1
answer
378
views
Iteration of random reals
Consider two random reals $x, y$ over a transitive model $V$ of ZFC. More specifically, if $\mathcal C^V={}^\omega2$ is the Cantor space, composing the canonical homeomorphism with the projections $\...
- 1,688
6
votes
1
answer
419
views
A special c.c.c forcing notion and adding minimal generic reals
This question is related to my question "Forcing with c.c.c forcing notions, Cohen reals and Random reals".
A natural way to answer Prikry's conjecture is to build a c.c.c. forcing notion which adds ...
- 32.2k
6
votes
2
answers
482
views
Complete atomless Boolean algebras with abelian automorphism group
Is there any example of a complete atomless Boolean algebra with a non-trivial abelian automorphism group?
This is equivalent, by Stone duality, to asking for an extremally disconnected compact ...
- 3,115
6
votes
3
answers
837
views
Is the power set axiom essential for constructing L?
Take ZFC, remove axiom of Power set, and put instead of it the following axiom:
Axiom of Successor Cardinals: $\forall \kappa\, \exists x \, \forall \alpha \, ( \alpha \leq \kappa \to \alpha \in x)$
...
- 11.3k
6
votes
2
answers
456
views
When are all greater cardinals sharply greater?
Makkai and Paré introduced the following binary relation on regular cardinals: given $\kappa$ and $\lambda$, $\kappa \vartriangleleft \lambda$ (read, $\kappa$ is sharply less than $\lambda$) when $\...
- 15.9k
6
votes
1
answer
727
views
What is the consistency strength of this theory?
Language: first-order logic
Primitives: $=, S, \in $ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation).
Axioms: those of identity ...
- 11.3k
6
votes
5
answers
2k
views
Zermelo-Frankel set theory for algebraists
$\DeclareMathOperator\Var{Var}\DeclareMathOperator\CRings{CRings}\DeclareMathOperator\Grp{Grp}\DeclareMathOperator\Sets{Sets}$I'm not a logician/set theorist, and I have some questions on set theory ...
user122276
6
votes
3
answers
537
views
Limits of determinacy on reals
For $X\subseteq\mathbb{R}^\omega$, say that $X$ is determined if the associated game on $\mathbb{R}$ of length $\omega$ (players I and II alternate playing reals, player I wins iff the sequence built ...
- 20.5k
6
votes
1
answer
914
views
The set of largest numbers definable by formulas in different lengths
Let $n=\phi(l)$ to be the largest number definable by a first order arithmetic formula $f(x)$ having length at most $l$. By "$n$ is definable by formula $f(x)$" I mean $\mathcal{N}\vDash f(a)$ iff $a=...
- 2,619
6
votes
1
answer
333
views
Can we have this sequence where choice fails and returns?
Can we have a sequence of transitive sets $\langle\mathcal V_0, \mathcal V_1, \mathcal V_2,...\rangle$, all modeling $\sf ZF$, such that $\mathcal P(V_n) \subset \mathcal V_{n+1}$, and the cardinality ...
- 11.3k
6
votes
1
answer
205
views
Preserve validity between the two Kripke frames
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $n \geq 1$, let $\mathcal{C}_n$ denote the frame which is shown in Fig.1. ...
- 53
6
votes
1
answer
541
views
Does Playfair imply Proclus?
I am interested in the interplay between the Playfair and Proclus Axioms in linear spaces.
By a linear space I understand a pair $(X,\mathcal L)$ consisting of a set $X$ and a family $\mathcal L$ of ...
- 42k
6
votes
3
answers
392
views
Intuition behind Kleene's “second algebra” $\mathcal{K}_2$
The “second Kleene algebra” $\mathcal{K}_2$ is defined, e.g. here on nLab, or in section 1.4.3 of van Oosten's book Realizability: an Introduction to its Categorical Side (2008), or as example 3.4 of ...
- 32.5k
6
votes
3
answers
393
views
Structure theorem for a class of idempotent monoids (where $xy = x$ or $xy = y$ for all $x, y$)
Question. Is there any structure theorem for the class of monoids $H$ with the property that $xy = x$ or $xy = y$ for all $x, y \in H$? Or does this look hopeless for some good reasons?
A monoid with ...
- 10.5k
6
votes
0
answers
190
views
The highest degree of a polynomial on a finite group
This question is motivated by the comments and the answer to this MO-question.
First let us recall some definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\...
- 42k
6
votes
4
answers
1k
views
Is every Heyting algebra the Lindenbaum algebra of an intuitionistic first order theory?
This question comes after the comments in the recent related question Sigma-complete Lindenbaum algebras?, but in its current form is sufficiently different in my opinion, and so I decided to follow ...
- 5,902
6
votes
1
answer
505
views
Upward Löwenheim–Skolem theorem for well-ordered models with/without measurable cardinals
Consider a complete first order theory $T$ whose language contains a binary predicate $\leq$. Assume that $T$ has an uncountable model that is well-ordered by $\leq$ so that this question isn't stupid ...
- 12.6k
6
votes
2
answers
3k
views
Existence of an $\omega$-nonstandard model of ZFC from compactness
I have read several times that assuming Con(ZFC), and using compactness it can be proved the existence of a model of ZFC with an ill-founded $\omega$. How is that? Any reference will be welcome.
- 1,465
6
votes
1
answer
423
views
Which model is the minimal pointwise definable model of $\sf ZFC$?
Is the minimal transitive model of $\sf ZFC$ pointwise definable?
If not, then what is the minimal pointwise definable model of $\sf ZFC$?
Can we define that using Hamkins result for existence of ...
- 11.3k
6
votes
0
answers
274
views
Forcing Martin's Axiom without cardinal arithmetic
We know that if $\kappa>2^{\aleph_0}$ and $\kappa^{<\kappa}=\kappa$, then there is a c.c.c. forcing which forces $\sf MA+2^{\aleph_0}=\kappa$. Traditionally, we even start with $\sf GCH$, which ...
- 39.8k
6
votes
3
answers
1k
views
Proof formalization
I read some time ago some papers about proof formalization. Typically, I began whith this one, from Lamport.
Are there more recent works in this field ?
6
votes
2
answers
406
views
Axiomatic strength of the cumulative hierarchy
In the 2021 paper Level Theory Part I: Axiomatizing the Bare Idea of a Cumulative Hierarchy of Sets by Tim Button, a first order theory of the cumulative hierarchy is explored. Initially no axioms ...
- 10.1k
6
votes
1
answer
742
views
Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?
EDIT: Noah Schweber helpfully points out that $\mathsf{ACA}_0$ is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
- 708
6
votes
2
answers
522
views
addition of definable numbers decidable?
Define a number generating machine to be a total turing machine running on input alphabet {0,1} (or, any ary), that given input n (in binary) outputs a digit (binary or decimal or whatever).
Given ...
- 119
6
votes
3
answers
1k
views
Provability in Second-Order Arithmetic without the Successor Axiom
Consider second-order Peano Arithmetic Z2, i.e. the two-sorted first-order theory with induction and comprehension. Remove the assumption about the totality of the successor relationship (the ...
- 1,974
6
votes
1
answer
969
views
Is Ackermann's set theory minus class comprehension equal to ZF?
Ackermann in 1956 proposed an axiomatic set theory.
Reinhardt proved that Ackermann's set theory equals ZF
It's clear that Zermelo set theory can be interpreted in Ackermann's set theory minus class ...
- 11.3k
6
votes
2
answers
1k
views
MIP*=RE theorem and its impact on logic and proof theory
In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
- 9,330
6
votes
3
answers
595
views
What's the current state of one-rule semi-Thue system termination problem?
What's the current state of one-rule semi-Thue system termination problem? Search produces a lot of references, but it's hard to find out if decidability of this problem has been proven or not.
6
votes
2
answers
999
views
Are omega-consistent extensions of PA always consistent with each other?
The question is as in the title. In the edit history you can find my attempt to formalise the question, but that was a failure, for reasons stated clearly in the comments. Thus, my question is just:
...
- 1,344
6
votes
1
answer
352
views
Quantifier complexity of definition of compactness
This question is inspired by the post on quantifier complexity of
continuity. We work with metric spaces M
considered as two-sorted first-order structures (M,$\mathbb R$,d,+,⋅,<)
where $d:M^2→\...
- 16.6k
6
votes
2
answers
512
views
Is strengthening Foundation in NBG sufficient to make it prove Con(ZFC)?
Can $\sf NBG$ class theory prove the foundation scheme:
Foundation schema: if $\Phi(X)$ is a formula in which "$X$" occurs free and only free, and in which "$Y$" doesn't occur, ...
- 11.3k
6
votes
0
answers
632
views
Generating functions in countable commutative monoids
Let $f: \mathbb{N}_0 \rightarrow \mathbb{C}$ be a function. The power series of $f$ can be viewed as the function $\mathscr{P}_f : q \mapsto \sum_{n \in \mathbb{N}_0}^{} f(n)q^n$ where $q \in \mathbb{...
- 405
6
votes
1
answer
293
views
Need help in trying to understand an argument by V. A. Yankov on the nonrealizability of Scott's axiom
(This is really long because I give a lot of context, but you can skip right to the end where the excerpt I'm trying to make sense of is copied and translated.)
Background: I'm trying to understand ...
- 32.5k
6
votes
1
answer
309
views
Failure of Cantor-Bernstein for the Levy Collapse
Related to this question, is it possible to give an example of the failure of Cantor-Bernstein for complete embeddings of forcing notions involving the Levy Collapse $Col(\omega,<\kappa)$? Suppose ...
- 18.6k
6
votes
0
answers
1k
views
Undecidability degree of some elementary theories (two equivalence relations, ...)
I have a question about some results in the paper
I. A. Lavrov. Effective inseparability of the sets of identically true formulae and finitely refutable formulae for certain theories (in Russian). ...
- 768
6
votes
3
answers
1k
views
Set theory inside arithmetics via the Ackermann yoga
Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of ZF-Infinity in PA (see for refs this MO question and here for an excellent ...
- 7,853
6
votes
1
answer
226
views
Are $G$-limits of a slender group $G$ in the space of marked groups also slender?
A group $G$ is slender if every subgroup $H \leq G$ is finitely generated. This includes polycyclic-by-finite groups. Such groups are also called noetherian.
Suppose that $L$ is a $G$-limit group in ...
- 1,033
6
votes
0
answers
357
views
How much "finitary combinatorics" can be emulated by an infinite Dedekind-finite set?
Throughout, we work in $\mathsf{ZF}$. Let $[n]=\{1,...,n\}$. Given a set $X$ and a first-order sentence $\varphi$, let $M_X(\varphi)$ be the set of isomorphism types of models of $\varphi$ with ...
- 20.5k
6
votes
1
answer
258
views
Do escaping sets "uniformly" cover dominating sets under determinacy?
For $\mathbb{A},\mathbb{B}\subseteq\mathcal{P}(\omega^\omega)$, say $\mathbb{A}$ spreads onto $\mathbb{B}$ iff there is some $F:\omega^\omega\rightarrow\omega^\omega$ such that for all $X\in\mathbb{A}$...
- 20.5k
6
votes
1
answer
485
views
Show that the positive existential theory is undecidable
To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...
- 309
6
votes
2
answers
318
views
Can a nontrivial $\phi \in Gal(\bar K /\bar k )$ preserve all algebraically closed subfields?
The answer is "yes" if $\bar K = \overline{k(x)}$ (in fact, every $\phi \in Gal(\overline{k(x)}/\bar k)$ preserves all algebraically closed subfields -- there's only two of them, so it's not that hard!...
- 64k
6
votes
5
answers
3k
views
A meta-mathematical question related to Hilbert tenth problem
I am reading Bjorn Poonen's very nice survey on Hilbert's Tenth problem
(http://www-math.mit.edu/~poonen/papers/uniform.pdf), and while I believe I understand the mathematics well, I have widespread ...
- 26k
6
votes
1
answer
1k
views
MIP^*=RE and quantum computation
I recently learned about the MIP^*=RE result. I have to admit that I don't understand big parts of this paper and I am barely familiar with quantum physics. I hope my questions below make sense.
I ...
- 2,882
6
votes
1
answer
185
views
A name for semigroups in which left and right principal ideals coincide
Is there any standard name for semigroups $S$ in which $xS=Sx$ for all $x\in S$?
Examples of such semigroups are commutative semigroups and Clifford inverse semigroups.
- 42k
6
votes
1
answer
292
views
Decidability of completeness in propositional logic
Propositional logic can be presented as in Mendelson’s book, with the sole inference rule of modus ponens, and with the following three axioms:
$$B \Rightarrow (C \Rightarrow B)$$
$$(B \Rightarrow (C \...
- 1,075
5
votes
4
answers
866
views
A Fraïssé class without the strong amalgamation property.
I am trying to find some examples of Fraïssé classes that do not have the strong amalgamation property. Anyone?
5
votes
2
answers
2k
views
Are all models of ZF + DC + "All set of reals are lebesgue measurable" also models of CH? [duplicate]
Possible Duplicate:
Lebesgue Measurability and Weak CH
I have studied a little set theory and I found that Solovay constructed a model of ZF+DC+"All set of reals are Lebesgue measurable" and I ...
5
votes
2
answers
332
views
Questions on weakly symmetric algebras
A finite dimensional algebra $A$ over a field $K$ is called weakly symmetric in case $soc(P)=top(P)$ for every indecomposable projective module $P$ and it is called symmetric in case $D(A) \cong A$ as ...
- 26.5k
5
votes
2
answers
598
views
Translating basic number theory to the monadic theory of the real line
What corresponds to $\forall m\forall n(2m \neq 2n+1)$ or $\forall p\forall q(p^2 \neq 2q^2)$ in the monadic theory of the real line?
Shelah (1975) proved that arithmetic can be reduced the monadic ...
user44143