All Questions
6,026 questions
7
votes
4
answers
1k
views
$\aleph_\omega$ many subsets of $\aleph_\omega$
Consider the following question:
Is there a family $\mathcal{F}$ of subsets of $\aleph_\omega$ that satisfies the following properties?
(1) $|\mathcal{F}|=\aleph_\omega$
(2) For all $A\in \mathcal{...
- 2,882
4
votes
1
answer
505
views
Hyperarithmetic statements decidable by induction up to a recursive ordinal
The first version of this question received a helpful answer but was too vague to fully convey what I intended. I hope this version remedies that problem. For any hyperarithmetic set of integers $S$, ...
- 371
1
vote
2
answers
798
views
Subtler than meets the eye: does x=y imply forall x forall y x=y? [closed]
In Enderton's "Mathematical Introduction to Logic" (2ed p.88), $\Gamma\models\phi$ is defined to mean that for every model $M$ and every assignment $s$ such that $M\models\Gamma[s]$, $M\models \phi[s]$...
- 121
5
votes
1
answer
346
views
Semigroup product of the left-invariant completion of a Polish group (restatement of Question 71389)
This is a re-statement, of sorts, of the question Is there a relational countable ultra-homogeneous structure whose countable substructures do not have the amalgamation property?, so far unanswered.
...
- 577
3
votes
1
answer
1k
views
ordered fields with the bounded value property
Say that an ordered field $F$ satisfies the bounded value property if, for all $a < b$ in $F$ and for every continuous function $f$ from $[a,b]_F := ${$x \in F: a \leq x \leq b$} to $F$, there ...
- 19.7k
4
votes
3
answers
961
views
The Reverse Mathematics of writing a set as a union?
To be more precise, a countable collection of sets $(S_n)_{n \in \mathbb{N}}$ is encoded as the row of some given set $S$, i.e. $S_n = S^{[n]}$. Futhermore, for any function from $\mathbb{N} \...
- 155
16
votes
3
answers
1k
views
Is there a relational countable ultra-homogeneous structure whose countable substructures do not have the amalgamation property?
Is there a relational countable ultra-homogeneous structure whose countable substructures do not have the amalgamation property?
The question can be stated in a fashion not requiring much background:
...
- 577
8
votes
1
answer
897
views
Nelson natural number objects in a topos (say)
Nelson's predicative arithmetic (survey article) is a very weak system of arithmetic extending Robinson's $Q$ (Wikipedia).
We can have natural number objects in a topos, or even a merely finitely ...
- 35.5k
8
votes
3
answers
786
views
truth vs. provability for ordered fields
In Propositions equivalent to the completeness of the real numbers I started by asking "Can anyone point me to a reasonably comprehensive article (or book chapter) explaining which basic theorems of ...
- 19.7k
3
votes
1
answer
347
views
Formal verification of simple equational proofs (as in Universal Algebra...)?
Is there an software package aimed at verfication of simple equational proofs?
I am hoping to avoid the usual overhead involved with First Order Logic or Higher Order Logic verification systems.
[...
- 437
35
votes
9
answers
3k
views
Are there examples of statements that have been proven whose consistency proofs came before their proofs?
I'm wondering if there are examples of statements that have been proven whose consistency proofs came before the proofs of the statements themselves.
More informally, I'm wondering how promising in ...
- 505
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
3
votes
1
answer
411
views
density of formal language？
let $\sum_0^n l_i x^i$ and $\sum_0^n 2^i x^i$ be generating function of L a given language and the closure over alphabet $\Sigma= \{0,1 \}$ when $n\to\infty$.
let$$D=\frac{\sum_0^n l_i }{\sum_0^n 2^...
- 3,094
9
votes
1
answer
449
views
Two-cardinal models of the random graph
For a first-order theory $T$ and cardinals $\kappa < \lambda$, we say that $M$ is a $(\kappa,\lambda)$-model if it is of size $\lambda$ and has a definable (with parameters) subset of size $\kappa$....
- 341
4
votes
1
answer
638
views
Proof systems and their hierarchy
Why ZFC is placed in top of the proof system hierarchy? How it can p-simulate other systems?
- 41
6
votes
1
answer
709
views
complete embeddings of boolean algebras and preservation of stationarity
Define a complete embedding of Boolean algebra as an homomorphism of Boolean algebras which preserves also the sup and inf operations. Notice that if $\mathbb{B}$ and $\mathbb{D}$ are complete boolean ...
- 489
0
votes
1
answer
280
views
What is the conditional probability or probablity of classes of languages?
What is the conditional probability or probability of classes of languages?
Let $E,C,S,F,R $ be the class of computably enumerable languages,computable languagesl,context-sensitive anguages,context-...
- 3,094
8
votes
3
answers
2k
views
Surreal Numbers and Set Theory
Hello,
I looked through MathOverflow's existing entries but couldn't find a satisfactory answer to the following question:
What is the relationship between No, Conway's class of surreal numbers, and ...
- 1,035
32
votes
2
answers
2k
views
The NP version of Matiyasevich's theorem
By Matiyasevich, for every recursively enumerable set $A$ of natural numbers there exists a polynomial $f(x_1,...,x_n)$ with integer coefficients such that for every $p\ge 0$, $f(x_1,...,x_n)=p$ has ...
user6976
4
votes
1
answer
351
views
Hyperarithemtic statements decidable by induction up to a recursive ordinal
Kleene's O is a $\Pi_1^1$ complete set that decides every hyperarithmetic statement. A Turing Machine that uses this set as an oracle to decide a hyperarithmetic question can only look at a finite ...
- 371
6
votes
1
answer
1k
views
How are mathematical objects defined from an ultrafinitist perspective?
I remember attending a lecture given by an ultrafinitist who denied that curves are a set of points, he would only say that any particular point may or not be on the curve. Similarly for algebraic or ...
- 4,351
3
votes
0
answers
257
views
Oracle separating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)
Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP?
Such an oracle ...
- 5,502
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
1
vote
0
answers
245
views
Defining filters in closure algebras: reference request
A closure algebra C is a boolean algebra B together with a unary closure operator, and additional axioms, the Kuratowski axioms, that the closure operator must satisfy. (The Wikipedia article prefers ...
- 327
7
votes
1
answer
266
views
Positive cone of a subgroup of $\mathbb{Z}^n$
This question sounds like it should be very well known, but for some reason I failed to find a decent answer anywhere. Let $G\subset\mathbb{Z}^n$ be a subgroup, and $G_+=G\cap\mathbb{Z}_{\ge0}^n$ be a ...
- 16.9k
2
votes
0
answers
169
views
Are there any recommended texts that cover Turing Tilings?
I have read the original paper by Wang, as well as a paper by Boas [1996] entitled 'the Convenience of Tilings', but wanted to know if there were any other texts that people could recommend that ...
- 83
9
votes
1
answer
1k
views
Large cardinals and constructible universe
We know that if $V=L$ holds, then $|\cal{P}(\omega)|=|\cal{P}(\omega)\cap \textrm{L}|=\aleph_1$ whereas, in the presence of a measurable cardinal (in fact, even Ramsey) $|\cal{P}(\omega)\cap \textrm{L}...
- 207
8
votes
2
answers
789
views
Why is this theorem (about $L(P(\omega_1))^V$ and $L(P(\omega_1))^{V[G]}$) nice?
I was recently told that the following (due to M. Viale) is a nice theorem:
Suppose there are arbitrarily large supercompacts, and $\mathrm{MM}$ holds in $V$. Let $G$ be generic for a proper ...
5
votes
2
answers
966
views
Program transformation as alternative for Hoare logic or temporal logic
When trying to prove something about a program, the known techniques are Hoare logic and temporal logics.
An alternative is to transform a program in a mathematical (logical) expression. So, rather ...
- 1,659
25
votes
2
answers
2k
views
Axiom of choice: ultrafilter vs. Vitali set
It is well known that from a free (non-principal) ultrafilter on $\omega$ one can define a non-measurable set of reals. The older example of a non-measurable set is the Vitali set,
a set of ...
- 16.2k
15
votes
1
answer
817
views
Undecidable theories easier than $Q$
Most proofs of undecidability for various theories (pure logic with binary relation, group theory, etc.) show that the natural numbers and Robinson's $Q$, in one form or another, can be encoded ...
- 3,475
23
votes
3
answers
2k
views
An ultrafilter is a set of subsets containing exactly one element of each finite partition: reference request
There are probably dozens of ways of defining "ultrafilter". The definition I've seen most often involves first defining "filter", then declaring an ultrafilter to be a maximal filter.
But there's ...
- 27.7k
41
votes
2
answers
2k
views
On the difference between two concepts of even cardinalities: Is there a model of ZF set theory in which every infinite set can be split into pairs, but not every infinite set can be cut in half?
An interesting question has arisen over at this
math.stackexchange
question
about two concepts of even in the context of infinite
cardinalities, which are equivalent under the axiom of
choice, but ...
- 236k
12
votes
7
answers
17k
views
What is some good introduction to lambda calculus?
I have some background in set theory and automata and I am looking for a good place to start with lambda calculus.
- 131
0
votes
1
answer
725
views
Do we need more than the periods? [closed]
Reading this question, and the Wikipedia page on reverse mathematics, I wonder whether one needs more than the subfield $\mathcal{P} \subset \mathbb{C}$ of periods for applied mathematics, or indeed ...
- 35.5k
16
votes
2
answers
2k
views
Why should I believe the Singular Cardinal Hypothesis?
The Singular Cardinal Hypothesis (SCH) is the statement that $\kappa^{cf(\kappa)} = \kappa^+ \cdot 2^{cf(\kappa)}$ for every singular cardinal $\kappa$ (or various equivalent statements).
It is ...
- 1,793
18
votes
4
answers
4k
views
Proof strength of Calculus of (Inductive) Constructions
This is a follow-on from this question, where I pondered the consistency strength of Coq. This was too broad a question, so here is one more focussed. Rather, two more focussed questions:
I've read ...
- 35.5k
5
votes
2
answers
825
views
Semantic definition of sentence
This is a follow-up to question Completeness vs Compactness in logic 68788. One common theme was that compactness in logic is a purely semantic notion, so should have no need of completeness.
The ...
- 3,475
1
vote
2
answers
832
views
Intension vs. Extension: Coextensive relations in model and set theory
(originally posted at MSE as Same same but different: Coextensive relations in model and set theory, slightly modified)
The official definition of a structure in model theory in its presumably most ...
- 9,720
20
votes
1
answer
2k
views
Axiom of choice and bases of vector spaces over a fixed field
Let $k$ be a field. In 1984 Andreas Blass proved that the axiom "for every extension $K|k$, every vector space over $K$ has a basis" implies the axiom of choice. He also raised the question
Does ...
- 16.2k
6
votes
1
answer
678
views
Is it possible to define a closure operator in terms of partial ordering?
For boolean algebra, let's take Roman Sikorski's Boolean Algebras as our reference. After giving a set of axioms, he proves (p.9) that the join of A and B is the least element of the algebra such that ...
- 327
16
votes
3
answers
4k
views
Quantum field theory in Solovay-land
Constructing quantum field theories is a well-known problem. In Euclidean space, you want to define a certain measure on the space of distributions on R^n. The trickiness is that the detailed ...
- 921
23
votes
10
answers
5k
views
Completeness vs Compactness in logic
One standard approach to showing compactness of first-order logic is to show completeness, of which compactness is an easy corollary. I am told this approach is deprecated nowadays, as Compactness is ...
- 3,475
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
11
votes
1
answer
949
views
Magma "actions" (or alternatively, "What is the Yoneda lemma for magmas?")
Arguably the most import thing about groups, semigroups and more generally categories, is that they can act on sets (or even collections of sets in the case of a category). This is the basis for all ...
- 2,392
4
votes
2
answers
889
views
Existence of a set of valid Busy-Beaver entries.
In reference to 1961 paper "On Non Computable Functions" by T. Rado.
Motivation - Scott Aaronson's Who Can Name the Bigger Number?.
M is an n-state binary Turing machine. A valid BB-n entry is a ...
- 43
2
votes
4
answers
1k
views
Are inference laws consistent?
Please forgive me if this question sounds too naive... Well, in mathematics a formal theory consists of a collection of axioms $T$ (such as Peano arithmetics, or Group Theory, or ZFC), which ...
- 23.3k
6
votes
1
answer
517
views
Growth zeta-functions of regular languages
Dear All,
my following question may be known and ought to be known, so in case it is folklore please could you give me the references.
To start, it is obvious that growth of rational languages are ...
- 1,437
29
votes
2
answers
2k
views
What do coherent topoi have to do with completeness?
There is a theorem of Deligne in SGA4 that a "coherent" topos (e.g. one on a site where all objects are quasi-compact and quasi-separated) has enough points (i.e. isomorphisms can be detected via ...
- 25.6k
0
votes
1
answer
1k
views
Is it possible to construct a finite mathematical universe? [duplicate]
Possible Duplicate:
Is there any formal foundation to ultrafinitism?
Very recently I have come across the skeptic opinions of a school of mathematicians(ultrafinitist) over a physically ...
- 19