# Tagged Questions

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

10k views

Are there some proofs that can only be shown by contradiction or can everything that can be shown by contradiction also be shown without contradiction? What are the advantage/disadvantages of proving ...
6k views

3k views

### Why is compactness in logic called compactness?

In logic, a semantics is said to be compact iff if every finite subset of a set of sentences has a model, then so to does the entire set. Most logic texts either don't explain the terminology, or ...
7k views

### What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
52k views

### What's the difference between predicate and propositional logic?

I'd heard of propositional logic for years, but until I came across this question, I'd never heard of predicate logic. Moreover, the fact that Introduction to Logic: Predicate Logic and Introduction ...
21k views

### Why is “the set of all sets” a paradox?

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 "...
5k views

### How is the Gödel's Completeness Theorem not a tautology?

As a physicist trying to understand the foundations of modern mathematics (in particular Model Theory) $-$ I have a hard time coping with the border between syntax and semantics. I believe a lot would ...
2k views

### What does it take to divide by $2$?

Theorem 1 [ZFC, classical logic]: If $A,B$ are sets such that $\textbf{2}\times A\cong \textbf{2}\times B$, then $A\cong B$. That's because the axiom of choice allows for the definition of ...
5k views

### Is it possible that “A counter-example exists but it cannot be found”

Then otherwise the sentence "It is not possible for someone to find a counter-example" would be a proof. I mean, are there some hypotheses that are false but the counter-example is somewhere we ...
13k views

### Why do people lose in chess?

Zermelo's Theorem, when applied to chess, states: "either white can force a win, or black can force a win, or both sides can force at least a draw [1]" I do not get this. How can it be proven? ...
4k 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)...
7k views

### Infinite sets don't exist!?

Has anyone read this article? This accomplished mathematician gives his opinion on why he doesn't think infinite sets exist, and claims that axioms are nonsense. I don't disagree with his arguments, ...
3k views

### What is a proof?

I am just a high school student, and I haven't seen much in mathematics (calculus and abstract algebra). Mathematics is a system of axioms which you choose yourself for a set of undefined entities, ...
1k views

### Is it possible to prove a mathematical statement by proving that a proof exists?

I'm sure there are easy ways of proving things using, well... any other method besides this! But still, I'm curious to know whether it would be acceptable/if it has been done before?
4k views

### Is there such a thing as proof by example (not counter example)

Is there such a logical thing as proof by example? I know many times when I am working with algebraic manipulations, I do quick tests to see if I remembered the formula right. This works and is ...
8k views

### Understanding Gödel's Incompleteness Theorem

I am trying very hard to understand Gödel's Incompleteness Theorem. I am really interested in what it says about axiomatic languages, but I have some questions: Gödel's theorem is proved based on ...
3k views

### Proving the existence of a proof without actually giving a proof

In some areas of mathematics it is everyday practice to prove the existence of things by entirely non-constructive arguments that say nothing about the object in question other than it exists, e.g. ...
4k views

### An easy example of a non-constructive proof without an obvious “fix”?

I wanted to give an easy example of a non-constructive proof, or, more precisely, of a proof which states that an object exists, but gives no obvious recipe to create/find it. Euclid's proof of the ...
9k views

### “If everyone in front of you is bald, then you're bald.” Does this logically mean that the first person is bald?

Suppose we have a line of people that starts with person #1 and goes for a (finite or infinite) number of people behind him/her, and this property holds for every person in the line: If everyone ...
1k views

### Combinatorics Problem: Box Riddle

A huge group of people live a bizarre box based existence. Every day, everyone changes the box that they're in, and every day they share their box with exactly one person, and never share a box with ...
6k views

### Are proofs by contradiction really logical?

Let's say that I prove statement $A$ by showing that the negation of $A$ leads to a contradiction. My question is this: How does one go from "so there's a contradiction if we don't have $A$" to ...
4k views

### Can proof by contradiction 'fail'?

I am familiar with the mechanism of proof by contradiction: we want to prove $P$, so we assume $¬P$ and prove that this is false; hence $P$ must be true. I have the following devil's advocate ...
2k views

### Does “This is a lie” prove the insufficiency of binary logic?

If "This is a lie" were a true statement, its fulfilled claim of being a lie implies it can't be true, leading to a contradiction. If it were false, it could not be a lie and thus had to be true, ...
12k views

### First-Order Logic vs. Second-Order Logic

Wikipedia describes the first-order vs. second-order logic as follows: First-order logic uses only variables that range over individuals (elements of the domain of discourse); second-order logic ...
3k views

### What's between the finite and the infinite?

I'm wondering if there are any non-standard theories (built upon ZFC with some axioms weakened or replaced) that make formal sense of hypothetical set-like objects whose "cardinality" is "in between" ...
3k views

### What are Some Examples of “Non-Logical Theorems” Proven by Logic?

I am still an undergraduate student, and so perhaps I just haven't seen enough of the mathematical world. Question: What are some examples of mathematical logic solving open problem outside of ...
19k views

### Good books on mathematical logic?

I just started to learn mathematical logic. I'm a graduate student. I need a book with relatively more examples. Any recommendation?
3k views

### Why not both true and false?

Why can't some mathematical statement (or whatever is the correct term) be both true and false? For example we can prove (e.g. by induction) that $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ for all positive ...
2k views

### If all sets were finite, how could the real numbers be defined?

An extreme form of constructivism is called finitisim. In this form, unlike the standard axiom system, infinite sets are not allowed. There are important mathematicians, such as Kronecker, who ...
10k views

### Implies vs. Entails vs. Provable

Consider A $\Rightarrow$ B, A $\models$ B, and A $\vdash$ B. What are some examples contrasting their proper use? For example, give A and B such that A $\models$ B is true but A $\Rightarrow$ B is ...
440 views

### When are two proofs “the same”?

Often, we find different proofs for certain theorems that, on the surface, seem to be very different but actually use the same fundamental ideas. For example, the topological proof of the infinitude ...
2k views

### Do the axioms of set theory actually define the notion of a set?

In Henning Makholm's answer to the question, When does the set enter set theory?, he states: In axiomatic set theory, the axioms themselves are the definition of the notion of a set: A set is ...
1k views

### When should I be doing cohomology?

Background: I'm a logic student with very little background in cohomology etc., so this question is fairly naive. Although mathematical logic is generally perceived as sitting off on its own, there ...