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.

Filter by
Sorted by
Tagged with
291 votes
34 answers
50k 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 ...
249 votes
16 answers
67k 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 ...
178 votes
11 answers
49k 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 ...
AgCl's user avatar
  • 2,677
168 votes
1 answer
16k 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\...
Simon Thomas's user avatar
  • 8,348
150 votes
45 answers
29k 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 ...
141 votes
12 answers
29k 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 ...
Gil Kalai's user avatar
  • 24.2k
135 votes
43 answers
37k 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 ...
128 votes
13 answers
23k 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 ...
Johan Wästlund's user avatar
121 votes
17 answers
17k views

Pressure to defend the relevance of one's area of mathematics

I am a set theorist. Since I began to study this subject, I became increasingly aware of negative attitudes about it. These were expressed both from an internal and an external perspective. By the “...
117 votes
4 answers
36k 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 ...
Anixx's user avatar
  • 9,306
113 votes
11 answers
17k 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 ...
113 votes
2 answers
12k 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 ...
Bill Dubuque's user avatar
  • 4,706
111 votes
2 answers
15k 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 ...
Konrad Swanepoel's user avatar
109 votes
10 answers
23k 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 $...
Jacques Carette's user avatar
106 votes
36 answers
20k views

Interesting examples of vacuous / void entities

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 ...
103 votes
19 answers
11k 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 ...
Martyguy's user avatar
  • 1,031
98 votes
16 answers
28k 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, ...
95 votes
16 answers
33k 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 ...
89 votes
10 answers
16k 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 ...
Michael O'Connor's user avatar
86 votes
7 answers
20k 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 ...
Terry Tao's user avatar
  • 108k
84 votes
9 answers
10k 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 ...
user2498's user avatar
  • 1,823
81 votes
3 answers
5k 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 ...
Nate Eldredge's user avatar
77 votes
9 answers
6k 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 ...
Joel David Hamkins's user avatar
76 votes
3 answers
18k views

Czelakowski's claimed proof of the Twin Prime Conjecture

It seems like the article "The Twin Primes Conjecture is True in the Standard Model of Peano Arithmetic: Applications of Rasiowa–Sikorski Lemma in Arithmetic (I)" by Janusz Czelakowski ...
Glycerius's user avatar
  • 1,023
76 votes
4 answers
8k views

Who first characterized the real numbers as the unique complete ordered field?

Nearly every mathematician nowadays is familiar with the fact that there is up to isomorphism only one complete ordered field, the real numbers. Theorem. Any two complete ordered fields are isomorphic....
Joel David Hamkins's user avatar
74 votes
8 answers
12k 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 ...
Scott Aaronson's user avatar
72 votes
31 answers
9k 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 ...
gowers's user avatar
  • 28.7k
72 votes
6 answers
7k views

A better way to explain forcing?

Let me begin by formulating a concrete (if not 100% precise) question, and then I'll explain what my real agenda is. Two key facts about forcing are (1) the definability of forcing; i.e., the ...
Timothy Chow's user avatar
  • 78.1k
72 votes
8 answers
12k views

Category theory and set theory: just a different language, or different foundation of mathematics?

This is a question to research mathematicians, as well as to those concerned with the history and philosophy of mathematics. I am asking for a reference. In order to make the reference request as ...
Claus's user avatar
  • 6,777
71 votes
13 answers
19k 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 ...
Gil Kalai's user avatar
  • 24.2k
70 votes
5 answers
9k 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 ...
Akhil Mathew's user avatar
  • 25.3k
69 votes
19 answers
8k 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 ...
Pete L. Clark's user avatar
69 votes
5 answers
9k 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 ...
Thomas Benjamin's user avatar
68 votes
4 answers
11k 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 ...
Andreas Thom's user avatar
  • 25.3k
68 votes
6 answers
8k 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 ...
Morteza Azad's user avatar
67 votes
9 answers
8k 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 ...
Richard Borcherds's user avatar
67 votes
5 answers
10k 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 ...
Richard Stanley's user avatar
66 votes
9 answers
26k 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 ...
65 votes
9 answers
13k views

Axiom of choice, Banach-Tarski and reality

The following is not a proper mathematical question but more of a metamathematical one. I hope it is nonetheless appropriate for this site. One of the non-obvious consequences of the axiom of choice ...
ThiKu's user avatar
  • 10.3k
65 votes
3 answers
4k 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 ...
Charles Staats's user avatar
64 votes
3 answers
6k 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 ...
Mirco A. Mannucci's user avatar
63 votes
16 answers
8k 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 ...
63 votes
14 answers
6k views

Unnecessary uses of the axiom of choice

What examples are there of habitual but unnecessary uses of the axiom of choice, in any area of mathematics except topology? I'm interested in standard proofs that use the axiom of choice, but where ...
61 votes
8 answers
15k 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 ...
61 votes
9 answers
13k 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 ...
user8996's user avatar
  • 765
61 votes
5 answers
8k views

Bourbaki's definition of the number 1

According to a polemical article by Adrian Mathias, Robert Solovay showed that Bourbaki's definition of the number 1, written out using the formalism in the 1970 edition of Théorie des Ensembles, ...
John Baez's user avatar
  • 21.3k
60 votes
15 answers
10k 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 ...
60 votes
8 answers
9k 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 ...
Dustin G. Mixon's user avatar
60 votes
5 answers
11k 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 ...
Kaveh's user avatar
  • 5,362
60 votes
8 answers
6k 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. My ...
Joel David Hamkins's user avatar

1
2 3 4 5
103