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.
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 …
- 2,031
7
votes
Abstract thought vs calculation
An example of a slightly different kind -- not eliminating all calculation, but
showing that "all calculations are easy" -- is Dehn's algorithm in
combinatorial group theory. Dehn showed, using the co …
- 4,713
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 …
- 2,821
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 …
- 4,713
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 …
CommunityBot
- 1
8
votes
solvable word problem without algorithm
The technique for constructing groups with unsolvable word problems
applies more generally to construct groups that "simulate'' Turing
machines. So, if a Turing machine halts for a recursive set of in …
- 12.4k
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
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 …
- 12.4k
1
vote
Accepted
Is there a language in $RE \setminus R$ which is not $RE$-complete?
Examples of such languages are not easy to describe, and I think no
"naturally-occurring" example is known. However, Muchnik and Friedberg
found examples in 1957, and Friedberg's example is here.
- 12.4k
6
votes
Proofs of Gödel's theorem
Possibly the least "self-referential" argument for Gödel's incompleteness theorem
is the one due to Gentzen. His ordinal analysis of proofs in PA shows that any
ordering that PA can prove to be a well …
- 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 …
CommunityBot
- 1
8
votes
Membership problem in monoids
A rather nice example is the monoid of $3\times 3$ integer matrices.
Its membership problem is unsolvable, indeed so is the problem when $x$
is restricted to be the zero matrix. This is another way to …
CommunityBot
- 1
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
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
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