All Questions
6,026 questions
5
votes
0
answers
108
views
Structure of well-ordered commutative monoids
Let $(M,+)$ be a commutative monoid. Let $<$ be a well-ordering on $M$, where
$\forall a\in M,\ 0\leq a$
$\forall a,b,c\in M,\ a<b\Rightarrow a+c<b+c$
The first condition means $M$ will be ...
- 18.7k
5
votes
1
answer
361
views
Why is it not possible to define the necessity operator internally $\Box: \Omega \to \Omega$ in a topos?
I am looking for ways to internalize the modal operator of necessity $\Box$, ending up with a morphism $\Box: \Omega \to \Omega$ satisfying the necessitation rule (if $\phi$, then $\Box \phi$) and the ...
- 12.9k
4
votes
1
answer
436
views
Can we have an axiom that refers to itself and the prior axioms of the theory it is an axiom of?
I know that this question is little bit imprecise, I'll try to present it in the best I can.
Can one have an axiom which is self referential with respect to itself and the theory in which it belongs?
...
- 236k
16
votes
5
answers
4k
views
Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?
Gödel's original proof of the First Incompleteness theorem relies on Gödel numbering.
Now, the use of Gödel numbering relies on the fact that the Fundamental Theorem of Arithmetic is true and thus the ...
- 4,713
0
votes
0
answers
62
views
Is stratified Z - Infinity + there is a set as big as its powerset, consistent if NF is consistent?
The question of consistency of $\sf NF$ can be seen to be equivalent to the question of whether the theory "Stratified $\sf Z$ - Regularity - Infinity + There exists a set as big as its powerset&...
- 11.3k
2
votes
1
answer
164
views
Cardinality of maximal diverse families
Let $\kappa\geq \aleph_0$ be a cardinal. We say a collection ${\cal E} \subseteq {\cal P}(\kappa)$ is diverse if $|(A \setminus B) \cup (B \setminus A)| = \kappa$ whenever $A\neq B\in {\cal E}$. A ...
- 13.4k
3
votes
2
answers
622
views
Can uncountable sets be proved to exist in this variant of ZFC with definability restrictions?
If we restrict all parameters in the set building axioms of $\sf ZFC$ to definable sets, would the celebrated Cantor's theorem still apply? Can existence of uncountable sets be proven at all?
The set ...
- 32.2k
1
vote
2
answers
832
views
Intension vs. Extension: Coextensive relations in model and set theory
(originally posted at MSE as Same same but different: Coextensive relations in model and set theory, slightly modified)
The official definition of a structure in model theory in its presumably most ...
- 1,446
2
votes
1
answer
973
views
Compactness and completeness in Gödel logic
The standard proof of the completeness theorem in first-order Gödel logic is based
on a first-order countable language. I want to know that is there any proof of the completeness theorem in first-...
- 4,219
4
votes
0
answers
166
views
Consistency of definability beyond P(Ord) in ZF
Is it consistent with ZF that the satisfaction relation of $L(P(Ord))$ is $Δ^V_2$ definable? More generally, is it consistent with ZF that there is a $Δ^V_2$ formula (taking $α$ as a parameter) that ...
- 7,545
7
votes
2
answers
230
views
Why does Weihrauch reducibility make use of multi-functions?
This is probably a kinda dumb question, but why is Weihrauch reducibility defined in terms of multi-functions (i.e. why isn't it just the degree structure of regular functions under that reducibility)?...
- 4,359
2
votes
1
answer
176
views
Generating totally ordered free commutative monoids
Let’s say I have a set $A$. I build the free commutative monoid $M$ generated by $A$.
When can a well-order on $A$ be extended to $M$, in a way that is compatible with its monoid structure? I am ...
- 3,738
4
votes
1
answer
338
views
Expressiveness in arithmetic
Let $\mathcal{S}$ be a formal system for arithmetic (e.g. $P$ or $PA$), $f:N^q\rightarrow N^p$ a function of $N^q$ on $N^ p$ and $\alpha(\mathbf{x})$ a formula of $\mathcal{S}$ with $p$ free variables....
- 236k
5
votes
1
answer
564
views
Hilbert's and Gödel's expanded definition of "Recursive Function"
There is a very interesting comment in this post:
I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the ...
- 48.8k
5
votes
1
answer
294
views
End-extension in Gödel's constructible universe
Given two ordinals $\alpha < \beta$, considering the subsets of Gödel's constructible universe, one say that $L_\beta$ is a $\Sigma_n$ end-extension of $L_\alpha$ (and $L_\alpha$ is an $\Sigma_n$ ...
- 2,031
3
votes
2
answers
1k
views
Lindenbaum algebras and models
Sorry for this question out of the blue (especially if its answer should be trivial, obvious, or folklore):
(When and how) can we construct models of a consistent
first order theory $T$ from its
...
- 1,446
10
votes
1
answer
216
views
Is $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$ still the largest known polynomially bounded o-minimal structure so far?
From Chris Miller's paper in 1995, the structure $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$,is the largest known polynomially bounded o-minimal structure as of that time. I wonder if ...
- 2,519
1
vote
0
answers
139
views
Monads for proof relevance in type theory
I am just getting started with homotopy type theory. After watching an introductory lecture, I was attracted to the concept of proof relevance. In my understanding, the core idea here is to elevate ...
- 1,313
21
votes
1
answer
1k
views
Are the real numbers isomorphic to a nontrivial ultraproduct of fields?
Let $K_1, K_2, \dots$ be a countable sequence of fields, and let $\prod_{\mathcal F} K_i$ be the ultraproduct with respect to some nonprincipal ultrafilter $\mathcal F$.
Question: Can there be a field ...
- 236k
8
votes
0
answers
149
views
What is this quotient of the free product?
Previously asked at MSE. The construction here can generalize to arbitrary algebras (in the sense of universal algebra) in the same signature with the only needed tweak being the replacement of "...
- 20.5k
5
votes
1
answer
278
views
Would strengthening Foundation and Choice in NBG, make it equi-consistent with MK?
This is a follow up to an earlier question about strengthening of foundation in relation to proving the consistency of ZFC. It was shown that it would achieve that, but it may fail short of MK. Here, ...
- 236k
8
votes
1
answer
338
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 236k
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
7
votes
1
answer
759
views
Are there any recent advances in formalizing the undecidability of $\mathit{CH}$?
The website Formalizing 100 Theorems by Freek Wiedijk contains a list of some theorems that were chosen at some point as good candidates for formalization (because of their complexity, their ...
- 4,713
5
votes
1
answer
265
views
Long chains of Dedekind finite sets
This is a variation on this question with amorphous cardinals replaced with dedekind finite sets.
Dedekind finite sets are sets that have no countable subset, and it is well known that this is a ...
- 32.5k
12
votes
1
answer
556
views
Building the real from Dedekind finite sets
It is well known that the real numbers can be countable union of countable sets by starting with GCH and taking a finite support permutations while collapsing all of $\aleph_n$ for natural $n$.
The ...
- 4,316
13
votes
1
answer
565
views
Long chains of amorphous cardinalities
An amorphous set is an infinite set that cannot be partitioned into 2 infinite subsets. An amorphous cardinality is the cardinality of an amorphous set. Working in $\sf ZF$, it is consistent that ...
- 236k
11
votes
3
answers
582
views
What would you do with a new model of linear logic?
I have been working for some time with collaborators developing some models of linear logic which we are confident are new. However, none of us is deep enough in the field to answer the sceptic's ...
12
votes
2
answers
910
views
Bernstein's proof of the continuum hypothesis
In the paper The Continuumproblem, Felix Bernstein introduces a new axiom and uses it to conclude the continuum hypothesis.
(1) As the paper is relatively old and the writing style is somehow informal,...
- 20.5k
2
votes
0
answers
118
views
Uniformization and functions on Turing degrees
Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ?
$\mathcal{D}_t$ is the set of Turing ...
- 7,545
10
votes
2
answers
822
views
Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)?
In the math.se question Proof of no prime-representing polynomial in 2 variables, Alon Amit asks if Ribenboim's claim that a prime-representing polynomial (a Diophantine polynomial in which the ...
- 9,114
19
votes
2
answers
1k
views
Which graphs are elementarily equivalent to their own disjoint sums?
In Stefan Geschke's recent
question,
one of the solutions observed that the graph consisting of
a single infinite beaded chain, a $\mathbb{Z}$-chain where
each integer is connected to its nearest ...
- 4,713
1
vote
0
answers
106
views
Quasi polynomial algorithm for NP complete problem [closed]
I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
- 3,065
1
vote
0
answers
150
views
What is the strength of adding this de-schematizing inference rule to Ackermann's set theory?
Language: first order logic with equality, membership, and a constant symbol $W$.
Axioms:
Extensionality: $\forall z \, (z \in x \leftrightarrow z \in y) \to x=y$
Comprehension: $\exists x \forall y \,...
- 11.3k
4
votes
1
answer
332
views
Cohen forcing: why is the cardinality of $\mathcal P \left({\omega}\right)$ in ${\bf L}(\mathcal P \left({\omega}\right))$ independent of G?
This is a part of exercise E4 from Chapter VII of Kunen's Set Theory.
The hint (courtesy of A. Miller) goes like this: let ${\mathbb P} = Fn(I,2)$, $(|I| \geq \omega_{1})^M$. Let G be ${\mathbb P}$-...
- 5
4
votes
1
answer
254
views
Are there atoms in the lattice of intermediate logics?
A few days ago I stumbled upon this question on MS. The question is: Does the lattice of intermediate logics have an atom, i.e. an element that is strictly stronger than IPC but not strictly stronger ...
- 47.4k
8
votes
2
answers
536
views
Whether the pure implicational fragment of intuitionistic propositional logic is a finitely-many valued logic
Gödel (1932) showed that intuitionistic propositional logic (more precisely, any fragment with implication and disjunction) is not a finitely many-valued logic. What about the pure implicational ...
- 47.4k
1
vote
0
answers
132
views
Are gaps and loopy games interchangeable in the Surreal Numbers?
The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...
- 39.9k
10
votes
1
answer
416
views
Consistency strength of strongly compact cardinal
Where can I find a proof that strongly compact cardinal has higher consistency strength than Woodin cardinal, or even just strong? Recall that a strongly compact cardinal itself may not be strong, ...
- 8,099
18
votes
1
answer
1k
views
Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$
Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$.
Alice's color is red and Bob's color is blue. In each step, for each $s\in S$, a player will choose finitely many ...
- 13.4k
2
votes
1
answer
235
views
End elementary extension in infinitary logic of some $L_\alpha$ producing a $L_\beta$
Let $L_\alpha$ be some admissible level of the constructible hierarchy and $M \supseteq L_\alpha$ an extension of $L_\alpha$. I am looking for conditions under which $M \simeq L_\beta$. It is not ...
- 2,031
1
vote
0
answers
121
views
Is this modified H. Friedman theory bi-interpretable with ZFC + ORD is Mahlo?
The following theory is a modification of Harvey Friedman $\sf K(W)$ theory.
Language: first order logic with equality, membership, and a constant symbol $W$.
Axioms:
Extensionality: $\forall z \, (z ...
- 11.3k
2
votes
1
answer
427
views
What is the strength of adding limitation of size and a simple version of reflection to Ackermann set theory?
The following theory is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ denoting the class ...
- 11.3k
4
votes
2
answers
1k
views
Semantics of Higher-Order Logics
I've been trying to get to grips with the various semantics commonly discussed in formal logic. Specifically, the nature and role of interpretations of first and higher-order logics is slightly ...
- 1,446
9
votes
1
answer
255
views
What are these generalizations of the principles of omniscience called?
I will give some principles that are slightly stronger versions of the principles of omniscience. Despite being about the natural numbers, they imply their analytic versions! Under countable choice (...
- 179
6
votes
0
answers
125
views
From HODs to corresponding models of AD
If $M$ is HOD of a model $N$ of $\text{AD}^+ + V=L(P(ℝ))$, what kind of forcing construction in $M$ gives back such an $N$?
HODs for $\text{AD}^+ + V=L(P(ℝ))$ are conjectured (and under anti-large ...
- 7,545
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.
- 10.5k
2
votes
0
answers
80
views
An alternative definition for finitely generated (and principal) ideals in a semigroup
Let $S$ be a semigroup. An ideal (of $S$) is a subset $I$ of $S$ such that $SI$ and $IS$ are both contained in $I$. The non-empty ideals constitute a subsemigroup, $\mathfrak I(S)$, of the power ...
- 10.5k
7
votes
1
answer
205
views
Variation on definition of logical functors avoiding power objects
Without power sets in meta-theory not every Grothendieck topos is an elementary topos, Set is still Grothendieck, but it lacks power objects.
Now I am looking for a definition of a logical functor ...
- 66.8k
4
votes
1
answer
232
views
Simplified method of building an Aronszajn tree
There is a very interesting method to build an Aronszajn tree in Judith Roitman's "Introduction to Modern Set Theory", on pages 100-102. In short, we build a tree $T$ in which the nodes are ...
- 11.4k