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)

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: ...
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 ...
9
votes
5answers
1k 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 ...
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 ...
5
votes
6answers
1k views

Confused between Nested Quantifiers

I am reading nested quantifiers. I am confused in between two cases, ...
163
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 ...
21
votes
5answers
4k 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 ...
10
votes
8answers
9k views

Not understanding this row of truth table for logical implication

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\\ ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
14
votes
7answers
976 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 ...
10
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 ...
5
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 ...
7
votes
2answers
420 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
5k 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 ...
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 ...
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 ...
12
votes
6answers
688 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 ...
13
votes
5answers
792 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?
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?
7
votes
1answer
408 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 ...
12
votes
4answers
563 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 ...
7
votes
4answers
3k 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.
6
votes
4answers
396 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$?
6
votes
6answers
561 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
433 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
295 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 ...
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?
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 ...
19
votes
6answers
689 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
4answers
4k views

Why an inconsistent formal system can prove everything?

I am reading a Set Theory book by Kunen. He presents first-order logic and claims that if a set of sentences in inconsistent, then it proves every possible sentence. Since he does not explicitly ...
8
votes
8answers
2k 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 ...
12
votes
1answer
754 views

(Why) is topology nonfirstorderizable?

Is it the right point of view to say, that topology is nonfirstorderizable (only) because the union of arbitrarily many open sets has to be open? And if "arbitrarily many" was relaxed to "finitely ...
13
votes
5answers
888 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 ...
9
votes
1answer
487 views

Why is CH true if it cannot be proved?

Continuum hypothesis (CH) states that there can be no set whose cardinality is strictly between that of integers and real numbers. Godel, 1940 and Paul Cohen,1963 showed that CH can neither be proved ...
7
votes
2answers
805 views

Prove that $\beta \rightarrow \neg \neg \beta$ is a theorem using standard axioms 1,2,3 and MP

I've proven that $\neg \neg \beta \rightarrow \beta$ is a theorem, but I can't figure out a way to do the same for $\beta \rightarrow \neg \neg \beta$. It seems the proof would use Axiom 2 and the ...
13
votes
2answers
503 views

Mistake(s) in My Intuition of Vacuous Truth: $\forall \, x \, \in \,\emptyset : P(x) $

$\exists \, x \, \in \, \emptyset : P(x) $ will be false no matter what the statement $P(x)$ is. There can be nothing in $\emptyset$ that, when plugged in for $x$, makes $P(x)$ come out true, ...
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?
4
votes
2answers
562 views

How do I choose an element from a non-empty set?

Suppose I have a non-empty set $A$. How do I choose an element $x\in A$? More precisely, I believe I would like to find a formula $P(x,y)$ of ZF such that for every non-empty set $y$ there is ...
3
votes
7answers
4k views

The meaning of implication in logic

How to remember implication logic by remembering a simple english. I read some sentence like if P,then Q P only if Q Q if P But i am unable to correlate these ...
10
votes
1answer
681 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
2answers
489 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
162 views

Using $p\supset q$ instead of $p\implies q$

I saw that a use for the notation $p\supset q$ instead of $p\implies q$ that got me a bit confused. One occurrences is in this Wikipedia link. It seems to me opposite than what it should be, let me ...
2
votes
3answers
273 views

A question about a certain way to define mathematical objects

It is common in mathematics to see definitions of the following form: we begin with a certain object $A$. we perform some construction depending on a choice of some parameter $\lambda\in\Lambda$ for ...