Questions about 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)

43
votes
17answers
4k 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: ...
83
votes
4answers
8k 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 ...
9
votes
5answers
2k 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 ...
5
votes
6answers
2k views

Confused between Nested Quantifiers

I am reading nested quantifiers. I am confused in between two cases, ...
184
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 ...
63
votes
8answers
4k 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 ...
14
votes
8answers
10k 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\\ ...
39
votes
11answers
12k 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 ...
25
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))$
5
votes
1answer
1k views

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

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, where, ...
25
votes
5answers
5k 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 ...
17
votes
6answers
3k views

Why is mathematical induction a valid proof technique?

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 ...
109
votes
11answers
12k 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 ...
39
votes
5answers
7k 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 ...
14
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 ...
41
votes
9answers
5k 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, ...
25
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 ...
30
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 ...
62
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. ...
11
votes
1answer
4k 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 ...
14
votes
6answers
768 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 ...
9
votes
5answers
4k 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.
7
votes
2answers
485 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
6k 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 ...
6
votes
7answers
431 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 ...
6
votes
2answers
650 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 ...
117
votes
3answers
17k 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 ...
55
votes
3answers
13k 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 ...
6
votes
6answers
2k 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 ...
13
votes
4answers
838 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?
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 ...
14
votes
7answers
1k 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
3k 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 ...
5
votes
3answers
454 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
645 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 ...
5
votes
4answers
464 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] ...
5
votes
3answers
438 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 ...
22
votes
6answers
849 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 ...
8
votes
8answers
3k views

Tricks for Constructing Hilbert-Style Proofs

Several times in my studies, I've come across Hilbert-style proof systems for various systems of logic, and when an author says, "Theorem: $\varphi$ is provable in system $\cal H$," or "Theorem: the ...
16
votes
8answers
2k 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 ...
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 ...
5
votes
4answers
449 views

Can the principle of explosion be removed from constructive logic?

Classical logic has the theorem ($p\wedge\lnot p)\rightarrow q$, which I will call EFQ ("ex falso quodlibet"). Constructive logic often has the principle built in, in the form of an axiom ...
9
votes
5answers
1k views

What does it mean for something to be true but not provable in peano arithmetic?

Specifically, the Paris-Harrington theorem. In what sense is it true? True in Peano arithmetic but not provable in Peano arithmetic, or true in some other sense?
8
votes
2answers
431 views

Different standards for writing down logical quantifiers in a formal way

What are standard ways to write mathematical expressions involving quantifiers in a (semi)formal way ? In different posts of mine concerning similar question I have encountered for a generic ...
7
votes
1answer
436 views

First-order logic advantage over second-order logic

What is the advantage of using first-order logic over second-order logic? Second-order logic is more expressive and there is also a way to overcome Russell's paradox... So what makes first-order ...
6
votes
2answers
2k views

What is the difference between Gödel's Completeness and Incompleteness Theorems?

Same as title. What is the difference between Gödel's Completeness and Incompleteness Theorems?
12
votes
4answers
573 views

Number Theory in a Choice-less World

I was reading this article on the axiom of choice (AC) and it mentions that a growing number of people are moving into school of thought that considers AC unacceptable due to its lack of constructive ...
10
votes
1answer
741 views

Are there statements that are undecidable but not provably undecidable

This is a variant of Is there a statement whose undecidability is undecidable? and Can it be shown that ZFC has statements which cannot be proven to be independent, but are? (but is not asked or ...
6
votes
4answers
422 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$?
5
votes
2answers
313 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 ...