All Questions
1,135 questions
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
9
votes
3
answers
3k
views
What does the axiom of replacement mean and why should I believe it?
Here Professor Blass describes the following cumulative hierarchy of sets:
Begin with some non-set entities called atoms ("some" could be "none" if you want a world consisting exclusively of sets), ...
- 101
9
votes
1
answer
701
views
Case study: what does it take to formulate and prove Quillen's small object argument in ZFC?
I'm getting a bit lost over at Peter Scholze's interesting question about removing the dependence on universes from theorems in category theory. In particular, I'm being forced to admit that I don't ...
- 64k
9
votes
3
answers
560
views
Equational theories determined by "identities without variables"
How to characterize equational theories $T$ which have the following property: for any two terms $t(x_1,...,x_n)$ and $t'(x_1,...,x_n)$ in the signature of $T$, if for any closed terms (i. e. terms ...
- 18.4k
9
votes
3
answers
848
views
Conjecture on NP-completeness of tesselation of Wang Tile up to finite size
Motivated by these following questions on tessellation:
coloring in lattice
Reference for Wang Tile
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
...
user46976
8
votes
1
answer
738
views
Stationarity and Fodor's lemma for a (nice) poset?
The notion of a stationary set is peculiar in that it applies to subsets of certain very particular posets -- ordinals or powersets. At least to a non-set-theorist, the situation seems to beg for the ...
- 64k
8
votes
2
answers
1k
views
Surreals and NSA: some foundational issues
Surreals and NSA: some foundational issues.
A.
Leaving aside the whole internal machinery of surreals (with funny questions like is $\omega$ an entire number and if yes is it odd or even, simple, a ...
- 456
8
votes
1
answer
1k
views
Does the consistency strength hierarchy coincide with the "arithmetic consequence" hierarchy at ZF + Reinhardt?
In these slides (see especially slide 26), Steel emphasizes the phenomenon that for all known "natural" extensions of ZFC, the ordering by consistency strength agrees with the ordering by containment ...
- 64k
8
votes
1
answer
769
views
Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?
This question arises from an issue arising in user38200's recent question concerning models of set theory in which every definable set has a definable element. In my answer to that question, with ...
- 236k
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?
- 17.6k
8
votes
3
answers
2k
views
Does the Feferman-Schutte analysis give a precise characterization of Predicative Second-Order Arithmetic?
A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
- 4,597
8
votes
1
answer
580
views
Indeterminacy of long games
Hello, all,
Several months ago I sat in on a seminar on AD+, which was incredibly wonderful even though I could barely follow it at all. AD+ is a technical variant of AD, the axiom of determinacy, ...
- 20.5k
8
votes
1
answer
601
views
Proof-theoretic ordinals: inevitable consistency?
There are various different notions of the proof-theoretic ordinal of a theory; most of these are "notation-dependent" in that they're only nontrivial once we restrict attention to a class of "natural"...
- 20.5k
8
votes
1
answer
322
views
Does every cancellative duo semigroup embed into a group?
Prompted by the comments to a recent answer by YCor to a related question (here), I'd like to ask the following:
Q. Does every cancellative duo semigroup embed into a group?
A (multiplicatively ...
- 10.5k
8
votes
2
answers
596
views
If a semigroup embeds into a group, then is it a subdirect product of groups?
The title has it all:
Q. If a semigroup $S$ embeds into a group, then is $S$ (isomorphic to) a subdirect product of groups?
If yes, then $S$ is a subdirect product of subdirectly irreducible groups,...
- 10.5k
8
votes
1
answer
420
views
Undetermined games of "overdetermined" type
This is motivated by a previous question of mine, but I think it is ultimately more interesting (and hopefully easier to answer in the positive). In that question, a class of games (on $\omega$, of ...
- 20.5k
7
votes
1
answer
1k
views
Set-theoretic tautologies
Let us consider unquantified formulas of a set theory (for example, NBG), more precisely,
the formulas, constructed from variables and the constants $\emptyset, V$ (the empty set
and the class of all ...
- 897
7
votes
1
answer
350
views
Pushouts of injective monoid homomorphisms
Given a pushout square in the category of monoids
$$\begin{array}{ccc}A & \rightarrow & M \\ \downarrow && \downarrow \\ N & \rightarrow & P\end{array}$$such that $A \to M$ and ...
- 5,482
7
votes
1
answer
781
views
How do we know if Vaught's Conjecture is Absolute?
Please note that this might be some confusion on my part about the work surrounding Vaught's conjecture.
First of all, Vaught Conjecture states that if a first-order complete theory $T$ in a ...
- 756
7
votes
1
answer
369
views
Compatibility of Łośian phenomena in second-order logic
(Throughout, all ultrafilters are nonprincipal.)
Given a property $P$ - really, a sentence in some appropriate logic - say that a ultrafilter $\mathcal{U}$ on a cardinal $\kappa$ averages $P$ iff for ...
- 20.5k
7
votes
1
answer
673
views
Relationship between first and second incompleteness theorems
By my understanding, Gödel's first incompleteness theorem says that any theory with sufficient1 interpretability strength is essentially incomplete, that is, any consistent recursively enumerable ...
- 3,612
7
votes
1
answer
395
views
Every complex number has a square root via LLPO without weak countable choice
Is it possible to prove that every complex number has a square root using analytic LLPO, but avoiding Weak Countable Choice or Excluded Middle? Unique Choice is allowed.
(Analytic LLPO is the ...
- 4,943
7
votes
1
answer
275
views
Is $\mathbb{Q}$ "equivalent" to a structure with transitive automorphism group action?
Say that structures $\mathfrak{A},\mathfrak{B}$ with the same underlying set are parametrically equivalent iff every primitive relation/function in one is definable (with parameters) in the other. For ...
- 20.5k
7
votes
1
answer
457
views
The existence of definable subsets of finite sets in NBG
This question is motivated by my preceding MO-question on (in)consistency of NBG theory of classes.
Let $\varphi(x,Y,C)$ be a formula of NBG with free parameters $x,Y,C$ and all quantifiers running ...
- 42k
7
votes
6
answers
2k
views
Formal proof of Con(ZFC) => Con(ZFC + not CH) in ZFC
Is it possible to prove $Con(ZFC) \rightarrow Con(ZFC + \neg CH)$ purely within ZFC? To prove this (using forcing) one seems to need a countable transitive model of ZFC. The texts I am reading avoid ...
- 365
7
votes
1
answer
414
views
Is there an $E_1$-definition of primality?
Here, $E_1$ denotes the set of arithmetic formulas starting with a bounded existential quantifier, followed by a quantifier-free formula. Is there an $E_1$-formula $\phi$ such that $\phi(n)$ holds
iff ...
- 521
7
votes
2
answers
544
views
A linearly orderable monoid which does not embed into a linearly orderable group
It is known (after an example of A.I. Mal'cev) that there exist cancellative semigroups which do not embed into a group. On the other hand, it is not difficult to see that every linearly orderable ...
- 10.5k
7
votes
1
answer
581
views
Is this compactness property for "satisfiability on $\mathbb{R}$" consistent?
This was originally part of this older question of mine, but in retrospect that question should have been broken into two parts - this is the still-unanswered part.
Let $\Sigma$ be the language of ...
- 20.5k
7
votes
3
answers
525
views
Is the class of inverse semigroups globally determined?
This question is a follow-up to this one I asked on math.stackexchange. I've decided to ask here because I believe this is a research-level question. I'm sorry if I'm wrong -- I'm not a researcher ...
- 1,445
7
votes
3
answers
2k
views
Unprovable sentence about integers
Is there any natural* statement S about the natural integers such that if PA contains no contradictions then neither PA+S nor PA+not S contains a contradiction?
If unknown, where can I read about the ...
- 91
7
votes
1
answer
341
views
Can this weakish system of arithmetic express multiplication for second-sort numbers?
Consider a 2-sorted first-order logic with equality (for first-sort entities). The first sort consists of numbers, the second sort (which will be capitalized) of unary functions. There is one constant,...
- 1,974
6
votes
1
answer
234
views
How is this HA unprovable formula recursive realizable?
In Realizability: A Historical Essay [Jaap van Oosten, 2002], it is said that recursive realizability and HA provability do not concur, because although every HA provable closed formula is realizable, ...
- 173
6
votes
4
answers
2k
views
How short can we state the Axiom of Choice?
How short can we state a principle which is equivalent with the Axiom of Choice under $ZF$? The principle should be a sentence in the language of set theory with only $\in$ and$=$ as extralogical ...
- 3,574
6
votes
1
answer
368
views
Time functions of non-deterministic Turing machines
Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$. The smallest ...
user6976
6
votes
0
answers
153
views
Does every Tarski plane embed into a 3-dimensional Tarski space?
By a Tarski space I understand a mathematical structure $(X,B,\equiv)$ consisting of set $X$, a betweenness relation $B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\times X^2$ ...
- 42k
6
votes
2
answers
996
views
Elementary submodels of V
Consider the claim:
(C) There is a transitive set $S \in V$ such that the structure $(S, \in)$ is an elementary submodel of $(V,
\in)$.
Obviously, this claim cannot be a theoreom of ZFC, by Godel's ...
- 93
6
votes
1
answer
570
views
Ultraproducts in the category of structures and elementary embeddings
A previous question on the categorical nature of ultraproducts had great answers, mostly categorically characterizing ultraproducts in the category of $L$-structures and homomorphisms for a fixed ...
- 151
6
votes
2
answers
477
views
Heyting algebras originating from directed graphs
The category RefGph of reflexive directed graphs is the functor
category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is
the simplex category truncated at level 1.
Hence the poset Sub(X) of ...
- 567
6
votes
1
answer
406
views
Consistency results using nonstandard models
Are there any consistency results in set theory (or in mathematics) that can be proved using nonstandard models of ZFC but not using transitive models of ZFC?
- 32.2k
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.
- 42k
5
votes
2
answers
896
views
An axiom for collecting proper classes
I'm currently working on some universal algebra using proper classes (in MK class theory), and I repeatedly run into situations where I want to collect together some proper classes as the members of a ...
- 10.1k
5
votes
2
answers
622
views
A weak (?) form of Shelah cardinals
The following definition of a large cardinal property combines parts of the definitions of "Shelah cardinal" and "Woodin cardinal":
A cardinal $\kappa$ is weakly Shelah if for all $f : \kappa \to \...
- 5,471
5
votes
1
answer
958
views
Does a nonlinear additive function on R imply a Hamel basis of R?
A function is additive if $f(x+y) = f(x) + f(y)$. Intuitively, it might seem that an additive function from R to R must be linear, specifically of the form $f(x) = kx$. But assuming the axiom of ...
- 4,597
5
votes
3
answers
542
views
Congruences that aren't "finite from above"
Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with ...
- 20.5k
5
votes
1
answer
344
views
What is the proof of consistency of anterior reflection?
Let Anterior Reflection be the following principle: $$\forall \vec{v}~ \exists X: \operatorname {transitive} (X) \land \, (\varphi \to \varphi^{X"}) $$
where $\varphi$ is a formula in $\sf FOL(=,\in)$ ...
- 11.3k
5
votes
0
answers
653
views
Bourbaki-Witt in a textbook, other than in logic?
The Bourbaki-Witt theorem states that, in a chain-complete poset, the subset $X$ generated by an inflationary monotone function $s$ from the least element and joins of chains satisfies
$$ \forall x,y\...
- 8,481
5
votes
1
answer
471
views
Comparing the sizes of uncountable sets of reals under AD
Working in ZF+AD, let $$\theta_0(X)=\min\{\alpha\in ON: \not\exists f: X\rightarrow \alpha\mbox{ surjective and OD}\}$$ be the least ordinal onto which $X$ does not surject in an OD way, for $X\...
- 20.5k
5
votes
0
answers
431
views
Cardinal characteristics without choice
(I'm taking my definition of a cardinal characteristic from Blass' excellent article http://www.math.lsa.umich.edu/~ablass/need.pdf, which cites Vojtas/Fremlin/Miller; theirs is more general, but I'm ...
- 20.5k
4
votes
1
answer
169
views
Is every invertible-free cancellative monoid action represented by "shifting" certain maps?
[Note: This question is closed. It's current content reflects a draft of a potential new question, modified from the original by adding conditions to the premises; see comments]
Let $W,X$ be ...
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$,...
- 10.5k