# 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).

2,034 questions
14k views

7k views

### Does mathematics become circular at the bottom? What is at the bottom of mathematics? [duplicate]

I am trying to understand what mathematics is really built up of. I thought mathematical logic was the foundation of everything. But from reading a book in mathematical logic, they use "="(equals-sign)...
856 views

### In Godel's first incompleteness theorem, what is the appropriate notion of interpretation function?

Wikipedia states Godel's first incompleteness as follows. Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any ...
2k views

### What are the prerequisites for studying mathematical logic?

I am looking to study mathematical logic, however, I find that introductory books are very daunting, which kind of disheartens me. You see, slowly but surely, I started to realize that the maths which ...
1k views

### Are sets and symbols the building blocks of mathematics?

A formal language is defined as a set of strings of symbols. I want to know that if "symbol" is a primitive notion in mathematics i.e we don't define what a symbol is. If it is the case that in ...
39k views

### Why is “the set of all sets” a paradox, in layman's terms?

I've heard of some other paradoxes involving sets (ie, "the set of all sets that do not contain themselves") and I understand how paradoxes arise from them. But this one I do not understand. Why is "...
863 views

### Computability viewpoint of Godel/Rosser's incompleteness theorem

How would the Godel/Rosser incompleteness theorems look like from a computability viewpoint? Often people present the incompleteness theorems as concerning arithmetic, but some people such as Scott ...
23k views

### How do I convince someone that $1+1=2$ may not necessarily be true?

Me and my friend were arguing over this "fact" that we all know and hold dear. However, I do know that $1+1=2$ is an axiom. That is why I beg to differ. Neither of us have the required mathematical ...
7k views

### Why is this true? $(\exists x)(P(x) \Rightarrow (\forall y) P(y))$

Why is this true? $(\exists x)(P(x) \Rightarrow (\forall y) P(y))$
60k views

### Using proof by contradiction vs proof of the contrapositive

What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by ...
5k views

54k views

### Prove that the union of countably many countable sets is countable.

I am doing some homework exercises and stumbled upon this question. I don't know where to start. Prove that the union of countably many countable sets is countable. Just reading it confuses me. ...
9k views

### Why is mathematical induction a valid proof technique? [duplicate]

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ...
1k views

### Predicate logic: How do you self-check the logical structure of your own arguments?

In propositional logic, there are truth tables. So you can check if the logical structure of your argument is, not correct per se, but if it's what you intended it to be. In predicate logic, I have ...
713 views

### Is Gödel's modified liar an illogical statement?

In a previous question I relied on the notion of an "illogical statement" which led to some debate and I ended up making its definition an addendum to the question. I'd like to ask whether the notion ...
3k views

### When does the set enter set theory?

I wonder about the foundations of set theory and my question can be stated in some related forms: If we base Zermelo–Fraenkel set theory on first order logic, does that mean first order logic is not ...