Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

164
votes
14answers
7k 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 ...
138
votes
1answer
4k 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 } ...
109
votes
3answers
15k 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 ...
100
votes
11answers
11k 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 ...
78
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 ...
72
votes
15answers
7k 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 ...
68
votes
4answers
7k 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 ...
59
votes
6answers
3k 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. ...
57
votes
2answers
2k 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 ...
56
votes
13answers
11k views

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

Can you explain it in a fathomable way at high school level?
56
votes
8answers
3k 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 ...
50
votes
10answers
12k 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?
49
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 ...
49
votes
6answers
4k 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 ...
49
votes
3answers
10k 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 ...
48
votes
8answers
4k 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 ...
45
votes
8answers
11k 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? ...
44
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, ...
44
votes
7answers
6k 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 ...
43
votes
11answers
5k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Godel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
42
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?
41
votes
17answers
3k 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: ...
41
votes
9answers
3k 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 ...
40
votes
13answers
3k 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 ...
39
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
6answers
2k 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 ...
37
votes
8answers
5k views

Infinite sets don't exist!?

Has anyone read this article? Set theory 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 ...
36
votes
11answers
10k 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 ...
36
votes
5answers
6k 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 ...
36
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, ...
32
votes
5answers
2k views

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 ...
31
votes
15answers
4k 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 ...
29
votes
6answers
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 ...
28
votes
3answers
896 views

Are the axioms for abelian group theory independent?

(I give a lengthy introduction to a concise question -- scroll down if you want to jump straight up to the question). Recall that abelian group theory consists of two primitive symbols: $\cdot$ which ...
28
votes
5answers
2k views

An example of an easy to understand undecidable problem

I am looking for an undecidable problem that I could give as an easy example in a presentation to the general public. I mean easy in the sense that the mathematics behind it can be described, well, ...
28
votes
10answers
11k 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?
27
votes
3answers
7k 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 ...
26
votes
12answers
4k views

Prove that a counterexample exists without knowing one

I strive to find a statement $S(n)$ with $n \in N$ that can be proven to be not generally true despite the fact that noone knows a counterexample, i.e. it holds true for all $n$ ever tested so far. ...
26
votes
7answers
1k views

Are there infinite sets of axioms?

I'm reading Behnke's Fundamentals of mathematics: If the number of axioms is finite, we can reduce the concept of a consequence to that of a tautology. I got curious on this: Are there infinite ...
26
votes
5answers
2k views

Who invented $\vee$ and $\wedge$, $\forall$ and $\exists$?

I can rather easily imagine that some mathematician/logician had the idea to symbolize "it E xists" by $\exists$ - a reversed E - and after that some other (imitative) mathematician/logician had the ...
26
votes
4answers
1k views

Is $\mathbb{N}$ impossible to pin down?

I don't know if this is appropriate for math.stackexchange, or whether philosophy.stackexchange would have been a better bet, but I'll post it here because the content is somewhat technical. In ZFC, ...
26
votes
2answers
700 views

A few questions about intuitionistic mathematics

I have to write a paper on Intuitionism for my Philosophy of Science class and I'm struggling with a few concepts I have encountered in my self-study. The (intuitive) characterization of valid ...
25
votes
3answers
28k 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 ...
25
votes
7answers
6k views

Is there no solution to the blue-eyed islander puzzle?

Text below copied from here The Blue-Eyed Islander problem is one of my favorites. You can read about it here on Terry Tao's website, along with some discussion. I'll copy the problem here as ...
25
votes
3answers
976 views

**Ended Competition:** What is the shortest proof of $\exists x \forall y (D(x) \to D(y)) $?

The competition has ended 6 june 2014 22:00 GMT The winner is Bryan Well done ! When I was rereading the proof of the drinkers paradox (see Proof of Drinker paradox I realised that $\exists x ...
23
votes
9answers
2k 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 ...
23
votes
1answer
2k views

$e^{e^{e^{79}}}$ and ultrafinitism

I was reading the following article on Ultrafinitism, and it mentions that one of the reasons ultrafinitists believe that N is not infinite is because the floor of $e^{e^{e^{79}}}$ is not computable. ...
22
votes
6answers
2k views

What are natural numbers?

What are the natural numbers? Is it a valid question at all? My understanding is that a set satisfying Peano axioms is called "the natural numbers" and from that one builds integers, rational ...
22
votes
9answers
2k 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))$
22
votes
1answer
521 views

Model existence for infinitary logics

One of the problems of infinitary logic is that it is possible for compactness to fail in a spectacular way: for example, one can concoct an inconsistent set of axioms whose proper subsets are all ...