All Questions
6,027 questions
5
votes
0
answers
67
views
Definable pseudo-standard predicates in Internal Set Theory
Consider the usual language $\mathcal{L}=(\in, \mathrm{st})$ of Nelson's Internal Set Theory, and a unary $\mathcal{L}$-predicate $P$. For an $\mathcal{L}$-formula $\varphi$, let $\varphi^P$ denote ...
- 756
-5
votes
0
answers
250
views
Can Cardinality Theory capture ZFC?
Cardinality Theory "CT" is a theory of sets of cardinals and links between them, only sets of cardinals can be assigned cardinalities. The links are unordered edges linking cardinals, they ...
- 11.3k
5
votes
1
answer
622
views
Non-atomic probability measures on N
One can intuitively imagine picking a random natural number and ask to what extent the intuition can be axiomatized.
Using the axiom of choice, there is a total finitely additive (monotonic) averaging ...
- 7,545
6
votes
0
answers
188
views
Is there a characterization of measurables in terms of indiscernibles?
There is a characterization of $\alpha$-Erdős cardinals in terms of sets of indiscernibles of order type $\alpha$. There is also a characterization of Ramsey cardinals in terms of sets of good ...
- 2,031
10
votes
1
answer
501
views
What is the least $\alpha$ such that $L_\alpha$ contains a non-measurable set
What is the least level of the constructable hierarchy that contains a non-measurable (Lebesgue) subset of $2^\omega$. If it makes a difference assume we are working inside L (V=L).
I'm pretty sure it ...
- 3,029
5
votes
1
answer
633
views
Consistency of ZFC with inaccessible cardinals but no measurable cardinals
Let $S$ be a set and k a infinite field. The injection $S \to k\mathrm{Alg}(k^S, k)$ (sending a point to the evaluation in it) is a bijection if and only if $S$ is a non-measurable cardinal (see for ...
- 6,962
2
votes
0
answers
92
views
Geometric interpretation of flags and the role of the rook monoid and Kazhdan–Lusztig theory in $M_n(\mathbb{C})$
Let $G = GL_n(\mathbb{C})$, $B$ be its Borel subgroup, and $P$ a parabolic subgroup. The space $G/B$ corresponds to complete flags in $ \mathbb{C}^n$, and $G/P$ corresponds to partial flags. The ...
- 141
2
votes
2
answers
172
views
Can the Category of that kind of small sets in $\sf NFU$ be Cartesian closed?
Working in Quine's $\sf NFU$, with urelements being at least as many as sets. Formally the latter is: $|Ur| \geq |Set|$.
Where $Ur$ is the set of all urelements and $Set$ is the set of all sets. We ...
- 11.3k
8
votes
1
answer
228
views
Examples of anti-classical theories in iFOL
An anti-classical axiom $\phi$ is one which is inconsistent with LEM
Are there any sources for good examples of anti-classical theories in intuitionstic first-order logic? There are many examples of ...
- 183
5
votes
0
answers
138
views
Cone avoidance and $\Pi^0_1$-classes
Suppose $X \subseteq 2^{\omega}$ is nonempty and $\Pi^0_1$ relative to $a$. Assume $c_0 \nleq_T b_0 \oplus a$ and $c_1 \nleq_T b_1 \oplus a$. Must there exist some $y \in X$ such that $c_i \nleq_T ...
- 51
6
votes
2
answers
523
views
Is the logic of the ($\infty$-?)topos of simplicial sets "contradictory up to homotopy"?
In a sense this is a followup to my earlier question Does the (1-)topos structure on simplicial sets have any homotopy-theoretic significance?.
In the topos of simplicial sets, the subobject ...
- 18.4k
4
votes
0
answers
100
views
Explicit superexponential growth for Presburger Arithmetic
Fischer and Rabin proved a superexponential bound $2^{2^{cn}}$ for the worst-case length of a proof of a proposition of length $n$ in Presburger arithmetic. The result is in
Michael J. Fischer and ...
- 16.6k
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 ...
- 185
4
votes
1
answer
239
views
True or false? Every left or right cancellative, duo semigroup is cancellative
A semigroup $S$ is duo if $aS = Sa$ for all $a \in S$, where $aS := \{ax: x \in S\}$ and similarly for $Sa$; for instance, every commutative semigroup is duo, and so is every group. On the other hand, ...
- 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
5
votes
1
answer
268
views
What oracles make finding isomorphism (of finite structures) easy?
Below, all structures are finite, in a finite language, with underlying set an initial segment of the natural numbers. This has been edited to fix errors pointed out by Emil Jerabek in his answer ...
- 20.5k
7
votes
2
answers
490
views
Is every cancellative semigroup a subdirect product of subdirectly irreducible cancellative semigroups?
By a classical result of Birkhoff (that is, Theorem 2 in [G. Birkhoff, Subdirect unions in universal algebra, Bull. AMS, 1944]) and the trivial fact that the class of semigroups is closed under the ...
- 10.5k
6
votes
3
answers
554
views
Conjecture about commutative semigroups
Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, ...
- 1,000
6
votes
1
answer
162
views
Can there exist a set of all transitive sets in a model of NF or NFU?
Is it consistent with $\sf NF$ or $\sf NFU$ to have a set of all transitive sets? Formally:
$\exists t \forall x (x \in t \leftrightarrow x \text { is transitive})$
Where "$x$ is transitive" ...
- 11.3k
1
vote
1
answer
154
views
Looking for Fitch-style Natural Deduction system that allows for open formula
I find most Natural Deduction proof systems only allow for close formulas, which are not convenient for FOLs without a constant. Most Sequent Calculus systems instead allow for open formulas, but it ...
- 127
18
votes
1
answer
555
views
When can we add choice to a model of ZF
For countable transitive models of ZF, is existence of a ZFC extension with the same height a first order property?
In other words, is there a statement $τ$ (in the language of set theory) such that ...
- 7,545
11
votes
1
answer
416
views
Examples of natural algebraic irreflexive relations
To motivate the question, consider the theory of rings.
Define $x \parallel y$ to mean $\exists w \exists z .((x - y) z = w (x - y) = 1)$, or in words, "$x - y$ is a unit".
Then $\parallel$ ...
- 15.9k
2
votes
0
answers
189
views
Semantic equivalence between mathematical proofs
Sometimes, we recognize two proofs of the same claim to be the "same" proof. In some cases, this sameness is obvious -- for example, the proofs that $\sqrt{2}$ and $\sqrt{3}$ are irrational ...
- 225
1
vote
0
answers
96
views
Determine equivalences in the generated collection of subgroups and quotients
Let $A$ be an abelian group, and $B_1, B_2, \dots, B_m$ be subgroups of $A$. Define the family of subgroups $\mathcal{D}_0 = \{ \{0\}, A, B_1, B_2, \dots, B_m \}$.
Let $\mathcal{C}_1$ be the ...
- 807
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
1
answer
385
views
Is "every infinite set of strictly subnumerous sets is supernumerous to its union" equivalent to AC?
Is the following sentence equivalent to $\sf AC$ over the rest of axioms of $\sf ZF$?
For each infinite set $X$: if for all $y \in X$ we have $|y| < |X|$, then $| \bigcup X|\leq |X| $?
Note: ...
- 11.3k
7
votes
2
answers
399
views
Numerical choice and reverse mathematics
Consider the following fragment of numerical choice in the language of second-order arithmetic:
for any arithmetical $\varphi$, we have:
$$
(\forall n\in \mathbb{N})(\exists m\in \mathbb{N})(\forall X\...
- 4,359
11
votes
3
answers
781
views
Is every recursively axiomatizable and consistent theory interpretable in the true arithmetic (TA)?
I am looking for a scholarly text that discusses this issue in detail.
- 317
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 $\...
6
votes
1
answer
228
views
Can we computably escape infinitely many functions (allowing partiality)?
Let $(p_i)_{i\in\omega}$ be a uniformly computable sequence of partial functions (i.e. the partial function $q(i,x)=p_i(x)$ is computable) such that infinitely many $p_i$s are total. Must there be a ...
- 20.5k
1
vote
0
answers
109
views
Name For Effective Cantor-Bendixsonish Derivitive
When dealing with a tree (substring closed subset of $\omega^{< \omega})$ a useful operation will frequently be to remove any nodes with finite ordinal rank (i.e., all nodes whose extensions on the ...
- 3,029
-2
votes
1
answer
218
views
If existence of a pre-isomorphism implies existence of an isomorphism, would AC follow?
Let a surjection $f: M \to N$ be called a pre-isomorphism on membership, if and only if:
$\begin{align} \forall x \in M \,\forall y \in M \,\exists x' \in M \exists y' \in M : \ & f(x')=f(x) \...
- 11.3k
15
votes
3
answers
2k
views
Exponentials of truth values
I noticed that the exponentiation identity
$$\exp(r + s) = \exp(r) \cdot \exp(s)~,$$
which is of course completely standard for real or complex numbers also holds in a Boolean setting.
That is, when I ...
- 349
13
votes
1
answer
291
views
Descriptive complexity of analytic continuation
Consider the set of complex power series
$$
f(z)=\sum_{n=0}^\infty a_nz^n
$$ that have radius of convergence $1$ and can be analytically continued to the neighborhood of some point on the unit circle. ...
- 623
4
votes
0
answers
214
views
Algebraic logic in the style of algebraic geometry
I am writing a thesis on algebraic logic, I wonder if there is any recent research on an idea mentioned in Yuri Manin's book on algebraic geometry and in another Russian textbook on differential ...
- 558
7
votes
1
answer
556
views
Does this ZFC+V=L like theory, have a limit on large cardinal properties?
Let $\sf T$ be a theory that has as axioms every axiom of $\sf ZFC$, and every theorem of $\sf ZFC + [V=L]$ that is neither provable nor disprovable by $\sf ZFC$, whose addition or addition of its ...
- 11.3k
14
votes
1
answer
642
views
Example of a forcing notion with finite-predecessor condition that does not add reals
This question seems very basic but I cannot seem to find any literature on it.
Let $\mathbb{P}$ be a forcing notion. If $p$ is a condition of $\mathbb{P}$, define the predecessor set of $p$ to be $$\{...
- 1,328
2
votes
0
answers
117
views
Can we have the set world obeying Quine's New Foundations with its well-founded realm obeying $\sf ZFC$?
Is this theory consistent?
Language: first order language of set theory,
Extra-logical axioms:
1. Extensionality: as in $\sf NF$.
2. Stratified Comprehension: as in $\sf NF$.
Define: a set is said ...
- 11.3k
20
votes
1
answer
694
views
Is the theory of ordinals in Cantor normal form with just addition decidable?
This seems like it should be a pretty well-studied question but I can't seem to find an easy answer:
Is the theory $(\varepsilon_0, +, \omega^{\ \cdot}, 0, 1)$ decidable?
From Is the theory of $(\...
- 1,452
-5
votes
1
answer
233
views
First research papers in mathematical logic [closed]
Hello I'm a software engineer who just wants to start research in mathematics soon. I'm interested in the foundations and hence I'm picking mathematical logic. As I have never touched undergraduate-...
19
votes
6
answers
2k
views
Book recommendation introduction to model theory
Next semester I will be teaching model theory to master students. The course is designed to be "soft", with no ambition of getting to the very hardcore stuff. Currently, this is the syllabus....
- 9,111
7
votes
1
answer
716
views
What is the flaw in Cooper's argument?
Lately I have been studying in the subject of degree theory, specifically definability results related to $\mathcal{D}$. A famous conjecture in the field due to Slaman and Woodin is that the only ...
- 893
11
votes
0
answers
430
views
Is $(\mathbb{R}, +)$ still injective as long as $(\mathbb{Q},+)$ is?
It is known that the existence of nontrivial injective abelian groups is independent of choice in ZF (or, rather, ZFA). In particular, $\mathbb{Q}$ is not provably injective, much less $\mathbb{R}$, ...
- 433
-4
votes
1
answer
140
views
About the definitions of well-foundedness in this extension of NFU that interprets ZFC?
Lets see how the world of sets could look like from the perspective of $\sf NFU$. So, here we work within the first order language of set theory, with the following extra-logical axioms:
1. Quine atom:...
- 11.3k
2
votes
0
answers
232
views
Is the poset in the following construction stationary $\aleph_{\alpha + 2}$-linked?
Definition: A poset P is $\mathbf{stationary}$ $\kappa^{+}$-$\mathbf{linked}$ if for every sequence of conditions $(p_{\gamma} | \gamma < \kappa^{+})$, there is a regerssive function $f: \kappa^{+} ...
2
votes
0
answers
102
views
Direct construction of an arithmetically high degree below $0^{(\omega)}$
The existence of a high arithmetic degree (meaning the degrees induced by the notion of relative arithmetic definability) below $0^\omega$ can be established by using Harrington/Simpson's ...
- 3,029
5
votes
1
answer
157
views
Intersection cardinalities in MAD families
Let $\newcommand{\o}{[\omega]^\omega}\o$ denote the collection of infinite subsets of the set of nonnegative integers $\omega$. We say ${\cal A}\subseteq \o$ is almost disjoint if $A\cap B$ is finite ...
- 48.9k
7
votes
0
answers
262
views
A version of determinacy for all sets
Under ZF + AD, some games are undetermined because of lack of choice. In fact, the axiom of choice is equivalent to determinacy of games of length 2. However, we can ask whether the lack of choice ...
- 7,545
82
votes
3
answers
20k
views
Czelakowski's claimed proof of the Twin Prime Conjecture
It seems like the article "The Twin Primes Conjecture is True in the Standard Model of Peano Arithmetic: Applications of Rasiowa–Sikorski Lemma in Arithmetic (I)" by Janusz Czelakowski ...
- 1,083
20
votes
1
answer
557
views
Almost orthogonal maps $f:\omega \to \{-1,1\}$
Let $\omega$ denote the set of non-negative integers. For sets $A,B$, let $B^A$ denote the set of maps $f:A\to B$. For $f,g\in\{-1,1\}^\omega$ we say that $f,g$ are almost orthogonal if there is $C_0\...
- 48.9k