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.
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
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
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
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
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
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 …
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
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
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
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
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 …
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 …
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
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
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 …