### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Intro Symbol Logic PHIL 303

UM

GPA 3.7

### View Full Document

## 6

## 0

## Popular in Course

## Popular in PHIL-Philosophy

This 13 page Class Notes was uploaded by Mazie Kilback Sr. on Thursday October 29, 2015. The Class Notes belongs to PHIL 303 at University of Michigan taught by Staff in Fall. Since its upload, it has received 6 views. For similar materials see /class/231661/phil-303-university-of-michigan in PHIL-Philosophy at University of Michigan.

## Reviews for Intro Symbol Logic

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Induction and Recursion Notes for Phil 303 JT Fall 2007 Contents 1 Recursion Some basic facts 2 Inductive de nition of descendent77 2 12 Recursion on numbers A simple example 5 13 lnduction on numbers Deal two cards 6 14 Ordinary Induction and Complete lnduction 7 15 Recursion and induction on languages with structure 8 16 Closure clause 9 2 Induction on Numbers and Strings More Cases 10 21 Palindromes 10 22 Fibonacci numbers 11 23 Choosing teams 12 24 Something to try yourself 14 1 Recursion Some basic facts A simple pattern of reasoning that shows up from time to time in everyday life and is indispensible to computer programming and analysis of numbers is mathematical induction There is a related pattern of de nition also very important called de nition by induction or de nition by recursion Typically the uses of this reasoning are relatively abstract but the core pattern is simple and occurs in concrete cases as well as abstract ones As we often nd in this course the pattern we are trying to learn is just a common sense pattern of thinking rendered in a more rigorous and explicit way The basic idea of induction is this Say you have a xed starting point and an operation you can apply over and over again Lets say that when you apply the oper ation to a given argument you get something new Then you can apply this operation to that something new77 and get a further new thing And you can keep going ap plying the operation again and again and getting new things again and again Of course with some operations you just keep getting the same thing back over and over again This gives a way to de ne a collection start at the starting point and take what you get by applying the operation over and over again as often as possible So for example the set of non negative integers 0 1 2 can be characterized by the instruction start with 0 and put into the set everything you get by adding one Typically when induction is used it is applied to in nite sets of abstract things But the basic reasoning can apply also to nite sets of concrete things It will be good to consider one mundane example to dispel any air of mystery the de nition of descendent 11 Inductive de nition of descendent A familiar example of an inductive de nition though in everyday conversation it isnt crafted in the canonical form is the de nition of descendent of x Recently there was a dispute about whether or not a particular currently living person was a descen dent of Thomas Jefferson But what does it mean to say someone is a descendent of Thomas Jefferson How do we de ne that set lt7ll be easier for our exposition if we tweak the de nition of descendent77 a bit so that Thomas Jefferson is one of his own descendents lnformally we can say Thomas Jefferson is one of Jefferson7s descen dents and all the children of Jefferson are among Jefferson7s descendents and all the children of each of the children of Jefferson are among Jefferson7s descendents and so on77 Or we might put it a little differently You know You take Jefferson and his children7 and the children7s children7 and the children7s children7s children7 and keep on going like that To the logician7 the crucial unclarity is in the meaning of and so on 7 or keep on going like that lmagine we had to give explicit instructions to a computer to list the Jefferson descendents How would we make the instructions rigorous One way to get oriented is to work backwards Under what conditions is Amy one of Jefferson7s descendents Well7 if at least one of her parents is a descendent of Jefferson Under what conditions is one of Amy7s parents a descendent of Jefferson Well7 if at least one of their parents is a descendent of Jefferson Under what conditions is one of Amy7s parents parents a descendent of Jefferson This could in principle generate an in nite regress7 except that there is one point where it stops In some cases the people in question are actually children of Je erszm This tracing back through the descendents involves one xing the basis principle x is a descendent of Jefferson if x is Jefferson and a further condition that gets repeated over and over again x is a descendent of Jefferson if x is the child of a descendent of Jefferson We can sum up the de nition this way x is a descendent of Jefferson if and only if either i x is Jefferson or ii x is the child of a descendent of Jefferson This may appear circular7 but it isnt l7ll explain why it isnt circular in a moment First l7ll introduce you to a standard format that we use to express de nitions like this Basis clause x is Jefferson Recursion clause x is the child of a descendent of Jefferson Closure clause nothing else is a descendent of Jefferson l7ll say more about the closure clause later l7m including it now just for the record In fact it is usually just left implicit It might seem as if the recursive de nition has a crucial7 intrinsic problem One way for a de nition to be defective is for it to be circular Say that I want to de ne poefool like this x is a poefool if and only if x is a bird and x has feathers7 and x is a poefool This is defective because the term l7m trying to de ne occurs in the clause that is supposed to de ne it If I nd a peacock and ask myself if it is a poefool I cant use this de nition to answer because I would have to already know that it is a poefool to apply the de nition At rst glance the de nition of descendent might seem to have this defect because the term being de ned occurs in the de nition itself In fact this isnt a problem but you need to understand the structure of recursive de nitions to see why not note that each time you apply the de nition you get a bit closer to the baseline stipulation that Jefferson is a descendent of Jefferson and that baseline stipulation doesn7t presuppose any prior grasp of the de nition of de scendent of Jefferson Recursive de nitions support the special kind of reasoning we7ve mentioned called Inductive Reasoning The Jefferson7s descendents77 example gives a deceptively simple example of this One test we would regard as conclusive for demonstrating that someone is a Jefferson descendent is a DNA test We check a sample of Jeffer son7s DNA and a sample of the prospective descendent7s DNA and see if it matches in the relevant ways Now why should this tell us anything Answer because certain properties of DNA are passed on from parents to children The reasoning involved is absolutely familiar but logically it is a bit intricate so I7ll spell it out more ruthlessly than we usually do I will label the parts of this bit of reasoning so that we can refer to them easily Basis Jefferson has DNA property a Induction Step If a person has DNA property 04 then their children have DNA property a Therefore Every descendent of Jefferson has DNA property 041 In most ofthe inductive arguments we7ll study we actually prove the two premises using mathematics or logic In this case the two premises are established by empir ical scienti c investigation of microbiology But the structure of the reasoning from the premises isn7t affected by the way that the premises are justi ed There are two observations worth making First The inference from the basis and induction step to the conclusion is one we nd obvious and untroubling Second The inference is logically rather intricate The premises have to do with the basis and the links of a chain the conclusion concerns every member of the chain 1Of course it matters both that Jeffersonls descendents have a certain property and that people who arenlt Jefferson descendents don t have the property This inductive argument is only relevant to the rst of these But that doesnlt matter to the example Among the most prominent topics that invite inductive arguments and support recursive de nitions are the natural numbers 07127 71 and languages that are generated by iterating rules We will be principally concerned with the structured languages7 but inductive arguments in arithmetic are simpler7 so PM look at an couple of illustrations from arithmetic as well as from structured languages 12 Recursion on numbers A simple example A simple example of a recursive de nition is the de nition of multiplication by some number say 17 in terms of adding 17 Basis clause 170 0 Recursion clause 17 n 1 17 n 17 More generally7 we can de ne z 71 recursively by replacing 17 with z Say that we are asked to calculate 17 23 This de nition xes a value for 17 237 though to get it we need to unpack the de nition by applying the recursion clause repeatedly until we hit the bedrock of the basis 1723172217 17211717 1720171717 17117171717 W 22times 17017171717 23times 017171717 23times At each step7 until the last one7 you get the value of a product of 17 with some number in terms of the product of 17 with a smaller number At the bottom of the chain7 you nally get an expression that is i unpacked in terms of the basis clause alone7 and ii several 17 7s and doesn7t contain any reference to the 17 func tion we are trying to de ne 13 Induction on numbers Deal two cards As noted when you have a domain of objects structured by a recursive de nition it supports arguments by induction Since the simplest example of a recursive de nition is the de nition of the natural numbers in terms of 0 and 1 it is not suprizing that inductive arguments occur especially often in arithmetic The standard example of an inductive argument is given in the textbook section 281 prove that 1 2 3 Here is another In some card games such as blackjack single deck or Texas hold 7em poker at the beginning of a round two cards are dealt to each player Of course for the value of the hand it doesnt matter in what order the cards are dealt if both are face down the hand with AQ dealt rst and then 60 is the same hand as the one with 60 rst and then AQ How many possible rst hands can there be The answer is W 1326 This is an instance of a general pattern whenever ewactly two things are chosen from a sample of k things there are exactly 2 1 different possible choices of pairs if the order doesnt matter Let7s prove the general fact by induction Prove Show that the number of ways to deal two cards out of a deck of k gt 2 cards ignoring the order in which the cards are dealt and assuming that all the cards are different is Proof Base Case The base case is when k 2 There is of course exactly one way of choosing two things from a set of two things M g 1 so our thesis holds for k 2 Induction step Choose 1 gt 2 and assume Induction Hypothesis that there are 190971 2 exactly ways of dealing two cards out of a deck of k cards We Want to Show in the Induction Step There are exactly 9ng ways of dealing two cards out of a deck of k1 cards Proof of induction step Take the deck of I 1 cards and remove one card 0 The remaining cards once 0 is removed are a deck with k cards and so there are a ways of dealing two cards from the deck without 0 It will be useful to have names for the cards in the deck without 0 well call the cards 0102 0g710 The deck consisting of 017 027 7017 Cg has 1 cards and so by the induction hypothesis7 there are exactly a ways of dealing a pair of cards from the reduced deck In the full deck 017027 7019717019 U 0 you can deal all the pairs from the smaller deck7 plus all the pairs consisting of one element from the smaller deck and 0 Since there are exactly 1 elements in the smaller deck7 there are exactly 1 different pairs consisting of one element of the smaller deck and 0 So the full deck contains a 1 possible two card hands Now we just do some simple algebra to get this expression into the form we want 1971 7 271 2 quot i Wie zwb 7 122 7 MFA f k i 2 f i f i T i 2 2 This is just what we want7 so the induction step7 and hence the thesis7 is proven 14 Ordinary Induction and Complete Induction Proofs by mathematical induction t into two slightly different schemes7 depending on how much you assume about the numbers less than n 1 These argument pat terns aren7t importantly different7 but to avoid confusion it is worthwhile to note the surface difference in form We have just seen arguments where we prove some property is true of 0 or whatever is the rst in the series sometimes it is 17 and then we prove that if we assume that property is true of an arbitrary 717 it will also be true of n 1 These two supports allow us to conclude that the property holds of every number A variation is sometimes called the method of complete induetwm though this usage doesn7t appear to be completely standard In complete induction7 we prove the base clause as before7 and then we assume that the property holds of every number less than n 1 The difference is that instead of assuming the thesis just for the number preceding the given one7 we assume it for every number less than the given one Neither of these methods is any less correct than the other it just happens that one form is convenient for some problems7 and the other form is conve nient for others When dealing with strings of symbols in a language7 the method of complete induction tends to be a little more useful 15 Recursion and induction on languages with structure If you speak English or any other natural language uently you are able to produce long and complicated sentences like lncredibly my neighbor was as irritated as a nest of disturbed bees when I asked reluctantly but insistently for the prompt return of the hedge trimmer I needed to tidy up the back yard before my sons already delayed birthday party We can understand sentences like this Of course when they are unusually long it may take some concentration to gure out what they say but we can usually puz zle them out in no more than a few seconds lt7s reasonable to conjecture that this ability is grounded in the fact that complex sentences are generated from simpler components by the application possibly the repeated application of rules Here7s an example Say we have a sentence The dog bit the cat ofthe form nounlverbnoun2 We can form a noun phrase The cat the dog bit of the form The noun2 the nounl verb Also as our sentence The dog bit the cat exempli es given two nouns nounl and noun2 and a verb that takes two arguments we can form a sen tence nounlverbnoun2 Similarly we can form The cat chased the rat from The cat chased and the rat and then from The cat chased the rat we can form the noun phrase The rat the cat chased Notice that we can iterate these operations over and over I can form The dog bit the cat then form The cat the dog bit then taking this as nounl I can form The cat the dog bit chased the rat And we don7t have to stop there Further iterations give us some real prizes The cheese the rat the cat the dog bit chased ate had spoiled in the fridge The fridge the cheese the rat the cat the dog bit chased ate had spoiled in sat next to the stove A digression For entertainment purposes note that some sh like angler sh feed themselves by shing for other sh We can put this fact this way Fish sh sh And of course following roughly the above pattern we can note that there are some sh that are the targets of the sh who sh for sh These are the sh sh sh So understood the sentence Fish sh sh and the noun phrase Fish sh sh support further iterations using the above rules to get meaningful sentences like Fish sh sh sh sh sh sh The examples we have just spun out are all meaningful English sentences though it may take some concentration to puzzle out what they mean if this is the rst time you7ve seen them The way we can understand them is that i we trace back to the basic meaningful constituents ca 77 cheese etc and ii gure out the sentence structure by applying and re applying the rules This is recursion in action As we7ll see as the course goes on this makes it possible learn things about logic and languages by reasoning inductively 16 Closure clause 1 should say explicitly what the closure clause does The closure clause is necessary because there will typically be many sets that contain the basis set and are closed under the conditions given by the recursion clause We are interested in the smallest one For example if we make the huge assumption for the sake of the example that there was a rst pair of human beings called Adam and Eve and that every living person is descended from that pair we can de ne the set of human beings who have lived or are currently living by this recursive de nition Basis clause Adam and Eve are human beings Recursion clause If x is the child of a human being then x is a human being But there are other sets containing Adam and Eve and closed under x is a child of For example the set containing all the human beings who have ever lived plus the Empire State Building also contains Adam and Eve and is also closed under x is a child of The point of the closure clause is to exclude everything like in this case the Empire State Building that isnt explicitly forced into the set we de ne by either the basis clause or the recursion clause 2 Induction on Numbers and Strings More Cases 21 Palindromes According to the most common de nition7 a palindrome is a string of letters that reads the same way backwards and forwards ignoring spaces and punctuation One simple example is race car More elaborate examples tend to sound a bit stilted7 but they can be found Some instances are Madam7 l7m Adam 7 A Man7 A Plan7 A Canal Panama and thought of as spoken by Napoleon before his downfall and exile on the island of Elba Able was l7 ere I saw Elba For more7 you can search on youtube for a truly odd video by the parodist Weird Al Yankovic making fun of a truly odd Bob Dylan video from the 1960s Subterranean Homesick Blues 2 The lyrics of Yankovic7s song are a series of palindromes Nurse7 l spy gypsies runl Do geese see God Go hang a salami7 l7m a lasagna hog There are some trivial cases too I is an English language palindrome7 and so is a For bookkeeping purposes7 let7s count the empty string as an English language expression then it is a palindrome as well We can study the simpler case of palindromes in a regular language lets say we are considering the set of all strings in the alphabet 177 c As far as the structure of palindromes is concerned7 one particular property is especially interesting if you remove the rst and last letter of a palindrome7 you get another palindrome7 two letters shorter This fact gives us a way to inductively de ne palindrome Call a string over 17 be an inductive palindrome if it satis es the conditions Base clause 6 a77 b and c7 are inductive palindromes Recursion clause lf 039 is an inductive palindrome7 then a gtk 039 gtk 17 b gtk 039 gtk b7 0 gtk 039 gtk c are inductive palindromes Closure Nothing else is an inductive palindrome in a7b7c What we want to do now is prove that every palindrome is an inductive palindrome The proof exploits the recursive structure of inductive palindrome to give an in ductive proof 2For Yankovic s video7 a youtube search on Yankovic palindrome will most likely turn it up For full effect7 you might want to watch part of the original Dylan video A search on Dylan Subterranean should do Proof The induction will be on the length of the string 039 Base case Say that 039 is 0 symbols long Then it is 67 which is both a palindrome and an inductive palindrome Inductive step Assume Induction hypothesis that every palindrome of length less than k symbols is an inductive palindrome Say that 039 is a palindrome with exactly k symbols lf 039 has exactly one symbol7 then it is one of a77 b7 or c which are inductive palin dromes by de nition lf 039 has two or more symbols7 then we can remove the rst and last letter7 leaving a string 0 Since 039 reads the same backwards and forwards7 and 0 comes from 039 by removing the rst and last letter7 0 reads the same backwards as forwards That is7 U is a palindrome Since 0 is a palindrome7 and it has fewer than k letters7 then it is an inductive palindrome by the induction hypothesis Since 039 is a palindrome7 the rst and last letter must be the same7 so it is either a b7 or c Soa agtka gtka7 or 039 bgtka gtkb7 or 039 cgtka gtkc7 where as we have shown 0 is an inductive palindrome So7 by the inductive clause of the de nition of inductive palindrome7 039 is an inductive palindrome 22 Fibonacci numbers A sequence of numbers that shows up in a surprizing number of places in nature is the Fibonacci sequence 11727375787137217347 Each number in the sequence is the sum of its two predecessors The inductive def inition of this one is a bit different from the ones we are used to7 since we need to consider both fk and fk 71 to de ne fk17 and we need to de ne two starting points But these are minor adjustments Here7s the de nition fn71fn forngt1 As usual7 the inductive structure makes it possible to prove things Here7s a question is the Fibonacci function f we7ve just de ned dominated by the exponential function 11 g 2m That is7 is it always the case that fx lt g except for f0 3 90 Think about how you might prove this Its easy to con rm this for the base cases 0 90 and 21 90 But once you7ve taken care of these speci c cases7 how can you go on The basic observation is simple use the elementary fact that if a S c and b lt c then ab lt 20 This tells us that repeatedly taking bonacci numbers is not going to pull ahead of repeatedly multiplying by two Try it for the rst seven or so values of each sequence 17172737578713 17274787167327647 No doubt by now you get the idea the inductive argument is the way to make the idea rigorous We have already proven the base case for f0 and f1 now we Assume that for every n such that 1 lt n lt k7 fn lt 2 We want to show fk lt 2k That follows immediately from the fact that by the induction hypothesis fk 7 1 lt 2kquot1 and fk72 lt 2k lt 2kquot1 and the fact that fk fk72fk71 lt 2k 12k 1 2 gtlt 21H 2k This proves the inductive step7 and were done 23 Choosing teams Say that you have a situation where k friends are scattered among n teams7 with both k and n greater than or equal to 4 All the friends want to be on the same team The league has a rule that you can only move players from one team to another if you choose two players from two dz erent teams and transfer them to a third team different from the rst two Can the friends hope that eventually they might end up on the same team For any number of teams and friends7 is it always possible to repeatedly apply this rule to shift all the friends onto the same team Yes it is7 and here7s the proof Proof This problem illustrates an issue that sometimes comes up with inductive proofs even if you are sure that an inductive argument is the way to go7 it might 12 be unclear what you should do the induction on Here we have the choice between induction on the number of players or the number of teams In this situation you should ddle around a bit to gure out what works and do the induction on the number of players Base case Say that n the number of players 4 This is one of the rare cases where the base case is more involved than the induction step Take the teams with our friends on them plus as many extra teams we need to get a total of four Ignore the other teams We7ll write 711712713714 711712 ngandm all numbers to represent the number of friends on each team So for example 2 1 0 1 means that 2 friends are on team 1 one of the friends is on team 2 one of the friends is on team 4 and none of the friends is on team 3 Here are the possible starting con gurations the last ofthem represents the target situation where all the friends are on the same team Con gurations Note that the order doesnt matter so we can count both say 1210 and 1102 as con guration b The hardest case is a Beginning there we can move to e in a way that passes through every other con guration So this sequence of moves also shows how to cover the other con gurations 1717171 3717070 2707270 1707172 0707074 I WW 1 w f39ymuu39u c w f39ymuu39u 17 f 5 So however the four friends may start out distributed you can shift them onto the same team while obeying the move two from different teams onto a third team77 rule Induction step OK so what should we do if we have more than four players The induction step will show that if we have a procedure for k players then we have a procedure for k1

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.