All Questions
6,026 questions
4
votes
0
answers
148
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 ...
CommunityBot
- 1
7
votes
1
answer
489
views
Is $ACA_0$ + 'True Arithmetic exists' interpretable in $ACA$?
Maybe someone here can help me with a question concerning second-order arithmetic. Consider the system $ACA_T := ACA_0 + \exists X \forall x (x \in X \leftrightarrow T(x))$, where $T(x)$ is a $\Pi_1^1$...
- 328
20
votes
1
answer
694
views
Is the theory of ordinals in Cantor normal form with just addition decidable?
This seems like it should be a pretty well-studied question but I can't seem to find an easy answer:
Is the theory $(\varepsilon_0, +, \omega^{\ \cdot}, 0, 1)$ decidable?
From Is the theory of $(\...
- 47.4k
4
votes
0
answers
261
views
Läuchli's "intermediate thing"
On page 230 of An abstract notion of realizability ..., Läuchli writes the following:
If we drop the restrictions put on $\Theta$, then we get classical logic in one case and an intermediate thing in ...
- 20.5k
7
votes
2
answers
568
views
Proof of ¬(¬1 ⊗ ¬1) in tensorial logic
I believe I once had a proof of this proposition, but it's been lost to the mists of time and old hard drives, so who knows if it was correct, and try as I might I can't seem to reproduce it.
Is it ...
- 275
-2
votes
1
answer
181
views
What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]
As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
- 3,065
8
votes
1
answer
280
views
What is the consistency strength of "Singular worldly that is inaccessible in an inner model"?
In short, what can we say about the consistency strength of "$\kappa$ is a singular worldly and inaccessible in an inner model"?
Clearly, $0^\#$ exists since we have a singular cardinal ...
- 9,902
0
votes
0
answers
114
views
Clarifications sought on the paper on the semigroup associated with a free polynomial by Ali Abbas and Abdallah Assi
I have three questions regarding the proof of Proposition 4 on page 4 of this paper here. For those interested in addressing these questions, please refer to some definitions in the first two or three ...
- 63.9k
3
votes
0
answers
211
views
Intuitionistic set-theoretic geology
Work in ZF, if there are proper class many supercompact cardinals, then all grounds are uniformly definable. Hence under reasonable assumption, we can have choiceless set-theoretic geology.
But can we ...
- 63.9k
13
votes
1
answer
933
views
Consistency strength of HoTT
What is the consistency strength of Homotopy type theory (HoTT) relative to various set theories (e.g., are there any known set theories that it can interpret)? Does this question even make sense?
- 6,353
1
vote
1
answer
309
views
Is reflection on Grothendieck universes equivalent to TG set theory?
Let take the first order set theory whose axioms are Extensionality, Separation and Universal reflection.
By $\operatorname {unv}(x)$, denoting "$x$ is a universe", we'll take it to mean ...
- 11.3k
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
15
votes
0
answers
244
views
Natural examples of Borel surjections without right inverse
As discussed in this question, in general a Borel surjection $f:\mathbb{R}\rightarrow\mathbb{R}$ may not have a Borel right inverse, namely a $g$ such that $f\circ g=id$, although there is always a ...
- 623
67
votes
10
answers
14k
views
Arguments against large cardinals
I started to learn about large cardinals a while ago, and I read that the existence, and even the consistency of the existence of an inaccessible cardinal, i.e. a limit cardinal which is additionally ...
- 4,985
40
votes
1
answer
2k
views
Rigid non-archimedean real closed fields
Update. The question has been recently answered in the positive by David Marker and Charles Steinhorn (as in indicated in Marker's answer). Note that Remark 3 below is now expanded by reference to a ...
- 3,530
3
votes
0
answers
161
views
On generators of the multiplicative semigroup $\{r\in\mathbb Q:\ r>1\}$
The set $M=\{r\in\mathbb Q:\ r>1\}$ is a commutative semigroup with respect to the multiplication. For any integers $a>b\ge1$, we clearly have
$$\frac ab=\prod_{n=b}^{a-1}\frac{n+1}n.$$
So the ...
- 15.6k
3
votes
0
answers
92
views
Reference for the monoidal category structure $X \otimes Y = X + Y + X \times Y$ on a distributive category
Given a distributive category $\mathscr C$ (more generally a rig category), we can define a (semicocartesian) monoidal category structure on $\mathscr C$ with tensor product given by $X \otimes Y := X ...
- 10.7k
11
votes
3
answers
949
views
Some "axiom of choice" and "dependent choice" issues
I am probably about to ask some fairly basic questions, and yet I have found it quite hard to find the answers to these.
If I understand correctly, mathematicians tend to be quite happy working with ...
- 623
2
votes
0
answers
192
views
Can PA be acyclically complete?
Any formula $\phi$ in the first order language of arithmetic is to be called acyclic if and only if we can associate with it an acyclic undirected graph whose nodes are the variable symbols occurring ...
- 11.3k
4
votes
0
answers
143
views
Part II to Ketonen's "Set Theory for a Small Universe I. The Paris-Harrington Axiom"
There is an unpublished manuscript "Set Theory for a Small Universe I. The Paris-Harrington Axiom" by Ketonen which appeared early in the study of the Paris-Harrington theorem, around 1979. ...
- 2,031
19
votes
2
answers
1k
views
Is the theory of a partial order bi-interpretable with the theory of a pre-order?
A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric.
A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
- 2,467
8
votes
0
answers
157
views
How to define Dedekind reals and Eudoxus reals such that they are equivalent to unmodulated Cauchy reals
In constructive mathematics without choice, we have three different versions of the real numbers (each embedding into the next).
Regular Cauchy reals (functions $f : \mathbb N \to \mathbb Q$ such ...
- 6,353
6
votes
0
answers
298
views
What are these non-classical versions of ZFC defined by realizability?
See Kleene realizability in Peano arithmetic for a similar question, but about PA instead of ZFC. (In particular, an answer as specific as Emil Jeřábek's answer would be great!)
In the context of ...
- 6,353
10
votes
3
answers
1k
views
Categoricity in second order logic
Hi,
It's shown by an easy cardinality argument that there are complete second-order theories that are not categorical (have more than one model up to isomorphism). Anyone knows of a concrete example ...
- 17.7k
6
votes
1
answer
197
views
Is there a 1-generic degree g such that Th(D(< g)) is more complicated than true arithmetic?
I am currently reading an article titled "Embedding and Coding Below a 1-Generic Degree" by Greenberg and Montalbán(link to a free source:https://pi.math.cornell.edu/~erlkonig/Papers/...
- 1,780
12
votes
5
answers
3k
views
Difference between constructive Dedekind and Cauchy reals in computation
If the Axiom of Countable Choice (ACC)
$$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \forall n \in \mathbb{N} . \varphi [n, f(n)] $$
...
- 6,353
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 ...
- 5,827
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
2
votes
3
answers
445
views
Existence of equivalence checking algorithm
Set D : Set of decision algorithms
X∈D if and only if
X is a Turing machine algorithm with finite length
takes one input i, binary number
X(i)=0 or X(i)=1 or X(i) runs forever.
Definition: ...
- 12.9k
18
votes
2
answers
1k
views
Is there a name for sets for which it is easier to test membership than to find members---and vice versa?
This is a question my son Bob asked me. For some sets it is relatively easy
to test for membership but a lot more difficult to find members, and for others
the reverse is true. Here is an elementary ...
- 236k
4
votes
1
answer
394
views
How many variations can be derived from Gödel's fixed-point lemma?
Recently, I attempted to generalize the fixed-point lemma and proved the following:
Let $ F_n $ be the set of all formulas with $ n $ free variables in $L_{PA}$.
Let us define the unary function $ f $ ...
- 127
5
votes
1
answer
167
views
Cardinality of separating families on an infinite cardinal $\kappa$
Let $\kappa$ be an infinite cardinal. We say ${\cal S}\subseteq {\cal P}(\kappa)$ is separating if whenever $a\neq b\in \kappa$ there is $T\in {\cal S}$ such that $|T\cap\{a,b\}| = 1$. Let $\...
- 2,206
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?
- 35.5k
2
votes
0
answers
142
views
Can a path in Kleene's $\mathcal{O}$ enumerate all of the computable reals via uniform diagonalization?
It's a well-known fact that there are computable diagonalization functions on Baire space $\mathbb{B} = \mathbb{N}^\mathbb{N}$ (i.e., functions which take a sequence $(r_i)_{i\in \mathbb{N}}$ of ...
- 12.5k
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
$...
- 236k
2
votes
0
answers
100
views
Realizing arithmetic hierarchy in algebraic number theory
Is it possible to realize arithmetic hierarchy in algebraic number theory?
For example, consider a $\Pi^0_4$ statement of the form $\forall x \exists y \forall z \exists w \phi(x,y,z,w)=0$ where $\phi$...
- 593
4
votes
1
answer
274
views
Transfinitely iterated limit computability
Call a real $x$ limit computable iff there is a Turing machine $T$ such that, for any $i\in\omega$, there is $t(i)\in\omega$ such that the $i$th entry on the tape is not changed after time $t(i)$ and ...
- 236k
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 ...
- 96
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 ...
- 236k
106
votes
19
answers
12k
views
When are two proofs of the same theorem really different proofs
Many well-known theorems have lots of "different" proofs. Often new proofs of a theorem arise surprisingly from other branches of mathematics than the theorem itself.
When are two proofs really the ...
- 35.5k
13
votes
1
answer
2k
views
Shelah's book on "Classification Theory"
As we know one of the most important and fundamental books in stability, simplicity, forking and ... classification theory, is Shelah's "Classification Theory" where lots of original ideas ...
- 241
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
37
votes
4
answers
2k
views
Is the field of constructible numbers known to be decidable?
By the field of constructible numbers I mean the union of all finite towers of real quadratic extensions beginning with $\mathbb{Q}$. By decidable I mean the set of first order truths in this field, ...
- 4,713
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 ...
- 47.4k
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 ...
- 234
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 ...
- 16.2k
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
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
9
votes
2
answers
473
views
Completing half of Hilbert's program: Foundations that are conservative over Peano Arithmetic
The goal of the Hilbert program was to find a complete and consistent formalization of mathematics. Gödel's first incompleteness theorem establishes that completeness is impossible with first-order ...
- 6,353
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 ...
- 13.4k