All Questions
1,141 questions
16
votes
1
answer
1k
views
Does Urysohn's Lemma imply Dependent Choice?
It's widely known$^{1}$ that in the proof of Urysohn's Lemma (UL) one uses the Principle of Dependent Choice (DC). Inspired by the equivalence between DC and Baire's Category Theorem$^{2}$, I'd like ...
- 405
16
votes
1
answer
462
views
What sets of primes can we pick out with first-order statements?
For each prime $p$, we have the algebraically closed field $\bar{\mathbb F}_p$ with the Frobenius automorphism.
Given any first-order statement with no free variables using the symbols $0,1, +, \...
- 149k
16
votes
4
answers
4k
views
How are Modal Logic and Graph Theory related?
I am currently taking a graduate logic course on Modal Logic and I can't help notice that there are a certain class of graphs characterized by the modal axioms such as (4) $\Box p \rightarrow \Box \...
- 1,441
16
votes
2
answers
1k
views
Ultrafilters arising from Keisler-Shelah ultrapower characterisation of elementary equivalence
In model theory, two structures $\mathfrak{A}, \mathfrak{B}$ of identical signature $\Sigma$ are said to be elementarily equivalent ($\mathfrak{A} \equiv \mathfrak{B}$) if they satisfy exactly the ...
16
votes
1
answer
846
views
Are the rationals definable in any number field?
Let $K$ be a number field. Is it necessarily true that $\mathbb{Q}$ is a first-order definable subset of $K$? Equivalently (since in any number field, its ring of integers is a definable subset), is $\...
- 2,130
15
votes
2
answers
919
views
Which are the hereditarily computably enumerable sets?
My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a hereditarily computably enumerable (h.c.e.) set is ...
- 236k
15
votes
3
answers
1k
views
What did Paul Cohen mean by saying that generic sets of natural numbers have "no asymptotic density?"
In Paul Cohen's original 1963 paper on forcing, The independence of the Continuum Hypothesis, published in PNAS, he gives his general proof sketch of how he intends to create a model of ZFC that doesn'...
- 4,907
15
votes
1
answer
605
views
Is choice needed to establish the existence of idempotent ultrafilters?
It is well known that the Stone–Čech compactification $\beta \mathbb N^+$ of the positive natural numbers has the structure of a compact left semitopological semigroup and hence, by Ellis's lemma, has ...
- 38.6k
15
votes
1
answer
2k
views
Hartogs number and the three power sets
One of the most important constructions in ZF+$\lnot$AC is Hartogs number, defined as:
$$\aleph(X)=\min\lbrace\alpha:|\alpha|\nleq|X|\rbrace$$
We can prove that this ordinal always exists in the ...
- 39.8k
15
votes
1
answer
1k
views
Are wild problems related to undecidable ones?
In representation theory, there is a well-known notion of a wild classification problem (such problems have been discussed often on this forum, for example, here). In logic, there is a notion of an ...
- 5,654
15
votes
2
answers
2k
views
Propositional logic with categories
I have some vague sense that certain types of categories are related to certain types of logic. I've been meaning to learn more about this, so I thought I'd ask about the simplest case, propositional ...
- 118k
15
votes
2
answers
916
views
Element being trivial in a finitely presented group independent of ZFC
Is there an explicit finitely presented group $G$ and an element $g\in G$ such that the statement "$g$ is equal to the identity" is independent of ZFC?
user178109
15
votes
2
answers
2k
views
Is "There exists an unbounded non-measurable set but no bounded non-measurable set" consistent with $\mathsf{ZF}$?
This is a follow-up to this question. We say that a set $A \subseteq \mathbb{R}$ is bounded if there exists a finite interval $(a,b)$ such that $A \subseteq (a,b)$.
Working in $\mathsf{ZFC}$, the ...
- 1,442
15
votes
1
answer
986
views
Does every model of ZF-foundation have an extension, with no new well-founded sets, where every set is bijective with a well-founded set?
This question follows up on an issue arising in Peter LeFanu
Lumsdaine's nice question: Does foundation/regularity have any
categorical/structural consequences, in
ZF?
Let me mention first that my ...
- 236k
15
votes
1
answer
2k
views
Automorphisms of $P(\Bbb N)$
I believe I've proved that the power semigroup of non-negative integers with addition has a trivial automorphism group. The proof is a bit long, completely elementary and rather unremarkable (as the ...
- 1,445
15
votes
1
answer
1k
views
Is it consistent relative to ZF that $\frak c = \aleph_\omega$?
In ZFC we know that the continuum cannot have cofinality $\omega$.
However, in the Feferman-Levy model we have that $\frak c=\aleph_1$, and that $\operatorname{cf}(\omega_1)=\omega$. In fact in the ...
- 39.8k
15
votes
2
answers
1k
views
Exact sequence of monoids
What is the right definition of an exact sequence of monoid homomorphisms?
I can't seem to find a consistent in my searches; indeed Balmer (Remark 2.6,
http://www.math.ucla.edu/~balmer/Pubfile/...
- 3,009
14
votes
2
answers
1k
views
Economical hard word problem
Can anyone give me an example of a very simple word problem, where by "simple" I mean that it has very few generators and relations, that is nevertheless insoluble. To make the question easier, I am ...
- 29k
14
votes
2
answers
982
views
Can we collapse $\omega_1$ to $\omega$ without adding a dominating real?
(Disclaimer: This question was also asked at MSE (https://math.stackexchange.com/questions/71020/can-we-collapse-omega-1-without-adding-a-dominating-real). I'm posting it here because, when I asked it,...
- 20.5k
14
votes
2
answers
984
views
Recovering a monoidal category from its category of monoids
What kind of additional properties and/or structures one needs to impose on the category
of (commutative or noncommutative) monoids of some monoidal category
so that one can recover the original ...
- 37.8k
14
votes
1
answer
840
views
Is there a minimal inner model for determinacy?
Assume $\sf ZF+AD$. Is there some inner model $M$ containing all the ordinals such that $M\models\sf ZF+AD$ as well?
What if we require $\omega_1$ and/or $\omega_2$ to be computed correctly?
Can we ...
- 39.8k
14
votes
2
answers
2k
views
Condensed / pyknotic sets in terms of forcing over Boolean-valued models of set theory / multiverse concepts?
Here is one way of saying what a pyknotic set is. Fix an inaccessible cardinal $\kappa$, and let $Proj_\kappa$ be the category of $\kappa$-small, extremally disconnected compact Hausdorff spaces. ...
- 64k
14
votes
1
answer
417
views
Definability in the field of reals with a predicate for some powers of two
In "The field of reals with a predicate for the powers of two", Van den Dries has proved that the set of integers is not definable in $(\mathbb{R}, +,\cdot, \leq, 0, 1, 2^{\mathbb{Z}})$, where
$2^{\...
- 32.2k
14
votes
0
answers
297
views
Ordinal-valued sheaves as internal ordinals
Let $X$ be a topological space (feel free to add some separation axioms like “completely regular” if they help in answering the questions). Let $\alpha$ be an ordinal, identified as usual with $\{\...
- 32.5k
14
votes
2
answers
3k
views
Maximal ideal and Zorn's lemma
It is known that any nonzero ring A (say commutative with 1) has a maximal ideal. The proof uses Zorn's lemma.
Now I heard some people saying that if we assume A to be noetherian, then we don't need ...
- 1,271
14
votes
3
answers
867
views
Is Prikry forcing minimal?
Let $M$ be a model of $\sf ZFC$ in which $\kappa$ is a measurable cardinal, and $\cal U$ is a normal measure on $\kappa$. We can define the Prikry forcing (the most simple one) as the poset: $$\Bbb P=\...
- 39.8k
14
votes
1
answer
641
views
First order decidability of rings vs Diophantine decidability
Are there known (preferably ``concrete'') examples of a ring $R$ (commutative, with 1) such that:
$\bullet$ the first order theory of $R$ is undecidable, but
$\bullet$ the positive existential (= ...
- 19.6k
14
votes
2
answers
1k
views
Decomposing $\mathbf{\Pi}^1_1$ sets into closed sets
It is well known that every $\mathbf{\Pi}^1_1$-set is a union of $\aleph_1$-many Borel sets. I wonder whether it can be improved under certain reasonable set theory axioms assumption.
For example, ...
- 4,201
14
votes
3
answers
4k
views
Is non-connectedness of graphs first order axiomatizable?
A recent
question
asked for graph properties that are first order axiomatizable but not finitely axiomatizable.
Connectedness was mentioned in the context. Connectedness can be axiomatized in ...
- 16.2k
14
votes
1
answer
2k
views
What sort of large cardinal can continuum be?
I have stumbled across a related question asking which large cardinal properties can hold for $\aleph_1$. This question is probably also related, asking in what ways $\aleph_0$ is a "large" cardinal.
...
- 28.2k
14
votes
1
answer
523
views
Is there an infinitary sentence which is absolutely not second-order expressible?
This is a "forcing-absolute" followup to this question, whose answer was largely unsatisfying. The question is:
Suppose $V=L$. Is there an $\mathcal{L}_{\infty,\omega}$-sentence $\varphi$ ...
- 20.5k
14
votes
6
answers
28k
views
Induction vs. Strong Induction
Is there ever a practical difference between the notions induction and strong induction?
Edit: More to the point, does anything change if we take strong induction rather than induction in the Peano ...
14
votes
4
answers
2k
views
Fermat's Last Theorem and Computability Theory
This question stems from the paper "Computably categorical fields via Fermat's Last Theorem," by Russell Miller and Hans Schoutens (available online at http://qcpages.qc.cuny.edu/~rmiller/Fermat.pdf). ...
- 20.5k
14
votes
0
answers
427
views
Which functions have all the common $\forall\exists$-properties of continuous functions?
This is an attempt at partial progress towards this question. Meanwhile, Sam Sanders pointed out that my original term was already in use, as were a couple other back-up terms, so ... oh well.
For a ...
- 20.5k
14
votes
0
answers
391
views
Can the axiom of choice be expressed in 4 quantifiers?
This 2007 paper presents a 5-quantifier $(\in, =)$-expression that is ZF-equivalent to the axiom of choice, but leaves open the 4-quantifier case:
Thus the gap is reduced to the undecided case of a 4 ...
- 2,213
14
votes
3
answers
1k
views
The set of Godel numbers of true sentences.
Tarski's Theorem on the undefinability of truth gives me a bit of a headache, and as a beginner I am still trying to grapple with its consequences. Here's a question.
Let $T$ be the set of Godel ...
14
votes
1
answer
2k
views
Martin's "Philosophical Issues about the Hierarchy of Sets"
Some months ago (October 2010), in the context of the Workshop on Set Theory and the Philosophy of Mathematics, Professor Donald A. Martin gave a talk entitled "Philosophical issues about the ...
- 1,465
14
votes
1
answer
391
views
Reference request: Heyting algebra structure on Catalan numbers
I've noticed that for every natural number $n\in\mathbb{N}$, there is a finite Heyting algebra with cardinality $C(n)$, where $C(n)$ is the $n$th Catalan number,
$$1,1,2,5,14,42,132,\ldots$$
I'm ...
- 8,669
14
votes
2
answers
4k
views
Consequences of technically proving anything in Coq (on at least Linux) exploiting a bug? [closed]
Technically, it is possible to prove anything in Coq proof assistant [1] (on at least Linux) due to a programming feature (or bug). This seems tractable when validating large proofs. Human analysis ...
- 25.4k
14
votes
3
answers
778
views
When is $A$ "$L$-ish" whenever $B$ is "$L$-ish"?
My question is about a variant of the usual notion of relative constructibility, $\le_c$ (which an earlier version of this question confusingly denoted "$\le_L$"), in set theory.
Fix a ...
- 20.5k
14
votes
3
answers
2k
views
Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets
I just ran into this deceptively simple looking question.
Is it always possible to partition $\mathbb{R}$ (or any other standard Borel space) into precisely $\aleph_1$ Borel sets?
On the one hand, ...
- 44.4k
14
votes
2
answers
1k
views
Induction, the infinitude of the primes, and workaday number theory
There are various open problems in the subject of logical number theory concerning the possibility of proving this or that well-known standard results over this or that weak theory of arithmetic, ...
- 17.6k
14
votes
2
answers
1k
views
Perfect set property for projective hierarchy
Is there any paper discussing the consistency strength (or possible equivalents, maybe large cardinals) of just assuming the perfect set property for certain levels of the projective hierarchy?
- 392
14
votes
3
answers
941
views
Reverse mathematics below RCA
I'm sure this is a fairly basic question, but I can't seem to find a solid answer:
My primary question is: Is there a reasonably nice subsystem of second-order arithmetic corresponding essentially to ...
- 20.5k
14
votes
1
answer
508
views
What are internal complete atomic boolean algebras, intuitively?
The category of complete atomic boolean algebras $\mathbf{CABA}$ is equivalent to $\mathbf{Set}^{\mathrm{op}}$ via
$$\mathbf{Set}^{\mathrm{op}} \to \mathbf{CABA}, ~ X \mapsto (P(X),\bigcup,\bigcap).$$
...
- 63.1k
14
votes
2
answers
1k
views
Is Kripke Platek theory finitely axiomatizable?
I know that closure under the Gödel operations is equivalent to $\Delta_0$-separation (plus extensionality, union, pair, foundation). This is finitely axiomatizable. But when we add $\Delta_0$-...
- 183
14
votes
3
answers
3k
views
Definition of relativization of complexity class
Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$?
Usually, these classes and their relativizations seem to be defined in an ad-hoc ...
- 3,475
14
votes
1
answer
1k
views
Is it possible for a theorem to be constructive only in a non-constructive metatheory?
There are several theorems in category-theoretic logic which say something like, "any proposition in X logic that is provable in topos logic assuming (the law of excluded middle and) the axiom of ...
- 15.9k
13
votes
3
answers
1k
views
Which ordinals can be proof-theoretic ordinals of a reasonable theory?
When talking to a friend recently he asked a question - are there any reasonable first-order theories which have proof theoretic ordinal equal to small or large Veblen ordinal? I have then extended ...
- 28.2k
13
votes
1
answer
672
views
Forcing PFA with ccc forcing
Is it consistent (from suitable large cardinals) that there is a ccc poset which forces PFA?
This seems quite implausible to me. If we could force PFA via ccc forcing, the ground model would have to ...
- 2,389