Generalization (logic)

Generalization (logic)

Generalization is an inference rule of predicate calculus which states that::"If vdash P(x) is true (valid) then so is vdash forall x , P(x) ."Generalization" can be abbreviated as GEN. The inference rule can be summarized as the sequent: P(x) vdash forall x , P(x) ,but this gives rise to an important restriction: the Deduction Theorem cannot be applied to it to derive:

vdash P(x) ightarrow forall x , P(x)
This formula is wrong because "x" has an unbound instance in its antecedent and a bound occurrence in its consequent, so that if the formula were instead correct, then its free instance of "x" could be replaced by any constant (element of the domain):: vdash P(t) ightarrow forall x , P(x) but this is incorrect. E.g. if P(x) means "x" is a prime number" and the domain is the set of natural numbers, then: vdash P(7) ightarrow forall x , P(x) is clearly not true, because from it and: vdash P(7) ,"7 is a prime number", can be deduced: vdash forall x , P(x) ,"all natural numbers are prime numbers", a contradiction, by means of modus ponens, so the wrong formula is reduced to the absurd.

This restriction applies to proofs: if generalization is applied to a formula in a proof, thereby binding its free variable "x", then DT cannot be applied to the proof to move this formula to the right side of the turnstile.

Note that "P(x)" symbolizes an open statement with free variable "x", whose truth is contingent on "x", but vdash P(x) symbolizes a statement which is valid (for all values of "x"), even though its variable "x" is free. Generalization applies to such valid statement, binding its free variable and yielding vdash forall x , P(x) .

So the formula vdash forall x , P(x) is just a more explicit way of stating what was already implicitly meant by vdash P(x) .

There is also an axiom of Pred.Calc. which states that: vdash forall x , P(x) ightarrow P(x) which transforms by the converse of the Deduction Theorem into: forall x , P(x) vdash P(x) ,meaning that from vdash forall x , P(x) can be deduced vdash P(x) . Putting generalization and the axiom together, one deduces that: vdash P(x) Leftrightarrow vdash forall x , P(x) which does not mean the same as:

P(x) Leftrightarrow forall x , P(x)
which is wrong because here "P(x)" could be any contingent, invalid, open formula. In order to prevent such wrong formula from being at all provable, the restriction is added to DT in Pred.Calc.

The turnstile symbol vdash is not a part of a well-formed formula: strictly speaking it belongs neither to Prop.Calc. or Pred.Calc., but might be thought of as a "metasymbol". Therefore, ultimately vdash forall x , P(x) really does mean more than vdash P(x) , because the vdash symbol is not really a part of the formula "P(x)"; it is just a "handle" used to "grab" the formula, figuratively speaking.

Example of a proof

Prove: forall x , (P(x) ightarrow Q(x)) ightarrow (forall x , P(x) ightarrow forall x , Q(x)) .

Proof:

In this proof, DT was applicable in step (10) because the formula forall x , P(x) which was to be moved to the right of the turnstile (by DT) did not contain any free variable. DT was also applicable in step (11) for the same reason.

ee also

*First-order logic
*Universal instantiation


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Logic and the philosophy of mathematics in the nineteenth century — John Stillwell INTRODUCTION In its history of over two thousand years, mathematics has seldom been disturbed by philosophical disputes. Ever since Plato, who is said to have put the slogan ‘Let no one who is not a geometer enter here’ over the… …   History of philosophy

  • Generalization — is a foundational element of logic and human reasoning. Generalization posits the existence of a domain or set of elements, as well as one or more common characteristics shared by those elements. As such, it is the essential basis of all valid… …   Wikipedia

  • Logic — Log ic, n. [OE. logike, F. logique, L. logica, logice, Gr. logikh (sc. te chnh), fr. logiko s belonging to speaking or reason, fr. lo gos speech, reason, le gein to say, speak. See {Legend}.] 1. The science or art of exact reasoning, or of pure… …   The Collaborative International Dictionary of English

  • Logic — For other uses, see Logic (disambiguation). Philosophy …   Wikipedia

  • logic, philosophy of — Philosophical study of the nature and scope of logic. Examples of questions raised in the philosophy of logic are: In virtue of what features of reality are the laws of logic true? ; How do we know the truths of logic? ; and Could the laws of… …   Universalium

  • logic — logicless, adj. /loj ik/, n. 1. the science that investigates the principles governing correct or reliable inference. 2. a particular method of reasoning or argumentation: We were unable to follow his logic. 3. the system or principles of… …   Universalium

  • generalization — /jen euhr euh leuh zay sheuhn/, n. 1. the act or process of generalizing. 2. a result of this process; a general statement, idea, or principle. 3. Logic. a. a proposition asserting something to be true either of all members of a certain class or… …   Universalium

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • Hasty generalization — is a logical fallacy of faulty generalization by reaching an inductive generalization based on insufficient evidence  essentially making a hasty conclusion without considering all of the variables. In statistics, it may involve basing broad… …   Wikipedia

  • Epistemic modal logic — is a subfield of modal logic that is concerned with reasoning about knowledge. While epistemology has a long philosophical tradition dating back to Ancient Greece, epistemic logic is a much more recent development with applications in many fields …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”