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 answers only
not deleted
user 8133
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.
7
votes
What logic can express this sentence?
You're looking for infinitary logic - probably $\mathcal{L}_{\omega_1\omega_1}$ if you're using countably many distinct free varables. See https://en.wikipedia.org/wiki/Infinitary_logic, as well as ht …
- 20.7k
6
votes
Can the omega-rule rescue Hilbert's program?
Addressing your issue with Godel: note that even the one-use $\omega$-rule is not computable. There's no obstacle to a non-recursive theory being complete.
Actually this is a bit more subtle than I …
- 20.7k
10
votes
Accepted
Does there exist inconsistent axiom schemata which require arbitrary long proofs of their in...
This depends on the precise proof system, and notion of proof length, that you use. For example, the proof system that allows you to deduce any valid conclusion in one step is certainly sound and comp …
- 20.7k
7
votes
Can a universal induction rule be formulated?
I think the program you are outlining will not work: there is a limit to how far we can get by looking at induction on $\omega$, and once we pass to arbitrary induction schemes - where the real power …
- 20.7k
1
vote
A question about first order theories having only finite models
Really, this is just a comment, but it's way too long:
First, a quick observation: assuming your language is finite, every example must be finitely axiomatizable. (Although that finite axiomatization …
- 20.7k
2
votes
Statement of consistency in Godel's second incompleteness theorem
What is $A$? When I read this question, I thought that $A$ might mean the theory of the natural numbers ("true arithmetic"); in this case, there is even a non-cheating solution. We can formulate, in t …
- 20.7k
1
vote
which texts do you recommend to study mathematical logic ?
I'm a huge fan of Boolos, Burgess, and Jeffreys, "Computability and Logic." The first-order logic part proper starts with the chapter "A precis of first-order logic: syntax," and the book can be begun …
- 20.7k
9
votes
Accepted
Question on Godel completeness theorem
(For simplicity, I assume all languages and theories are countable.)
I'm not sure what "really exists" means; Godel's theorem says that a model of $T$ exists whenever $T$ is consistent.
If by "reall …
- 20.7k
5
votes
Accepted
Are there "typical" formal systems that have mutual consistency proofs? How long a chain of ...
No, this cannot happen, although it's a little bit trickier than one might expect to prove this!
First, a miniature result:
Suppose $T,S$ are computably axiomatizable theories in the language of ari …
- 20.7k
4
votes
Is true arithmetic + $\lnot Con (TA)$ consistent?
I think you haven't written what you want to.
At present your theory has a simple model: it's the expansion of standard arithmetic by interpreting $P$ as exactly the set of Godel numbers of sentences …
- 20.7k
3
votes
Accepted
Reduction of the predicate calculus to the propositional calculus in the case of one sigle o...
It's quite simple: in a structure with a single object - and for simplicity, let's assume only unary relations at first - we think of each unary relation as a single atomic proposition, and of the sin …
- 20.7k
2
votes
Accepted
Is every true $\Pi^0_1$ statement entailed from a consistency statement of $PA$?
The statement you want to prove is true, and your argument works - but there's a simpler one: drop all reference to the recursion theorem and Godelian incompleteness, and just change the second clause …
- 20.7k
2
votes
Accepted
Weak Skolem-Löwenheim and completeness
For simplicity, below all languages are finite.
At least at an abstract enough level, neither implication holds. When we go a bit more into the details, there is some truth to "completeness yields WL …
- 20.7k
9
votes
Henkin semantics for second-order logic
Well, there aren't really explicit examples, basically because of Tennenbaum's Theorem. But they exist, via the Compactness Theorem for first-order(!) logic.
Specifically, consider the two-sorted, f …
- 20.7k
2
votes
Accepted
Special classes of the arithmetical hierarchy of sentences of finite-order arithmetic
Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in m …
- 20.7k