Talk:Universal generalization
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||
|
Generalization
editIt is not explained why the deduction theorem does not apply in this case. ---- NoizHed (talk) 18:13, 16 November 2007 (UTC)
(I am not a logician)
Let 1) If |-P(x) then |- AllxP(x)
2) P(x)|-AllxP(x)
3)|-[P(x) --> AllxP(x)] False
I think (1) does not give (2).
I) Enderton has (1) as a Metatheorem [p117, use Gamma as empty] and has Unrestricted Deduction Metatheorem [p118] If (1) gives (2) then these combine to give the false (3).
II) Mendelson and Detlovs/Podniak have (2) [in the form of a Rule of Inference]. However, they have a Restricted Deduction Theorem which does not apply to (2). Please correct me if I am misreading something.
(It is clear that (2) gives (1). Starting with a deduction of P(x) one attaches the deduction (2) to get a deduction of AllxP(x).)
128.241.40.80 (talk) 22:35, 22 November 2007 (UTC)A. Reader
To make this more accessible to laypeople (like your's truly), lets try an example: Suppose t=2, and x is defined on the real numbers. Suppose further that P(x) is only true if x=2. so
t=2 (hypothesys)
Vx (x=2->P(x)) (by definition).
P(t) (from 1 and 2, by one of the axioms, we call it L12, not sure what anyone else calls it)
P(t)|-VxP(x) (form 3 according to Gen, right?)
thus t=2|-P(t)->VxP(x) (deduction)
so, that would mean any number is equal to 2, so long as 2 actualy exists.
(Something is rotten in the kingdom of Denmark...)
195.13.158.11 (talk) 15:05, 12 January 2011 (UTC)
Supems(17:03, 16 April 2008 (UTC)
I am not a expert on this area but I need knowledge in this area to pursue my Mathematical studies.
I feel that it is not a good idea to consider the generalization as a |-P(x) -> |-for all x P(x) and talk about the using of deduction theorem because when we prove P(x) for arbitrary x we get (for all x P(x)) which is the generalization so there is no point of talking about using deduction theorem. So it is better to use the gen abbrv and use it as a mere rule of inference. And if there is a restriction of using deduction theorem the restriction is not quite clear in the article including the example proof it is bit confusing when reading the proof and the restriction said above in the article. so it will be better if someone who knows about this clarify this to me. And please let me know if there are any restrictions for deduction thm (not only in this case)
Thanks Supems (talk) 17:09, 16 April 2008 (UTC)
I'm not an expert on this subject but I happen to be studying this subject now, and it seems it is more apt to split this article into universal generalization and existential generalization, as they are two very different rules of inference for quantified statements.
Move proposal
edit- The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.
The result of the move request was: page moved. Vegaswikian (talk) 21:05, 17 March 2012 (UTC)
Generalization (logic) → Universal generalization – This is the more common term for this concept. Greg Bard (talk) 22:23, 10 March 2012 (UTC)
HoldOkay The sources are just partial names, with no page references. I've heard of a Copi and of Morley (Cornell), but both are long of tooth.... Why not provide references to a recent source. What about all the fundamental works about the lambda calculus (Scott-Strachey, Lambek, combinators, etc.)? I cannot remember reading about the term "universal generalization". What about abstraction? Have you asked at the Computer Science and Logic and Philosophy WikiProjects? Kiefer.Wolfowitz 12:22, 13 March 2012 (UTC)- "Universal generalization" is the usual term for the inference rule that adds a universal quantifier (in natural deduction, for example). The rule can also be called "∀ introduction". "Existential generalization" is the matching rule to add an existential quantifier. The thing I have always thought was strange about this article is that there are two generalization rules but this article only talks about one. — Carl (CBM · talk) 12:57, 13 March 2012 (UTC)
- Carl's word suffices for me. Kiefer.Wolfowitz 13:32, 13 March 2012 (UTC)
- "Universal generalization" is the usual term for the inference rule that adds a universal quantifier (in natural deduction, for example). The rule can also be called "∀ introduction". "Existential generalization" is the matching rule to add an existential quantifier. The thing I have always thought was strange about this article is that there are two generalization rules but this article only talks about one. — Carl (CBM · talk) 12:57, 13 March 2012 (UTC)
- Support. Generalization (logic) will still be useful as a redirect after this move but Universal generalization is definitely the common term now. Mark Hurd (talk)
- The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.
Example is not good?
editUnder "Generalization with hypotheses" an example of what can go wrong if the "second restriction" (x [should] not occur in φ) is not followed. It seems to me that this is not a good example to demonstrate the need for the restriction, because if it is corrected so that step 4. uses a variable that does not occur in φ, e.g. 4. were rewritten as "(ForEvery V) V is not equal to x", the second restriction would be respected but the deduction would still be unsound. Tom Cohoe (talk) 11:32, 9 November 2012 (UTC)
Wow. 9 years later the example still hasn't been repaired.
The second restriction needs a new example where the only error is overloading the bound variable name, e.g.,\\ Let x be arbitrary\\ Assume ∀z P(z,y)\\ P(x,y)\\ ∀y P(y,y)\\
Without the second restriction, one could make the following deduction:\\ {\displaystyle \exists z\,\exists w\,(z\not =w)} {\displaystyle \exists z\,\exists w\,(z\not =w)} (Hypothesis)\\ {\displaystyle \exists w\,(y\not =w)} {\displaystyle \exists w\,(y\not =w)} (Existential instantiation)\\ {\displaystyle y\not =x} y \not = x (Existential instantiation)\\ {\displaystyle \forall x\,(x\not =x)} {\displaystyle \forall x\,(x\not =x)} (Faulty universal generalization)\\
Example of a Proof
editIn the example given, the last two lines are redundant, because the question was asking to prove A is derivable from B and C, which line 9 establishes that. LoMaPh (talk) —Preceding undated comment added 02:49, 21 November 2017 (UTC)
The First Restriction
editThe first restriction needs to be restated because it seems to allow the following invalid reasoning:\\ Assume ∃z P(z) \\ P(x)\\ ∀y P(y)
ProfRB (talk) 21:06, 22 March 2019 (UTC)
The real issue is how universal generalization (ug) restrictions combine with the existential instantiation (ei) rule. Correctness of ug restrictions also depends on whether the logic involved allows function symbols to properly execute the ei rule. The ug rule alone needs restrictions that depend on the logic it is part of and the ei rule it is combining with. The page does not handle this and is broken.
If the logic allows/requires Skolem functions (applied to the variables remaining) to be introduced by ei then the ui restrictions shown are adequate, assuming ei always introduces such terms. (We only need to prevent premises about the variable we are generalizing and avoid variable capture; we have no worries about ei.)
The example leading this talk section is easily disallowed, as it introduces x by ei, and x is a variable. The restrictions on ug shown in the page would appear to assume that ei cannot introduce variables.
So the rule shown on the page is fine if we assume ei does not introduce variables and further assume that function symbols are allowed and used by ei as needed. But many students learn predicate logic with no function symbols (cf. Gersting text[1]). In that setting, ei can only introduce constants, and won't capture the dependency of those constants on variables in the ei-introduced formulas and later generalization can go awry (as in the example shown in an earlier section of the talk page, closely related to the broken example on the current public page, which I discuss next). Versions of predicate logic lacking function symbols will have this issue and will need a restriction on ug like "the line being generalized cannot contain (even transitively) depend on an ei line containing the variable being generalized", as in the Gersting text cited. More complex restrictions can be formulated that allow more proofs, this one is over-restricting for simplicity.
HOWEVER, the current public page goes on to discuss an example disallowed proof supposedly motivating the restrictions on the rule and that example actually uses ei to introduce a constant symbol that would need to be a functional Skolem term in order to get along with the ug rule restrictions shown. That section, as discussed by others above in this talk page, is badly broken, and has been for 9 years. It can be fixed by changing so that the ei usage shown introduces a Skolem function in the first use of ei, using y(w) instead of just y. With this fix it will get along with the restrictions shown on ug but it will no longer be an example of why they are needed.
References
editThe references are
Copi and Cohen Hurley Moore and Parker
(I kid you not.) How is the reader supposed to know what works are being referred to? 31.50.156.39 (talk) 15:42, 23 March 2019 (UTC)