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)

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|} ...
21
votes
6answers
4k 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 ...
106
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 ...
26
votes
11answers
16k views

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

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
49
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 ...
52
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 ...
5
votes
6answers
3k views

Confused between Nested Quantifiers

I am reading nested quantifiers. I am confused in between two cases, ...
14
votes
5answers
3k views

How is exponentiation defined in Peano arithmetic?

How would exponentiation be defined in Peano arithmetic? Unless $n$ is fixed natural number, $x^n$ seems to be hard to define. Edit 2: So, what would be the way to define $x^n+y^n = z^n$ using ...
7
votes
1answer
2k views

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions if no two of these lines are parallel and no three pass through a common point. I know we start with the base case, ...
28
votes
9answers
4k 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))$
219
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 ...
65
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 ...
76
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 ...
33
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 ...
66
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. ...
22
votes
6answers
1k 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 ...
15
votes
4answers
1k views

Is there a statement whose undecidability is undecidable?

We know there are statements that are undecidable/independent of ZFC. Can there be a statement S, such that (ZFC $\not\vdash$ S and ZFC $\not\vdash$ ~S) is undecidable?
8
votes
9answers
2k views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
7
votes
5answers
525 views

Equivalence of $a \rightarrow b$ and $\lnot a \vee b$

Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?
121
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 ...
35
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?
15
votes
7answers
1k views

Applications of ultrafilters

I'm looking for some interesting applications of ultrafilters and also everything of interest involving ultrafilters. Do you know some applications or interesting things involving ultrafilters? I'm ...
21
votes
8answers
3k views

Assumed True until proven False. The Curious Case of the Vacuous Truth

Given two statements, $P$ and $Q$, and the logical connective, $\implies$, the truth table for $P \implies Q$ is: $$\begin{array}{ c | c || c | } P & Q & P\Rightarrow Q \\ \hline \text T ...
6
votes
4answers
647 views

What is the “correct” reading of $\bot$?

I have some doubts about the "natural" interpretation of $\bot$ in Natural Deduction and sequent calculus. In Prawitz (1965) $\bot$ (falsehood or absurdity) is called a sentential constant [page 14] ...
6
votes
3answers
6k views

Write ‘There is exactly 1 person…’ without the uniqueness quantifier

During a lecture today the prof. posed the question of how we could write "There is exactly one person whom everybody loves." without using the uniqueness quantifier. The first part we wrote as a ...
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 ...
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 ...
35
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 ...
15
votes
9answers
13k 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. ...
27
votes
6answers
2k views

How to avoid perceived circularity when defining a formal language?

Suppose we want to define a first-order language to do set theory (so we can formalize mathematics). One such construction can be found here. What makes me uneasy about this definition is that words ...
14
votes
5answers
8k views

Example of set which contains itself

I am trying to understand Russells's paradox How can a set contain itself? Can you show example of set which is not a set of all sets and it contains itself.
8
votes
6answers
1k views

Why is predicate “all” as in all(SET) true if the SET is empty?

Can anyone explain why the predicate all is true for an empty set? If the set is empty, there are no elements in it, so there is not really any elements to apply ...
1
vote
7answers
909 views

Understanding Vacuously True (Truth Table) [duplicate]

I don't know very much about formal logic, and I'm trying to understand the concept of vacuously true statements. Consider the truth table below: $$\begin{array} {|c|} \hline P & Q & P\implies ...
139
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 ...
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, ...
7
votes
2answers
621 views

How does (ZFC-Infinity+“There is no infinite set”) compare with PA?

How does (ZFC-Infinity+"There is no infinite set") compare with (first order) PA? Intuitively, neither theory should be more powerful than the other.
4
votes
4answers
7k views

What is the name of the logical puzzle, where one always lies and another always tells the truth?

So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this: Each inhabitant of a remote village always tells the truth or always lies. A villager will ...
15
votes
1answer
1k 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 ...
6
votes
2answers
1k views

intersection of the empty set and vacuous truth

Let $\mathbb S = \varnothing$. Then from the definition: $ \bigcap \mathbb S = \left\{{x: \forall X \in \mathbb S: x \in X}\right\}$ Consider any $x \in \mathbb U$. Then as $\mathbb ...
5
votes
3answers
561 views

How to show that $\vdash (\forall x \beta \to \alpha) \leftrightarrow \exists x (\beta \to \alpha)$?

Assume $x$ doesn't occur free in $\alpha$, show that: $$\vdash (\forall x \beta \to \alpha) \leftrightarrow \exists x (\beta \to \alpha)$$ This is an exercise on page 130, A Mathematical ...
7
votes
6answers
4k views

How to interpret material conditional and explain it to freshmen?

After studying mathematics for some time, I am still confused. The material conditional “$\rightarrow$” is a logical connective in classical logic. In mathematical texts one often encounters the ...
9
votes
2answers
3k views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and ...
13
votes
5answers
1k views

Why is it possible to conclude everything from a false statement? [duplicate]

Possible Duplicates: In classical logic, why is (p -> q) True if both p and q are False? Why an inconsistent formal system can prove everything? I heard a professor of mathematics ...
19
votes
7answers
2k views

Why in an inconsistent axiom system every statement is true? (For Dummies)

I would like to know if someone can explain in a somehow down to earth (almost logic free) way why is it true that in an axiom system where there is some statement $P$ such that $P$ and its negation ...
5
votes
3answers
1k views

How to prove or statements

How do I prove statements of the following types: $A \text{ or } B \implies$ C $A \implies B \text{ or } C$ I don't know how to go about proving statements like this when they have "or". Can ...
5
votes
2answers
354 views

Open Sets of $\mathbb{R}^1$ and axiom of choice

In the proof of 'Every open set in $\mathbb{R}^1$ is a countable union of disjoint open intervals', we need to pick one rational representative from each of the intervals hence establish the ...
76
votes
14answers
28k views

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

Can you explain it in a fathomable way at high school level?
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 ...
26
votes
7answers
8k 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 ...
12
votes
1answer
6k views

What's the difference between material implication and logical implication?

When I read the definitions of material and logical implications, they seem to me pretty much equivalent. Could someone give me an example illustrating the difference? (BTW, I have no problem with ...