Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with lo.logic
Search options not deleted
user 1587
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.
135
votes
What are the most attractive Turing undecidable problems in mathematics?
The mortality problem for $3\times 3$ matrices: given a finite set $F$ of $3\times 3$
integer matrices, decide whether the zero matrix is a product of members of $F$
(with repetitions allowed). This …
98
votes
Nontrivial theorems with trivial proofs
A nontrivial geometric theorem of the type you are looking for may be the
Desargues theorem:
If two triangles are in perspective then the intersections of their corresponding sides lie on a line.
In …
38
votes
What was Gödel's real achievement?
I posted this earlier on the "narrowly-missed discoveries" thread, but I think the two paragraphs below address your three questions. For the most
recent scholarly account of Post's work, see the arti …
- 12.4k
34
votes
Does anyone know a polynomial whose lack of roots can't be proved?
Something close to what you want is in the paper
"Universal Diophantine Equation" by James P. Jones in the
Journal of Symbolic Logic 47 (1982), pp. 549--571.
Jones produces an explicit list of 37 eq …
- 12.4k
28
votes
Most 'unintuitive' application of the Axiom of Choice?
Maybe this is not the kind of application you have in mind, but a well-ordering of the reals seems highly counterintuitive to me. I would argue that well-ordering of $\mathbb{R}$ is the essence of man …
27
votes
2
answers
2k
views
Are any natural examples of Gödel speed-up known?
In 1936 Gödel announced a theorem to the effect that proofs of certain theorems $T_1,T_2,\ldots$ become dramatically shorter when one passes from a formal system, such as Peano arithmetic PA, to a str …
- 12.4k
21
votes
2
answers
4k
views
Question arising from Voevodsky's talk on inconsistency
This question arises from the talk by Voevodsky mentioned in
this recent MO question. On one of his slides, Voevodsky says that
a general formula even with one free variable describes a subset of …
- 12.4k
20
votes
Knuth's intuition that Goldbach might be unprovable
There are also some concrete examples in graph theory, such as Kruskal's tree
theorem and the Robertson-Seymour graph minor theorem. These theorems
about infinite sequences of graphs were actually pro …
- 12.4k
19
votes
Why worry about the axiom of choice?
It is a mistake to think that the axiom of choice has no relevance to, say,
undergraduate mathematics. The axiom of choice makes undergraduate
analysis easier by enabling one to say that $f(x)$ is con …
16
votes
3
answers
2k
views
Natural examples of Reverse Mathematics outside classical analysis?
Harvey Friedman at the 1974 ICM motivated Reverse Mathematics by the
following statement:
When the theorem is proved from the right axioms, the axioms can be proved
from the theorem.
Reverse Mathema …
- 12.4k
15
votes
Why can't proofs have infinitely many steps?
Andreas Blass has nicely explained why it is not helpful to use
infinitary logic in an attempt to prove the axiom of choice.
It may be worth adding that the seemingly similar idea, of
considering co …
- 12.4k
12
votes
Accepted
Is any interesting question about a group G decidable from a presentation of G?
It seems to me that the analogue of Rice's theorem fails for finitely presented
groups $G$ because of questions like: is the abelianization of $G$ of rank 3?
The rank of the abelianization of any fini …
- 12.4k
12
votes
Has there ever been a weaker Church-like thesis?
I think it unlikely that anyone ever proposed a weaker Church's thesis,
because, as Tim Chow points out, diagonalization was known (and known to be
constructive) before anyone ever contemplated a def …
- 12.4k
11
votes
Non-computable but easily described arithmetical functions
There are some easily-described noncomputable functions, if you are willing to accept functions that
take finite objects other than numbers as inputs. The "objects" I'm referring to represent instance …
- 12.4k
10
votes
What is the high-concept explanation on why real numbers are useful in number theory?
A possible candidate for a "minimal" result about integers that is a "projection" of a
result about reals: the group structure of the solutions of the Pell equation
$x^2-dy^2=1$ for $d$ a nonsquare po …