Formal Logic 101 – Part 19: Proofs in Predicate Logic (Part 2)
Last time we covered two of our final 4 inference rules (Universal Instantiation and Existential Generalization). Today we’ll be wrapping up the last of our new rules. Beyond this I have a couple posts planned for less-common situations, and then the series will be done. So let’s get to it.
Existential Instantiation (EI)
If you remember our last past, you might have a guess about how this next rule is going to work. EG let us go from Dm to (∃x)Dx, so EI is probably going to let us go from (∃x)Dx to Dm. If that was your guess, you’re basically right, however, EI is going to have some additional restrictions on how it can be used. To understand the need for these restrictions, I will present the following example where I will INCORRECTLY use EI by treating it exactly the same way as UI.
Consider the following premises: Some numbers are odd. Some numbers are even.
Let us say that “Nx” is “x is a Number”, “Ox” is “x is Odd”, and “Ex” is “x is Even”. Observe the following argument:
1. (∃x)(Nx ^ Ox) P
2. (∃x)(Nx ^ Ex) P
3. Na ^ Oa 1 EI
4. Na ^ Ea 2 EI
5. Ea 4 simp
6. (Na ^ Oa) ^ Ea 3,5 conj
7. (∃x)[(Nx ^ Ox) ^ Ex] 6 EG
*Note: In this instance we haven’t defined what “a” is. That’s perfectly fine, we’re absolutely within our rights to just select an undefined letter and let it serve as a “stand-in”. For instance, we might say “There was some person who was the first to set foot in South America. Since we don’t know who this person was, let’s call them ‘Sam’.” In this instance “Sam” is our stand-in for whoever the actual first person was.
Returning to our above example: In seven lines I have taken two obviously true premises and concluded “There is at least one number that is both odd and even”, which we know at a glance to be false. So where did I go wrong? Line 4 seems to be the likely culprit. After all, on line 3 I established that “a” is my stand-in for an odd number, and then in line 4 I also tried to use “a” as my stand-in for an even number.
This brings us to our first restriction: Any letter used in EI must not have already been used at any previous point in the proof. So, for line 4, we would be unable to conclude “Na ^ Ea”, since we already used “a” on line 3. Instead, we would have to conclude “Nb ^ Eb”, selecting “b” as our stand-in for an even number.
If we introduce a letter via EI, we will need to “flag” it. Think of “flagging” a letter as something vaguely akin to making an Assumption. Just as – with an assumption – we are not saying “this thing is true” but merely saying “Let’s suppose that this is true and see where it would lead.” With flagging a letter we are not saying “the first person to set foot in South America was named Sam”, we’re merely saying “There was a first person to set foot in South America, let’s just call them Sam since we don’t know who they are.” So we flag the letter to indicate that it’s being used as a stand-in. Using our previous example of odd and even numbers the correct use of EI would be as follows:
1. (∃x)(Nx ^ Ox) P
2. (∃x)(Nx ^ Ex) P
3. Na ^ Oa 1 EI – Flag a
4. Na ^ Ea 2 EI – Flag b
One last note before moving on: Because EI requires you to use a letter that hasn’t been used previously, and UI has no such restrictions, if you have a proof that requires you to use both, it’s usually best to use EI first.
I think the need for restrictions should be pretty obvious. While using EG to move from “Max is a dog” (Dm) to “There is at least one dog” (∃x)Dx is correct just on the face of it, using UG to move from “Max is a dog” to “Everything is a dog” (x)Dx, is blatantly incorrect even at first glance.
In order to use UG appropriately we need to make use of “flagging” letters, in order to create a “flagged subproof” (F.S.). As our example, consider the premises “All cats are mammals. All mammals are vertebrates. Therefore, all cats are vertebrates. We can symbolize this as:
1. (x)(Cx→Mx) P
2. (x)(Mx→Vx) P – prove (x)(Cx→Vx)
In order to begin a Flagged subproof, we pick a letter to serve as our stand-in. We need a letter to serve as a stand-in to ensure that our conclusion is truly universal. For instance, say that I don’t choose a stand-in. Instead, let’s say I pick my cat, J’zargo. I see that he’s a cat, that he is in fact a mammal, and that he’s clearly a vertebrate. But have I really proven that this is universal? Or have I just proven that this is true of my cat? In order to avoid possible confounds we pick a random stand-in. So for our next line we would use:
3. a F.S. (U.G.)
In this line we’re saying “so let’s just consider this hypothetical thing. We’ll call it ‘a’. What is ‘a’? We don’t really know, it’s just a thing.” Since we don’t know anything about “a” we don’t need to worry about pre-existing knowledge of it influencing our outcomes. So if we reach a conclusion using our flagged letter, we can conclude that it is actually universally true. From here we would complete the proof as follows:
If you’re looking at this thinking “ok, so flagging really does work a whole lot like an Assumption.” Good! Keep that mindset. It will help keep our last two restrictions on flagging make sense:
Restriction 2: A flagged letter may not appear in either the premises or in the conclusion of a proof.
This prevents us from moving from “Earth has intelligent life” (Le) to “Everything has intelligent life” (x)(Lx), and also prevents us from moving from “Some planets have rings” (∃x)(Px ^ Rx) to “Earth is a planet with rings” (Pe ^ Re)
Restriction 3: A flagged letter may not appear outside the subproof in which it is flagged.
This is very similar to our restriction that – once we’ve discharged an assumption – we cannot use that assumption or any line that depends upon it ever again. Remember when we’re flagging a letter, we’re selecting it as a stand-in for the actual thing, NOT claiming to know what the actual thing is. We’re just using “Sam” as our stand-in for the first person to set foot in South America for purposes of the discussion. We’re NOT actually claiming to know anything about the actual first person to set foot in South America.
So, to restate our restrictions on EI and UG
1) A letter being flagged must be “new to the proof”. It may not appear anywhere in any step prior to the step in which you are flagging it.
2) A flagged letter may not appear in the premises or conclusions of a proof.
3) A flagged letter may not appear outside of the subproof in which it is flagged.
Ok, if you stuck with me through that, congrats, you now know every inference rule we’re going to cover! If your head is swimming and you’re not sure you’re following me… EI and UG are literally two of the most obnoxious rules in all of logic, and I typically make sure that I have my logic book in front of me every time I intend to use them in an argument just to make sure I’m not misusing them, because they suck. So cut yourself some slack. If you remember from a few posts back, we technically have one more replacement rule, which is “Categorical Quantifier Negation” but it’s really kind of “shortcut” rule, designed to make Quantifier Negation take fewer steps. So what I’m going to do is include that rule in the practice problems, and let you all prove it.
So that’s it. That’s all the rules. Next time will be some more-nuanced symbolization stuff which will probably take a couple posts to get through, and then that will be that.
A. ~(x)(Ax→Bx) P – Prove (∃x)(Ax ^ ~Bx)
B. ~(∃x)(Ax ^ Bx) P – Prove (x)(Ax→~Bx)
C. ~(x)(Ax→~Bx) P – Prove (∃x)(Ax ^ Bx)
D. ~(∃x)(Ax ^ ~Bx) P – Prove (x)(Ax→Bx)
E. (∃x)(Ax ^ ~Bx) P – Prove ~(x)(Ax→Bx)
F. (x)(Ax→~Bx) P – Prove ~(∃x)(Ax ^ Bx)
G. (∃x)(Ax ^ Bx) P – Prove ~(x)(Ax→~Bx)
H. (x)(Ax→Bx) P – Prove ~(∃x)(Ax ^ ~Bx)
A
1. ~(x)(Ax→Bx) P – Prove (∃x)(Ax ^ ~Bx)
2. (∃x)~(Ax→Bx) 1 QN
3. (∃x)~(~Ax v Bx) 2 CE
4. (∃x)(~~Ax ^ ~Bx) 3, DeM
5. (∃x)(Ax ^ ~Bx) 4 DN
B
1. ~(∃x)(Ax ^ Bx) P – Prove (x)(Ax→~Bx)
2. (x)~(Ax ^ Bx) 1 QN
3. (x)(~Ax v ~Bx) 2 DeM
4. (x)(~~A → ~Bx) 3 CE
5. (x)(A→~Bx) 4 DN
Existential Instantiation (EI)
If you remember our last past, you might have a guess about how this next rule is going to work. EG let us go from Dm to (∃x)Dx, so EI is probably going to let us go from (∃x)Dx to Dm. If that was your guess, you’re basically right, however, EI is going to have some additional restrictions on how it can be used. To understand the need for these restrictions, I will present the following example where I will INCORRECTLY use EI by treating it exactly the same way as UI.
Consider the following premises: Some numbers are odd. Some numbers are even.
Let us say that “Nx” is “x is a Number”, “Ox” is “x is Odd”, and “Ex” is “x is Even”. Observe the following argument:
1. (∃x)(Nx ^ Ox) P
2. (∃x)(Nx ^ Ex) P
3. Na ^ Oa 1 EI
4. Na ^ Ea 2 EI
5. Ea 4 simp
6. (Na ^ Oa) ^ Ea 3,5 conj
7. (∃x)[(Nx ^ Ox) ^ Ex] 6 EG
*Note: In this instance we haven’t defined what “a” is. That’s perfectly fine, we’re absolutely within our rights to just select an undefined letter and let it serve as a “stand-in”. For instance, we might say “There was some person who was the first to set foot in South America. Since we don’t know who this person was, let’s call them ‘Sam’.” In this instance “Sam” is our stand-in for whoever the actual first person was.
Returning to our above example: In seven lines I have taken two obviously true premises and concluded “There is at least one number that is both odd and even”, which we know at a glance to be false. So where did I go wrong? Line 4 seems to be the likely culprit. After all, on line 3 I established that “a” is my stand-in for an odd number, and then in line 4 I also tried to use “a” as my stand-in for an even number.
This brings us to our first restriction: Any letter used in EI must not have already been used at any previous point in the proof. So, for line 4, we would be unable to conclude “Na ^ Ea”, since we already used “a” on line 3. Instead, we would have to conclude “Nb ^ Eb”, selecting “b” as our stand-in for an even number.
If we introduce a letter via EI, we will need to “flag” it. Think of “flagging” a letter as something vaguely akin to making an Assumption. Just as – with an assumption – we are not saying “this thing is true” but merely saying “Let’s suppose that this is true and see where it would lead.” With flagging a letter we are not saying “the first person to set foot in South America was named Sam”, we’re merely saying “There was a first person to set foot in South America, let’s just call them Sam since we don’t know who they are.” So we flag the letter to indicate that it’s being used as a stand-in. Using our previous example of odd and even numbers the correct use of EI would be as follows:
1. (∃x)(Nx ^ Ox) P
2. (∃x)(Nx ^ Ex) P
3. Na ^ Oa 1 EI – Flag a
4. Na ^ Ea 2 EI – Flag b
One last note before moving on: Because EI requires you to use a letter that hasn’t been used previously, and UI has no such restrictions, if you have a proof that requires you to use both, it’s usually best to use EI first.
Universal Generalization (UG)
The last of our four inference rules will be Universal Generalization, which will allow us to go from a specific instance to a universal statement (so from “Ab” to “(x)Ax”). Similar to EI, UG will require use of flagging, and will need us to place a couple additional restrictions on flagging.I think the need for restrictions should be pretty obvious. While using EG to move from “Max is a dog” (Dm) to “There is at least one dog” (∃x)Dx is correct just on the face of it, using UG to move from “Max is a dog” to “Everything is a dog” (x)Dx, is blatantly incorrect even at first glance.
In order to use UG appropriately we need to make use of “flagging” letters, in order to create a “flagged subproof” (F.S.). As our example, consider the premises “All cats are mammals. All mammals are vertebrates. Therefore, all cats are vertebrates. We can symbolize this as:
1. (x)(Cx→Mx) P
2. (x)(Mx→Vx) P – prove (x)(Cx→Vx)
In order to begin a Flagged subproof, we pick a letter to serve as our stand-in. We need a letter to serve as a stand-in to ensure that our conclusion is truly universal. For instance, say that I don’t choose a stand-in. Instead, let’s say I pick my cat, J’zargo. I see that he’s a cat, that he is in fact a mammal, and that he’s clearly a vertebrate. But have I really proven that this is universal? Or have I just proven that this is true of my cat? In order to avoid possible confounds we pick a random stand-in. So for our next line we would use:
3. a F.S. (U.G.)
In this line we’re saying “so let’s just consider this hypothetical thing. We’ll call it ‘a’. What is ‘a’? We don’t really know, it’s just a thing.” Since we don’t know anything about “a” we don’t need to worry about pre-existing knowledge of it influencing our outcomes. So if we reach a conclusion using our flagged letter, we can conclude that it is actually universally true. From here we would complete the proof as follows:
4. Ca → Ma 1 U.I.
5. Ma → Va 2 U.I.
6. Ca → Va 4,5 H.S.
7. (x)(Cx→Vx) 3-6 U.G.
5. Ma → Va 2 U.I.
6. Ca → Va 4,5 H.S.
7. (x)(Cx→Vx) 3-6 U.G.
If you’re looking at this thinking “ok, so flagging really does work a whole lot like an Assumption.” Good! Keep that mindset. It will help keep our last two restrictions on flagging make sense:
Restriction 2: A flagged letter may not appear in either the premises or in the conclusion of a proof.
This prevents us from moving from “Earth has intelligent life” (Le) to “Everything has intelligent life” (x)(Lx), and also prevents us from moving from “Some planets have rings” (∃x)(Px ^ Rx) to “Earth is a planet with rings” (Pe ^ Re)
Restriction 3: A flagged letter may not appear outside the subproof in which it is flagged.
This is very similar to our restriction that – once we’ve discharged an assumption – we cannot use that assumption or any line that depends upon it ever again. Remember when we’re flagging a letter, we’re selecting it as a stand-in for the actual thing, NOT claiming to know what the actual thing is. We’re just using “Sam” as our stand-in for the first person to set foot in South America for purposes of the discussion. We’re NOT actually claiming to know anything about the actual first person to set foot in South America.
So, to restate our restrictions on EI and UG
1) A letter being flagged must be “new to the proof”. It may not appear anywhere in any step prior to the step in which you are flagging it.
2) A flagged letter may not appear in the premises or conclusions of a proof.
3) A flagged letter may not appear outside of the subproof in which it is flagged.
Ok, if you stuck with me through that, congrats, you now know every inference rule we’re going to cover! If your head is swimming and you’re not sure you’re following me… EI and UG are literally two of the most obnoxious rules in all of logic, and I typically make sure that I have my logic book in front of me every time I intend to use them in an argument just to make sure I’m not misusing them, because they suck. So cut yourself some slack. If you remember from a few posts back, we technically have one more replacement rule, which is “Categorical Quantifier Negation” but it’s really kind of “shortcut” rule, designed to make Quantifier Negation take fewer steps. So what I’m going to do is include that rule in the practice problems, and let you all prove it.
So that’s it. That’s all the rules. Next time will be some more-nuanced symbolization stuff which will probably take a couple posts to get through, and then that will be that.
Practice
As promised, todays practice is proving the Categorical Quantifier Negations. This is a grouping of four replacement rules. For each, we need to prove that they work both ways, so it’s technically eight proofs. (Remember, you’re not doing this for a grade. If you do one or two and feel like you have it, hey good on you.)A. ~(x)(Ax→Bx) P – Prove (∃x)(Ax ^ ~Bx)
B. ~(∃x)(Ax ^ Bx) P – Prove (x)(Ax→~Bx)
C. ~(x)(Ax→~Bx) P – Prove (∃x)(Ax ^ Bx)
D. ~(∃x)(Ax ^ ~Bx) P – Prove (x)(Ax→Bx)
E. (∃x)(Ax ^ ~Bx) P – Prove ~(x)(Ax→Bx)
F. (x)(Ax→~Bx) P – Prove ~(∃x)(Ax ^ Bx)
G. (∃x)(Ax ^ Bx) P – Prove ~(x)(Ax→~Bx)
H. (x)(Ax→Bx) P – Prove ~(∃x)(Ax ^ ~Bx)
Answers
I think that proving these two answers should be enough to help everyone figure out answers to the other 6.
1. ~(x)(Ax→Bx) P – Prove (∃x)(Ax ^ ~Bx)
2. (∃x)~(Ax→Bx) 1 QN
3. (∃x)~(~Ax v Bx) 2 CE
4. (∃x)(~~Ax ^ ~Bx) 3, DeM
5. (∃x)(Ax ^ ~Bx) 4 DN
B
1. ~(∃x)(Ax ^ Bx) P – Prove (x)(Ax→~Bx)
2. (x)~(Ax ^ Bx) 1 QN
3. (x)(~Ax v ~Bx) 2 DeM
4. (x)(~~A → ~Bx) 3 CE
5. (x)(A→~Bx) 4 DN
Comments
Post a Comment