Questions tagged [proof]
For questions about the correctness of a proof or the nature of proofs in general.
323
questions
2
votes
1
answer
208
views
Quick logic deduction question
I have to provide a natural deduction derivation for:
¬∀xFx ⊢ ∃x¬Fx
That´s what I got so far:
1.¬∀xFx
2.‖ ¬∃x¬Fx (Indirect proof hypothesis)
3.‖‖ ¬¬Fy (Indirect proof hypothesis 2)
4.‖‖ Fy (...
- 65
3
votes
1
answer
6k
views
Use the Fitch system to prove the tautology (p ∨ ¬p)
I've scoured the math stackexchange and the philosophy one for some guidance on how to go about this while using the Fitch System.
Anyone can attempt it here;
http://logic.stanford.edu/intrologic/...
1
vote
4
answers
215
views
Is the reasoning behind this proof that a unified scientific theory of everything in physics is impossible correct?
I wrote this originally as a response to another question posed on Quora as to whether or not but I was wondering if someone could reexamine this and find any possible possible gaps in logic or ...
- 111
4
votes
2
answers
718
views
Can there be true conclusions without assumptions?
I was thinking of the sentence
"I think therefore I am",
which I had for a long time considered indisputable because it's self-evident.
Then I considered the hypothetical situation where my ...
- 41
4
votes
2
answers
3k
views
Mill's Proof and Nozick's Experience Machine
I'm trying to grasp how Mill's claim that the only good is happiness/pleasure is able to respond to Nozick's though experiment.
Humans strive for virtue and other goods only if they are associated ...
- 173
3
votes
1
answer
476
views
Clear and canonical examples of analytical proofs in philosophy
I am used to the proof methods of mathematics, and I have formally studied formal logic and mathematical logic. I like philosophy but have never followed a rigorous course in analytical philosophy.
...
- 251
5
votes
3
answers
3k
views
Are axioms tautologies?
My understanding is that axioms are the unprovable statements upon which systems are built. Tautologies are in essence things that can't be false.
Godel's Incompleteness Theorem, though, shows that ...
- 171
1
vote
0
answers
321
views
Axiomatic Proof of Symmetry and Transitivity of Identity
Given the axioms below and the rules of Modus Ponens and Universal Generalization, how can you prove that t=s → s=t for any terms s and t? Additionally, how do you prove that t = s → (s = r → t = r) ? ...
- 31
3
votes
2
answers
2k
views
The Principle of Explosion v. Reductio ad Absurdum
The proof for the Principle of Explosion starts by assuming a contradiction.
When we use reductio ad absurdum, we establish a proof by reaching a contradictory conclusion in sub-argument and then ...
- 149
4
votes
1
answer
234
views
Is it provable that epistemically possible (possible for all I know) does not imply possible?
Here is an argument that it is not. Let's start with some equivalences:
X is epistemically possible
iff
X is possible for all I know
iff
not (X is impossible given what I know)
iff
X is not ...
- 41
4
votes
7
answers
578
views
Is there any difference of terminology between a person who would never worship God and one who will upon proof?
What I mean is that I've seen atheists being asked what would it take for them to worship God. Ultimately their answers amount to, "nothing will make me worship God - even if God exists - because I ...
- 291
3
votes
2
answers
278
views
What is the relationship between the BHK interpretation of propositional logic and Natural Deduction?
This is a repost from MathSE.
I've been getting into intuitionistic logic lately, starting from propositional logic. I am interested in proof-theoretic semantics, meaning the idea that the truth of ...
- 133
2
votes
1
answer
843
views
prove: ∃x ∃y (Cube(x) ∧ Cube(y) ∧ x ≠ y ∧ ∀z (Cube(z) → (z = x ∨ z = y)))
I need a formal (Fitch) first order logic proof for:
∃x ∃y (P(x) ∧ P(y) ∧ x ≠ y ∧ ∀z (P(z) → (z = x ∨ z = y)))
Given
∃x ∃y (P(x) ∧ P(y) ∧ x ≠ y)
∀x ∀y ∀z ((P(x) ∧ P(y) ∧ P(z)) → (x = y ∨ x = z ∨...
- 21
2
votes
2
answers
199
views
Is there something wrong in breaking the symmetry of Natural Deduction?
In the intuitionistic natural deduction (NJ) we have a nice symmetry : each logical connective has an introduction rule and an elimination rule.
But when we want to switch to classical logic (NK) we ...
- 878
2
votes
1
answer
153
views
Predicate logic proof
I need to prove: ∀xRax → ∀x∃yRyx
My available axioms are:
ϕ → (Ψ→ϕ )
(ϕ → (Ψ→χ)) → ((ϕ→Ψ) → (ϕ→χ)
(~Ψ→~ϕ) → ((~Ψ→ϕ) →Ψ)
∀αϕ→ϕ(β / α)
∀α(ϕ→Ψ) → (ϕ→∀αΨ)
Our rules are modus ponens and universal ...
- 31
7
votes
3
answers
567
views
What is behind Girard's idea of distinguishing implication ( ⇒) and entailment (⊢) without separating language and meta-language?
How should we understand the distinction between ⇒ and ⊢ ?
I often see that A ⇒ B lives in the object language and A ⊢ B in the meta language. But I need a different interpretation, without any ...
- 878
5
votes
2
answers
536
views
Philosophical interpretation of the cut rule of Sequent Calculus
It seems that the cut elimination theorem of Sequent Calculus has some interesting consequences.
Quote from Alain Lecompte, La logique linéaire et la question des fondements des lois logiques (French)...
- 878
1
vote
2
answers
2k
views
Can a true statement also imply the opposite of itself?
It's unlikely that there could be a thesis that also is its own antithesis. Similarly, a formula usually isn't the "opposite" of itself if we use well-defined terminology.
Somehow I have a notion ...
3
votes
3
answers
225
views
New riddle of induction; does the observer know the arbitrary time t?
Wikipedia, in "New riddle of induction", sets out Nelson Goodman's paradox as follows:
Goodman defined grue relative to an arbitrary but fixed time t as
follows: An object is grue if and only if ...
- 6,140
2
votes
1
answer
64
views
Is this a valid move in a proof or does this create a contradiction?
If I have something like the following can I use the add inference rule to add ~A. Does that cause a contradiction, or am I fine since it's if A and not A being directly declared?
1. (A ⊃ B) ⊃ C
2. ~...
- 23
3
votes
2
answers
356
views
How would one go about proving the following statement in predicate logic?
I need to prove this:
⊢(∀x)((Fx→Gx)∨(Gx→Fx))
Not entirely sure how I'd go about this.
- 33
5
votes
2
answers
712
views
How does one prove properties of soundness and completeness for a logic using proof-theoretic semantics?
Can one prove these properties at all without relying on notions of models and interpretations?
Are there other properties that proof-theorists usually prove instead?
From what I've read, I've only ...
- 53
6
votes
3
answers
2k
views
In Fitch, how does one prove "(P → Q)" from the premise "(¬P ∨ Q)"?
It's all in the question really. I am working on a proof in Fitch for a class, but I am very much stuck.
I am proving the tautology that "(P → Q) ↔ (¬P ∨ Q)", and I have already finished half of it, ...
- 61
13
votes
9
answers
1k
views
Is a proof still valid if only the author understands it?
Some time ago I was reading about the recent Shinichi Mochizuki's proof for the famous ABC conjecture. It's enormous and so incredibly difficult that at that time virtually nobody was able to ...
- 311
2
votes
1
answer
347
views
Formal proofs using subproofs
I have been trying to solve this question for couple hours and I still don't get it. The problem I'm trying to solve is 6.14 in the link below.
This is what I attempted so far:
I'm sure this is ...
- 21
1
vote
1
answer
174
views
How do you prove A <-> C given the following premises?
Using the 20-rule proof system (replacement rules, rules of inference, conditional proof, and reductio ad absurdum) and given these 3 premises:
A -> ~B
~C -> B
~A -> ~C
I know that since I'm ...
- 13
2
votes
1
answer
229
views
How would you go on proving Law of Excluded Middle with Quantifiers?
The following obviously follows true from no premises, but I can't seem to find a formal proof to it unfortunately.
∃x ∀y (¬P (y) ∨ P (x))
- 23
2
votes
1
answer
1k
views
Prove ◇(p ∨ q) → (◇p ∨ ◇q) and ◇(p ∧ q) → (◇p ∧ ◇q) in Modal Logic K
I would really appreciate a rundown of a proof of one of the formulas or both:
1) ◇(p ∨ q) → (◇p ∨ ◇q)
2) ◇(p ∧ q) → (◇p ∧ ◇q)
I'm allowed to use following proof procedures of modal logic K:
1) ...
6
votes
3
answers
5k
views
Propositional Logic: How to prove the contraposition in the Fitch system?
Given that:
p ⇒ q
prove that:
¬q ⇒ ¬p
using the Fitch system.
(This being the proof of the Contraposition)
- 101
1
vote
1
answer
388
views
Given proofs of A → B and A, when do we get a proof of B?
In intuitionistic mathematics, a proposition is true only when a proof of it has been experienced. Following the BHK semantics, a proof of A → B is an algorithm that, when given a proof of A, will ...
- 153
5
votes
5
answers
428
views
A Paradox of Precision?
Yesterday I was talking to one of my mathematics professor regarding the notion of proof in general (whatever the word "general" means to the reader).
In short my claim was,
We can only be ...
user13627
3
votes
2
answers
593
views
A and ~A in logical proof
In my logic class last semester, we went over proofs with the rules of induction and replacement. In a couple of the exercises, I noticed something. In each of the exercises in question, all of the ...
- 31
1
vote
0
answers
342
views
What are some active areas of research in proof theory?
Is there any research activity going on in the field of proof theory today? If so, what are some of the most active areas, what types of questions do they deal with, and where can I go to find out ...
5
votes
2
answers
551
views
What is the difference between everyday realism and metaphysical realism?
At an everyday level, we seem to subscribe to a from of strong realism which doesn't leave any room for skepticism. We are certain that individuals who hear voices in their heads or who have ...
- 27.1k
1
vote
4
answers
3k
views
Fitch Formal Logic Help 6.26
6.26
Premise:
A v (B ^C)
Premise: ~B v ~C v D
Goal:
A v D
Prove it formally without using DeMorgan's Law.
- 27
13
votes
3
answers
609
views
What is the relation between proof in mathematics and observation in physics?
Recently in his 2015 Hirzebruch Lecture in Bonn, Arthur Jaffe re-amplified his famous perspective that finding proof in mathematics is analogous to making experimental observation in physics. In ...
- 1,506
-1
votes
1
answer
333
views
Logic proof on biconditional [closed]
(P → Q) ↔ ( ¬P ∨ Q) is the goal, there's no premises
I start with
2.|_ P -> Q..................
3.||_ P......................
4., _ ~P....................
5., |....................RULE: | INTRO 3,...
5
votes
6
answers
3k
views
Is any aspect of the supernatural testable? What level of proof is possible for the supernatural?
Assume the supernatural does exist, and consists of beings/forces that can interact with our natural universe in ways that are contrary to the natural laws of this universe (at least as we know them).
...
- 956
6
votes
4
answers
936
views
Can something "count" as TRUE without support by logic and empirical data?
I was in an online debate and had this statement presented to me.
I would note further that your apparent positivism rests on what is
logically a faith claim - specifically, the unproveble claim ...
- 163
2
votes
1
answer
163
views
Using the conception of 'reliable, unchanging' does 'truth' exist?
An 'archaic' definition for TRUE,TRUTH implies constancy, reliability, unchanging, fidelity.
Using this concept of TRUTH is the following valid?
There exists either that which is TRUE or that which ...
- 21
0
votes
1
answer
308
views
Prove (P → Q) ↔ (¬Q → ¬P) using conditional elimination and negation introduction. [closed]
I'm trying to prove that (P → Q) ↔ (¬Q → ¬P) using Fitch.
I know I have to prove two subproofs.
1) P → Q
2)¬Q → ¬P
5
votes
3
answers
3k
views
What exactly are the identity rules in logic?
In first order logic, I have read that there are a couple of identity rules.
If I have "a=b" does it mean that I can also write it as "b=a"?
Is it true one-way or both?
And if I have two ...
- 527
2
votes
4
answers
23k
views
Does the famous Descartes quote "dubito, ergo cogito, ergo sum" suggests secure knowledge of ones existence?
After a discussion about the "difficulties to distinguish knowledge from faith" someone replied to me that the quote implies faith because it uses the word "think". But as it is generally understood:
...
- 1,324
4
votes
2
answers
179
views
Where can I learn about the philosophy behind mathematical and logical proofs?
I'm looking for something that dives into the philosophical idea of a "proof," and explains how the subjects of mathematics and logic deal with it. Does anyone have any book or article recommendations ...
6
votes
3
answers
4k
views
Does predicate logic have truth tables?
As I recall in propositional logic, it was possible to draw truth tables for the arguments such as for:
(P ∨ R) [I live in Paris or I live in Rome]
Therefore, (~P ⊃ R) [If I don't live in Paris ...
- 527
1
vote
3
answers
177
views
How does this propositional proof make sense?
How does the following proof of argument is valid and makes sense?
1. (R • C) [It is raining and It is cloudy]
2. ~R [It is not raining]
Therefore, S [It is snowing]
According to proof by ...
- 417
8
votes
5
answers
17k
views
How does one prove De Morgan's laws for quantifiers?
One of De Morgan's laws state that ¬∃x P(x) is equivalent to ∀x ¬P(x), but how would one go about formally proving this?
Numerous attempts to find a solution have been futile, even proofwiki.org ...
- 321
2
votes
2
answers
956
views
Subjective Proofs
I've been having thoughts for a while about what constitutes a proof. Formal logic usually consists of incredibly detailed steps and, as such, is usually not utilized that often in everyday life.
...
- 157
6
votes
2
answers
1k
views
Given P ∨ ¬ P prove (P → Q) → ((¬ P → Q) → Q) by natural deduction
I am very new to proof and logic and I would really appreciate a rundown of this proof.
I use a program called Fitch to construct my proofs.
I understand there are two types of proofs. Direct ...
4
votes
2
answers
143
views
Multiple universal quantifiers in an argument
Consider the argument
∀x∀y((S(x,a)∧ S(a,y))→S(x,y)),
∀x¬S(x,x)
├ ∀x(S(x,a)→¬S(a,x))
My approach to formally proving this was to first eliminate ∀x and use x0 as the free variable. Then afterwards ...
- 321