All Questions
6,026 questions
6
votes
1
answer
481
views
Topological dynamics and Turing complete automata
One can look at, say, Conway's Game of Life in at least two ways:
1) as a cellular automaton; and
2) as a discrete topological dynamical system (on an underlying Cantor set).
Famously, Conway ...
- 17.6k
2
votes
2
answers
355
views
"Duals" of Lindenbaum algebras
From Wikipedia I learn:
The Lindenbaum algebra A of a theory T consists of the equivalence
classes of sentences of T. The operations in A are inherited from those in T.
If there are disjunction,...
- 9,720
10
votes
2
answers
822
views
Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)?
In the math.se question Proof of no prime-representing polynomial in 2 variables, Alon Amit asks if Ribenboim's claim that a prime-representing polynomial (a Diophantine polynomial in which the ...
- 9,114
3
votes
2
answers
410
views
mutually incompatible abstraction terms?
If $\phi$ is any formula of set theory with just one free variable $x$, the abstraction term $A_{\phi}=\lbrace x | \phi(x) \rbrace$ is either a set or a proper class. Assume that ZFC is consistent, or ...
- 3,595
27
votes
1
answer
1k
views
Independence of being an integer
In this MO question, the OP asked for an example of a statement which was known not to be independent of ZFC, but for which the truth value was unknown. I immediately thought of a question I asked on ...
- 9,683
6
votes
3
answers
1k
views
Is there an "undecided" assertion of which a proof that it's not undecidable is known?
Just a curiosity:
Is there an assertion of which a proof (formalizable, say, in ZFC) is not known but a proof that it's not undecidable (in ZFC) is known?
Edit: after the comments, I think the ...
- 23.3k
8
votes
1
answer
3k
views
Foundations: Existence of uncountable ordinals.
This isn't really a research question, but at least it's research-level mathematics. I'm talking with some other people about the first uncountable ordinal, and I want some facts to inform this ...
- 2,754
18
votes
1
answer
4k
views
Countable unions and the axiom of countable choice
Let us denote by ACC the axiom of countable choice, namely the assertion that the product of countably many non-empty sets is non-empty, and denote by UCC the assertion that a countable union of ...
- 39.8k
7
votes
1
answer
2k
views
"Almost all" quantifier
Suppose I enlarge the first-order logic with an "almost all" quantifier, let's denote it by G, ie.:
$G_x P(x) \iff$ for all but finitely many x, P(x)
Syntax for G is the same as for other ...
- 2,197
17
votes
4
answers
2k
views
Notation in Frege's Grundgesetze der Arithmetik: The U with a flourish
In the Grundgesetze der Arithmetik, Frege used a number of strange characters for notation. I would be most interested to know anything about the typography (origin, usage and so on) of the strange U ...
- 2,545
6
votes
2
answers
2k
views
Are all countable, nonstandard models of arithmetic given by ultrapowers?
Countable models of PA fall into two categories: the standard one $(\omega, S)$ and the nonstandard ones (all the rest). The only way I've seen to construct a nonstandard model is through taking an ...
- 168
1
vote
1
answer
184
views
Type implication
Hello,
Can anybody explain to me how, in model theory, a type $p$ in a theory $T$ and language $L$ implies a type $p'$ in theory $T'$ and language $L'$, with $T \subset T'$ and $L \subset L'$. \
Also ...
user16974
30
votes
3
answers
3k
views
Is it decidable whether or not a collection of integer matrices generates a free group?
Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
- 18.7k
16
votes
2
answers
602
views
Formally undecidable problems on finitely presented quandles
In the literature, one sometimes sees the claim that finitely presented quandles (in particular, knot quandles) are "hard to deal with". Hence, a great deal of effort has gone into studying finite ...
- 1,889
0
votes
0
answers
179
views
semigroup actions of groups on regular rooted trees
If $G$ is a group which has a semigroup action on a regular rooted tree via prefix-preserving, continuous transformations (I give the tree the path metric), what kinds of algebraic restrictions can we ...
- 125
4
votes
1
answer
378
views
Does ZF prove that proximity spaces are completely regular?
(This is based on my earlier question, but I think this one would be easier to answer.)
Let $\langle X,\mathbf{\delta} \hspace{.01 in} \rangle$ be a separated proximity space, and let $\cal{T}\hspace{...
user5810
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
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
5
votes
1
answer
710
views
Does ZF prove that a finite subtheory axiomatizes it over transitive proper class models?
If $\text{ZF}$ is consistent, then it is not finitely axiomatizable. For if $\Gamma$ is a finite axiomatization, then $\text{ZF}$ proves by reflection that $\Gamma$ has a set model, and hence (since $...
- 1,081
6
votes
2
answers
687
views
A necessary condition for S4-completeness?
It is well-known that the modal logic S4 is complete with respect to the class of all finite quasi-trees (where we interpret the $\Box$ modality as topological interior, and topologize a quasi-tree ...
- 373
17
votes
1
answer
1k
views
Does ZF prove that topological groups are completely regular?
Let $\mathbf{G} = \langle G,\cdot,\mathcal{T}\;\rangle$ be a topological group. Let $\mathbf{e}$ be the identity element of $\langle G,\cdot \rangle$.
Assume $\{\mathbf{e}\}$ is closed in $\langle G,\...
user5810
29
votes
6
answers
4k
views
Concrete example of $\infty$-categories
I've seen many different notions of $\infty$-categories: actually I've seen the operadic-globular ones of Batanin and Leinster, and the opetopic, and eventually I'll see the simplicial ones too. ...
- 3,349
6
votes
1
answer
623
views
When is the cofibrant replacement of a product the product of the cofibrant replacements?
I'm in a situation where I'd like to prove $Q(E\otimes E) \simeq QE \otimes QE$ for a monoid $E$ in a symmetric monoidal model category. I know it's not true in general that $Q(E\otimes F)\simeq QE \...
- 30.3k
4
votes
2
answers
394
views
Stable theory: question about definability of independece
I would like to know why the relation: R(x,y) iff x independent from y (i.e: tp(x/y) doesn't fork over the empty set) is type definable in stable theory?
Thanks to the helper.
- 41
3
votes
1
answer
449
views
Paths in Kleene's O and deciding $\Pi^0_1$ sentences
This question comes from the
Wikipedia article on Kleene's O and a previous Math Overflow question.
The claim in Wikipedia that I have a question about is the second sentence in the following quote.
"...
- 371
1
vote
1
answer
1k
views
Notion of Truth and Axioms
Hello,
The proofs in logic often use the notion of truth.
Can we ignore the notion of truth, if we add axioms to the Peano's axioms ?
Is it possible to prove Gödel's first incompleteness theorem ...
5
votes
2
answers
639
views
Characterizing elementary embeddings of $L$ and $L_\alpha$ under 0#
Suppose 0# exists.
It is clear that every order preserving map from the indiscernibles to the indiscernibles gives an elementary embedding from $L$ to $L$. Furthermore, following lemmas 18.7 and 18.8 ...
- 1,174
4
votes
1
answer
729
views
Proof system with same complexity as "informal mathematics"?
The Completeness Theorem in first-order logic states that any mathematical validity is derivable from axioms. Hence, any informal mathematical proof (which is rigorous) can be translated into a formal ...
- 3,475
4
votes
1
answer
306
views
ordered fields with the bounded value property, without choice
In his answer to my question ordered fields with the bounded value property, Ali Enayat showed that if one assumes the countable axiom of choice, then there exists a non-Archimedean ordered field $F$ ...
- 19.7k
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 ...
5
votes
1
answer
327
views
$\Sigma_n$ version of HOD
Fix a natural number, $n \geq 1$. Consider the class, M, of all sets hereditarily ordinal-definable using some $\Sigma_n$ formula. Since there is a universal $\Sigma_n$ formula, M is definable. Is M ...
- 1,174
11
votes
3
answers
1k
views
A unique ultrafilter extending a union of filters?
Original Question:
Let $\mathcal{P}(\omega)/fin$ denote the Boolean algebra formed from $\mathcal{P}(\omega)$ by modding out by the ideal $fin$ of finite subsets of $\omega$. As a first pass at the ...
- 373
12
votes
3
answers
2k
views
What are some other uses for Ehrenfeucht-Fraïssé games?
Let $\mathfrak{A} = \langle A, \dots \rangle$ and $\mathfrak{B} = \langle B, \dots \rangle$ be structures for a signature $\mathscr{L}$. For each ordinal $\gamma$ we define a game of perfect ...
- 1,081
3
votes
3
answers
1k
views
ZFC, set membership and FOL
Hi,
Is set membership defined in the signature of ZFC, or is it *specified" in the signature of ZFC? The wikipedia article http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory says that ...
- 133
23
votes
1
answer
2k
views
Can we axiomatize Omnific Integers without the Surreal Number system?
Omnific integers are the counterpart in the Surreal numbers of the integers. The surreal numbers are usually defined using set theory, and then the omnific integers are defined as a particular subset (...
- 4,597
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
22
votes
5
answers
1k
views
What is the spectrum of possible cofinality types for cuts in an ordered field? Or in a model of the hyperreals? Or in a nonstandard model of arithmetic?
I am interested to know the full range of possibilities for the cofinality type of cuts in an ordered field and in other structures, such as nonstandard models of arithmetic.
Definitions. ...
- 236k
4
votes
2
answers
2k
views
a different nested intervals theorem
Is there any literature on (and a standard name for) the proposition that for any arbitrary-cardinality collection of closed intervals in the reals that is nested (in the sense that, given any two of ...
- 19.7k
1
vote
1
answer
260
views
The intersection of Block Groups and R-trivial (finite) monoids
Let $\textbf{BG}$ be the pseudovariety of block groups, also known as $\textbf{EJ}, \textbf{PG},\ldots,\text{etc.}$(see [1]), and let $\textbf{R}$ be the pseudovariety of R-trivial monoids, by the ...
- 424
4
votes
2
answers
1k
views
density of boolean algebras
For a boolean algebra B, let d(B) be the least cardinality of a dense subset of B. Let A be a (non-regular) subalgebra of a boolean algebra B. Is it possible that d(A) > d(B)? What if d(B) = $\...
- 18.6k
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
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
2
votes
1
answer
367
views
is $ded^{*}(\kappa)< ded(\kappa)$ consistent?
Hello,
I wonder if anyone knows this.
Definition:
$ded\left(\lambda\right)$ is the supremum of all sizes
of linear orders with a dense subset of size $\lambda$.
$ded^{*}\left(\lambda\right)$ is the ...
- 428
7
votes
2
answers
875
views
Is $Ded(\kappa)<Ded(\kappa)^\omega$ consistent?
Hello,
I want to ask if anyone can tells us what is known (consistently) about $Ded(\kappa)$, $\kappa$ an infinite cardinal.
Definition If there is a dense linear order w/o endpoints of size $\...
- 2,882
46
votes
8
answers
12k
views
What are some proofs of Godel's Theorem which are *essentially different* from the original proof?
I am looking for examples of proofs of Godel's (First) Incompleteness Theorem which are essentially different from (Rosser's improvement of) Godel's original proof.
This is partly inspired by ...
18
votes
1
answer
1k
views
Lebesgue Measurability and Weak CH
Let $LM$ denote "all subsets of $\Bbb{R}$ are Lebesgue measurable", and
$WCH$ (weak continuum hypothesis) denote "every uncountable subset of $\Bbb{R}$ can be be put into 1-1 correspondence with $\...
- 17.7k
20
votes
3
answers
2k
views
A limit to Shoenfield Absoluteness
Shoenfield's Absoluteness Theorem states that if $\phi$ is any $\Sigma^1_2$ sentence of second-order arithmetic, then $\phi$ is absolute between any two models of $ZF$ which share the same ordinals. ...
- 20.5k
5
votes
1
answer
902
views
How much of P versus NP's difficulty stems from having to rule out the existence of Turing machines that "accidentally" solve, say, 3-SAT efficiently?
It seems like there is a sense in which a Turing machine that demonstrates P=NP could be said to "accidentally" exist. I'm wondering the extent to which the possibility of such machines is the main ...
- 505
11
votes
1
answer
1k
views
Cherlin's "Main Conjecture"
Cherlin's "Main Conjecture" from his 1979 paper "Groups of Small Morley Rank" is the following: Every simple $\omega$-stable group is an algebraic group over an algebraically closed field. Zilber was ...
- 359
5
votes
2
answers
634
views
Questions regarding "second and higher-order-undecidability"
I have moved this question here from MSE, because I did not receive any answers as of yet over there.
I know that there are statements that are neither provable nor disprovable within some set of ...
- 4,829