All Questions
6,026 questions
8
votes
4
answers
630
views
closure of separative quotients
Does there exist a partial order, nontrivial for forcing, that is countably closed, but whose separative quotient is not countably closed? Supposing the answer is yes, then is there a partial order, ...
- 2,153
27
votes
6
answers
9k
views
What is a topos?
According to Higher Topos Theory math/0608040 a topos is
a category C which behaves like the
category of sets, or (more generally)
the category of sheaves of sets on a
topological space.
Could one ...
3
votes
1
answer
252
views
Can a general recursive function be defined by Pr(x)?
In the book Metamathematics of First-Order Arithmetic, I learned that a general recursive function can be defined by a $\Delta_1$-formula. I am curious about another matter: Since we have $Pr_T^\...
- 236k
64
votes
15
answers
7k
views
Unnecessary uses of the axiom of choice
What examples are there of habitual but unnecessary uses of the axiom of
choice, in any area of mathematics except topology?
I'm interested in standard proofs that use the axiom of choice, but where
...
- 328
14
votes
3
answers
871
views
Is it possible to completely embed complete Heyting algebras into upsets of a poset?
Let $H$ be a Heyting algebra. It is a well-known result that there is a partially ordered set (Kripke frame) $X$ such that there is an embedding of Heyting algebras $f: H \to \mathsf{Up}(X)$, where $\...
- 12.9k
86
votes
10
answers
11k
views
What's wrong with the surreals?
Of all the constructions of the reals, the construction via the surreals seems the most elegant to me.
It seems to immediately capture the total ordering and precision of Dedekind cuts at a ...
- 10.1k
7
votes
2
answers
311
views
At what ordinal $\chi$ does $\mathrm{L}_\chi$ contain a surjection from $\omega$ to $\mathrm{L}_{\beta_0}$?
Let $\mathrm{ZF^-}$ be $\mathrm{ZF}$ minus power set, and let $\beta_0$ be the ordinal for ramified analysis so that $\mathrm{L}_{\beta_0}$ is the least $\mathrm{L}$-model of $\mathrm{ZF}^-$. Clearly, ...
- 3,574
5
votes
1
answer
212
views
Image-catching families in $\omega$
Let $[\omega]^\omega$ be the collection of infinite subsets of the set of nonnegative integers $\omega$, and let $\newcommand{\I}{\cal{I}}\I=$ $\{S\in[\omega]^\omega: (\omega\setminus S)\in[\omega]^\...
- 9,902
7
votes
1
answer
459
views
Is it consistent that $|[\kappa]^{<\kappa}| > \kappa$?
Let $\kappa>\aleph_0$ be a cardinal, and let $[\kappa]^{<\kappa}$ denote the collection of subsets of $\kappa$ having cardinality strictly less than $\kappa$. Is it consistent that $$|[\kappa]^{&...
- 48.9k
2
votes
1
answer
119
views
Does $\mathrm{L}_{s_{n+1}}$ contain a surjection from $\omega$ to $\mathrm{L}_{s_n}$?
Let $s_n$ be the least $\Sigma_n-$admissible ordinal, so that $\mathrm{L}_{s_n}$ is a model of Kripke-Platek set theory with $\Sigma_n-$collection and $\Sigma_n-$separation.
Does $\mathrm{L}_{s_{n+1}}$...
- 20.5k
20
votes
5
answers
1k
views
Uniqueness results that follow from CH
Recently, Joel David Hamkins presented a historical thought experiment that shows that CH could have been adopted as an axiom if we had been using the hyperreal field $\mathbb{R}^*$ instead of $\...
CommunityBot
- 1
14
votes
2
answers
1k
views
If every definable class admits a group structure, must global choice hold?
It is a remarkable fact, due to Hajnal and Kertész and explained very well in this MathOverflow answer by user Ashutosh, that the axiom of choice is equivalent to the assertion that every nonempty set ...
- 1,851
5
votes
0
answers
81
views
Which pseudovarieties have (Eilenberg/Schutzenberger) minimal descriptions?
Suppose $\mathscr{V}$ is a pseudovariety in a countable language $\Sigma$. Say that a minimal description of $\mathscr{V}$ (in the sense of Eilenberg/Schutzenberger rather than Reiterman) is a pair $(...
- 20.5k
2
votes
1
answer
154
views
The Dirichlet principle and arithmetical induction
Let us consider the Dirichlet principle as follows: for all natural numbers $n > k > 0$, there is no injection from $\{0, \dots, n-1\}$ into $\{0, \dots, k-1\}$.
Is it true that in some non-...
- 236k
3
votes
1
answer
329
views
Nonexistence of short integer program sequence which generates squares
Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to ...
- 13.9k
2
votes
1
answer
169
views
Smallest ${\mathbf B}$-function $f:\omega\to( \omega\setminus\{0\})$
Motivation. Every hypergraph $(\omega, E)$ where $E$ is countable and consists of infinite sets has property $\newcommand{\B}{\mathbf{B}}\B$. On the other hand, if the members of $E$ are allowed to be ...
- 13.4k
20
votes
3
answers
3k
views
On statements independent of ZFC + V=L
Let $V=L$ denote the axiom of constructibility. Are there any interesting examples of set theoretic statements which are independent of $ZFC + V=L$? And how do we construct such independence proofs? ...
- 328
5
votes
3
answers
851
views
What are some examples of non-commutative $\mathbb{Q}$-monoids and/or $\mathbb{R}$-monoids?
Definition 0. Let $R$ denote a commutative semiring with $0$ and $1$. By an $R$-monoid, I mean a monoid $M$ equipped with an action $R \times M \rightarrow M$ denoted $r,m \mapsto m^r$, satisfying the ...
- 17k
4
votes
1
answer
150
views
Comparing semiring of formulas and Lindenbaum algebra
This is motivationally related to an earlier question of mine.
Given a first-order theory $T$, let $\widehat{D}(T)$ be the semiring defined as follows:
Elements of $\widehat{D}(T)$ are equivalence ...
- 5,831
25
votes
7
answers
3k
views
When can we prove constructively that a ring with unity has a maximal ideal?
Many commutative algebra textbooks establish that every ideal of a ring is contained in a maximal ideal by appealing to Zorn's lemma, which I dislike on grounds of non-constructivity. For Noetherian ...
- 35.5k
6
votes
0
answers
173
views
Measurable functions from logical formulas
Let $A(X, Y)$ be an arithmetical formula with (only) second-order variables $X, Y\subset \mathbb{N}$.
Assuming $(\forall X\subset \mathbb{N})(\exists Y\subset\mathbb{N})A(X, Y)$, there is a choice ...
- 236k
-4
votes
2
answers
399
views
Two equivalent statements about formulas projected onto an Ultrafilter
Question 1:
In the same language, let $ X $ be a nonempty set, and let $ \{ (\forall x_{x(i)} f(i)) \ | \ i \in X \} $ be a set of formulas. We use $ x(i) $ to denote the index of the variable on ...
- 127
1
vote
1
answer
138
views
Is there inconsistency with having countable models of Z with these internalizing properties?
Is there a clear inconsistency with the following?
There exists a countable transitive model of Zermelo set theory, such that for all external bijections between sets the images and preimages of sets ...
- 236k
3
votes
0
answers
99
views
Counting Eilenberg/Schutzenberger-type definitions of pseudovarieties
See Eilenberg/Schutzenberger, On pseudovarieties for background on pseudovarieties. I've phrased things in terms of pairs-of-sets to avoid some annoying language about multisets. Also, I'm aware that ...
- 20.5k
5
votes
1
answer
170
views
Can we see quantifier elimination by comparing semirings?
This question came up while reading the paper Hales, What is motivic measure?. Broadly speaking, I'm interested in which ideas from motivic measure make sense in arbitrary first-order theories (or ...
- 20.5k
1
vote
1
answer
180
views
Natural functions outside $\sf PA$?
Can theories stronger than $\sf PA$ manage to define functions from the naturals to the naturals, that $\sf PA$ cannot? If so, what are examples of those functions?
- 11.3k
6
votes
1
answer
1k
views
An axiomatic approach to the multiverse of sets
Work in a theory where the primitives are classes $X,Y,Z,\dots$, and class membership $X\in Y$, and add an individual constant $\mathcal{M}$ called 'the multiverse'. Classes $V$ which are members of ...
- 10.1k
4
votes
0
answers
146
views
Can one formalize the prevalence of the Big Five systems of reverse math?
Simpson's systems of second order arithmetic turn out to be five in
number; to simplify notation let's denote them A, B, C, D, E. What
seems to be an empirical observation is that most theorems in
...
- 16.6k
1
vote
1
answer
146
views
Can PA define functions related to higher theories?
Working in $\sf ZFC$ we can define a function $F$ from naturals to naturals such that $F(0) = \, ^\circ\ulcorner r({\sf Z}) \urcorner$, where $r({\sf Z})$ is the Rosser sentence of Zermelo set theory $...
- 11.3k
6
votes
1
answer
286
views
Example of applying real quantifier elimination algorithm for polynomials
Sorry if any of this is unclear, or doesn't make much sense, I'm still trying to figure it out, a practical example such as this would likely help me understand better than anything else. I have read ...
- 326
3
votes
1
answer
151
views
Large almost disjoint family on $\mathbb{N}$ with property $\mathbf{B}$
Let
$\newcommand{\oo}{[\omega]^\omega}\oo$ denote the collection of all infinite subsets of the set of nonnegative integers $\omega$. We say that $\newcommand{\ss}{{\cal S}}\S\subseteq \oo$ ...
- 73.2k
23
votes
2
answers
3k
views
Does the "three-set-lemma" imply the Axiom of Choice?
Consider the following curious statement:
$(S)$ $\;$ Let $X$ be a non-empty set and let $f:X \to X$ be fixpoint-free (that is $f(x) \neq x$ for all $x\in X$). Then there are subsets $X_1, X_2, X_3 \...
- 47.4k
9
votes
2
answers
381
views
How big can function spaces get without extensionality?
In what follows we work in the usual formulation of Martin-Löf Type Theory including Axiom K [1]. Boldface numbers $\mathbf{n}$ denote the usual finite type with $n$ elements.
Motivation
Postulating ...
- 756
0
votes
0
answers
143
views
Introductory resources on rewriting logic
Hi I would like to grasp the theory behind Maude [1], [2]
Are there any recommended video lecture notes, talks or introductory notes?
I have been exposed to Functional Analysis, Topology and some Term ...
9
votes
10
answers
2k
views
What do models where the CH is false look like?
Additionally, is there any intuitive way to visualize the cardinalities that result?
- 328
15
votes
3
answers
3k
views
Finite verification for theorems due to Busy Beaver numbers
I recently learned about the Busy Beaver function, and a formulation of it that essentially tells us if a turing machine of $n$ states takes over $BB(n)$ steps, it will never halt.
One consequence I ...
- 2,031
5
votes
3
answers
665
views
Negating fundamental axioms
It is commonplace to consider standard axiomatic systems (e.g. $ZF$) with one of the 'less essential' axioms negated, like infinity, 'less essential' here having some ambiguous definition related to ...
- 4,359
0
votes
0
answers
245
views
Is this mereotopology theory consistent?
$ \newcommand{\Pt}{ \ \mathbb P \ }
\newcommand {\cz}{\ C_z \ }
\newcommand {\eps}{\ \varepsilon \ }$Logic: first order logic with equality
Extra-logical primitives:
"$\varepsilon$" ...
- 11.3k
36
votes
3
answers
3k
views
Latest status of core model theory?
What is the "strongest" core model to this day? In particular, how far are we from a core model for supercompact cardinals? There are rumors of some notes from a workshop in 2004:
https://...
- 24.2k
2
votes
0
answers
132
views
A property of < in Primitive recursive arithmetic
In Primitive recursive arithmetic (PRA), we can introduce $\lt$ by introducing its representing function $K_{\lt}$, where $K_{\lt}(x,y) =sg(x+1-y)$. Here "sg" and "-" are the ...
- 29
9
votes
2
answers
426
views
Can local $0^\#$ exists in L?
Assume $0^\#$ exists and there is an inaccessible cardinal.
Are there two transitive sets $M,N$ s.t. $M\in N,M\vDash ZF+V=L[0^\#],N\vDash ZF+V=L$?
- 20.5k
1
vote
1
answer
215
views
Reference about cancellation property for semigroups
Have the semigroups with the following cancellation property been studied?
Property: Let $S$ be a semigroup and $x,y\in S$ such that $xz=yz,$ for all $z\in S,$ then $x=y$.
- 468
7
votes
0
answers
161
views
Is strictness decidable?
Let $\mathcal C$ be an $\infty$-category. We can ask:
Q: Is $\mathcal C$ a 1-category?
That is, are the hom-spaces of $\mathcal C$ essentially discrete?
Roughly, my question is:
Proto-Question: Is Q ...
- 64k
8
votes
1
answer
222
views
Mostowski's absoluteness theorem and proving that theories extending $0^\#$ have incomparable minimal transitive models
This question says that the theory ZFC + $0^\#$ has incomparable minimal transitive models. It proves this as follows (my emphasis):
[F]or every c.e. $T⊢\text{ZFC\P}+0^\#$ having a model $M$ with $On^...
- 1,097
8
votes
0
answers
164
views
Is there a substructure-preservation result for FOL in finite model theory?
It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
- 20.5k
3
votes
0
answers
115
views
Are "equi-expressivity" relations always congruences on Post's lattice?
Given a clone $\mathcal{C}$ over the set $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with (symbols corresponding to) elements of $\mathcal{C}$ replacing the ...
- 20.5k
1
vote
0
answers
165
views
Can this formalism prove the consistency of ZFC?
Working in bi-sorted first order logic with equality and membership. First sort variables written in lower case range over sets. Second sort variables written in upper case range over classes. Lets ...
- 11.3k
6
votes
1
answer
333
views
Can we have this sequence where choice fails and returns?
Can we have a sequence of transitive sets $\langle\mathcal V_0, \mathcal V_1, \mathcal V_2,...\rangle$, all modeling $\sf ZF$, such that $\mathcal P(V_n) \subset \mathcal V_{n+1}$, and the cardinality ...
CommunityBot
- 1
15
votes
2
answers
1k
views
Proof/Reference to a claim about AC and definable real numbers
I’ve read somewhere on this site (I believe from a JDH comment) that an argument in favor of AC (I believe from Asaf Karagila) is that without AC, there exists a real number which is not definable ...
CommunityBot
- 1
6
votes
2
answers
406
views
Axiomatic strength of the cumulative hierarchy
In the 2021 paper Level Theory Part I: Axiomatizing the Bare Idea of a Cumulative Hierarchy of Sets by Tim Button, a first order theory of the cumulative hierarchy is explored. Initially no axioms ...
- 136