All Questions
6,026 questions
32
votes
5
answers
4k
views
How many of the true sentences are provable?
Is there a natural measure on the set of statements which are true in the usual model (i.e. $\mathbb{N}$) of Peano arithmetic which enables one to enquire if 'most' true sentences are provable or ...
- 5,339
7
votes
11
answers
3k
views
Is there a theorem that says that there is always more than one way to "continue a finite sequence"? [closed]
I have come across a bit of folklore(?) which goes something like "given any finite sequence of numbers, there is more than one 'valid' way of continuing the sequence". For example see here. I would ...
- 1,418
3
votes
2
answers
341
views
Definition modifications without choice
What definitions or equivalencies between definitions for standard set theory objects (such as large cardinals) do not hold or do not carry through in the expected manner to the world without choice? ...
- 153
5
votes
2
answers
831
views
Godel's 1st incompleteness theorem - clarification.
This should be a trivial question for people who know Gödel's 1st incompleteness theorem. I quote the statement the theorem from wikipedia: "Any effectively generated theory capable of expressing ...
- 5,339
20
votes
4
answers
14k
views
What does it mean to 'discharge assumptions or premises'?
When constructing proofs using natural deduction what does it mean to say that an assumption or premise is discharged? In what circumstances would I want to, or need to, use such a mechanism?
The ...
- 313
106
votes
19
answers
12k
views
When are two proofs of the same theorem really different proofs
Many well-known theorems have lots of "different" proofs. Often new proofs of a theorem arise surprisingly from other branches of mathematics than the theorem itself.
When are two proofs really the ...
- 1,069
2
votes
2
answers
707
views
Minimal axiom system for a set of provable statements
I am not a mathematician, so forgive me if this question is trivial. The basic idea of my question is: For a given set of provable statements, can we find an axiom system with the smallest number of ...
- 39
4
votes
3
answers
418
views
Is there a formula phi s.t. phi and not-phi have a stronger consistency?
Let Σ be an axiom system. Can there be a formula φ, s.t.
Con(Σ) does not imply Con(Σ + φ) AND
Con(Σ) does not imply Con(Σ + not φ)
If yes, can you give me ...
- 205
8
votes
7
answers
2k
views
A few questions on model theory, especially model theory of rings
I have never really read anything proper about model theory, so I have a few questions:
Someone told me that a school of logicians managed to give a very short proof of Falting's Theorem using model ...
- 5,530
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
11
votes
7
answers
3k
views
Is no proof based on "tertium non datur" sufficient any more after Gödel?
There are many proofs based on a "tertium non datur"-approach (e.g. prove that there exist two irrational numbers a and b such that a^b is rational).
But according to Gödel's First Incompleteness ...
- 5,935
8
votes
1
answer
640
views
Controlling Ultrapowers
Say I start with some a transitive model of a large fragment of ZFC (say enough to run Łoś' Theorem externally) and a specific set x∈M. Now let's say I'm going to pick some M-ultrafilter U on x. ...
- 5,275
13
votes
3
answers
2k
views
Intuitionistic Lowenheim-Skolem?
Is there a version of the Löwenheim-Skolem theorem in intuitionistic logic? I'm particularly interested in the "downward" form. The standard proof I know uses the Tarski-Vaught test for ...
- 66.8k
7
votes
1
answer
534
views
Actions of finite permutation groups on hereditarily finite sets.
Model theorists have a lot to say about so-called definable imaginary elements of a structure. One way to formulate imaginaries is the following: Suppose $\mathcal{M}$ is a structure with universe $M$,...
- 179
6
votes
2
answers
564
views
Cofinality of Theta if sharps exist
If $\mathbb R^\sharp$ exists then why is $\textrm{cof}(\Theta^{L(\mathbb R)})=\omega$? Also I have the same question for the $L(V_{\lambda+1})$ generalization (if it's actually a different proof; I ...
- 153
44
votes
5
answers
5k
views
Several Topos theory questions
Hey. I have a few off the wall questions about topos theory and algebraic geometry.
Do the following few sentences make sense?
Every scheme X is pinned down by its Hom functor Hom(-,X) by the ...
- 12.1k
16
votes
4
answers
7k
views
Why do I find Category Theory mostly just a way to make simple things difficult?
I have a basic working knowledge of category thoery since I do research in programming languages and typed lambda-calculus. Indeed, I have refereed many papers in my area based on category theory.
...
- 213
298
votes
34
answers
53k
views
What are some reasonable-sounding statements that are independent of ZFC?
Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC."
For example, suppose $A$ is an abelian group such ...
15
votes
4
answers
2k
views
Does Cantor-Bernstein hold for classes?
In Bonn, we've been have a discussion on the topic in the title:
Suppose that $A$ and $B$ are classes and that there are injections from $A$ to $B$ and from $B$ to $A$. Does it follow that there is a ...
- 2,600
16
votes
7
answers
3k
views
Intro to automatic theorem proving / logical foundations?
Is there any web-based course or materials about logic / automatic theorem proving? (I checked MIT's OpenCourseWare and I only found a vaguely related AI course)
- 161
16
votes
7
answers
3k
views
What is lambda calculus related to?
So I'm not much of a math guy but I've really enjoyed programming in Lisp and have become interested in the ideas of lambda calculus which it is based.
I was wondering if anyone had a suggestion ...
- 163
9
votes
10
answers
2k
views
What do models where the CH is false look like?
Additionally, is there any intuitive way to visualize the cardinalities that result?
- 2,615
36
votes
6
answers
5k
views
Does finite mathematics need the axiom of infinity?
A statement referring to an infinite set can sometimes be logically rephrased using only finite sets/objects. For example, "The set of primes is infinite" <-> "There is no largest prime". ...
- 11.3k
27
votes
13
answers
4k
views
Homological algebra for commutative monoids?
Homological algebra for abelian groups is a standard tool in many fields of mathematics. How much carries over to the setting of commutative monoids (with unit)? It seems like there is a notion of ...
- 27.5k
27
votes
6
answers
9k
views
What is a topos?
According to Higher Topos Theory math/0608040 a topos is
a category C which behaves like the
category of sets, or (more generally)
the category of sheaves of sets on a
topological space.
Could one ...
- 15.1k
15
votes
3
answers
2k
views
Complete theory with exactly n countable models?
For $n$ an integer greater than $2$, Can one always get a complete theory over a finite language with exactly $n$ models (up to isomorphism)?
There’s a theorem that says that $2$ is impossible.
My ...
- 5,275