2

Firstly, excuse my simplicity in describing the title; I couldn't find a proper title that could explain what I am confused about. The example looks at how we express the following statements in predicates and quantifiers,

  • “Every student in this class has visited Mexico”
  • “Some student in this class has visited Mexico”

The first statement is fairly easy. If we take $x$ as the domain of people, $S(x)=$ '$\text{x is a student}$', and $M(x)=$ '$\text{x visited Mexico}$'. We have $\forall x(S(x) \rightarrow M(x))$. Its clear that it wouldn't work if we had it like this $\forall x(S(x) \land M(x))$. Because that would mean that all the domain of $x$ is $S(x)$ but that isn't true.

Now, the confusion comes when we the second statement comes in. The answer is $\exists x(S(x) \land M(x))$ but I don't see how this representation $\exists x(S(x) \rightarrow M(x))$ can be wrong.

John
  • 1,149
  • $S(x)\rightarrow M(x)$ is also fulfilled for all people who aren't students. – Alex R. Feb 02 '14 at 14:31
  • @AlexR. Then wouldn't that mean that for the first statement that the same idea("fulfilled for all people who aren't students") also applies? Thus making the first representation also inaccurate. – John Feb 02 '14 at 14:32
  • yes, but we don't care what the other people are doing, as long as all students have visited Mexico. $P\rightarrow Q$ only has the truth value false, if $P = true$ and $Q=false$. – Alex R. Feb 02 '14 at 14:34
  • @AlexR. I don't see how we can ignore the non-students in the first one but we don't in the second. Naturally, if we don't talk about the non-students we shouldn't worry about them. The statement doesn't say that the non-student haven't traveled to mexico. In fact, it is very likely that more than one non-student has indeed traveled to mexico. – John Feb 02 '14 at 14:37
  • Because the implication is automatically true for all non-students, so there always exist people who fulfill $S(x)\rightarrow M(x)$ even though they are not students. The first statement, however, is asking for $S(x)\rightarrow M(x)$ to be fulfilled for all people. You could also see $\forall$ as logical AND, and $\exists$ as logical OR. – Alex R. Feb 02 '14 at 14:44
  • @AlexR. I don't think what you said answers my question. Even for the existential statement one should expect it to be automatically true for non-students. Its no different. The difference is that the first one says that all the students traveled to mexico and the latter at least one student traveled to mexico. – John Feb 02 '14 at 14:54
  • Surely the latter is not supposed to come out true if nobody is a student and nobody has ever visited Mexico, right? – Malice Vidrine Feb 02 '14 at 14:57
  • @MaliceVidrine Applying the same thought to the former? – John Feb 02 '14 at 15:01
  • In the case of $\forall x(\neg S(x) \wedge\neg M(x))$, the former logically follows. You would not want $\forall x(S(x)\wedge M(x))$, since my friend's infant daughter is not a student that has visited Mexico. – Malice Vidrine Feb 02 '14 at 15:05
  • @MaliceVidrine As I said in the question its clear why the $\forall x(S(x)\wedge M(x))$ is not true for the first statement. – John Feb 02 '14 at 15:12
  • Yes, you did; which is why I found it puzzling that you asked to apply that reasoning to the former case. The idea I'm trying to get at is that you need to consider what happens if you change out the truth function operators. A conditional is clearly not what you mean in the latter case, just as conjunction or straight alternation is not what you mean in the former. – Malice Vidrine Feb 02 '14 at 15:21
  • @MaliceVidrine While I understand what you mean in logical argumentation, the way it is written $\exists x (S(x) \to M(x))$ translates to: there exists an x which satisfies that following property-if x is a student then he has traveled to Mexico. And this is what the latter statement is saying that in the domain of all students there is one or more students who have traveled to mexico. – John Feb 02 '14 at 15:26
  • But the formulation with a conditional does not say that at least one student has travelled to Mexico, since it can be true when nobody has traveled to Mexico at all. The English statement is claiming that someone has gone to Mexico, so you don't want a statement that's true if no one has. – Malice Vidrine Feb 02 '14 at 15:31
  • @MaliceVidrine Aha, I think found the problem. The problem happens when $S(x)$ is true and $M(x)$ is false. This means that the whole implication is false which contradicts the initial statement--which insures that not all of the students have traveled to mexico. And with the implication being false it suggests that there can't exist a student who hasn't traveled to mexico. But that does not follow from the initial statement. Correct? – John Feb 02 '14 at 15:34
  • I'm not sure I follow the exact thread of your reasoning there, but the idea is "there isn't a student that's gone to Mexico" should not imply that everyone is a student and nobody's gone to Mexico; similarly "no human has gone to Mars" shouldn't imply either that everything is human or that nothing's been on Mars. But this is exactly what $\neg\exists x(S(x)\to M(x))$ says. – Malice Vidrine Feb 02 '14 at 15:49
  • @MaliceVidrine I am saying that when $S(x)$ is true i.e. x is a student and $M(x)$ is false, x hasn't traveled to mexico, then the total implication is false($T\to F = F$). So, that would imply that a student has to travel to mexico for the implication to be true. But,would it mean that all students had to have traveled to mexico? – John Feb 02 '14 at 15:57
  • @MaliceVidrine What I just said doesn't say why it is wrong. Because if we took the accepted answer $\exists x(S(x) \land M(x))$, $T \land F$ give $F$. I am officially confused about this when I look at it in isolation.... – John Feb 02 '14 at 16:12
  • I don't know how else to point out the issue; I've already pointed out that $\exists x(S(x)\to M(x))$ is going to be true under circumstances that $\exists x(S(x)\wedge M(x))$ is not, and that some of those circumstances are not what you mean. – Malice Vidrine Feb 02 '14 at 16:27
  • @MaliceVidrine The circumstances for which they conflict are about non-students that the statement doesn't talk about. My book says this: Our statement cannot be expressed as $\exists x(S(x) → M(x))$, which is true when there is someone not in the class because, in that case, for such a person x, $S(x) → M(x)$ becomes either $F→T$ or $F→F$, both of which are true. – John Feb 02 '14 at 16:31
  • Let's say I told you I wasn't a student; could you logically conclude from that that a student had visited Mexico from just that information? Because you could conclude $\exists x(S(x)\to M(x))$ from that. – Malice Vidrine Feb 02 '14 at 16:34
  • @MaliceVidrine Nope you can't, but can you also conclude that from this $ \forall x(S(x) \rightarrow M(x))$. If the answer was no, then all my problems would be solved. I hate memorizing things and not understanding them. If I take this the way it is now, then I feel I will hate discrete math. – John Feb 02 '14 at 16:36
  • Actually no. If I told you I was not a student you absolutely could not infer $\forall x (S(x)\to M(x))$. That follows from no logical principle. – Malice Vidrine Feb 02 '14 at 16:42
  • @MaliceVidrine How does the truth value of the implication affect the whole statement as a whole. For example, if your not a student i.e. S(x) is false then the implication is always true. What does that mean? – John Feb 02 '14 at 16:45
  • 1
    You can't look at the implication alone; you have to look at the quantifiers, and you need to understand what a quantifier says about the domain of the theory; because quantifiers are fundamentally about domains, not individual entities. – Malice Vidrine Feb 02 '14 at 16:53
  • 1
    @MaliceVidrine I think I got it. Thanks for answering all my questions :) – John Feb 02 '14 at 16:58

2 Answers2

2

Your confusion probably lies in that you haven't clear what you're supposed to do. You want to express some facts:

  1. Every student in the class has visited Mexico
  2. At least one student in the class has visited Mexico

At this stage you're not asking if either is true or false. You just want a formal statement that expresses those facts.

Consider the truth table for $\to$: $$ \begin{array}{cc|c} A&B& A\to B \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array} $$ Thus the statement $\exists x(S(x)\to M(x))$ is true if there's an individual in your domain who's not a student and either visited Mexico or not. Therefore, as soon as there's a non student, the statement is true.

You can also see it by substituting $\exists x$ with $\lnot\forall x\lnot$ and $S(x)\to M(x)$ by $\lnot S(x)\lor M(x)$: \begin{gather} \exists x(S(x)\to M(x))\\ \lnot\forall x\lnot(\lnot S(x)\lor M(x))\\ \lnot\forall x(\lnot\lnot S(x)\land \lnot M(x))\\ \lnot\forall x(S(x)\land \lnot M(x)) \end{gather} Thus the initial statement is false if and only if $$ \forall x(S(x)\land \lnot M(x)) $$ is true, that is, every individual is a student and no individual has visited Mexico.

Look at the truth table for $\land$, instead: $$ \begin{array}{cc|c} A&B& A\land B \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \end{array} $$ Now all should be clear: the statement is true if and only if you have $S(x)$ and $M(x)$ true for the same individual.

egreg
  • 238,574
  • $\exists x(S(x)\to M(x))$ is also true when both are true which is what is required, i.e. there exists an x for which(which satifies the property) if x is a student then he has traveled to mexico. – John Feb 02 '14 at 15:17
  • @John But it can be true also in other cases, for instance for me: I am not a student and I've never visited Mexico. So the statement is true even if no student has ever visited Mexico. – egreg Feb 02 '14 at 15:18
  • Then, if we look at the first one $\forall (S(x)\to M(x))$. How would this play if $S(x)$ is false. Isn't it always true? In other terms, it also implies that there is a non-student who has traveled to mexico and there is a non-student who has not traveled to mexico. – John Feb 02 '14 at 15:20
  • @John No, why should it be? It is false precisely when (at least) one of the students has never visited Mexico. – egreg Feb 02 '14 at 15:21
  • $F \to T $ is $T$ and $ F \to F$ is also true. – John Feb 02 '14 at 15:22
  • @John So what? There can certainly be nonstudents who have visited Mexico. You want to express that all students visited Mexico and you don't care about other people. – egreg Feb 02 '14 at 15:25
  • Similarly, why should I care about the non-students in the latter case. – John Feb 02 '14 at 15:27
  • You need to care about the non-students because it needs to follow that not everyone is a non-student. This doesn't logically follow from $\exists x(S(x)\to M(x))$. – Malice Vidrine Feb 02 '14 at 15:33
  • I helped a guy do a proof in diff. eq. once without ever taking the class, and this still hurts me to think about. – Mr. Minty Fresh Sep 26 '19 at 07:59
1

Maybe look at the negation of the second sentence, which would be:

None of the students has visited Mexico

or:

Every student in this class has not visited Mexico

So you would translate it as $$ \forall x(S(x)\to\neg M(x))$$ or equivalently $$ \forall x(\neg(S(x)\land M(x))$$ Something that's wrong for all must be true for some, i.e. $\forall x\neg\Phi$ is the same as $\exists x \Phi$. So we indeed arrive at $$ \exists x(S(x)\land M(x)).$$

Hagen von Eitzen
  • 374,180
  • Your explanation is well thought of. I am convinced because I accept the first one and not the latter so if we proved the latter from the first...it would solve the problem. But, I can't help but feel ignorant if I don't look at the second one. – John Feb 02 '14 at 16:00
  • You mean $\neg\exists\Phi$, yes? Or $\neg\forall\neg\Phi$? – Malice Vidrine Feb 02 '14 at 16:01