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 10909
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
2
answers
2k
views
Tennenbaum's Theorem and polynomials
Tennenbaum's Theorem theory says that in a countable non-standard model of arithmetic with an underlying set consisting of standard numbers, neither the polynomial $A(x,y):=x+y$ nor the polynomial $M …
- 17.6k
50
votes
1
answer
6k
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 c …
- 17.6k
2
votes
Is the set of undecidable problems decidable?
I believe that one can expand on boumol's answer, as follows.
The spirit of the OP's question attempts to regain Eden after the Turing-Godel expulsion.
One might attempt to repair the OP's attempt …
- 17.6k
7
votes
1
answer
769
views
Schemes (as in algebraic geometry) and first-order logic.
Affine schemes are simply the Zariski spectra of commutative rings, and commutative rings occurs as models of a first-order theory.
I would guess that general schemes do not naturally correspond to …
- 17.6k
6
votes
1
answer
481
views
Topological dynamics and Turing complete automata
One can look at, say, Conway's Game of Life in at least two ways:
1) as a cellular automaton; and
2) as a discrete topological dynamical system (on an underlying Cantor set).
Famously, Conway showe …
- 17.6k
8
votes
2
answers
844
views
Hilbert style axioms for Euclidean and/or hyperbolic geometry without reference to congruence?
Hilbert's axioms from Grundlagen der Geometrie involve notions of incidence, between-ness, segment congruence and angle congruence.
Consider the sub-theories of either Euclidean or hyperbolic geome …
- 17.6k
22
votes
1
answer
1k
views
Concerning the rarity of provably transcendental real numbers
Does there exist any rubric where provably transcendental real numbers emerge, in a meaningful way, as rare among all the transcendental numbers?
Here are some of the things I'm worried about:
1) To …
- 17.6k
14
votes
2
answers
1k
views
Induction, the infinitude of the primes, and workaday number theory
There are various open problems in the subject of logical number theory concerning the possibility of proving this or that well-known standard results over this or that weak theory of arithmetic, usua …
- 17.6k
9
votes
2
answers
682
views
Boolean Prime Ideal Theorem versus the Axiom of Determinacy
I'm assuming someone must have scooped me on this simple argument. Where does it (first) appear in the literature?
Fix an ultrafilter $\mu$ on $\omega$, the natural numbers.
Alice and Bob play a n …
- 17.6k
13
votes
Zero-knowledge proof that 0 = 1
Well you're not going to prove 0=1 in PA, because PA is consistent,
(though not PA-provably so), following Gentzen. But I digress.
If you proved 0=1 in, say, ZFC, that would simply mean that
ZFC was …
9
votes
2
answers
684
views
Radix notation and toposes
In classical logic plus ZF, the field of real numbers admits infinitely many isomorphic realizations as a numeral system --- as the radix varies. The intuitionistic status of these systems seems less …
- 17.6k
10
votes
1
answer
541
views
Beyond Presburger Arithmetic
Do there exist known examples of predicates $P$ (possibly functional) such that
1) $P$ admits a first-order definition in the language ${\Bbb N}(+,\times,0,1)$;
2) $P$ admits no definition that does …
- 17.6k
8
votes
1
answer
526
views
Theory of addition and a predicate that recognizes powers of 2
What is the complexity of the theory of addition (Presburger arithmetic) augmented by a unary predicate that recognizes powers of 2?
- 17.6k
7
votes
1
answer
773
views
2nd Incompleteness and Model Theory
In the presence of Godel's Completeness Theorem, the 2nd Incompleteness Theorem has
the following strictly model theoretic interpretation: if there exists any model at all of (say) ZFC, there also exi …
- 17.6k
26
votes
1
answer
2k
views
Nontrivial circular arguments?
There is a famous circular argument for the Prime Number Theorem (PNT). It turns
out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates
that taken together imply P …
- 17.6k