All Questions
1,135 questions
13
votes
3
answers
1k
views
Can ultraproducts avoid all "factor structures"?
This came up in the comments to an answer of Joel's. Suppose $\mathcal{M}_i$ ($i\in I$) are elementarily equivalent structures in the same fixed signature and $\mathcal{U}$ is an ultrafilter on $I$. ...
- 20.5k
13
votes
0
answers
252
views
Intuitionistic proofs of propositional formulae versus natural transformations between finite sets
The setup: Given a formula $\varphi$ of intuitionistic propositional logic (i.e., made from the connectors $\Rightarrow$, $\land$, $\lor$, $\top$ and $\bot$ from propositional variables $A,B,C,\ldots$)...
- 32.5k
13
votes
0
answers
387
views
On sentences true in all finite groups (revisited)
Let $w$ be a group word with variables $\bar x, \bar y$, where
$\bar x=(x_1,\dots ,x_m)$ and
$\bar y=(y_1,\dots ,y_n).$
I am interested in the following questions.
(1) Is the sentence $(\forall\bar ...
- 893
13
votes
1
answer
565
views
Long chains of amorphous cardinalities
An amorphous set is an infinite set that cannot be partitioned into 2 infinite subsets. An amorphous cardinality is the cardinality of an amorphous set. Working in $\sf ZF$, it is consistent that ...
- 576
13
votes
1
answer
438
views
Is this notion of finiteness closed under unions?
This was asked and bountied at MSE without success.
Throughout, we work in $\mathsf{ZF}$.
Say that a set $X$ is $\Pi^1_1$-pseudofinite if for every first-order sentence $\varphi$, if $\varphi$ has a ...
- 20.5k
13
votes
1
answer
524
views
How much determinacy do you need for second order arithmetic to be as strong as ZFC?
From Wikipedia (I couldn't find the original source):
$\text{ZFC} + \{\text{there are $n$ Woodin cardinals: $n$ is a natural number}\}$ is conservative over $\text{Z}_2$ with projective determinacy.
...
- 6,353
13
votes
3
answers
796
views
How to make countably closed forcing "nice" without choice
When working over a model $V$ of $ZFC$, countably closed forcings are extremely nice:
If $\mathbb{P}$ is countably closed, then $V[G]$ has no new $\omega$-sequences of elements of $V$. In ...
- 20.5k
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
4
answers
2k
views
Set-Theoretic Issues/Categories
It is a major bummer that one cannot strictly speaking talk about the category of all categories without saying "it is not really a category, since the morphisms between objects may form a class" and "...
- 131
13
votes
1
answer
561
views
Iterating Neeman's forcing
In the paper, "Forcing with sequences of models of two types," (MR3201836), Neeman claims that, using a supercompact and a weakly compact above, one can force with his pure side conditions ...
- 18.6k
13
votes
1
answer
472
views
Real numbers with given complexity
This may be an easy question or it may be related to a well known open problem in Computer Science.
Let $\alpha>0$. We say that $\alpha$ is computed in time $T(n)$ if there is a Turing machine ...
user6976
13
votes
1
answer
988
views
What is the proof-theoretic ordinal of PA + Con(PA), PA + Con(PA + Con(PA)) etc., and why?
I seem to remember having read that the proof-theoretic ordinal (sup of ordinals the theory can prove well-ordered) of $\mathsf{PA} + \mathsf{Con}(\mathsf{PA})$ is the same as that of $\mathsf{PA}$, ...
- 151
13
votes
0
answers
345
views
Can you define a probability measure on the set of countable transitive models of ZFC?
It is well known that the set of hereditarily countable sets $H(\omega_1)$ —or, if you prefer, $H_{\omega_1}$— has cardinality $2^{\aleph_0}$, and I understand that every countable ...
- 1,124
13
votes
1
answer
1k
views
What ccc forcings add a Suslin tree?
In a comment to Miha's question in Forcing PFA with ccc forcing, I suggested that if such situation is even possible, it might be achieved by screwing with PFA by some ccc forcing (e.g. adding a Cohen ...
- 39.8k
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
13
votes
5
answers
1k
views
"Let $x \in A$", beginning a proof of "$\forall x \in A$ ...", if A were empty [closed]
I work at a four-year teaching school, where we pride ourselves on teaching pure math, proof, and a rather obsessive carefulness of work. Recently I have been criticized for saying that "Let $x \in A$...
- 139
12
votes
1
answer
780
views
Does every countable set of Turing degrees have an upper bound, without AC?
It is easy to see that every countable collection of sets $A_n\subseteq\mathbb{N}$ has an upper bound in the Turing degrees, since we can just take a copy of their disjoint sum $\oplus_n A_n=\{\langle ...
- 236k
12
votes
1
answer
794
views
Is Girard's LU just an embedding of classical and intuitionistic logic into linear logic?
This question is about Girard's system LU, presented in his paper On the unity of logic. Girard starts by giving a "modal" sequent calculus with two zones of both hypotheses and consequents, $\Gamma;\...
- 66.8k
12
votes
1
answer
1k
views
Is an ultrafinitist Hilbert's program doomed?
Hilbert's program is popularly understood as an attempt to justify infinitary mathematics with a finitary consistency proof. Godel's Second Theorem is usually considered as showing this is not ...
- 1,974
12
votes
6
answers
2k
views
Uses of bisimulation outside of computer science.
Bisimulation is one of the most important ideas of theoretical computer science. I was wondering whether bisimilarity is used/known outside of computer science/modal logic? I am aware that it ...
- 1,882
12
votes
0
answers
357
views
Undetermined copy/diagonalize games without CH
This question was the motivation behind an earlier question of mine; having thought about it some more, that question seems nontrivial and the connection is actually pretty tenuous anyways, so I've ...
- 20.5k
12
votes
0
answers
721
views
Diagonal lemma from recursion theorem?
Does Gödel's diagonal lemma follow from Kleene's recursion theorem? I believe the converse is true, by an argument like the following.
Let e ↦ θe be a bijection between ω and ...
- 1,081
12
votes
2
answers
583
views
Do there exist acyclic simple groups of arbitrarily large cardinality?
Recall that a group $G$ is acyclic if its group homology vanishes: $H_\ast(G; \mathbb Z) = 0$. Equivalently, $G$ is acyclic iff the space $BG$ is acyclic, i.e. $\tilde H_\ast(BG;\mathbb Z) = 0$.
In ...
- 64k
12
votes
1
answer
744
views
Is the following construction of the 0-Hecke monoid (well) known?
Let W be a Coxeter group with Coxeter generators S. The corresponding 0-Hecke monoid H(W) has generating set S, the braid relations of W and the relations that each element of S is an idempotent. If ...
- 38.6k
12
votes
2
answers
429
views
Trading Choice for Comprehension (or Replacement)
This question is basically a request for clarification about a remark made by Sam Sanders in a comment to another question: IIUC what he's saying, there are statements that can be proved either with a ...
- 32.5k
12
votes
1
answer
863
views
Probability that a Turing machine is universal?
I choose a Turing machine T with n states and an input tape at random.
What can be proven about the probability P_A(n) that it is not decidable whether T will halt for a particular input? What can be ...
- 187
12
votes
1
answer
1k
views
Testing whether $e^x+ax^2+bx+c$ has a zero
What is the simple test with exponential polynomials to determine whether
$$f(x)=e^x+ax^2+bx+c$$ has a positive zero?
This was prompted by the question about discriminants here. We have an ineffective ...
user44143
12
votes
1
answer
584
views
"Set theory" founded on lists rather than sets
On a computer, sets are often represented rather "indirectly / implicitly", e.g. in terms of some properties that they or their members satisfy. But some sets can be represented more "directly / ...
- 3,612
12
votes
1
answer
482
views
Is there a useful measure of density of decidable sentences in PA?
Essential undecidability of PA says every complete extension of PA includes a non r.e. set of new "axioms," all undecidable in PA. In that sense lots of sentences of PA are undecidable in ...
- 11.1k
12
votes
6
answers
3k
views
Can you do math without knowing how to count?
Are there mathematical theories that do not use intuitive integers? [That is, do not use integers to write statements.]
Can you propose a theory that describes natural integers, without using ...
- 4,074
12
votes
1
answer
475
views
Stone duality for the algebra of Boolean functions such that $f(\top,\dots,\top) = \top$, or: What does the presheaf topos on $FinSet_\ast$ classify?
$\newcommand\FinSet{\mathit{FinSet}}\newcommand\FinBool{\mathit{FinBool}}\newcommand\FreeFinBool{\mathit{FreeFinBool}}\newcommand\Set{\mathit{Set}}\newcommand\Psh{\mathit{Psh}}$It's well-known that ...
- 64k
12
votes
2
answers
778
views
Why "adding" a single extender cannot give an L-like inner model for say, a strong cardinal?
The constructible universe $L$ is too thin for large cardinals greater than measurable. To build $L$-like inner models for large cardinal, it is natural to think about "adding" the evidences into the ...
- 779
12
votes
1
answer
486
views
The strength of "There are no $\Pi^1_1$-pseudofinite sets"
For $\Gamma$ a set of second-order sentences in the empty language, say that a set $X$ is $\Gamma$-pseudofinite if $X$ is infinite but for every sentence $\varphi\in\Gamma$ which is satisfied in every ...
- 20.5k
12
votes
1
answer
429
views
The scope of a "strong Cantor-Bernstein" property
This question is of course related to this earlier MO question, but I don't believe is answered by the posts there.
My favorite proof of the Cantor-Schroeder-Bernstein theorem actually establishes ...
- 20.5k
12
votes
1
answer
695
views
A new cardinality living in every forcing extension?
I'm broadly interested in notions of "generic presentability" - when a given object exists in every forcing extension of the universe by some fixed forcing, at least up to the appropriate ...
- 20.5k
12
votes
1
answer
556
views
Building the real from Dedekind finite sets
It is well known that the real numbers can be countable union of countable sets by starting with GCH and taking a finite support permutations while collapsing all of $\aleph_n$ for natural $n$.
The ...
- 1,676
12
votes
1
answer
296
views
Can the cardinal $2^{\aleph_0}$ be order-embedded in ${\cal P}(\omega)/(\text{fin})$?
For $A,B\in{\cal P}(\omega)$ we say $A\subseteq^* B$ if $A\setminus B$ is finite (that is, $A$ is "almost contained" in $B$). We write $A\simeq_{\text{fin}} B$ if $A\subseteq^* B$ and $B\...
- 48.9k
12
votes
1
answer
1k
views
Can there be only one (uncountable transitive model of ZFC)?
It is an immediate consequence of Cohen's forcing that if there is one countable transitive model of $\sf ZFC$, then there are many of them. Even if all of these models are of the same height, there ...
- 39.8k
12
votes
1
answer
448
views
Comparing generic versions of $\mathbb{R}$
This question was previously asked and bountied at MSE, unsuccessfully.
I'm currently interested in the behavior of cardinalities in generic extensions of models of $\mathsf{ZF+\neg AC}$, and ...
- 20.5k
12
votes
1
answer
834
views
Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?
Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
- 6,819
12
votes
1
answer
512
views
What is the "iterated definability" limit of first-order logic?
Roughly speaking, given a set-sized logic $\mathcal{L}$ let $\mathcal{L}'$ be gotten by adding to $\mathcal{L}$ the ability to quantify over $\mathcal{L}$-definable relations. (The details are a bit ...
- 20.5k
12
votes
2
answers
490
views
Conflating reals and sets of countable ordinals "nicely"
It is consistent with ZFC that $2^{\aleph_1}=2^{\aleph_0}$. This can be gotten easily via forcing; more interestingly, it is a direct consequence of forcing axioms (which also set this value at $\...
- 20.5k
12
votes
1
answer
681
views
Can there be a small complete category in ZF?
It's a ZFC theorem of Freyd, any small complete category is a preorder. Freyd's theorem continues to hold in any Grothendieck topos. But Hyland showed it fails in some elementary toposes.
I don't ...
- 64k
11
votes
1
answer
812
views
Set-theoretic geology: controlled erosion?
I have to say that after the two last posts by Timothy Chow on Forcing I got so intrigued that I am trying to rethink the little I know about this formidable chapter of mathematics.
I have also to add ...
- 7,853
11
votes
5
answers
6k
views
Finding minimal or canonical expressions for Boolean truth tables
This is not an urgent question, but something I've been curious about for quite some time.
Consider a Boolean function in n inputs: the truth table for this function has 2n rows.
There are uses of ...
- 524
11
votes
2
answers
574
views
Identifying a group without 2-torsion
Suppose we have a finitely presented group $G$ with solvable word problem. (For instance, the command RWSGroup in Magma terminates giving us a finite [but possibly gigantic] rewrite system.) Is there ...
- 18.7k
11
votes
2
answers
483
views
The "strong" measure number
Beyond measure zero we have yet another measure-y notion of smallness: strong measure zero. A set $S\subseteq\mathbb{R}$ is strong measure zero if, for any $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$, ...
- 20.5k
11
votes
3
answers
946
views
When is $\mathbb{L}$-rank definable in inner models of $\mathbb{V} = \mathbb{L}$?
Suppose $\mathbb{V} = \mathbb{L}$ and there is a countable transitive model $\mathbb{M}$ of $ZFC$.
Let $\rho$ be the $\mathbb{L}$-rank, i.e. for all $a \in \mathbb{V}$, $\rho(a) = $the least $\alpha$...
- 2,146
11
votes
1
answer
452
views
A weak form of countable choice
Let $\Omega$ be the set/type of truth values. We're using constructive logic. Define
$AC_{0, 0} = \forall P : \mathbb{N}^2 \to \Omega, (\forall n \in \mathbb{N}, \exists m \in \mathbb{N}, P(n, m)) \to ...
- 263
11
votes
2
answers
720
views
Is there a modern account of Veblen functions of *several* variables?
Veblen $\phi$ functions extend the $\xi \mapsto \phi(\xi) := \omega^\xi$ and the $\xi \mapsto \phi(1,\xi) := \varepsilon_\xi$ functions on the ordinals by repeatedly taking fixed points (I won't ...
- 32.5k