Tutorial for Problem Set
In question 1 on problem set 4, we choose from the following four options the expression that is equivalent to this one. We must negate a universally quantified statement in which there is a conditional. Only one of these four answers is correct, so let’s look at the correct answer first. It is part C: the not for all becomes an existence and the negation goes into this part. When negating a conditional, you end up with its antecedent together with the negation of the consequent. And when negating a disjunction, the negations filter in and the disjunction becomes a conjunction. If you follow these patterns, then universals exist. You have the truth of the antecedence in place of an implication; in place of a conditional, you have a conjunction. When negating these guys, the negation applies to each one and that becomes a conjunction. Okay, but that being said, let us indicate: concentrate on why a behavior is occurring. Why does this give you px and not that? Why does negating this give you a conjunction there? It’s all about understanding. And if you simply learn to apply the rules, you really don’t have a useful skill. Computers are good at applying rules; humans can go much beyond that. Firstly, the first one is hopeless. There is no such thing as a situation like that. If you got that as your answer, either you were having a temporary aberration or you really don’t understand the issue very well at all. The next three could be wrong for different reasons. And those reasons were included because these are mistakes that people frequently make. In this case, you have negated the wrong part of the sentence: when you negate a conditional sentence, the negation should come before “if” not after it; so it’s just mixing up where the negation goes. But otherwise there’s no place where you could have gone wrong: You’re applying the right rule but you’ve missed out one step in applying it. In the case of (a), there was one mistake in the formula: the sign was incorrect. In cases (b), (d), and (e) there was just one thing wrong with each problem, which could have been caused by a slip of the hand or mind. It is important to keep in mind that what you write down on paper is not necessarily whatnyou think you are writing down. Furthermore, what you say may not be what younthink you are saying. Let’s move on to the second formula. The second formula reads: For every person P, there is a person Q such that P defeats Q in game T. In everyday English, we might say: Everybody beats someone in some game. That’s true, but it’s not the same as the sentence we’re looking for. This sentence says: For every player P, there is another player Q such that P always beats Q in game T. Note that this one doesn’t have an “every” word in it, so we can’t substitute an “every” word for the “for every” word here. There is a player who loses every game. If there were a formula that described this situation, it would include the following: For all players and all times, player p loses to player q in that game. However, one of the players will be q himself, so this formula does not quite work. If you wish to narrow the scope of your hypothesis, you should include clauses that denote the specific scope of inquiry. For example, if you are concerned with tennis games in which players win, then you can specify that fact by adding a conditional clause: “For all games of tennis in which players win, players win.” There will be similar issues when writing additional clauses; however, these can be addressed by comparing each new clause with existing ones. However, you would have the same issue. Among the questions is a possible solution. And you’d have to be careful to take account of the fact that the ‘t’ ranges over all possible games. And you only want to be making a statement about the games that we did play together. And you could have amended this by putting clauses in. There are various ways out of that. Which (one) of the following is equivalent to neg forall x [P(x) Rightarrow (Q(x) lor R(x))]? (a) exists x [P(x) lor neg Q(x) lor neg R(x)] (b) exists x [P(x) wedge Q(x) wedge R(x)] (c) exists x [P(x) wedge neg Q(x)wedge neg R(x)] True (d) exists x [P(x) wedge (neg Q(x) lor neg R(x))] (e) exists x [P(x) lor (neg Q(x) wedge neg R(x))] Let p, q be variables denoting tennis players, let t be a variable denoting games of tennis, and let W (p,q, t) mean that p plays against q in game t and wins. Which of the following claims about tennis players mean the same as the symbolic formula forall p exists p exists t W (p,g,t)? Select all that have that meaning. (a) Everyone wins a game True (b) Everyone loses a game (c) For every player there is another player they beat all the time (d) There is a player who loses every game exists q forall p forall t W(p,q,t) (e) There is a player who wins every game exists p forall q forall t W(p,q,t) Let’s move on to number three. But this time there is a deliberate mistake to emphasize the issue that will come up later. Go through these three and look at answers to all of them, but one of them will be a wrong answer, and then we’ll correct it. So this one—actually if you remember from earlier—is the one that we saw before. That means everyone wins the game! For each player p, there is a time t such that p beats q at time t. The statement “Everyone beats everyone else at some time in some game” is equivalent to saying that for every pair of players p and q, there is a time t such that p beats q at time t. And this one, it is essentially well, actually, what is the difference? That one says for all p, there exists a q. This one says for all q, there exists a p. So these aren’t mutually exclusive statements. One of these must be possibly true and the other possibly false. Let’s see which one works out. We’re talking about everyone winning or losing a game here. Let’s correct the typo – which one cannot possibly be true. Well, that could possibly be true, everyone beats everyone else all the time. Everyone loses a game – that’s certainly possible, that’s okay. Coming to this one, can this be true? We’re talking about the real world here when people are playing tennis; however it doesn’t have to be one of these things or none of these things can be true if you prefer that option. In fact, if you got this far, you probably did say that they are all okay. But actually this one is not. Because, when you say for all p and for all q that includes the case of q and p being equal. That would mean everybody has to beat themselves at some time amongst everything else. So a player cannot beat every other player. To make that statement true, you would have to say: “If p and q are different, there is a t so it should not w.” But if p beats q in a game, then it follows that t is true. So this statement is not possible. In the real world, players cannot beat themselves. So the issue was whether one could take formal systems like those in set theory and correctly tie them into what they say about the real world. Let p, q be variables denoting the tennis players in a club, let t be a variable denoting the club’s games of tennis, and let W(p, q, t) mean that p plays against q in game t and wins. Assuming that there are at least two tennis players and games between them do take place, which (if any) of the following symbolic formula cannot possibly be true? Select all you think cannot possible be true. (a) forall p exists q exists t W(p,q,t) Everyone wins a game (b) forall p forall q exists t W(p,q,t) Everyone beats every else at some time (c) forall q exists p exists t W(p,q,t) Everyone loses again Let’s move on to question four. Okay, now this expression is a colloquial expression:”to be a lover.” What I did was give you options that you should be able to distinguish between simply by doing the logical structure. The reason I like to give these kinds of examples is because they capture an awful lot of social and cultural knowledge, and there’s an interesting challenge in capturing that kind of thing in formalisms. But to help you there are three options so that if you know what being a lover means in this case, then you’ll be able to sort out just on the basis of logic which one it is. A lover is someone in a mutual relationship. If you look at this one, it says that person x is in love with everybody else. So, if you see this part: L love, x loves z and z loves x. That means person X is in a loving relationship with everybody else. That doesn’t make sense, so we can forget that one. So it comes down to these two; both of those say that person x is in a loving relationship with some z, and that relationship is mutual—x loves z and z loves x. The same clause here. So it is between a and c. Well, let’s look at what a says. It says if x is in a loving relationship, then y loves x. Now the y doesn’t come in here so this part has to do with this part. So it says take any person x, if that person is a lover, then every person loves them, if they know them, so that actually is the correct one. All people love a lover of these three; that’s the one. You know you could argue about whether that’s the absolute best interpretation but out of these three it’s certainly a correct one and so it’s the one here. Let’s look at this one. This one is a little bit different because it’s got for ally in here. So, it says for all x, if x is a lover, then it doesn’t say then, it says and for all y, L, y, x. So the for all actually applies to this part as well. So what this really means is that for all x and for all y, if x is a lover or if y is a lover then x loves y. In other words, everybody loves everybody. Well that’s not the case because this isn’t conditional on being a lover. This just really says that’s the case and that’s the case. The statement for all x, if x is a lover then L(x) does not hold. So this means that for all y, if y is a lover then L(y) does not hold. In other words, everybody loves everybody. This is not the case because this is not conditional on being a lover. This just says that it’s true and it’s true. For all values of x, for all values of y and z, if x is less than or equal to y and y is less than or equal to z, then x is less than or equal to z. This is known as the transitivity of the order relationship. If x is to the left of y and y is to the left of z, then x is to the left of z. All three statements are true. For all x, there is a y such that for all z, if z is less than or equal to y and y is less than or equal to z, then z is equal to x. This statement is true because if x is less than or equal to y and y is less than or equal to x then they must be equal. What about part c? For all x, if x equals y then x is less than or equal to y or y is less than or equal to x. It’s certainly true because given the case of x equaling y, you have the situation where you can substitute that into this equation here and see that it holds: if x equals y then z will be less than or equal to y or y will be less than or equal to z — which makes sense because it must hold true in any case where the original statement holds true. It’s beginning to look like they’re all true. Let’s look at the last part. There exists an x such that for every possible value of y, if y is less than or equal to x, then we also have x less than or equal to y. You might be tempted to think that every y is either less than or bigger than every x. But wait a minute: If there were an x that had that property, then among the y’s, when you universalize them with a quantifier, you would have x itself. But this would mean that you had x smaller than itself—which is impossible. And so this sentence is false because any sentence involving universal quantifiers must include the thing that we are universalizing over and so it doesn’t work because it ends up including itself in its own predicate. Which of the following means “Everybody loves a lover”, where L(x, y) means (person) x loves (person) y and a lover is defined to be someone in a mutual loving relationship? (a) forall x forall y [exists z (L(x,z) wedge L(z,x)) Rightarrow L(y,x)] ✓ (b) forall x forall y [forall z (L(x,z) lor L(z,x)) Rightarrow L(y,x)] (c) forall x [exists z (L(x,z) wedge L(z,x)) wedge L(y,x)] X Which of the following statements about the order relation on the real line is/are false? (a) forall x forall y forall z [(x≤y) wedge (y≤z) Rightarrow (x≤z)] TRUE Transitivity of ≤ (b) forall x forall y [(x≤y) wedge (y≤x) Rightarrow (x=y)] TRUE (c) forall x exists y [(x≤y) wedge (y≤x)] TRUE (d) exists x forall y [(y<x) lor (x<y)] FALSE For the last question on problem set four, suppose N is divisible by p. It has already been stated that N is an integer and it does not matter whether it is positive or negative. It has also been said that p is a prime. The next step is to find q, an integer such that N + 1 = pq. This can be seen by dividing q by p to get N + 1 over p. Assume that N+1 is divisible by P, and then show that there exists an integer R such that N+1=PR. If we subtract N from both sides of this equation, we are left with PR-PQ=P(R-Q). Since N+1-N=1, we know that P(R-Q)=1. But since P is prime, it must be greater than two (since any number greater than one and smaller than another whole number can only divide into itself or into 1). So, there is a contradiction: P cannot equal one, since it does not divide into 1; yet it cannot equal two or more because it is prime. This contradiction shows that the assumption made at the beginning of the argument–that N+1 is divisible by P–was false. Hence, the original assumption here was false. Hence N plus 1 is not divisible by P. Notice that this is almost the same, in a sense this is equivalent to this. It’s not the same as this, but it’s equivalent, because the R here is N plus 1 over P. So this is the R. In the course of this discussion, we will be using addition, subtraction, and multiplication operations. It is important to note that no division operation is used in this example; instead, we introduce a new symbol called R, which is equal to one divided by x. This work around allows us to solve for x without having to use division. It is important to note that this substitution is not possible with all numbers; however, it can be used on those numbers where divisibility holds true.
