Induction of a quantifier free sentence: Philosophy Forums

Induction of a quantifier free sentence

feefoo
Initiate

Usergroup: Members
Joined: Oct 31, 2005
Total Topics: 4
Total Posts: 4

Posted 12/08/05 - 06:52 PM: Subject: Induction of a quantifier free sentence	#1
I was wondering if anyone can give me a hand with this question i have encountered. The question states that A is a quantifier free sentence. Prove by induction that a set containing all the atomic subsentences of a sentence A either implies A or implies A's negation. To simplify, I am omitting the cases of disjunction, the conditional, and the biconditional for now. Thanks in advance for any advice you may give.

MoeBlee
aka I. Kabruob

Usergroup: Members
Joined: May 19, 2005
Total Topics: 10
Total Posts: 1030

Posted 12/08/05 - 07:25 PM:	#2
feefoo wrote: The question states that A is a quantifier free sentence. Prove by induction that a set containing all the atomic subsentences of a sentence A either implies A or implies A's negation. Unless I'm overlooking something, this is very easy. Induction on A. A is atomic. Then the only atomic subsentence of A is A. And A implies A. A is ~P, and the set of atomic subsentences of P either implies P or implies ~P. The set of atomic subsentences of ~P is the set of atomic subsentences of P. If this set implies P, then it implies ~~P, which is the negation of ~P, which is the negation of A. If this set implies ~P, then it implies ~P, which is A. A is P & Q, and the set of atomic subsentences of P either implies P or implies ~P, and the set of atomic subsentences of Q either implies Q or implies ~Q. The set of atomic subsentences of P & Q is the set of atomic subsentences of P union the set of atomic subsentences of Q. Suppose the set of atomic subsentences of P implies P and the set of atomic subsentences of Q implies Q, then the union implies P & Q, which is A. Suppose one of the sets implies a negation. Then that set alone implies ~(P & Q), so a fortiori, the union implies ~(P & Q), which is the negation of A. Edited by MoeBlee on 12/08/05 - 07:31 PM

muxol
yuletide

Usergroup: Members
Joined: Dec 07, 2003
Total Topics: 1
Total Posts: 1834

Posted 12/09/05 - 08:08 PM:	#3
Prove that for any quantifier-free sentence A with occurrences of the atomic sentences B_1(x),,...,B_n(x) (where 'x' is short for 'x_1,...,x_k' for any finite k), there is a deducibility relation in which the following holds. Lemma: B_1(x)',...B_n(x)' \|- A' where for a given assignment of truth-values to the atoms B_1(x),...,B_n(x) we have B_i(x)' = B_i(x) if B_i(x) is true, otherwise B_i(x)' = ~B_i(x) if B_i(x) is false. Proof We proceed by induction on the number m of occurrences of ~ and -> in A. If A is atomic, then the lemma reduces to B_1(x) \|- B_1(x) or ~B_1(x) \|- ~B_1(x). Now assume that the lemma holds for j<m. Case 1. A is ~C(x). Then C has fewer than m occurrences of ~ and ->. Subcase 1a. Let C(x) be true, so C(x)' = C(x) and A' = ~A. By the induction hypothesis applied to C, B_1(x)',...,B_n(x)' \|- C(x). Since \|- C(x) -> ~~C(x), by MP we have B_1(x)',...,B_n(x)' \|- ~~C(x). But ~~C(x) is A'. Subcase 1b. Let C(x) be false, so C(x)' = ~C(x) and A' = A. By the induction hypothesis applied to ~C(x), B_1(x)',...,B_n(x)' \|- ~C(x). But ~C(x) is A'. The other cases are similar. Edited by muxol on 12/09/05 - 09:37 PM

rayzer
Initiate

Usergroup: Members
Joined: Apr 17, 2008
Total Topics: 0
Total Posts: 6

Posted 04/17/08 - 10:57 PM:	#4
I'm curiouse, what would be the proof for a case where A is a disjunction? and where A is a negation?

You don't have permission to post.