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.
109
votes
13answers
4k 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 ...
71
votes
3answers
6k 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-set ...
63
votes
3answers
2k 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 ...
49
votes
11answers
4k 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 ...
44
votes
6answers
1k views
How far can one get in analysis without leaving $\mathbb{Q}$?
Suppose you're trying to teach analysis to a stubborn algebraist who refuses to acknowledge the existence of any characteristic $0$ field other than $\mathbb{Q}$. How ugly are things going to get for ...
42
votes
2answers
1k 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
...
40
votes
6answers
2k 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. ...
40
votes
8answers
2k 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 ...
40
votes
5answers
2k 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 ...
39
votes
4answers
823 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 ...
37
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 ...
35
votes
5answers
1k 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, ...
34
votes
6answers
3k 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 ...
34
votes
2answers
671 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?
32
votes
6answers
1k 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 ...
28
votes
9answers
2k 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 ...
28
votes
5answers
4k 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 ...
24
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 ...
24
votes
5answers
1k 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, ...
24
votes
2answers
816 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 proofs by ...
24
votes
10answers
4k 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?
23
votes
16answers
2k 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:
...
23
votes
6answers
2k 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
...
23
votes
3answers
572 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 ...
22
votes
7answers
1k 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 ...
22
votes
3answers
2k 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 ...
22
votes
4answers
980 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 ...
22
votes
2answers
495 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 ...
21
votes
6answers
1k 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 ...
20
votes
6answers
1k 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 ...
20
votes
5answers
715 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?
(PD: I'm not religious)
20
votes
6answers
563 views
Axiomatic characterization of the rational numbers
We have the well-known Peano axioms for the natural numbers and the real numbers can be characterized by demanding them to be a Dedekind-complete, totally ordered field (or some variation of this).
...
20
votes
2answers
570 views
Is the fundamental theorem of calculus independent of ZF?
By the fundamental theorem of calculus I mean the following.
Theorem: Let $B$ be a Banach space and $f : [a, b] \to B$ be a continuously differentiable function (this means that we can write $f(x + ...
20
votes
2answers
263 views
FO-definability of the integers in (Q, +, <)
With $Q$ the set of rational numbers, I'm wondering:
Is the predicate "Int($x$) $\equiv$ $x$ is an integer" first-order definable in $(Q, +, <)$ where there is one additional constant symbol ...
20
votes
4answers
361 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, ...
19
votes
2answers
440 views
Finding the Robot
There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory ...
18
votes
8answers
4k 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 ...
17
votes
7answers
494 views
What's the deal with empty models in first-order logic?
Asaf's answer here reminded me of something that should have been bothering me ever since I learned about it, but which I had more or less forgotten about. In first-order logic, there is a convention ...
17
votes
1answer
1k 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. ...
16
votes
5answers
1k views
Is 1+1 =2 a theorem?
A theorem is defined to be a mathematical statement that is proven to be true. The statement $1+1=2$ has definitely been proven in the history of mankind (Russel and Whitehead had once proven it in ...
16
votes
3answers
598 views
How do proof verifiers work?
I'm currently trying to understand the concepts and theory behind some of the common proof verifiers out there, but am not quite sure on the exact nature and construction of the sort of systems/proof ...
16
votes
1answer
358 views
Are the real numbers ever needed to prove a property of the natural numbers?
Suppose no one had invented/discovered the real numbers yet (so e.g., no calculus), would this constrain the possible theorems or knowledge we could have about the natural numbers?
16
votes
3answers
631 views
Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?
Prompted by some of the comments on this question, I'm wondering if anything is known about the place of the Collatz Conjecture in the arithmetic hierarchy. More specifically, is Collatz known to be ...
15
votes
2answers
725 views
Gödel's incompleteness theorem and real closed fields
I am familiar with the result of Gödel's incompleteness theorem. I find it hard though, to convince myself that when we replace normal number arithmetic with real closed fields, that there is an ...
15
votes
4answers
626 views
How did the ancients view *infinitesimals*?
With some category/topos theory we can now put infinitesimals on a rigorous ground, as in Bell's A Primer of Infinitesimal Analysis, where the author introduces $\epsilon$ satisfying \begin{equation}
...
15
votes
5answers
560 views
What are the theorems of mathematics proved by a computer so far?
By theorems, I mean the ones you can find in an undergraduate course of mathematics, not the ones you can find in a textbook of automated proofs.
I mean by "proved by a computer" that an existing ...
15
votes
4answers
519 views
An (apparently) vicious circle in logic
Can someone please help me with this following exercise 4.4 (p. 114) from the Mathematical Logic book of Ebbinghaus et al(this is not homework, but rather something that has been bugging me for a long ...
15
votes
1answer
592 views
Infinite Set is Disjoint Union of Two Infinite Sets
A finite set is a set such that there exists a bijection from it to some finite ordinal. An infinite set is a set that is not finite.
In ZF, can you prove that every infinite set is the union of two ...
14
votes
11answers
2k views
Logic nonsense/paradox
I'm not sure if this is a paradox or a nonsense or neither of both.
Anyway this is the "problem" if we can call it like that:
A: B is True
B: A is False
How can ...
14
votes
8answers
867 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 ...
