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.

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 ...
164
votes
15answers
36k views

Why worry about the axiom of choice?

As I understand it, it has been proven that the axiom of choice is independent of the other axioms of set theory. Yet I still see people fuss about whether or not theorem X depends on it, and I don't ...
164
votes
1answer
15k views

Ultrafilters and automorphisms of the complex field

It is well-known that it is consistent with $ZF$ that the only automorphisms of the complex field $\mathbb{C}$ are the identity map and complex conjugation. For example, we have that $\vert\...
141
votes
13answers
34k views

Knuth's intuition that Goldbach might be unprovable

Knuth's intuition that Goldbach's conjecture (every even number greater than 2 can be written as a sum of two primes) might be one of the statements that can neither be proved nor disproved really ...
113
votes
10answers
20k views

Solutions to the Continuum Hypothesis

Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? ; Completion of ZFC ; Complete resolutions of GCH; How far wrong could the Continuum Hypothesis be?; When was ...
110
votes
44answers
27k views

What are the most attractive Turing undecidable problems in mathematics?

What are the most attractive Turing undecidable problems in mathematics? There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
106
votes
43answers
18k views

nontrivial theorems with trivial proofs

A while back I saw posted on someone's office door a statement attributed to some famous person, saying that it is an instance of the callousness of youth to think that a theorem is trivial because ...
93
votes
16answers
23k views

What if Current Foundations of Mathematics are Inconsistent? [closed]

The title of the question is also the title of a talk by Vladimir Voevodsky, available here. Had this kind of opinion been expressed before? EDIT. Thanks to all answerers, commentators, voters, ...
93
votes
9answers
12k views

On Mathematical Arguments Against Quantum Computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
92
votes
2answers
9k views

Does every non-empty set admit a group structure (in ZF)?

It is easy to see that in ZFC, any non-empty set $S$ admits a group structure: for finite $S$ identify $S$ with a cyclic group, and for infinite $S$, the set of finite subsets of $S$ with the binary ...
91
votes
11answers
12k views

Checkmate in $\omega$ moves?

Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for ...
86
votes
2answers
7k views

How would you solve this tantalizing Halmos problem?

$1-ab$ invertible $\implies$ $1-ba$ invertible has a slick power series "proof" as below, where Halmos asks for an explanation of why this tantalizing derivation succeeds. Do you know one? Geometric ...
81
votes
28answers
12k views

Sexy vacuity … ${{{{{{}}}}}}$

I included this footnote in a paper in which I mentioned that the number of partitions of the empty set is 1 (every member of any partition is a non-empty set, and of course every member of the empty ...
79
votes
4answers
21k views

Is the analysis as taught in universities in fact the analysis of definable numbers?

Ten years ago, when I studied in university, I had no idea about definable numbers, but I came to this concept myself. My thoughts were as follows: All numbers are divided into two classes: those ...
73
votes
7answers
16k views

How many orders of infinity are there?

Define a growth function to be a monotone increasing function $F: {\bf N} \to {\bf N}$, thus for instance $n \mapsto n^2$, $n \mapsto 2^n$, $n \mapsto 2^{2^n}$ are examples of growth functions. Let's ...
72
votes
9answers
10k views

Is there any formal foundation to ultrafinitism?

Ultrafinitism is (I believe) a philosophy of mathematics that is not only constructive, but does not admit the existence of arbitrarily large natural numbers. According to wikipedia, it has been ...
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 ...
70
votes
3answers
4k views

How do I verify the Coq proof of Feit-Thompson?

I probably don't have the appropriate background to even ask this question. I know next to nothing about formal or computer-aided proof, and very little even about group theory. And this question is ...
68
votes
16answers
20k views

Most 'unintuitive' application of the Axiom of Choice?

It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis. Even ...
68
votes
9answers
5k views

Can we unify addition and multiplication into one binary operation? To what extent can we find universal binary operations?

The question is the extent to which we can unify addition and multiplication, realizing them as terms in a single underlying binary operation. I have a number of questions. Is there a binary ...
67
votes
31answers
7k views

Can infinity shorten proofs a lot?

I've just been asked for a good example of a situation in maths where using infinity can greatly shorten an argument. The person who wants the example wants it as part of a presentation to the general ...
66
votes
8answers
8k views

Succinctly naming big numbers: ZFC versus Busy-Beaver

Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge: You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
63
votes
13answers
13k views

Logic in mathematics and philosophy

What are the relations between logic as an area of (modern) philosophy and mathematical logic. The world "modern" refers to 20th century and later, and I am curious mainly about the second half of ...
63
votes
9answers
5k views

What's wrong with the surreals?

Of all the constructions of the reals, the construction via the surreals seems the most elegant to me. It seems to immediately capture the total ordering and precision of Dedekind cuts at a ...
63
votes
5answers
6k views

What was Hilbert's view of Gödel's Incompleteness Theorems?

According to Solomon Feferman, in his slide presentation "Three Problems for Mathematics", Hilbert wrote (in regards to Gödel's second incompleteness theorem): ...the end goal [is] to establish as ...
62
votes
4answers
9k views

Nelson's program to show inconsistency of ZF

At the end of the paper Division by three by Peter G. Doyle and John H. Conway, the authors say: Not that we believe there really are any such things as infinite sets, or that the Zermelo-Fraenkel ...
57
votes
8answers
9k views

Set theories without “junk” theorems?

Clearly I first need to formally define what I mean by "junk" theorem. In the usual construction of natural numbers in set theory, a side-effect of that construction is that we get such theorems as $...
57
votes
9answers
6k views

Has anyone thought about creating a formal proof wiki with verifier?

Mathematics has undergone some rather nice developments recently with the adoption of new techologies, things like on-line journals, the arXiv, this website, etc. I imagine there must be many further ...
56
votes
3answers
4k views

Forcing as a new chapter of Galois Theory?

There is a (very) long essay by Grothendieck with the ominous title La Longue Marche à travers la théorie de Galois (The Long March through Galois Theory). As usual, Grothendieck knew what he was ...
55
votes
9answers
9k views

Arguments against large cardinals

I started to learn about large cardinals a while ago, and I read that the existence, and even the consistency of the existence of an inaccessible cardinal, i.e. a limit cardinal which is additionally ...
54
votes
19answers
6k views

What are some results in mathematics that have snappy proofs using model theory?

I am preparing to teach a short course on "applied model theory" at UGA this summer. To draw people in, I am looking to create a BIG LIST of results in mathematics that have nice proofs using model ...
54
votes
5answers
7k views

Decidability of chess on an infinite board

The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
52
votes
15answers
8k views

Abstract Thought vs Calculation

Jeremy Avigad and Erich Reck claim that one factor leading to abstract mathematics in the late 19th century (as opposed to concrete mathematics or hard analysis) was the use of more abstract notions ...
52
votes
2answers
2k views

Reasons to prefer one large prime over another to approximate characteristic zero

Background: In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a large prime $p$, rather ...
52
votes
3answers
3k views

What is the geometry of an undecidable diophantine equation?

As an arithmetic algebraic geometer of the highest moral fiber, I am trained to look at Diophantine equations in terms of the geometry of the corresponding scheme. For instance, if the Diophantine ...
51
votes
7answers
10k views

Reductio ad absurdum or the contrapositive?

From time to time, when I write proofs, I'll begin with a claim and then prove the contradiction. However, when I look over the proof afterwards, it appears that my proof was essentially a proof of ...
51
votes
8answers
5k views

Is all ordinary mathematics contained in high school mathematics?

By high school mathematics I mean Elementary Function Arithmetic (EFA), where one is allowed +,×, xy, and a weak form of induction for formulas with bounded quantifiers. This is much weaker than ...
51
votes
9answers
6k views

How do they verify a verifier of formalized proofs?

In an unrelated thread Sam Nead intrigued me by mentioning a formalized proof of the Jordan curve theorem. I then found that there are at least two, made on two different systems. This is quite an ...
50
votes
14answers
6k views

What is the high-concept explanation on why real numbers are useful in number theory?

The utopian situation in mathematics would be that the statement and the proof of every result would live "in the same world", at the same level of mathematical complexity (in a broad sense), unless ...
50
votes
8answers
7k views

What does it mean to suspect that two conjectures are logically equivalent?

Here's a familiar conversation: Me: Do you think Conjecture A and Conjecture B are equivalent? Friend: Yes, because I think they're both true. Me: [eye roll] You know what I mean... Does there ...
50
votes
6answers
4k views

Has decidability got something to do with primes?

Note: I have modified the question to make it clearer and more relevant. That makes some of references to the old version no longer hold. I hope the victims won't be furious over this. Motivation: ...
50
votes
5answers
5k views

The Logic of Buddha: A Formal Approach

Buddhist logic is a branch of Indian logic (see also Nyaya), one of the three original traditions of logic, alongside the Greek and the Chinese logic. It seems Buddha himself used some of the features ...
49
votes
5answers
6k views

Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?

1) Can the Riemann Hypothesis (RH) be expressed as a $\Pi_1$ sentence? More formally, 2) Is there a $\Pi_1$ sentence which is provably equivalent to RH in PA? Update (July 2010): So we have two ...
49
votes
2answers
5k views

Does Godel's incompleteness theorem admit a converse?

Let me set up a strawman: One might entertain the following criticism of Godel's incompleteness theorem: why did we ever expect completeness for the theory of PA or ZF in the first place? Sure, one ...
48
votes
10answers
14k views

What are some important but still unsolved problems in mathematical logic?

In the past, first-order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of ...
48
votes
5answers
6k views

Does anyone know a polynomial whose lack of roots can't be proved?

In Ebbinghaus-Flum-Thomas's Introduction to Mathematical Logic, the following assertion is made: If ZFC is consistent, then one can obtain a polynomial $P(x_1, ..., x_n)$ which has no roots in the ...
47
votes
7answers
4k views

Is the ultraproduct concept fundamentally category-theoretic?

Once again, I would like to take advantage of the large number of knowledgable category theorists on this site for a question I have about category-theoretic aspects of a fundamental logic concept. ...
46
votes
7answers
5k views

In what respect are univalent foundations “better” than set theory?

It was an ambitious project of Vladimir Voevodsky's to provide new foundations for mathematics with univalent foundations (UF) to eventually replace set theory (ST). Part of what makes ST so ...
46
votes
5answers
11k views

Can the Riemann hypothesis be undecidable?

The question is contained in the title; I mean the standard axioms ZFC. The wiki link: Riemann hypothesis. There are finite algorithms allowing one to decide if there are non-trivial zeroes of the $\...
46
votes
4answers
4k views

What was Gödel's real achievement?

When I first heard of the existence of Gödel's theorem, I was amazed not just at the theorem but at the fact that the question could be made precise enough to answer: how on earth, even in ...