All Questions
6,027 questions
8
votes
1
answer
343
views
What topos-theoretic construction lies behind the “symmetric model” construction (used to refute AC) in Set Theory?
Suppose we want to prove that (classical!) $\mathsf{ZF}$ does not prove, say, “for every infinite set $A \subseteq \{0,1\}^{\mathbb{N}}$ there exists an injection $\mathbb{N} \to A$” (I take this ...
- 32.5k
3
votes
0
answers
90
views
Existence of symmetric total measures
Is it consistent that there is a total finitely additive measure $μ$ on $ℝ$ extending the Lebesgue measure such that for every Borel Lebesgue-measure-preserving bijection $f$ of $ℝ$, $∀α∈Ord \, ∀s∈Ord^...
- 7,545
4
votes
2
answers
134
views
Properties of all relatively computable branches
I'm probably just missing something obvious but suppose that $T \subset 2^{< \omega}$ is a perfect tree with no terminal nodes (what about just $[T]$ non-empty?). If $Y \leq_{T} X$ for all $X \...
- 3,029
4
votes
0
answers
206
views
Fine structure without choice
In set theory, are there approaches to fine structure that give fine-structural models that do not satisfy the axiom of choice?
We can build fine-structural models above a given set (such as $\mathbb ...
- 7,545
1
vote
2
answers
228
views
Can this semi-constructible structure satisfy existence of a measurable cardinal?
If we add a primitive unary function symbol $\mathfrak L$ to the first order language of set theory.
Axiom of semi-constructibility: if $\phi^\alpha (y,x_1,\ldots,x_n)$ is a formula in which all and ...
- 11.3k
3
votes
2
answers
390
views
Can there exists a model of ZFC with permutation that sends successor infinite stages to their predecessors?
Can there exist a model $M$ of $\sf ZFC$ and an external permutation $j$ on $M$ such that $j[(V_{\alpha+1})^M]=(V_\alpha)^M$ for each infinite $\alpha$?
- 11.3k
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?
- 4,985
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 ...
- 20.5k
9
votes
1
answer
366
views
Can the canonical Eudoxus-real representatives be defined easily?
(See e.g. here for background on the Eudoxus reals, which motivates this question.)
Let $\mathcal{Z}=(\mathbb{Z};+,<)$. Say that a Eudoxus function is an $f:\mathbb{Z}\rightarrow\mathbb{Z}$ such ...
- 20.5k
9
votes
0
answers
266
views
Consequences of recent claims of Ordinal Analysis of $Z_2$
Recently Toshiyasu Arai submitted "An ordinal analysis of $\Pi_{N}$-Collection" and Henry Towsner submitted "Proofs that Modify Proofs", both of which claim ordinal analysis of ...
- 161
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 ...
- 236k
3
votes
0
answers
250
views
Action (of a graded monoid) required
Reference request: Did the construction below appear anywhere before? Any mentions of it or especially any links to something commonly known would be really helpful. I feel that it might be related to ...
- 321
6
votes
0
answers
180
views
$Δ^1_3$ reals in transitive models
Every real number is $Δ^1_2$ in some $ω$-model of ZFC\P. I am looking for analogous statements for $Δ^1_3$ definability and transitive models, where the situation is more subtle.
What is the ...
- 7,545
7
votes
0
answers
265
views
Herbrand's consistency proof
Jacques Herbrand's thesis "Investigations in proof theory: The properties of true propositions" (or in the original French "Recherches sur la théorie de la démonstration", with the ...
- 161
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 ...
- 10.5k
3
votes
0
answers
153
views
What is known about the word problem on free algebraic models?
Consider the fragment of first-order logic with equality and universal quantification as the only logical symbols; we call this logic the logic of universal algebra. I am interested in languages $\...
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$. ...
- 195
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 ...
- 236k
4
votes
1
answer
238
views
AD and simultaneous well-orderability principle
Is the axiom of determinacy (AD) consistent with the following choice principle, and if yes, does it hold in $L(ℝ)$ under AD:
Simultaneous well-orderability: For every function $f:P(Ord)→\text{...
- 7,545
4
votes
1
answer
154
views
Minimal dominating sets in thin hypergraphs
Let $H=(V,E)$ be a hypergraph. We say that $H$ is thin if for every $v\in V$ the set $E_v=\{e\in E:v\in e\}$ is finite.
A subset $D\subseteq V$ is dominating if
$\bigcup \{e\in E:e\cap D \neq \...
- 48.9k
17
votes
2
answers
1k
views
Is it consistent with ZFC that the real line is approachable by sets with no accumulation points?
Let $P$ denote the following proposition:
There exists a set $S$ of subsets of $\mathbb{R}$ such that
$S$ is totally ordered by inclusion;
each member of $S$ has no accumulation points;
the union of ...
- 708
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 ...
- 293
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 ...
- 667
53
votes
7
answers
7k
views
Are there any undecidability results that are not known to have a diagonal argument proof?
Is there a problem which is known to be undecidable (in the algorithmic sense), but for which the only known proofs of undecidability do not use some form of the Cantor diagonal argument in any ...
- 114k
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 ...
- 11.3k
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
...
-1
votes
1
answer
141
views
Can stratification be used to internalize external functions inside models of $\sf ZF$?
Suppose $M$ is a model of $\sf ZF+\neg AC$ that is externally bijective to an element $k \in M$. Obviously if $j$ denotes such an external bijection, then it cannot be used in Separation and ...
- 11.3k
0
votes
0
answers
179
views
the (indirect) deduction theorem
$\DeclareMathOperator\Cn{Cn}\DeclareMathOperator\Sb{Sb}$I would like to ask about the Deduction Theorem for an inconsistent system. This is a very well-known fact that for the classical propositional ...
- 19
1
vote
0
answers
106
views
The proposition associated with a set
Given a set $U$ and a set $A \subseteq U$, is there an accepted symbol for the proposition $p$ over the universe $U$ such that for each $x \in U$, $p(x)$ is the assertion that $x \in A$? (The symbol $...
- 19.7k
5
votes
1
answer
416
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 ...
- 225
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
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 ...
- 39.8k
51
votes
30
answers
8k
views
Taking a theorem as a definition and proving the original definition as a theorem
Gian-Carlo Rota's famous 1991 essay, "The pernicious influence of mathematics upon philosophy" contains the following passage:
Perform the following thought experiment. Suppose that you are ...
4
votes
1
answer
186
views
Logical relationship between supercompact and rank-into-rank cardinals
It is well known that the large cardinals are ordered by logical consistency. In many cases, the logical consistency is, in fact, a direct implication - for example, Mahlo $\Rightarrow$ Inaccessible ...
- 463
23
votes
1
answer
3k
views
What is known about the theory of natural numbers with only 0, successor and max?
Consider the first-order theory whose intended/standard model is the natural numbers $\mathbb{N}$, with constant $0\in \mathbb{N}$, with an injective successor operation $s$ such that $0$ is not a ...
- 35.5k
3
votes
1
answer
162
views
Stone-Čech compactification of a Boolean subalgebra of $\{0,1\}^S$
Setup: Let $S$ be a set. Let $B$ be a Boolean subalgebra of $\{0,1\}^S$; i.e., just to be clear $B$ contains the constant $0$ and $1$ functions, and is stable under binary pointwise $\land$, $\lor$ ...
- 32.5k
-3
votes
1
answer
117
views
Can stratification be used to internalize functions on models of $\sf Z$?
Suppose $M$ is a model of $\sf Z +\neg AC$ that is externally bijective to an element $k \in M$. Obviously if $j$ denotes such an external bijection, then it cannot be used in Separation within $M$, ...
- 11.3k
3
votes
1
answer
199
views
Mutually equal Hamming distance of members of ${\cal P}(\mathbb{N})$
This is inspired by an older, as of yet unanswered question.
If $X$ is a set and $A,B\subseteq X$, we let the Hamming distance of $A, B$ be defined as $d_H:=\text{card}\big((A\setminus B)\cup (B\...
- 48.9k
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 ...
3
votes
0
answers
97
views
Can the differential field of d.c.e. reals be nicely construed as a field of functions?
This question is basically a special case of this older question of mine, which is still unanswered.
Let $\mathcal{D}$ be the field of d.c.e. reals; these turn out to be exactly the reals $\alpha$ for ...
- 20.5k
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
2
votes
0
answers
90
views
Intuitionistic countermodels in which $u \leq v \implies M_u \leq M_v$
In Fitting's Intuitionistic Logic Model Theory and Forcing, the following theorem is proven:
If $X$ is a formula with no universal quantifiers and $\not\vdash_I X$, then there is a countermodel $(\...
- 149
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
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 ...
- 10.1k
7
votes
0
answers
166
views
Examples of finitary problems/theorems of high logical complexity? [duplicate]
Generally, number theoretic conjectures which are well-known and easy to explain are either obviously $\Pi^0_1$ or $\Pi^0_2$, which is to say, their truth can be decided by a single membership query ...
- 1,452
19
votes
2
answers
1k
views
Axiom of Choice for collections of Equinumerous sets
Let ACE (Axiom of Choice for Equinumerous sets) be the following choice principle:
If $S$ is a set of non-empty sets such for any $X,Y\in S$ there is a bijection from $X$ to $Y$, then $S$ has a choice ...
- 528
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 $\...
- 20.5k
3
votes
0
answers
183
views
Can we have a theory that interpret $\sf ZFC$, proves existence of an infinite set, and yet prove all of its sets being Dedekind finite?
If we start with axioms of $\sf ZF$ replace the axiom of Infinity with an axiom stating the existence of a set that doesn't have an injection to a von Neumann natural, and replace the axiom of Power ...
- 11.3k
13
votes
4
answers
843
views
What is a "general" relation algebra?
I'm trying to understand why (or if) the axioms of relation algebras are "the right ones." For example, we can back up the idea that the group axioms exactly capture the notion of "...
- 20.5k