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.
Questions tagged [lo.logic]
5144 questions
67
votes
9 answers
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 primitive recursive arithmetic, which is in turn much…
Richard Borcherds
- 20,442
50
votes
2 answers
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 can devise complete theories semantically (taking…
David Feldman
- 17,466
42
votes
4 answers
Inconsistent theory with long contradiction
What can one say about an inconsistent theory $T$ which has no contradictions (i.e. deductions of $P \wedge \neg P$) of length shorter than $n$, where $n$ is some huge number?
There have been some discussions about the consistency of ZFC, for…
David Harris
- 3,397
36
votes
5 answers
What do we gain with higher order logics?
Gödel's speed up theorems seem to say that higher order logics offer shorter shortest proofs of various propositions in number theory. Explicitly, he gave the following
Theorem.
Let $n>0$ be a natural number. If $f$ is a computable function,…
Alec Rhea
- 9,009
35
votes
7 answers
Status of Harvey Friedman's grand conjecture?
Friedman [1] conjectured
Every theorem published in the Annals of Mathematics whose
statement involves only finitary mathematical objects (i.e., what logicians
call an arithmetical statement) can be proved in EFA. EFA is the weak
fragment of…
Charles
- 8,974
- 1
- 36
- 74
32
votes
11 answers
Is there a general setting for self-reference?
This is a question about self-reference: Has anyone established an abstract framework, maybe a certain kind of formal language with some extra structure, which makes it possible to define what is a self-referential statement?
Peter Arndt
- 12,033
31
votes
6 answers
A Model where Dedekind Reals and Cauchy Reals are Different
Is there a model where Dedekind reals and Cauchy reals are different? I'd appreciate if someone can refer me to any related work in case such a model exists.
Jean Joseph
- 365
29
votes
7 answers
What is a logic?
I am not interested in the philosophical part of this question :-)
When I look at mathematics, I see that lots of different logics are used : classical, intuitionistic, linear, modal ones and weirder ones ...
For someone new to the field, it is not…
alpheccar
- 435
29
votes
4 answers
Why do people say Gödel's sentence is true when it is true in some models but false in others?
I am a beginner, so this question may be naive.
Suppose we have a (sufficiently strong) consistent first order logic system. Gödel's first incompleteness theorem says there exists a Gödel sentence $g$ which is unprovable, and its negation is also…
27
votes
1 answer
Independence of being an integer
In this MO question, the OP asked for an example of a statement which was known not to be independent of ZFC, but for which the truth value was unknown. I immediately thought of a question I asked on math.SE: is $e^{e^{e^{79}}}$ an integer? This is…
Carl Mummert
- 9,593
26
votes
1 answer
Can we find strong fixed-points in the fixed-point lemma of Gödel's incompleteness theorem, that is, where the fixed point is syntactically identical to its substitution instance rather than merely provably equivalent to it?
At Graham Priest's talk for the CUNY set theory seminar yesterday, an issue arose concerning the possibility (or impossibility) of a stronger-than usual form of the arithmetic fixed-point lemma often used to prove the Gödel incompleteness theorem.…
Joel David Hamkins
- 224,022
24
votes
4 answers
Infinite mathematics as non-standard finite mathematics?
I have in mind something like the following:
Start with some suitable version of "finite" mathematics. Some possibilities might be maybe ZFC with a suitable anti-infinity axiom, the topos $\mathbf{FinSet}$, Peano arithmetic, Turing machines...…
user13113
24
votes
4 answers
Propositional Logic, First-Order Logic, and Higher-Order Logics
I've been reading up a bit on the fundamentals of formal logic, and have accumulated a few questions along the way. I am pretty much a complete beginner to the field, so I would very much appreciate if anyone could clarify some of these points.
A…
Noldorin
- 800
22
votes
4 answers
Impredicativity
I hope this question is not so elementary that it'll get me banned...
In mathematics we see a lot of impredicativity. Example of definitions involving impredicativity include: subgroup/ideal generated by a set, closure/interior of a set (in…
dumb student
- 231
- 2
- 4
21
votes
1 answer
the true reason of the incompleteness of formal systems
A 3/4 year ago, I read Gödel's beautiful paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme 1". There is one thing, I never understood.
In a footnote, Gödel says the following:
"Der wahre Grund für die…
asdfusername
- 211