2

Are all validities isomorphic or equivalent to valid proofs? I ask because of the following:

Let P be the set of prime numbers

  1. ∃x∃y(y>x∧y∈P)→∀x∃y(y>x→y∈P) translates to the following proof:

P1. ∃x∃y(y>x∧y∈P)

C. ∀x∃y(y>x→y∈P)

  1. ∀x∀y(y>x)∧∀x∃y(y>x→y∈P)→∀x∃y(y>x∧y∈P) translates to the following proof:

P1. The domain of discourse is such that y is always greater than x.

P2. ∀x∃y(y>x→y∈P)

C. ∀x∃y(y>x∧y∈P)

7
  • i can't read symbolic logic, so i feel useless, but the question title was fun
    – andrós
    Commented Apr 7 at 23:27
  • 2
    What do you mean by validities and isomorphism? What’s the definition of isomorphism your using? Commented Apr 7 at 23:37
  • 1
    The first proof is invalid, (1) is not a theorem. (2) is a theorem but I’m not sure if you understand what it means (given that you’re using <, which suggests at least it’s an anti symmetric relation) Commented Apr 7 at 23:39
  • 1
    @ayylien it’s valid in Classical FOL.
    – PW_246
    Commented Apr 8 at 0:17
  • 2
    @PW_246 ah I read the last part wrong, thought it was also a conjunction Commented Apr 8 at 4:16

3 Answers 3

4

You’re on the right track, but it’s worth noting that the notion of proof is dependent on which proof system you use, while the notion of valid argument form is more general. A valid argument just requires that the premises logically entail the conclusion, while a valid proof requires using only the inference rules available to a given proof system.

For example, if you’re in a system of Classical Logic it’s perfectly valid to make the argument:

  1. A∨~A [Pr]
  2. (A&~A)→B

However, such an argument is not always going to be a valid proof in a given proof system, even though there is a valid proof from the premise to the conclusion in any proof system for Classical Logic.

4

Are all validities isomorphic or equivalent to valid proofs?

as it stands, the question does not make much sense, but what you may have in mind are soundness and completeness results for a formal calculus/proof system and some semantics for it: a formal calculus being sound with respect to some given semantics means that provability implies validity, and completeness means the converse, so there is a correspondence, in a sense

2

'Isomorphic' isn't the right term, but in first order classical logic, and many others, there is a simple relationship between a valid sentence and a valid argument form.

For any given argument, you can form the corresponding conditional, which is single sentence whose main connective is a material conditional, with the conjunction of the premises as its antecedent, and its conclusion as the consequent. For example, suppose you have an argument with two premises:

A
B
---
C 

Then the corresponding conditional is a single sentence:

(A ∧ B) → C

Where ∧ is conjunction and → is the material conditional.

In classical logic, the argument form is valid if and only if the corresponding conditional is a valid sentence. This is guaranteed by the introduction and elimination rules for the material conditional.

There are non-classical logics, and conditionals other than the material conditional, in which this relation does not hold.

As PW_246 correctly points out, there is a difference between a valid argument form and a proof. A proof requires a specific proof system, so an argument may be valid but may fail to instantiate a correct proof in a given system.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .