# Questions tagged [proof]

For questions about the correctness of a proof or the nature of proofs in general.

323 questions
Filter by
Sorted by
Tagged with
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
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
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
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 ...
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
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
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
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
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
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
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
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
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 ∨...
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
153 views

### Predicate logic proof

I need to prove: ∀xRax → ∀x∃yRyx My available axioms are: ϕ → (Ψ→ϕ ) (ϕ → (Ψ→χ)) → ((ϕ→Ψ) → (ϕ→χ) (~Ψ→~ϕ) → ((~Ψ→ϕ) →Ψ) ∀αϕ→ϕ(β / α) ∀α(ϕ→Ψ) → (ϕ→∀αΨ) Our rules are modus ponens and universal ...
• 31
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
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
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 ...
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
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. ~...
356 views

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 ...
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
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
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
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
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
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) ...
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
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
428 views

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 ...
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 ...
1 vote
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 ...
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
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
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
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,...
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
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
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
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
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
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
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 ...
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
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
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 ...
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