# Questions tagged [logic]

Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).

26,500 questions
Filter by
Sorted by
Tagged with
21 views

### Why are there 5 propositional connectives in propositional calculus?

I don't understand why there are 5 propositional connectives (conjuction, disjunction, implication, negation and equivalence) that are regularly given a priori in propositional calculus? If the goal ...
47 views

### When should one use transfinite induction?

I've come across it multiple times now in proof theory papers that authors use (sometimes quite elaborate) inductions in order to prove easy results. The most striking example is the following, where ...
• 650
91 views

### Gödel on the “True Reason” for Incompleteness

In footnote 48a of his famous paper on incompleteness, Gödel writes: [T]he true reason for the incompleteness inherent in all formal systems of mathematics is that the formation of ever higher types ...
• 141
57 views

• 111
36 views

### How to understand Godel's Theorems [duplicate]

Can someone with close to zero knowledge of higher mathematics understand Godel's Theorems or does he first have to learn some mathematics? If the answer to the first part of the question above is yes,...
1 vote
35 views

### Software Recommendation for Theorem Suggestions

So I am not sure if this software already exists or perhaps this is something that humanity has to embark on to finally have as a product. A bit about myself, I am student training in a sub-area of ...
• 75
24 views

• 49
1 vote
58 views

### The concepts of P, NP and NP_complete problems for the dummies

While there are already lot of questions on this topics here on Mathematics (1,2, 3) and several (too many perhaps) Wikipedia pages on the subject (a, b, c), they all involve concepts that I am not ...
• 239
58 views

### Policy fallacy in a youtube video

The picture of a YouTube video below suggests that out of policy A, B, or C in a 3-voter system, policy A would win. The voters ranked policies by how much they favorite them. However, if we rank ...
44 views

### Forcing $\pi_1(\tilde f(a))=f(a)$ for an object of a sigma type

Suppose I have an object $f$ of type $\Pi x:A.B(x)$, and consider a new type $\Pi (x:A).\Sigma (t:B(x)).C(t)$. If $\tilde f$ is an object of the second type and $a:A$, then $\pi_1(\tilde f (a)):B(x)$, ...
• 177
1 vote
32 views

• 69
### Adding $\tfrac{}{\Gamma \varphi}$ (for a fixed non-correct $\Gamma \varphi$) to the rules of the sequent calculus, can one now derive every sequent?
One knows that the sequent calculus over the set of sequents $\Gamma \varphi$ is correct and complete, meaning that the derivable sequents are precisely the correct ones. However, adding just one ...