All Questions
6,026 questions
2
votes
1
answer
240
views
Can there be a minimal remote cardinal?
Working in $\sf Z- Reg.$ we can have sets bigger than every well-founded set, let's label such sets as "remote". Now, suppose we'll add the axiom of existence of transitive closures, and the ...
- 11.3k
3
votes
1
answer
234
views
Independence of CH and permutation models?
Can independence of $\sf CH$ from $\sf ZFCA$ be established using $\sf FM $ permutation models? And if so, then historically did this came first or Cohen's forcing?
- 20.5k
4
votes
1
answer
176
views
Can we have external automorphisms over intersectional models?
Is the following inconsistent:
By "intersectional" set I mean a set having the intersectional set of every nonempty subset of it, being an element of it.
$\forall S \subset M: S\neq \...
- 236k
10
votes
1
answer
262
views
Does every linear cover contain a minimal cover?
This is a follow-up question to an older question.
Let $X\neq \emptyset$ be a set. We say that ${\cal C}\subseteq {\cal P}(X)$ is a cover if $\bigcup {\cal C} = X$, and we call ${\cal C}$ linear if $|...
- 48.9k
84
votes
3
answers
6k
views
How do I verify the Coq proof of Feit-Thompson?
I probably don't have the appropriate background to even ask this question. I know next to nothing about formal or computer-aided proof, and very little even about group theory. And this question is ...
- 82.7k
1
vote
1
answer
310
views
Proof of the axiom of choice for finite sets in ZF [closed]
Let the set $A$ be finite and $\emptyset \notin A$. How can I, without using the axiom of choice, prove by mathematical induction that there exists a function $f : A \rightarrow \bigcup A$ satisfying $...
- 48.9k
2
votes
1
answer
423
views
Conjecture about semigroups
Let $G$ be a finite semigroup with order $n$ odd. Let $S_i \in G, i=1,\ldots,\binom{n}{(n+1)/2}$ be all the subsets of $G$ of size $(n+1)/2$.
Let $E(S_i)$ be the set obtained "expanding" $...
- 14.6k
4
votes
1
answer
205
views
How probability-rich is the $\sigma$-algebra generated by a sequence of sets? (Sierpiński's theorem on non-atomic measures without using the AoC.)
$\newcommand\F{\mathcal F}\newcommand\si{\sigma}\newcommand\Om{\Omega}\newcommand\ep{\varepsilon}$Let $p\in(0,1)$ and let $(\Om,\F,P)$ be a probability space. Let $(A_n)$ be a sequence in $\F$ such ...
3
votes
1
answer
366
views
Statements outside of the Kleene Hierarchy?
I take a list of $2*m$ natural numbers {$n_k$}. I encode them in some way together to a single bit sequence. Now I feed this bit sequence to a Turing machine $T$. Call the statement "For all $n_1$, ...
- 236k
6
votes
3
answers
872
views
An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved.
Edited (this question contains two versions of a similar question)
Is there some finitely presented group $G$ generated by $g_1,...,g_n$ such that
there is an element $g\in G$ expressed as a finite ...
- 236k
7
votes
9
answers
7k
views
Ultrainfinitism, or a step beyond the transfinite
Cantor has, in the immortal words of D. Hilbert, given all of us a paradise (or perhaps, I would rather say, a great vacation spot), the TRANSFINITE.
$\aleph_0, \aleph_1,\aleph_2\dots$
the lists ...
- 2,031
3
votes
1
answer
134
views
$\Pi^0_1$ sentences modulo "schematic entailment"
Let $\mathfrak{P}$ be the preorder of $\Delta^0_0$ (= only bounded quantifiers) formulas with one free variable in the language of arithmetic, under the relation $\alpha(x)\le\beta(x)$ iff there is a ...
- 20.5k
1
vote
1
answer
127
views
Can we effectively define a theory of all upward absolute sentences over theories of hereditarily bounded sets?
Lets' take the theory of hereditarily bounded sets[1][2]. We know that every $S_k$ where $k \in \omega$ is decidable and has as its canonical model the set ${\sf H}_k$ of all sets hereditarily of size ...
- 20.5k
4
votes
1
answer
247
views
Jensen's proof that $\diamondsuit$ holds at subtle cardinals
At the end of these notes by Ronald Jensen (which I found from this question) there is a proof that $\diamondsuit_\kappa$ (diamond principle) holds if $\kappa$ is a subtle cardinal.
By induction on $\...
- 73.2k
4
votes
1
answer
158
views
Impact of coining $L$ in $\mathcal L_{\omega_1, \omega}$ on which large cardinals it can satisfy?
What happens to the constructible universe $L$ if we build it in the first of infinitary languages $\mathcal L_{\omega_1, \omega}$?
Would the usual limitation of $L$ not satisfying existence of a ...
- 236k
6
votes
0
answers
151
views
On dual notions of morphisms of algebraic structures obtained by replacing equaliser with coequalisers
This question is based on this discussion from the Category Theory Zulip. See also the earlier question Natural cotransformations and "dual" co/limits.
Let $G$ and $H$ be groups. We define ...
- 11.8k
16
votes
2
answers
797
views
Operations on the set of large cardinal axioms
Here's a question from a non-set-theorist, but a sometime-user of large cardinals.
The name Cantor's attic is pretty evocative for the collection of large cardinal axioms: looking through the pages ...
- 1,097
10
votes
0
answers
181
views
"Effective gaps" in the c.e. degrees
Below, $W_e$ is the $e$th c.e. set according to some appropriate list of such.
In a very loose analogy with Hausdorff gaps, say that an effective gap is a pair of computable sequences $(c_i)_{i\in\...
- 20.5k
5
votes
1
answer
158
views
(Weakly) minimal subcovers of linear covers
Motivation. The starting point of this question is the trivial observation that if we cover $\mathbb{N}$ with $$\big\{\{0,\ldots n\}: n\in \mathbb{N}\big\},$$ then this cover doesn't have a minimal ...
- 13.4k
8
votes
0
answers
368
views
An obscure case of Curry-Howard
It is a theorem of the Intuitionistic Propositional Calculus that
$$
(p\to q)\to p = (q\to p) \land ((p\to q)\to q).
$$
The Curry-Howard correspondence realizes this as a pair of operators (for any ...
- 18.4k
3
votes
3
answers
1k
views
Countable atomless boolean algebra covered by a larger boolean algebra
Suppose $Q$ is an atomless countable boolean algebra, and $B$ is an arbitrary atomless boolean algebra. $Q$ is unique modulo isomorphisms. There is a subalgebra in $B$ that is isomorphic to $Q$. There ...
- 4,219
24
votes
0
answers
3k
views
What's the smallest $\lambda$-calculus term not known to have a normal form?
For Turing Machines, the question of halting behavior of small TMs has been well studied in the context of the Busy Beaver function, which maps n to the longest output or running time of any halting n ...
- 1,734
7
votes
1
answer
795
views
Must there be a proper class of Reinhardt cardinals if there is a Reinhardt cardinal?
A cardinal is Reinhardt if $\kappa$ is the critical point of a nontrivial elementary embedding of $V$ to itself, where $V$ is the class of all sets. As Reinhardt cardinals are inconsistent with $\...
- 2,031
21
votes
2
answers
1k
views
Is factorial definable using a $\Delta_0$ formula?
The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?
- 4,713
3
votes
2
answers
510
views
Semilattices in atomless boolean algebras
Let S be a bounded semilattice without maximal elements. Can we always construct an atomless boolean algebra B, containing S as a subsemilattice, such that S is cofinal in B-{1}? That is, for every x&...
- 4,219
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
1
vote
1
answer
558
views
Natural Numbers
Let $L$ be a countable language and $M$ be a model of $L^N$ (the realization of $L$ in the natural numbers $N$) in which every recursive unary relation is expressible. Show that $M$ is not recursive.
- 236k
4
votes
2
answers
544
views
Membership problem in monoids
What is the simplest example of a monoid with undecidable membership problem? In other words, I'm looking for a concrete monoid $S$ such that there is no algorithm which takes elements $s_1,...,s_n$ ...
- 236k
9
votes
9
answers
2k
views
Existence of unknowable algorithms ?
Here by «algorithm» I mean a (halting) Turing machine with finite alphabet and memory.
Is it possible to obtain by purely existential (i.e. non-constructive) means the existence of an algorithm ...
- 236k
13
votes
0
answers
261
views
Big list of Hochster dual concepts
Let $X$ be a spectral space. Then there is a canonical space $X^\vee$ with the same points, same constructible topology, and the opposite specialization order. This is known as “Hochster duality”, and ...
- 11.8k
3
votes
1
answer
266
views
A question about the "information-content" of a very simple type of Turing machine.
All the Turing machines we consider have (1) a two-way infinite tape (2) one and only one halting
state (3) an alphabet of exactly two symbols-"1" and " "(or "blank"). Let n be any positive integer.
...
- 236k
13
votes
1
answer
2k
views
Are some interesting mathematical statements minimal?
Gödel's set $\mathrm{L}$, of constructible sets, decides many interesting mathematical statements, as the Continuum hypothesis and the Axiom of Choice.
Are some interesting mathematical questions, ...
- 236k
8
votes
0
answers
247
views
Large cardinals beyond choice and HOD(Ord^ω)
Are Reinhardt and Berkeley cardinals (and even a stationary class of club Berkeley cardinals) consistent with $V=\mathrm{HOD}(\mathrm{Ord}^ω)$ ?
It seems natural to expect no, but I do not see a proof....
- 7,545
5
votes
1
answer
597
views
The "first-order theory of the second-order theory of $\mathrm{ZFC}$"
$\newcommand\ZFC{\mathrm{ZFC}}\DeclareMathOperator\Con{Con}$It is often interesting to look at the theory of all first-order statements that are true in some second-order theory, giving us things like ...
- 236k
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
3
votes
1
answer
510
views
Harvey Friedman: The expanding mind
In reference 1, Friedman writes:
I discuss my efforts concerning 3 crucial issues in the foundations of mathematics that are deeply connected with the great work of Kurt Gödel.
[...]
B. Are there ...
- 2,031
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
0
votes
0
answers
95
views
Which algebraic structure characterizes the set of non-trivial qudratic residues in a finite field?
I understand this question may be too naive to ask, but I am unable to figure it out.
Suppose, $\mathbb{QR^*}$ denotes the set of all quadratic residues in a finite field except the identity element $...
8
votes
2
answers
774
views
Does PA prove (Artemov-style) the consistency of a stronger system?
There was a recent question on Artemov's paper here on MO Situation with Artemov's paper?
In one of the answers there it was asserted (apparently incorrectly - see Noah Schweber's comments and ...
- 1,974
14
votes
3
answers
1k
views
Examples of concrete games to apply Borel determinacy to
I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves ...
- 32.2k
9
votes
1
answer
261
views
Does there exist a geometric morphism between the effective and topological topoi? Does one arise from synthetic topology?
I'm presenting in final projects for my computability and computational topology courses on the connections between computability, continuity, and logic. As a mathematician/unmentored baby logician ...
- 48.8k
23
votes
4
answers
3k
views
Is Bauer–Hanson’s result “there is a topos where the Dedekind reals are countable” novel?
Last year, Andrej Bauer gave a talk showing that there is a topos in which the set of Dedekind reals is (sub)countable, and thus, you cannot prove that $\mathbb{R}$ is uncountable without LEM. He ...
- 48.8k
10
votes
4
answers
662
views
Deciding homomorphic images of De Bruijn graphs
The De Bruijn graph $B_n$ of
dimension $n$ (on the two-letter alphabet) is defined as the directed graph on
$2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in
2^{n+1}$ we put ...
5
votes
1
answer
493
views
Subcountability
In these slides of a talk Giovanni Curi shows that the generalized uniformity principle follows from Troesltra’s uniformity principle and from the subcountability of all sets, which are both claimed ...
- 2,031
8
votes
2
answers
483
views
Posets obtained from a semigroup by the definition $x \leq y \iff x \cdot y = x$
A po-groupoid is a groupoid $\langle A,\cdot\rangle $ such that the relation
defined by
$$
x \leq y \text{ if and only if } x \cdot y = x
$$
is a partial order on $A$, the order related to $\langle ...
- 1,124
8
votes
1
answer
236
views
Quiver and relations for a monoid related to Catalan numbers
Let $C_n$ be the monoid consisting of monotone maps $\{1,...,n\} \rightarrow \{1,...,n\}$ with $f(i) \leq i$ for all $i$.
The cardinality of $C_n$ is given by the Catalan numbers.
Consider $A_n= \...
- 38.6k
7
votes
0
answers
306
views
The constructive Eudoxus reals
Recently arxiv submitted a new paper (Andrej Bauer, James E. Hanson, The Countable Reals) claiming an incredible theorem that Dedekind reals are not sequence-avoiding, and furthermore obtaining a ...
- 35.5k
7
votes
0
answers
255
views
Is it decidable whether a statement about reals (in the language of ordered rings) is constructively provable?
The language of ordered rings is a first-order language with operators for $+$, $-$, and $\cdot$, constants for $0$ and $1$, and relations for $<$, $=$ and $>$.
To decide whether such a ...
- 6,353
0
votes
1
answer
248
views
Can there be a set larger than any well-founded set?
Based on this answer. Working in ZF-Reg., is it possible to have a non-well founded set that is strictly supernumerous to any well founded set?
If that is possible, then can this be extended ...
- 11.3k
3
votes
3
answers
345
views
Examples of cancellative normal semigroups
I've got a couple of things to test against normality in cancellative semigroups. A normal semigroup $S$ is one in which for any $x\in S$ we have $xS=Sx.$ This implies the Ore condition $$x,y\in S\...
- 10.5k