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

learn more… | top users | synonyms (1)

221
votes
15answers
10k views

Can every proof by contradiction also be shown without contradiction?

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 ...
184
votes
1answer
6k views

Is there a 0-1 law for the theory of groups?

For each first order sentence $\phi$ in the language of groups, define : $$p_N(\phi)=\frac{\text{number of nonisomorphic groups $G$ of order} \le N\text{ such that } \phi \text{ is valid in } G}{\...
140
votes
3answers
25k views

Why can a Venn diagram for 4+ sets not be constructed using circles?

This page gives a few examples of Venn diagrams for 4 sets. Some examples: Thinking about it for a little, it is impossible to partition the plane into the $16$ segments required for a complete $4$-...
122
votes
11answers
13k views

Do we know if there exist true mathematical statements that can not be proven?

Given the set of standard axioms (I'm not asking for proof of those), do we know for sure that a proof exists for all unproven theorems? For example, I believe the Goldbach Conjecture is not proven ...
108
votes
4answers
12k 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 ...
90
votes
16answers
10k views

Why did mathematicians take Russell's paradox seriously?

Though I've understood the logic behind's Russell's paradox for long enough, I have to admit I've never really understood why mathematicians and mathematical historians thought it so important. Most ...
88
votes
3answers
3k views

True or false? $x^2\ne x\implies x\ne 1$

Today I had an argument with my math teacher at school. We were answering some simple True/False questions and one of the questions was the following: $$x^2\ne x\implies x\ne 1$$ I immediately ...
78
votes
14answers
29k views

Can someone explain Gödel's incompleteness theorems in layman terms?

Can you explain it in a fathomable way at high school level?
77
votes
8answers
5k views

Are the “proofs by contradiction” weaker than other proofs?

I remember hearing several times the advice that, we should avoid using a proof by contradiction, if it is simple to convert to a direct proof or a proof by contrapositive. Could you explain the ...
72
votes
2answers
3k views

Help me put these enormous numbers in order: googol, googol-plex-bang, googol-stack and so on

Popular mathematics folklore provides some simple tools enabling us compactly to describe some truly enormous numbers. For example, the number $10^{100}$ is commonly known as a googol, and a googol ...
68
votes
8answers
14k views

Learning Lambda Calculus

What are some good online/free resources (tutorials, guides, exercises, and the like) for learning Lambda Calculus? Specifically, I am interested in the following areas: Untyped lambda calculus ...
67
votes
6answers
4k views

Why is $\omega$ the smallest $\infty$?

I am comfortable with the different sizes of infinities and Cantor's "diagonal argument" to prove that the set of all subsets of an infinite set has cardinality strictly greater than the set itself. ...
67
votes
4answers
24k views

Proof by contradiction vs Prove 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 ...
64
votes
10answers
14k views

How is a system of axioms different from a system of beliefs?

Other ways to put it: Is there any faith required in the adoption of a system of axioms? How is a given system of axioms accepted or rejected if not based on blind faith?
59
votes
9answers
6k views

Does mathematics require axioms?

I just read this whole article: http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf which is also discussed over here: Infinite sets don't exist!? However, the paragraph which I found most ...
59
votes
6answers
8k views

In what sense are math axioms true?

Say I am explaining to a kid, $A +B$ is the same as $B+A$ for natural numbers. The kid asks: why? Well, it's an axiom. It's called commutativity (which is not even true for most groups). How do I "...
56
votes
19answers
7k views

In classical logic, why is $(p\Rightarrow q)$ True if both $p$ and $q$ are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: $$\begin{array}{|c|c|c|} \...
55
votes
12answers
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 ...
55
votes
7answers
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 ...
54
votes
5answers
51k 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 ...
53
votes
13answers
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 "...
53
votes
8answers
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 ...
52
votes
1answer
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 ...
51
votes
8answers
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 ...
51
votes
8answers
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? ...
50
votes
10answers
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, ...
50
votes
8answers
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)...
49
votes
13answers
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, ...
48
votes
2answers
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?
45
votes
15answers
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 ...
45
votes
5answers
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 ...
45
votes
6answers
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. ...
42
votes
14answers
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 ...
41
votes
12answers
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 ...
41
votes
11answers
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 ...
41
votes
4answers
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 ...
38
votes
3answers
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 ...
38
votes
5answers
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, ...
36
votes
3answers
11k 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 ...
36
votes
4answers
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" ...
36
votes
6answers
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 ...
36
votes
12answers
18k 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?
35
votes
11answers
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 ...
35
votes
4answers
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 ...
35
votes
2answers
438 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 ...
34
votes
5answers
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 ...
34
votes
2answers
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 ...
33
votes
7answers
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 ...
32
votes
15answers
5k views

Is it true to say that “it's not logically possible to prove something can't be done”?

A friend of mine asked me if I could explain this statement: "It's not logically possible to prove that something can't be done". The actual reason is the understanding of this strip: Since I'm ...
32
votes
9answers
3k views

Where to begin with foundations of mathematics

I would like to know more about the foundations of mathematics, but I can't really figure out where it all starts. If I look in a book on axiomatic set theory, then it seems to be assumed that one ...