All Questions
6,026 questions
5
votes
1
answer
168
views
Countably compact Boolean algebras versus distributivity
Let us say that a complete Boolean algebra $B$ is:
countably distributive when for any sequence $(I_n)_{n\in\mathbb{N}}$ of sets and any elements $(u_{n,i})_{n\in\mathbb{N},i\in I_n}$ of $B$ we have
$...
- 32.5k
1
vote
0
answers
244
views
Christoph Benzmüller and Gödel's ontological proof?
Are there any notable mathematical or logical issues within Christoph Benzmüller and Bruno Woltzenlogel-Paleo formalized Gödel's ontological proof (pdf) that has been identified by the community?
11
votes
1
answer
1k
views
Had this attempt to salvage naïve comprehension been studied before?
Is the following a possible way to overcome inconsistency with naive comprehension:
We add an $\in_n$ symbol for each natural $n$ to the signature of this theory, which is a first order theory with ...
- 11.3k
1
vote
1
answer
246
views
Minimal Turing machines associated to math statements
It is known that some famous Number Theoretic problems are equivalent to halting of specific Turing machines:
Goldbach conjecture holds iff a 47 state TM halts
Lagarias' formulation of Riemann ...
- 593
6
votes
1
answer
199
views
$L(\mathbb{R})$-absoluteness from a proper class of Woodins: source?
For a paper I'm writing I need to use (as a blackbox) the following theorem: if there is a proper class of Woodin cardinals and $G$ is set-generic, then $L(\mathbb{R})$ and $L(\mathbb{R})^{V[G]}$ are ...
- 20.9k
4
votes
0
answers
147
views
Isomorphism between the reduced C*-algebra of a groupoid and the crossed product of inverse semigroups
In Paterson's book "Groupoids, Inverse Semigroups and their Operator Algebras" he proves that for any r-discrete groupoid $G$ with unit space $G^0$, its full $C^* $-algebra $C^* (G)$ is ...
- 261
11
votes
2
answers
558
views
Whether an isotone bijection from a power set lattice to another sends singletons to singletons
By the work of Paul Cohen (on the continuum hypothesis), one can neither prove nor disprove from the axioms of ZFC that a bijection $f$ from the power set $\mathcal{P}(S)$ of a set $S$ to the power ...
- 10.5k
5
votes
0
answers
191
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
10
votes
2
answers
564
views
Cardinal arithmetic under determinacy
Work in a reasonable theory of determinacy such as $\mathsf{ZF+DC+AD}$. Which of the following identities are true for arbitrary infinite sets?
$|A^2|=|A^3|$ (motivated by an MSE question that asks ...
- 667
14
votes
2
answers
725
views
Are there any non-conjugation "extendible automorphisms" in the category of finite groups?
Let $\mathbf{Grp}$ be the category of groups. Given a subcategory $\mathscr{G}$ of $\mathbf{Grp}$ and $G\in\mathit{Ob}(\mathscr{G})$, a $\mathscr{G}$-extendible map on $G$ will here mean an assignment ...
- 20.9k
6
votes
0
answers
263
views
Decidably clarifying ordinals
For a computable$^*$ ordinal $\alpha$ (viewed as an $\{<\}$-structure), say that a first-order sentence $\sigma$ in a relational language $\Sigma\supseteq \{<\}$ decidably clarifies $\alpha$ iff ...
- 20.9k
11
votes
2
answers
1k
views
An infinite hat puzzle variation—if we don't know our place, can we still be almost all correct?
An evil demon is holding uncountably many set theorists captive. He explains to us how he will presently arrange us into a well ordered sequence, with everyone facing the same direction upward in the ...
- 236k
3
votes
1
answer
252
views
Can a general recursive function be defined by Pr(x)?
In the book Metamathematics of First-Order Arithmetic, I learned that a general recursive function can be defined by a $\Delta_1$-formula. I am curious about another matter: Since we have $Pr_T^\...
- 127
3
votes
1
answer
256
views
Can these short set-building expressions of the finite set world extend to the infinite set world?
A formula of the form $\forall \vec{p}\, \exists x \, \forall y\, (y \in x \leftrightarrow \phi(y,\vec{p}))$
is to be named a "set-building" formula.
Now, when $\vec{p}$ includes a predicate ...
- 11.3k
2
votes
1
answer
119
views
Does $\mathrm{L}_{s_{n+1}}$ contain a surjection from $\omega$ to $\mathrm{L}_{s_n}$?
Let $s_n$ be the least $\Sigma_n-$admissible ordinal, so that $\mathrm{L}_{s_n}$ is a model of Kripke-Platek set theory with $\Sigma_n-$collection and $\Sigma_n-$separation.
Does $\mathrm{L}_{s_{n+1}}$...
- 3,574
16
votes
1
answer
1k
views
Proving that ZF is Artemov-consistent
As discussed in another MO question, Sergei Artemov has proposed that the standard formalization Con(PA) of "PA is consistent" is flawed, and has proposed a different way to formalize "...
- 82.7k
5
votes
1
answer
212
views
Image-catching families in $\omega$
Let $[\omega]^\omega$ be the collection of infinite subsets of the set of nonnegative integers $\omega$, and let $\newcommand{\I}{\cal{I}}\I=$ $\{S\in[\omega]^\omega: (\omega\setminus S)\in[\omega]^\...
- 48.9k
14
votes
2
answers
1k
views
If every definable class admits a group structure, must global choice hold?
It is a remarkable fact, due to Hajnal and Kertész and explained very well in this MathOverflow answer by user Ashutosh, that the axiom of choice is equivalent to the assertion that every nonempty set ...
- 236k
2
votes
1
answer
153
views
The Dirichlet principle and arithmetical induction
Let us consider the Dirichlet principle as follows: for all natural numbers $n > k > 0$, there is no injection from $\{0, \dots, n-1\}$ into $\{0, \dots, k-1\}$.
Is it true that in some non-...
20
votes
5
answers
1k
views
Uniqueness results that follow from CH
Recently, Joel David Hamkins presented a historical thought experiment that shows that CH could have been adopted as an axiom if we had been using the hyperreal field $\mathbb{R}^*$ instead of $\...
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.9k
2
votes
1
answer
169
views
Smallest ${\mathbf B}$-function $f:\omega\to( \omega\setminus\{0\})$
Motivation. Every hypergraph $(\omega, E)$ where $E$ is countable and consists of infinite sets has property $\newcommand{\B}{\mathbf{B}}\B$. On the other hand, if the members of $E$ are allowed to be ...
- 48.9k
6
votes
0
answers
173
views
Measurable functions from logical formulas
Let $A(X, Y)$ be an arithmetical formula with (only) second-order variables $X, Y\subset \mathbb{N}$.
Assuming $(\forall X\subset \mathbb{N})(\exists Y\subset\mathbb{N})A(X, Y)$, there is a choice ...
- 4,359
1
vote
1
answer
138
views
Is there inconsistency with having countable models of Z with these internalizing properties?
Is there a clear inconsistency with the following?
There exists a countable transitive model of Zermelo set theory, such that for all external bijections between sets the images and preimages of sets ...
- 11.3k
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.9k
4
votes
1
answer
150
views
Comparing semiring of formulas and Lindenbaum algebra
This is motivationally related to an earlier question of mine.
Given a first-order theory $T$, let $\widehat{D}(T)$ be the semiring defined as follows:
Elements of $\widehat{D}(T)$ are equivalence ...
- 20.9k
1
vote
1
answer
179
views
Natural functions outside $\sf PA$?
Can theories stronger than $\sf PA$ manage to define functions from the naturals to the naturals, that $\sf PA$ cannot? If so, what are examples of those functions?
- 11.3k
7
votes
2
answers
311
views
At what ordinal $\chi$ does $\mathrm{L}_\chi$ contain a surjection from $\omega$ to $\mathrm{L}_{\beta_0}$?
Let $\mathrm{ZF^-}$ be $\mathrm{ZF}$ minus power set, and let $\beta_0$ be the ordinal for ramified analysis so that $\mathrm{L}_{\beta_0}$ is the least $\mathrm{L}$-model of $\mathrm{ZF}^-$. Clearly, ...
- 3,574
4
votes
0
answers
146
views
Can one formalize the prevalence of the Big Five systems of reverse math?
Simpson's systems of second order arithmetic turn out to be five in
number; to simplify notation let's denote them A, B, C, D, E. What
seems to be an empirical observation is that most theorems in
...
- 16.6k
5
votes
1
answer
170
views
Can we see quantifier elimination by comparing semirings?
This question came up while reading the paper Hales, What is motivic measure?. Broadly speaking, I'm interested in which ideas from motivic measure make sense in arbitrary first-order theories (or ...
- 20.9k
1
vote
1
answer
146
views
Can PA define functions related to higher theories?
Working in $\sf ZFC$ we can define a function $F$ from naturals to naturals such that $F(0) = \, ^\circ\ulcorner r({\sf Z}) \urcorner$, where $r({\sf Z})$ is the Rosser sentence of Zermelo set theory $...
- 11.3k
3
votes
1
answer
151
views
Large almost disjoint family on $\mathbb{N}$ with property $\mathbf{B}$
Let
$\newcommand{\oo}{[\omega]^\omega}\oo$ denote the collection of all infinite subsets of the set of nonnegative integers $\omega$. We say that $\newcommand{\ss}{{\cal S}}\S\subseteq \oo$ ...
- 48.9k
0
votes
0
answers
143
views
Introductory resources on rewriting logic
Hi I would like to grasp the theory behind Maude [1], [2]
Are there any recommended video lecture notes, talks or introductory notes?
I have been exposed to Functional Analysis, Topology and some Term ...
3
votes
1
answer
329
views
Nonexistence of short integer program sequence which generates squares
Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to ...
- 13.9k
9
votes
2
answers
380
views
How big can function spaces get without extensionality?
In what follows we work in the usual formulation of Martin-Löf Type Theory including Axiom K [1]. Boldface numbers $\mathbf{n}$ denote the usual finite type with $n$ elements.
Motivation
Postulating ...
- 756
15
votes
3
answers
3k
views
Finite verification for theorems due to Busy Beaver numbers
I recently learned about the Busy Beaver function, and a formulation of it that essentially tells us if a turing machine of $n$ states takes over $BB(n)$ steps, it will never halt.
One consequence I ...
- 185
2
votes
0
answers
132
views
A property of < in Primitive recursive arithmetic
In Primitive recursive arithmetic (PRA), we can introduce $\lt$ by introducing its representing function $K_{\lt}$, where $K_{\lt}(x,y) =sg(x+1-y)$. Here "sg" and "-" are the ...
- 29
1
vote
1
answer
215
views
Reference about cancellation property for semigroups
Have the semigroups with the following cancellation property been studied?
Property: Let $S$ be a semigroup and $x,y\in S$ such that $xz=yz,$ for all $z\in S,$ then $x=y$.
- 313
7
votes
0
answers
161
views
Is strictness decidable?
Let $\mathcal C$ be an $\infty$-category. We can ask:
Q: Is $\mathcal C$ a 1-category?
That is, are the hom-spaces of $\mathcal C$ essentially discrete?
Roughly, my question is:
Proto-Question: Is Q ...
- 63.9k
2
votes
0
answers
196
views
On "necessary connectives" in a structure
Given a clone $\mathcal{C}$ over $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with connectives from $\mathcal{C}$ in place of the usual Booleans. Given a clone $...
- 20.9k
8
votes
1
answer
222
views
Mostowski's absoluteness theorem and proving that theories extending $0^\#$ have incomparable minimal transitive models
This question says that the theory ZFC + $0^\#$ has incomparable minimal transitive models. It proves this as follows (my emphasis):
[F]or every c.e. $T⊢\text{ZFC\P}+0^\#$ having a model $M$ with $On^...
- 1,097
1
vote
0
answers
165
views
Can this formalism prove the consistency of ZFC?
Working in bi-sorted first order logic with equality and membership. First sort variables written in lower case range over sets. Second sort variables written in upper case range over classes. Lets ...
- 11.3k
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.9k
5
votes
3
answers
665
views
Negating fundamental axioms
It is commonplace to consider standard axiomatic systems (e.g. $ZF$) with one of the 'less essential' axioms negated, like infinity, 'less essential' here having some ambiguous definition related to ...
- 10.1k
-4
votes
2
answers
399
views
Two equivalent statements about formulas projected onto an Ultrafilter
Question 1:
In the same language, let $ X $ be a nonempty set, and let $ \{ (\forall x_{x(i)} f(i)) \ | \ i \in X \} $ be a set of formulas. We use $ x(i) $ to denote the index of the variable on ...
- 127
6
votes
0
answers
251
views
Whence compactness of automorphism quantifiers?
The following question arose while trying to read Shelah's papers Models with second-order properties I-V. For simplicity, I'm assuming a much stronger theory here than Shelah: throughout, we work in $...
- 20.9k
8
votes
0
answers
164
views
Is there a substructure-preservation result for FOL in finite model theory?
It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
- 20.9k
7
votes
1
answer
290
views
Equivalence of omniscience principles for natural numbers and analytic omniscience principles for Cauchy real numbers
In constructive mathematics, a proposition $P$ is decidable if $P \vee \neg P$, and a proposition is stable if $\neg \neg P \implies P$. We have the following principles of omniscience for the natural ...
- 2,624
1
vote
1
answer
276
views
About having one axiom schema for ZFC motivated after the iterative conception of sets?
This posting is related to this posting, and builds its motivation from this answer to it.
Define: $\operatorname {History}(x) \iff \\\forall y \in x: y=\{c \mid \exists z : z \in y \cap x \land (c \...
- 11.3k
2
votes
0
answers
76
views
Defining fields of characteristic zero in existential second-order logic
Is it possible to define in existential second-order logic (ESO) the class of fields of characteristic zero? An easy compactness argument shows that the class of fields of positive characteristic is ...
- 135