Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lo.logic]

first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.

71
votes
16answers
7k 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 ...
2
votes
2answers
579 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 ...
3
votes
3answers
336 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 ...
7
votes
7answers
1k 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 ...
13
votes
7answers
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 ...
8
votes
1answer
582 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. ...
10
votes
3answers
1k 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 ...
7
votes
1answer
490 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$,...
6
votes
2answers
411 views

Cofinality of Theta if sharps exist

If ℝ# exists then why is cof(θL(ℝ)) = ω? Also I have the same question for the L(Vλ+1) generalization (if it's actually a different proof; I presume it isn't), i.e. if &...
35
votes
5answers
3k 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 ...
11
votes
4answers
4k 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. ...
209
votes
29answers
28k 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 that every ...
9
votes
4answers
1k 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 is are classes and that there are injections from A to B and fom B to A. Does it follow that there is a ...
13
votes
7answers
2k 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)
14
votes
7answers
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 ...
7
votes
10answers
2k views

What do models where the CH is false look like?

Additionally, is there any intuitive way to visualize the cardinalities that result?
27
votes
6answers
4k 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". ...
20
votes
6answers
6k 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. ...
9
votes
2answers
1k 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 ...