All Questions
6,026 questions
9
votes
2
answers
3k
views
Is Turing degree actually useful in real life? [closed]
In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this?
Edit: Given that we cannot explicitly and mechanically understand ...
- 4,713
-4
votes
0
answers
133
views
Which arithmetic\set theory is synonymous with this theory?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
Define: $x > y \iff y < x$
Define: $x \leq y \iff x < y \lor x=y$
$ \textbf{...
- 11.3k
-4
votes
1
answer
173
views
To which arithmetic\set theory this theory is bi-interpretable?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
$ \textbf{Axioms:}$
$ \textbf{Order:} \ x < y < z \to x < z $
$ \textbf{...
- 11.3k
12
votes
4
answers
1k
views
Is this theory synonymous with PA?
Language: Mono-sorted first order logic with equality.
Extralogical Primitives: $<, \in$
Define: $x \leq y \iff x < y \lor x=y$
$\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
- 11.3k
12
votes
1
answer
227
views
Is there a $\Pi_2$ sentence $A$ such that $\text{ZFC}^- + A$ proves powerset?
This is a follow-up to this question.
Let $\text{ZFC}^-$ be ZFC without powerset and with collection rather than replacement, as described here.
Is there a $\Pi_2$ (or perhaps $\Sigma_2$) sentence $A$ ...
- 7,545
5
votes
0
answers
67
views
Definable pseudo-standard predicates in Internal Set Theory
Consider the usual language $\mathcal{L}=(\in, \mathrm{st})$ of Nelson's Internal Set Theory, and a unary $\mathcal{L}$-predicate $P$. For an $\mathcal{L}$-formula $\varphi$, let $\varphi^P$ denote ...
- 16.6k
5
votes
0
answers
159
views
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
In his wonderfully titled paper Can you take Solovay's inaccessible away? Shelah showed that if every $\mathbf{\Sigma}^1_3$ set of reals is Lebesgue measurable, then $\omega_1$ is an inaccessible ...
- 12.5k
4
votes
0
answers
188
views
An analogue to Robinson's theorem for Kalmar-elementary functions
Julia Robinson proved that the family of all unary computable total functions is the smallest class containing $S$, $\mathrm{Exc}$, and closed under composition, addition and inversion of surjective ...
- 5
18
votes
2
answers
3k
views
(Fictive) story of a time where people reasoned only up to isomorphism
I seem to remember reading once a story that some mathematician had written to justify the use of categories, or isomorphisms or equivalences, or something like that. The story goes something like ...
- 8,481
2
votes
0
answers
92
views
Geometric interpretation of flags and the role of the rook monoid and Kazhdan–Lusztig theory in $M_n(\mathbb{C})$
Let $G = GL_n(\mathbb{C})$, $B$ be its Borel subgroup, and $P$ a parabolic subgroup. The space $G/B$ corresponds to complete flags in $ \mathbb{C}^n$, and $G/P$ corresponds to partial flags. The ...
- 141
3
votes
0
answers
120
views
References on P vs NP under various axiomatic systems
I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem.
This problem has resisted attacks ...
- 31
-4
votes
0
answers
189
views
Can ZFC be interpreted in this infinitary logic theory?
Working in language $\mathcal L_{\Omega^+,\Omega^+}$ where $\Omega$ is the first strongly inaccessible cardinal. If we add a primitive partial $\Omega$-ary function $F$ and a primitive constant $\...
- 11.3k
8
votes
1
answer
539
views
Theory of addition and a predicate that recognizes powers of 2
What is the complexity of the theory of addition (Presburger arithmetic) augmented by a unary predicate that recognizes powers of 2?
- 16.6k
2
votes
1
answer
162
views
Are Cohen Generics Minimal Covers?
Are Cohen generics (in $2^\omega$) minimal covers?
I'm ultimately interested in this question for some more effective notion of forcing but I realized I wasn't sure how to show this even assuming full ...
- 44.4k
6
votes
1
answer
243
views
Is it possible that the number of $\mathcal{T}$-algebras is an arithmetic progression?
For a single-sorted algebraic theory $\mathcal{T}$ denote by $t_n$ the number of $\mathcal{T}$-algebras with $n$ elements (up to isomorphism). Is there an example for $\mathcal{T}$ such that ...
- 14.6k
-5
votes
0
answers
250
views
Can Cardinality Theory capture ZFC?
Cardinality Theory "CT" is a theory of sets of cardinals and links between them, only sets of cardinals can be assigned cardinalities. The links are unordered edges linking cardinals, they ...
- 11.3k
4
votes
1
answer
364
views
Values attained by the coheight of $(H \setminus H^\times)^k$ as a function of $H$ and $k$
Edit (Apr 24, 2017). I'm updating this post in the light of the latest developments of a related thread.
Let $H$ be a multiplicatively written, commutative monoid, and set $M := H \setminus H^\times$,...
CommunityBot
- 1
6
votes
0
answers
188
views
Is there a characterization of measurables in terms of indiscernibles?
There is a characterization of $\alpha$-Erdős cardinals in terms of sets of indiscernibles of order type $\alpha$. There is also a characterization of Ramsey cardinals in terms of sets of good ...
- 2,031
18
votes
3
answers
1k
views
Computable nonstandard models for weak systems of arithmetic
By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of ...
- 16.6k
8
votes
0
answers
231
views
Complexity of integer programming with added predicates
A classical theorem in Integer Programming by Lenstra says that any integer system
$$A x \le b$$
can be solved in polynomial time, where $A \in \mathbb{Z}^{m \times n}, x \in \mathbb{Z}^n, b \in \...
- 16.6k
13
votes
0
answers
800
views
Reference request for a complete and formal Duality Principle in category theory
Most textbooks on category theory only sketch the meaning of the Duality Principle. But even when they do it more formally, I have only seen a version so far which concerns the language of a (single) ...
- 63.1k
0
votes
0
answers
61
views
Defining rank of an abelian subgroup using the second centralizer
I recently posted this on MSE, but didn't receive any feedback; so I'm posting it on MO.
I recently came across this article which explored the maximal abelian subgroups of the symmetric group $S_n$. ...
- 63.9k
16
votes
2
answers
713
views
Is (Z,+,0,1,P2,P3) decidable?
Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable?
I know that adding just one of P2, P3 to Presburger keeps it decidable, ...
- 16.6k
10
votes
1
answer
556
views
Beyond Presburger Arithmetic
Do there exist known examples of predicates $P$ (possibly functional) such that
1) $P$ admits a first-order definition in the language ${\Bbb N}(+,\times,0,1)$;
2) $P$ admits no definition that does ...
- 4,713
5
votes
1
answer
310
views
Is there a statement in Presburger arithmetic about primes this simple heuristic fails for?
I came up with the following conjecture while thinking about ways to formulate some heuristics about primes:
Conjecture: Given a statement $s$ in Presburger arithmetic, using an additional unary ...
- 16.6k
298
votes
34
answers
53k
views
What are some reasonable-sounding statements that are independent of ZFC?
Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC."
For example, suppose $A$ is an abelian group such ...
- 328
8
votes
1
answer
196
views
Weakly compact cardinals in $L$: how long do branches take to appear?
Throughout, we work in $\mathsf{ZFC+V=L+}$ "There is a weakly compact cardinal," $\kappa$ is the first weakly compact cardinal and "tree" means "subtree of $2^{<\kappa}$ of ...
- 9,902
5
votes
0
answers
137
views
Cone avoidance and $\Pi^0_1$-classes
Suppose $X \subseteq 2^{\omega}$ is nonempty and $\Pi^0_1$ relative to $a$. Assume $c_0 \nleq_T b_0 \oplus a$ and $c_1 \nleq_T b_1 \oplus a$. Must there exist some $y \in X$ such that $c_i \nleq_T ...
- 20.5k
6
votes
2
answers
321
views
Set theoretical foundations for derived categories
A modern approach to derived functors, that has been shown to be useful in a number of different circunstances is that of a derived category (see the book by Yakutieli, for example, here).
However, it ...
- 15.9k
4
votes
0
answers
100
views
Explicit superexponential growth for Presburger Arithmetic
Fischer and Rabin proved a superexponential bound $2^{2^{cn}}$ for the worst-case length of a proof of a proposition of length $n$ in Presburger arithmetic. The result is in
Michael J. Fischer and ...
- 16.6k
7
votes
1
answer
333
views
Why include $0$ and $1$ in the signature of Presburger arithmetic?
I recently became interested in some problems concerning decidability of extensions of Presburger arithmetic. However, being a number-theorist rather than a logician, I am confused by some notational ...
- 16.6k
7
votes
1
answer
232
views
Is Presburger arithmetic in stronger logics still complete?
Originally asked at MSE:
Let $\Sigma=\{+,<,0,1\}$ be the usual language of Presburger arithmetic. Given a "reasonable" logic $\mathcal{L}$, let $\mathbb{Pres}(\mathcal{L})$ be the $\...
- 16.6k
19
votes
2
answers
2k
views
Can there exist a definable "ultrafilter" on the ordinals?
Can there exist a model $\textit M$ of $\textit{ZF}$ (or $\textit{ZFC}$) that contains a definable nontrivial "ultrafilter" on $\sf Ord^{\textit M}$? By this I mean that there is some ...
- 17.7k
46
votes
8
answers
12k
views
What are some proofs of Godel's Theorem which are *essentially different* from the original proof?
I am looking for examples of proofs of Godel's (First) Incompleteness Theorem which are essentially different from (Rosser's improvement of) Godel's original proof.
This is partly inspired by ...
- 6,367
14
votes
3
answers
2k
views
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
- 4,713
2
votes
2
answers
335
views
Are there models of ZF in which all uncountable sets are super/hyper/ultra-singular?
This question is a follow up to that posting.
Recall the definition of super/hyper/ultra-singular set given in the linked posting.
Is there a model of $\sf ZF$ in which every uncountable set is super-...
- 2,206
5
votes
1
answer
415
views
Intuition for the "internal logic" of a cotopos
Let $\mathcal{E}$ be an elementary topos. By definition, $\mathcal{E}$ is a category that has finite limits, is Cartesian closed, and has a subobject classifier $\Omega$. This subobject classifier can ...
- 35.5k
5
votes
1
answer
422
views
What is the relationship between non-existence of those kinds of singular sets and AC?
Let's say a set $A$ is super-singular, if and only if, there exists a set $x$ such that $|A|=|\bigcup x|$ and $| A| > |x|$, and for each $y \in x$ we have: $ |y| \not > |x|$ .
A set $A$ is ...
- 11.3k
26
votes
3
answers
7k
views
Presburger Arithmetic
Presburger arithmetic apparently proves its own consistency. Does anyone have a reference to an exposition of this? It's not clear to me how to encode the statement "Presburger arithmetic is ...
- 35.5k
30
votes
6
answers
3k
views
Mathematics without the principle of unique choice
The principle of unique choice (PUC), also called the principle of function comprehension, says that if $R$ is a relation between two sets $A,B$, and for every $x\in A$ there exists a unique $y\in B$ ...
- 48.8k
2
votes
1
answer
428
views
Logic which depends on the perspective? (Semantic space of logic / perspectivism)
I am not sure if this question is appropriate for MO, since I have only a basic understanding of Boolean logic, and am maybe not qualified to ask questions beyond that, but still I will try to write ...
CommunityBot
- 1
5
votes
1
answer
435
views
Constructive compactness for countable models?
The compactness theorem for countable (Tarski?) models is equivalent to the weak König's lemma by a result of H. Friedman and others as noted here, in the context of classical logic. The weak König's ...
- 16.6k
24
votes
4
answers
2k
views
Infinite mathematics as non-standard finite mathematics?
I have in mind something like the following:
Start with some suitable version of "finite" mathematics. Some possibilities might be maybe ZFC with a suitable anti-infinity axiom, the topos $\mathbf{...
- 16.6k
8
votes
3
answers
516
views
Is there a constructive version of internal set theory?
Is there a theory T such that:
T includes all the axioms of CZF.
T includes the Idealization, Standardization, and Transfer schemas from IST.
Every axiom of T is a theorem of IST.
T has Church's rule....
- 16.6k
8
votes
2
answers
2k
views
Axiom to exclude nonstandard natural numbers
In Peano Arithmetic, the induction axiom states that there is no proper subset of the natural numbers that contains 0 and is closed under the successor function. This is intended to rule out the ...
- 16.6k
1
vote
0
answers
96
views
Determine equivalences in the generated collection of subgroups and quotients
Let $A$ be an abelian group, and $B_1, B_2, \dots, B_m$ be subgroups of $A$. Define the family of subgroups $\mathcal{D}_0 = \{ \{0\}, A, B_1, B_2, \dots, B_m \}$.
Let $\mathcal{C}_1$ be the ...
- 807
37
votes
6
answers
6k
views
Who needs Replacement anyway?
The set theory ETCS famously comes without the Replacement axiom schema (or an equivalent) that is part of ZFC. One (to me, not apparently useful) set that one cannot build in ETCS is $\coprod_{n\in \...
CommunityBot
- 1
4
votes
1
answer
239
views
True or false? Every left or right cancellative, duo semigroup is cancellative
A semigroup $S$ is duo if $aS = Sa$ for all $a \in S$, where $aS := \{ax: x \in S\}$ and similarly for $Sa$; for instance, every commutative semigroup is duo, and so is every group. On the other hand, ...
- 10.5k
3
votes
1
answer
170
views
Reverse mathematics on lightface $\Pi^1_1$-uniformization for unary relation
It is known that the following form of $\Pi^1_1$-uniformization is equivalent to $\Pi^1_1$-Comprehension over $\mathsf{ATR}_0$ (cf. VI.2.6 of Simpson's book) :
(Kondo's uniformization theorem) For ...
- 126
2
votes
0
answers
187
views
Semantic equivalence between mathematical proofs
Sometimes, we recognize two proofs of the same claim to be the "same" proof. In some cases, this sameness is obvious -- for example, the proofs that $\sqrt{2}$ and $\sqrt{3}$ are irrational ...
- 225