All Questions
1,141 questions
10
votes
4
answers
978
views
On surjections, idempotence and axiom of choice
The following assertion is trivial in ZFC, or even in much weaker theories. Is it also true in ZF?
(I couldn't find it in the Consequences site so far.)
If $A$ is an infinite set such that $A$ can ...
- 39.8k
10
votes
2
answers
455
views
Is equivalence of functions built from nested exponentiations a decidable problem?
Let $\mathcal{E}$ be the minimal set of symbolic expressions (without any predefined meaning) such that
The symbol $x$ is in $\mathcal{E}$, and
If expressions $P,Q\in\mathcal{E}$, then the ...
- 1,699
10
votes
1
answer
2k
views
Generating family for the Lebesgue $\sigma$-algebra
Let $X$ be a set, and $\cal F$ a family of subsets of $X$, let $\Sigma(\cal F)$ denote the smallest $\sigma$-algebra containing $\cal F$. We can also define $\Sigma(\cal F)$ internally using a ...
- 39.8k
10
votes
5
answers
2k
views
The use of the word "model" in Mathematical Logic vs the same word in Natural Sciences [closed]
I have always been wondering
why the term "model" is used by mathematicians (especially in mathematical logic) in a conceptually different (even opposite) way than it is used by other scientists, ...
- 23.3k
10
votes
1
answer
2k
views
Finite order arithmetic and ETCS
I'm looking for a reference to the statement that Lawvere's Elementary Theory of the Category of Sets (ETCS) is equal in proof-theoretic strength to finite order arithmetic. The person who informed ...
- 27.7k
10
votes
1
answer
3k
views
Axiom of choice and non-measurable set
We know that existence of a Lebesgue non-measurable set follows from the Axiom Of Choice. Is the converse true? That is, does the existence of a Lebesgue non-measurable set imply the Axiom Of Choice?...
- 101
10
votes
3
answers
1k
views
Categoricity in second order logic
Hi,
It's shown by an easy cardinality argument that there are complete second-order theories that are not categorical (have more than one model up to isomorphism). Anyone knows of a concrete example ...
- 666
10
votes
1
answer
462
views
Reverse mathematics of meromorphic functions on Riemann surfaces
Various sources touch briefly on the reverse mathematics of measure theory and complex analysis. But I have found none on the uniformization theorem for Riemann surfaces or the existence of non-...
- 11.1k
10
votes
2
answers
504
views
A totally categorical structure with trivial geometry which is not interpretable in the trivial structure
Among the theorems of early geometric model theory there is one by Lachlan stating that every totally categorical structure with a trivial pregeometry is intrepretable in a dense linear order.
That ...
- 4,070
10
votes
3
answers
545
views
A model of CH +$\lnot \diamondsuit$
All of the models of CH which I know of also satisfy $\diamondsuit$. What is the easiest way to produce a model of CH wherein $\diamondsuit$ is false?
- 103
10
votes
1
answer
440
views
Reference for a generalization of Γ-spaces to monoidal model categories
Γ-spaces were introduced by Segal in 1969 as models for what can be now described
as commutative ∞-monoids and ∞-groups in cartesian symmetric monoidal ∞-categories, e.g., E_∞-spaces and connective ...
- 37.8k
10
votes
2
answers
2k
views
Scott on the consistency of the lambda calculus
I have twice heard it attributed to Dana Scott that he said something to the effect that the consistency of the lambda-calculus was an accident.
Does anyone have a reasonable-sounding source for this?...
- 2,283
10
votes
0
answers
314
views
How much do idempotent ultrafilters generate in terms of semigroups?
It is known that the set of ultrafilters on, say, the natural numbers $\mathbb{N}$, can naturally be endowed with the structure of a compact topological left semigroup (which fails to be anything ...
- 1,914
10
votes
3
answers
1k
views
Is set-induction relatively consistent?
One way to state the axiom of foundation is that the $\in$ relation on any transitive set is well-founded in the following sense:
A relation $(X,\prec)$ is well-founded if for any subset $S\subseteq ...
- 66.8k
10
votes
2
answers
2k
views
The egg and the chicken
After posting this question (in particular after Carl's and Peter's answers) I have realized that the answer seems to depend on a basic problem in foundations.
Most mathematicians accept as given the ...
- 14.7k
10
votes
5
answers
1k
views
On the notion of partial semigroup
A partial binary operation on a set $X$ is just a (partial) function $\varphi: X \times X \rightharpoonup X$ (I'm using \rightharpoonup for partial maps), and a partial magma is a pair $\mathbb M = (M,...
- 10.5k
10
votes
0
answers
514
views
Existence of a regular subposet which collapses everything except the top cardinal
Suppose $\delta$ is an inaccessible cardinal, and $\mathbb{P}$ is the Levy Collapse $\text{Col}(\kappa, \delta)$ which adds a surjection from $\kappa \to \delta$ (for some regular $\kappa < \delta$)...
- 2,231
9
votes
1
answer
649
views
Can $\mathbb{R}$ be partitioned into dedekind-finite sets?
Assuming $ZF$ itself is consistent, it is consistent that there are sets $D$ which are infinite but cannot be placed in bijection with any of their proper subsets; such sets are called "strictly ...
- 20.5k
9
votes
1
answer
698
views
Source for NBG+Equipollence conservative over ZFC?
The "conservative" class theory, NBG, proves no new theorems about sets (with respect to ZFC). The choice function used here is set choice, and it's not too hard to prove (if M is a ctm for ZFC, then ...
- 1,979
9
votes
2
answers
1k
views
What sort of structure can amorphous sets support?
Assuming the Axiom of Choice, every cardinal is either finite (i.e., an element of $\omega$) or Dedekind-infinite (i.e., in bijection with a proper subset of itself). This dichotomy is not true in ZF, ...
- 20.5k
9
votes
1
answer
496
views
Can two versions of $\omega_1^{CK}(\mathsf{Ord})$ ever coincide?
The goal of this question is to fill in the gap in this old answer of mine.
For a transitive set $M$, thought of as an $\{\in\}$-structure, we define the following ordinals (this is not the notation ...
- 20.5k
9
votes
1
answer
336
views
How much can complexities of bases of a "simple" space vary?
Given a countable subbase of a topology, we can consider its complexity in terms of the difficulty of determining whether one family of basic open sets covers another basic open set. My question is ...
- 20.5k
9
votes
1
answer
634
views
Starting Hilbert's Program on the other end
The idea of Hilbert's program was to start with a simple finitary logic and proof the consistency of more complex systems in this system. Of course, this turned out to be problematic. Even when ...
- 1,659
9
votes
3
answers
1k
views
First-order axiomatization of free groups
Is there a way to axiomatize [non-abelian] free groups in first-order logic using the language of groups (which contains the binary operation symbol $\cdot$, and the constant symbol $e$)?
Is there ...
- 39.8k
9
votes
1
answer
232
views
Elementary equivalence of monoidal categories =?
Recall that, in model theory, two models $M_1$ and $M_2$ of the same signature are elementary equivalent if $ M_1 \models \phi \Leftrightarrow M_2 \models \phi $ for every first order formula $\phi$ ...
- 43.2k
9
votes
1
answer
782
views
Can the first ordinal in which $V\neq HOD$ be $\aleph_\omega$?
Assume that $V\neq HOD$ and let $\kappa = \min \{\alpha\in On \mid \mathcal{P}(\alpha) \not\subseteq HOD\}$.
Clearly, $\kappa$ is a cardinal.
Question: Is it consistent that $\kappa = \aleph_\...
- 5,112
9
votes
2
answers
2k
views
What is the free monoidal category generated by a monoid?
In several places in a segment on cohomology (for example, here (PDF)) in John Baez's online lecture notes for a course in 2007 on quantum gravity, much is made of the fact that the simplex category $...
- 1,446
9
votes
1
answer
552
views
"Towers" on singular cardinals with countable cofinality
Let $\lambda$ be a singular cardinal of countable cofinality.
Is there necessarily a sequence $\{A_\alpha\mid\alpha<\lambda^+\}$ of countable subsets of $\lambda$, such that $\alpha<\beta$ if ...
- 39.8k
9
votes
0
answers
256
views
A bi-modal logic related to determinacy
The short version of my question is as follows. There is a natural (I hope!) way to associate a bimodal theory to a game (two-player, perfect-information, length-$\omega$, on $\omega$); are there "...
- 20.5k
9
votes
9
answers
2k
views
Existence of unknowable algorithms ?
Here by «algorithm» I mean a (halting) Turing machine with finite alphabet and memory.
Is it possible to obtain by purely existential (i.e. non-constructive) means the existence of an algorithm ...
- 5,428
9
votes
1
answer
470
views
Is there any o-minimal expansion of the real field with functions of growth higher than exponential?
Let $\bar{\mathbb{R}}$ be the structure of the real field, that is $(\mathbb{R},0,1,+,-,*,<)$ . We say that a function $f$ is of growth higher than exponential if for all $N\in \mathbb{N}$ there $f(...
- 345
9
votes
1
answer
377
views
Is restricting Replacement and Separation enough to make $Q+I\Sigma_n$ bi-interpretable with Set Theory?
We have the result that $\mathsf{ZFCfin}$, the usual $\mathsf{ZFC}$ axioms with the axiom of infinity replaced by its negation, is bi-interpretable with $\mathsf{PA}$, first order Peano Arithmetic. We ...
- 482
9
votes
1
answer
489
views
Intuition behind Pincus' "injectively bounded statements"
In
David Pincus, Zermelo-Fraenkel Consistency Results by Fraenkel-Mostowski Methods,
The Journal of Symbolic Logic, Vol. 37, No. 4 (Dec., 1972), pp. 721-743
Pincus introduces the notion of ...
- 35.5k
9
votes
1
answer
765
views
Why relative consistency results by forcing arguments are provable in finitistic metatheory
It is claimed in many textbooks that relative consistency results, such as $\text{Con}(\text{ZFC})\rightarrow\text{Con}(\text{ZFC}+2^{\aleph_0}\geq\aleph_2)$, are provable in the finitistic metatheory....
- 779
9
votes
1
answer
603
views
Substitutional modality
An informal definition of a logical truth is a sentence that's true in virtue of its form alone: $\phi$ is logically true iff all substitutions of $\phi$ that leave its logical vocabulary alone are ...
- 357
9
votes
1
answer
834
views
Axiom of class collection
One version of the Axiom of Collection says that any surjection $A\to B$ from a class $A$ to a set $B$ is factored through by some surjection $C\to B$ where $C$ is a set.
Note that assuming $B$ is a ...
- 66.8k
9
votes
1
answer
749
views
Has Goedel's Second Incompleteness Theorem been proven using Lawvere's Fixed Point Theorem?
This question is a request for assistance in surveying the existing literature on applications of Lawvere's Fixed Point Theorem (LFPT).
Yanofsky [0] has demonstrated several applications of LFPT to ...
- 93
9
votes
0
answers
161
views
Number of tautologies of a given size?
Fix some complete set of $L$ logical connectives such as $\{ \wedge, \neg \}, \{\Rightarrow, \neg \}, \{\ \vee, \wedge, \neg \}, \{ \uparrow\}, \{\wedge, \vee, \neg, \Rightarrow \}$ - I'll assume all ...
- 1,075
9
votes
1
answer
341
views
Logics detecting their own equivalence notions, take two: $\mathcal{L}_{\omega_2,\omega}$
This question is a follow-up to another question of mine, with different language - see the link below.
Say that an infinite regular cardinal $\kappa$ is Fraissean iff the logic $\mathcal{L}_{\kappa,\...
- 20.5k
9
votes
1
answer
559
views
Just a little absoluteness might be cheaper?
Absoluteness is a wonderful thing, but expensive consistency-strength wise. My question is, when can we get large amounts of absoluteness in specific situations for much cheaper?
Specifically, fix a ...
- 20.5k
9
votes
1
answer
514
views
Is Heyting arithmetic sufficient to prove its own (formalized) existence property?
Let $\mathsf{HA}$ denote first-order Heyting arithmetic (viꝫ., Peano axioms with unrestricted recursion scheme, in first-order intuitionistic logic). It is known (e.g., Troelstra & van Dalen, ...
- 32.5k
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$?
- 1,490
9
votes
2
answers
844
views
Connection between the two-variable case of Hilbert's Tenth Problem and Roth's Theorem.
Connection between Hilbert's Tenth Problem and Roth's Theorem.
The following two decision problems seem to be open:
Given a polynomial equation in two variables with integer coefficients, determine ...
- 6,199
9
votes
4
answers
3k
views
Incompleteness and nonstandard models of arithmetic
The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome.
Reading Peter Smith's "Gödel Without (Too Many) Tears",...
- 1,465
9
votes
1
answer
862
views
Harrington's unpublished note "The constructible reals can be anything"
Around 1974, Leo Harringto wrote an unpublished note entitled "The constructible reals can be anything", in which he proved that it is consistent that being $\Delta^1_n$ is the same as being ...
- 32.2k
9
votes
3
answers
2k
views
What is the reverse mathematics of first-order logic and propositional logic?
Suppose one tries to formalize first-order logic. How much "strength" is required to do this?
Strength can mean in various senses:
The fragment of ZFC needed to codify first-order logic.
Which ...
user2529
9
votes
3
answers
1k
views
Structure Theorem for finitely generated commutative cancellative monoids?
Is there a Structure Theorem for finitely generated commutative cancellative monoids?
Of course they can be densely embedded into a finitely generated abelian group, whose structure is known. Also, ...
- 63.1k
9
votes
0
answers
243
views
Is this cardinal characteristic trivial? (Number of strategies needed to guarantee at least one win)
(Previously asked at MSE.)
Let the determinacy number, $\mathfrak{g}$ (for "game"), be the smallest cardinal such that for every (two-player, perfect-information, length-$\omega$) game on $\...
- 20.5k
9
votes
1
answer
1k
views
Definable set in ZF that cannot be proved to be Borel
Is there a predicate $P(x)$ such that $\mathrm{ZF} \vdash \exists! x. P(x)$, and $\mathrm{ZF} \vdash \forall x. P(x) \to (x \subseteq \mathbb R)$, but $\mathrm{ZF} \nvdash \forall x. P(x) \to \mathsf{...
- 1,262
9
votes
0
answers
440
views
A new maximality principle and its consequences
Let us consider the following maximality principle:
$(MP_*):$ For all uncountable regular cardinals $\kappa, 2^{<\kappa}=\kappa^{+}$
and all trees of height and size $\kappa$ are specialized.
It ...
- 32.2k