All Questions
6,026 questions
0
votes
0
answers
70
views
Is Acyclic ZF consistent with downshifting automorphisms?
Recall the criterion of acyclic comprehension. This is shown to be equivalent to stratified comprehension for language $\sf FOL(=, \in)$, given minimal assumptions. [See here, and here].
Let Acyclic ...
- 11.3k
4
votes
0
answers
177
views
Recording of 2009 lecture on Harvey Friedman's work
On December 13--20 2009 at Bristol, there was a meeting devoted to thorough dissection of Harvey Friedman's work on the foundations of mathematics and his statements claimed to be equivalent to ...
- 869
5
votes
2
answers
266
views
Formal languages with non-unique interpretations of terms
In mathematical logic and model theory, one considers interpretations of syntactic expressions: terms without free variables are interpreted as elements of some structure, formulas without free ...
- 1,481
20
votes
2
answers
2k
views
What is $\omega_1^{CK}(\mathsf{Ord})$?
We know that if $\alpha<\omega_1^{CK}$ then there is some recursive $R$ such that $(\omega,R)$ has order type $\alpha$.
Let's consider now the ordinals, $\mathsf{Ord}$ with their natural order. ...
- 20.5k
4
votes
0
answers
115
views
Is there an abstract logic satisfying the Löwenhein-Skolem property for single sentences but not for countable sets of sentences?
An abstract logic satisfies the LS property for single sentences if each satisfiable sentence has a countable model. Similarly, the LS property for countable sets of sentences holds if every ...
- 2,467
1
vote
1
answer
112
views
Constructible cardinality downslides and their consistency strengths?
Posting "Large cardinals and constructible universe" mentions that $\omega_1^L < \omega_1$ if we assume Ramsey cardinal.
My question can we have more downslides like for example $\omega_2^...
- 20.5k
10
votes
1
answer
502
views
Must strange sequences wear Russellian socks?
This is an attempt to make more precise a vague guess at the end of this answer of mine. We work in $\mathsf{ZF}$ throughout.
Say that a sequence $\mathcal{A}=(A_i)_{i\in\omega}$ of disjoint sets is ...
- 4,316
9
votes
1
answer
889
views
Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory
In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
- 12.9k
28
votes
2
answers
2k
views
The true reason for the incompleteness of formal systems
A 3/4 year ago, I read Gödel's beautiful paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme 1". There is one thing, I never understood.
In a footnote, Gödel ...
- 119
6
votes
0
answers
145
views
Alternative proofs of the countable chain condition in forcing
Advance warning: This question is more about history and pedagogy than "hard" mathematics.
I am studying Cohen forcing with the forcing poset $(\operatorname{Fin}(E,2),\supseteq,0)$, and I ...
- 35.5k
4
votes
0
answers
150
views
Does this rule imply axiom of choice?
if $\kappa; \lambda$ are infinite Scott cardinals, then: $$2^\kappa = 2^\lambda \leftrightarrow
\kappa \leq \lambda < 2^\kappa \lor \lambda \leq \kappa < 2^\lambda $$
Would adding the ...
- 11.3k
4
votes
1
answer
312
views
What determines internalization of graph-structures into the set world?
Can we add to $\sf MK$ a cardinality function that is indexed by sets?
That is, add a new primitive total unary function symbol $C$, then axiomatize: $$C(X) = C(Y) \leftrightarrow X \cong Y \\ \forall ...
- 236k
8
votes
1
answer
896
views
Quantifier elimination for abelian groups
In the Wikipedia article (https://en.wikipedia.org/wiki/Quantifier_elimination#cite_note-4) it is said that every abelian group has quantifier elimination property and a long old paper of W. Szmielew ...
- 47.4k
6
votes
2
answers
470
views
Does Well-Ordered Interval Power Set "WOIPS" principle , prove $\sf AC$ in $\sf ZFA$?
Does $\sf ZFA + WOIPS$ prove $\sf AC$?
Where $\sf WOIPS$ is phrased as: for every infinite set $X$ the set of intervening cardinals between $|X|$ and $|\mathcal P(X)|$ is well-ordered.
In $\sf ZF$, I ...
- 11.3k
4
votes
1
answer
193
views
Further research on relevant realizability etc
I just read Dunn's 1979 paper Relevant Robinson's Arithmetic, and the end especially caught my interest. Following the surprising role of constant functions in collapsing "relevant Q with zero&...
- 1,094
1
vote
0
answers
233
views
Can the Collatz conjecture be independent of ZFC? [closed]
It is known that the Continuum Hypothesis is independent of ZFC.
The formulation of the Collatz conjecture looks somehow more simple than that of the Continuum Hypothesis.
Is it possible that the ...
- 654
65
votes
7
answers
23k
views
Can the Riemann hypothesis be undecidable?
The question is contained in the title; I mean the standard axioms ZFC. The wiki link: Riemann hypothesis. There are finite algorithms allowing one to decide if there are non-trivial zeroes of the $\...
- 4,713
5
votes
1
answer
220
views
What is the theory of computably saturated models of ZFC with an *externally well-founded* predicate?
For any model of $M$ of ZFC, we can extend it to a model $M_{ew}$ with an "externally well-founded" predicate $ew$. For $x \in M$, We say that $M_{ew} \vDash ew(x)$ when there is no infinite ...
- 47.4k
1
vote
0
answers
67
views
How $n$-set -like functions are constructed?
if for every $f$ we define a relation $R_f$ as follows: $$ x \ R_f \ y \iff \exists z \in x : y=f(z)$$
So, the binary relation $R_f$ sends a set to each image under $f$ of an element of it.
Define $R \...
- 11.3k
6
votes
1
answer
447
views
Why should I believe Martin's Maximum++?
$\sf MM^{++}$ is a 'good' set-theoretic axiom because it is 'Maximum'. Of course, bigger is better. But I'd like to know exactly how the argument works.
Let me be clear about the question posed:
What ...
- 82.7k
1
vote
0
answers
62
views
Can this theory interpret TG? Would its Reinhardt's extension be equivalent to the usual one?
Language: FOL
Primitives: $=, \in$
Axioms:
Extensionality: as in Z
Define: $\operatorname {set}(y) \iff \exists x: y \in x$
Comprehension: $$n=0,1,2, \ldots \\ \forall \operatorname {set} x_1, \cdots, ...
- 11.3k
8
votes
2
answers
567
views
Darboux property of non-atomic sigma-additive nonnegative measures equivalent to the AC?
A result commonly, and probably erroneously, attributed to W. Sierpiński is that every non-atomic, countably additive, nonnegative measure $\mu: \Sigma \to \bf R$, where $\Sigma$ is a sigma-algebra on ...
- 273
10
votes
2
answers
240
views
Additive, multiplicative, and Dedekind infiniteness in ${\sf (ZF)}$
We call a set $X$
Dedekind-infinite if there is an injective map $f:X\to X$ that is not surjective,
addititvely infinite if $X \neq\emptyset$ and there is an injective map $f:\big((X\times\{1\})\cup(...
- 14.6k
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 ...
- 236k
18
votes
3
answers
2k
views
Scott-Solovay unpublished paper on ``Boolean valued models of set theory''
I have read some papers from 1970$^{th}$, and in some of them, the paper of Scott and Solovay on ``Boolean valued models of set theory'' is given as a main reference, with many references to the ...
- 47.4k
4
votes
1
answer
432
views
How to settle continuum hypothesis like questions for impure sets?
How questions similar to the continuum hypothesis can be solved if we work in a set theory that admits urelements and that permit impure sets that are not injective to any pure set, for example $\sf ...
- 11.3k
4
votes
1
answer
533
views
How to settle the Generalized Continuum Hypothesis when there are urelements?
Work in $\sf ZFCA$ and permutation models has preceded forcing by several decades. Was it used to settle the question of the Generalized Continuum Hypothesis $\sf GCH$ when urelements are admitted? I ...
- 11.3k
2
votes
0
answers
114
views
Robinson's views on Heyting's work?
Abraham Robinson and Arend Heyting had mutual respect (though holding differing philosophical views on the nature of mathematics). Heyting repeatedly expressed admiration for Robinson's work; see for ...
- 16.6k
5
votes
1
answer
177
views
The equivalence of Dedekind-infinite and dually Dedekind-infinite as a weak form of (AC)
A set $X$ is Dedekind-infinite if there is an injective map $f: X\to X$ that is not surjective.
A set $X$ is dually Dedekind-infinite if there is a surjective map $f: X\to X$ that is not injective.
In ...
- 39.8k
27
votes
1
answer
932
views
A cardinal inequality for finiteness
Nearly ten years ago, I explained in a blog post that, assuming only ZF, a cardinal number $\mathfrak{n}$ is finite if and only if it satisfies this monstrous inequality:
$$2^{2^{2^{2^{\mathfrak{n}}}}}...
- 1,792
12
votes
5
answers
5k
views
Proper classes and their consequences
I have two main questions:
What is a proper class? I've read that it's collection of objects that's "too big" to be a set, but in what sense is such a collection "too big"? Since I'd like this post ...
- 4,713
10
votes
0
answers
248
views
What is the tiling semigroup for an einstein "hat" tiling?
My undergraduate dissertation was on inverse semigroups and the key text I used for it was Lawson's, "Inverse Semigroups: The Theory of Partial Symmetries". In said book, Lawson describes ...
- 2,858
12
votes
1
answer
684
views
Graphs $G$ with $G \cong \text{Aut}(G)$
Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of graph isomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\...
- 1,543
53
votes
1
answer
4k
views
When does $A^A=2^A$ without the axiom of choice?
Assuming the axiom of choice the following argument is simple, for infinite $A$ it holds: $$2\lt A\leq2^A\implies 2^A\leq A^A\leq 2^{A\times A}=2^A.$$
However without the axiom of choice this doesn't ...
CommunityBot
- 1
4
votes
1
answer
454
views
Paris-Harrington via overspill?
I saw in an old logic paper that the Paris-Harrington theorem can be proved via Overspill. The presentation is unfortunately too technical for me to follow. Does somebody have any insight into this?
- 17.7k
14
votes
1
answer
619
views
Ordinal realizability vs the constructible universe
Koepke's paper Turing Computations on Ordinals defines a notion of "ordinal computability" using Turing machines with a tape the length of Ord and that can run for Ord-many steps, and shows ...
- 4,378
2
votes
0
answers
220
views
Which is richer Set or Graph Theory?
This theory about structures, defined as abstractions over isomorphic graphs, can interpret Set Theory in a rather creepy manner. Though the theory is largely technical, yet it is not far from being ...
- 11.3k
11
votes
2
answers
1k
views
If a set contains all its proper transitive subsets as members, do its members as well?
recently I came upon some personal notes I'd made several years ago while reviewing some basic set theory (ordinals, transfinite recursion, inaccessible cardinals etc.), and I stumbled upon a loose ...
- 194
20
votes
5
answers
2k
views
Constructively, is the unit of the “free abelian group” monad on sets injective?
Classically, we can explicitly construct the free Abelian group $\newcommand{\Z}{\mathbb{Z}}\Z[X]$ on a set $X$ as the set of finitely-supported functions $X \to \Z$, and so easily see that the unit ...
- 426
3
votes
0
answers
133
views
Comparing two fragments of SOL with the downward Lowenheim-Skolem property
For $S$ a set of (parameter-free) second-order formulas and $\mathfrak{A},\mathfrak{B}$ structures, write $\mathfrak{A}\trianglelefteq^S\mathfrak{B}$ iff $\mathfrak{A}$ is a substructure of $\mathfrak{...
- 20.5k
2
votes
0
answers
116
views
Reference for a coarse complexity notion
Throughout, I'm only interested in structures with domain $\mathbb{N}$, no primitive relations, and at least $0,\mathsf{Succ}$ as primitive functions. The length of $m\in\mathbb{N}$ is $\lfloor 1+\...
- 20.5k
12
votes
1
answer
449
views
Can Friedman's property fail at or above a supercompact cardinal?
If $\kappa>\omega_1$ is a regular cardinal, $FP_\kappa$ is the assertion that every stationary subset of $\kappa$ consisting of ordinals of countable cofinality has a closed subset of order type $\...
- 1,799
1
vote
0
answers
53
views
Can MLU prove symmetric comprehension?
Working in $\sf ML$$\sf U$:
Define: $x \in^f y \iff f(x) \in y$
by $\varphi^f$ we mean the formula obtained by merely replacing each "$\in$" symbol in formula $\varphi$ by the symbol "...
- 11.3k
3
votes
0
answers
154
views
How the cardinalities of $\mathcal H^*_x$ and $\mathcal P(x)$ compare?
Working in $\sf ZF$, regarding an arbitrary Dedekind infinite set $x$, what's the relationship between the cardinality of $\mathcal P(x)$ and $\mathcal H^*_x$? The latter is the set of all sets ...
- 11.3k
4
votes
0
answers
174
views
Centers and conjugacy classes of groups relative to a pair of group homomorphisms
$\newcommand{\defeq}{\mathbin{\overset{\mathrm{def}}{=}}}$Given a group $G$, its center $\mathrm{Z}(G)$ and set of conjugacy classes $\mathrm{Cl}(G)$ are defined by
\begin{align*}
\mathrm{Z}(G) &\...
- 11.8k
2
votes
0
answers
369
views
Constructing the Stone space of a distributive lattice
Does anyone have a good reference for the method of giving a topology to a distributive lattice as outlined in M.H. Stone's "Topological representation of distributive lattices and Brouwerian ...
- 4,219
11
votes
1
answer
722
views
Existence of finite powerset
Consider ZFC with both powerset and infinity removed and collection and $\in$-induction included. The well-ordering principle is not assumed.
Does this theory prove that, for every set $X$, there is ...
- 236k
8
votes
0
answers
388
views
Can the p-adic be countable?
Recently arxiv submitted a new paper (Andrej Bauer, James E. Hanson, The Countable Reals) claiming an incredible theorem that Dedekind reals are not sequence-avoiding, and furthermore obtaining a ...
- 695
3
votes
0
answers
164
views
Can we have an inverted iterative hierarchy?
Let stratified $\sf Z$ have all axioms of $\sf Z$-$\sf Reg.$ with Infinity stipulated by existence of a Dedekind infinite set, and with Separation restricted to use only stratified formulas, where ...
- 11.3k
39
votes
2
answers
5k
views
Why is this new result such a big deal?
This popular article reports a recent result in reverse mathematics, showing that a certain theorem in Ramsey theory is provable from RCA$_0$, the base theory in SOSOA. Then there are a bunch of ...
CommunityBot
- 1