0
$\begingroup$

In the book

Discrete Mathematics and Its Applications by Kenneth H. Rosen, page 77

appears this example.

Example 13: Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book.” Solution: Let C(x) be “x is in this class,” B(x) be “x has read the book,” and P (x) be “x passed the first exam.” The premises are ∃x(C(x) ∧ ¬B(x)) and ∀x(C(x) → P (x)). The conclusion is ∃x(P (x) ∧ ¬B(x)). These steps can be used to establish the conclusion from the premises.

example

There, the application of Existential Instantiation uses variable a and the usage of Universal Instantiation uses that same variable.

From (1), I can conclude $C(a) \wedge \neg B(a)$ is true for some a and from (4) I can conclude $C(a) \implies P(a)$ is true for any a ?

Are both variables conceptually different? i.e how can I know the second a is talking about the same object as the first a.

Any clarifications are very welcomed.

$\endgroup$
  • $\begingroup$ The term "existential instantiation" is bad/misleading. It is presumably chosen to parallel "universal instantiation", but, seeing as they are dual, these rules are doing conceptually different things. (Similarly for "existential generalization".) I prefer the "introduction/elimination" terminology, but that doesn't really indicate what's going on and is just based on where the connective is in the rule. Something like "existential packing/unpacking" would be more descriptive. $\endgroup$ – Derek Elkins Jun 9 at 20:53
1
$\begingroup$

As this is a real life example, let's use names.

From the first premise, we do not really know the name of the lazy student, it could be Jack or Jill or Sam or Kim or ... We don't know who it is so let's introduce a nickname Bludger. So we know

Bludger is in the class and did not read the book.

This is the existential instantiation.

From the second premise, we could infer "If Jack is in the class, then Jack passed the exam" as well as "If Jill is in the class, then Jill passed the exam", or even "If Abraham Lincoln is in the class, then Abraham Lincoln passed the exam" or "If my favourite unicorn is in the class, then my favourite iunicorn passed the exam". And of course we can also instantiate

If Bludger is in the class, then Bludger passed the exam.

$\endgroup$
1
$\begingroup$

From (1), I can conclude $C(a) \wedge \neg B(a)$ is true for some a and from (4) I can conclude $C(a) \implies P(a)$ is true for any a ?

This is almost correct except that it is not $C(a) \wedge \neg B(a)$ for some $a$ but $C(x) \wedge \neg B(x)$ is true for some $x$ ($a$ is a specific variable that makes that statement true). When this is the case, you can use a variable that is not occuring anywhere else, in this case it can become $a$. The reason why we need to have a variable that did not occur anywhere is that (1) is an assumption with $\exists$ here.

Also for the $C(a) \implies P(a)$ is true for any $a$ part, it should be $C(x) \implies P(x)$ for any $x$ and this time, we actually use the same $a$ intentionally since this is again an assumption with $\forall$ and this time, there is no restriction on the variable that we can use, and on further steps, this makes it possible for us to prove the conclusion (MP on (6) reaching us the conclusion depends on using the same $a$ in (3) and (5)).

$\endgroup$
0
$\begingroup$

When we say something such as $$\exists x \colon A(x)$$we want to say at least one object in our discourse universe makes $A$ true. Does how it is denotated matter? No. We mention it, we know it exists but we do not know who/what it is. So let us give to that object a name in order to remember and to recall it when we need: we can call it $a$ for example. When we claim that$$\forall x \colon A(x)$$we mean that every object in our discourse universe satisfies the property $A$, that is in particular $A(a)$ is true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.