Introduction to Mathematical Thinking. Tutorial for Assignment
A: There is a natural number solution to the equation x cubed equals 27. ( exists x in N ) [ x^3 =27] B: A million is not the largest natural number. There is an x in n such that x is greaterthan a million. ( exists x in N ) [ x > 1 000 000 ] C: The natural numbers are not all prime; there is a natural number p such that p > 1,and another natural number q such that q > 1, and n = pq. So there are natural numbers pq both of them greater than 1 such that n is their product. ( exists p in N ) ( exists q in N ) [p > 1 wedge q > 1 wedge n =pq] Part A: In mathematics, relationships are expressed in a certain order of precedence, whichis why it’s important to read formulas left to right. See how the formula ” p in q “(where p is greater than one and q is greater than one) became the variable n ?That’s because we must read things left to right, so we start with “there’s a p in n”and finish with “there’s a q in n”. The equation x q = 28 cannot be solved using natural numbers. neg (exists x in N) [x^3 =28] The most obvious way of expressing this is to say that there is no natural number xthat satisfies the equation. Whereas to give an assertion in its canonical form is toexpress it in the form of a universal statement with an “all” quantifier at the beginning. To say that for all x in N, it’s not the case that x cubed equals 28, write inthis familiar fashion x cubed is not equal to 28. (forall x in N) [x^3 =28] The last part does not hold for x = 28. (forall x in N) > [x^3 =28] According to the statement, every natural number fails to be a solution. We can infer that zero is less than every natural number because zero is a member of these quence of integers, which begins with one and ends with infinity. N=1, {2,3…} Historically, the number zero was an unnatural number. In fact, originally, a zero symbol was merely a circle that signified that there was nothing there, and a placeholder was needed to denote that nothing existed in certain places when””performing calculations. This practice became common in India around 600 B.C.Today it is known that the number zero is less than every natural number. (forall x in N) > [0 < x] The statement “zero is less than every natural number” may be captured concisely as “for all natural numbers x, x is greater than zero. [x > 0] There are several ways to express the statement that the natural number n is prime.The most important formula, however, is the one that captures the idea that it is not divisible by any other natural number besides one and itself. ( forall p in N ) ( forall q in N ) (n=pq) rightarrow (p=1 lor q=1) To say that a natural number, n, is prime requires one to first negate the universal quantifier statement. That is, if all possible factors were not equal to one of the natural numbers itself, then it would be prime. The only way that two numbers can be equal to each other is if they are both 1. Therefore, because there are no numbers that are multiplied by themselves (that is, the number 1), we can see that all possible factors of a number must be equal to 1. Therefore, if one of these factors is not equal to one, there is an error in the factorization somewhere. For every person x, there is a corresponding person y. So it’s just that x loves y. (forall x) ( exists y) L (x.y) For every pair of individuals, there is a pair they love. The individuals they love will depend on the pair you start with. These individuals need not be the same for any two different starting pairs. Thus x loves y only if x and y are different people. Some forum participants misunderstood this point and were able to see the problem with this statement only after it was explained; this shows that students need to learn how quantifiers work before they can understand why ordering is important. Part B: (forall x) [ Tall (x) lor Shot (x) ] For every person X, either X is tall or X is short. Everyone is one or the other. This is an example of an inclusive or, but of course, the properties themselves will make this a disjoint. You want to have someone that is both tall and short although in real lifetall and short will have an overlap you know there comes a point where is someone taller? Is someone short? So interpreting these is a matter of interpretation. Theheight—this is a clear answer. The point is, things like this become ambiguous when one considers that “tall” can mean different things. By writing something like this, wehave forced it to be precise. That is the whole point of what we are trying to do. This precision is not necessarily the same precision that exists in the real world, but it is an interpretation with in mathematics of something in the real world. Part C: (forall x) Tall (x) lor Shot (x) The statement “every person is tall” is equivalent to the statement “there exists at least one person who is tall”. The statement “everyone is short” is equivalent to the statement “all people are short”, which can be rewritten as “for every x, if x is aperson then x is short”. These brackets, which bind everything inside them, are very tight. This means that you have to use parentheses if you want to use a quantifier that binds everything like we did here. So in order to make this piece of text bindthese two words you would need to include a set of parentheses after “these”. Weuse the word “binds” to describe quantifiers. That means it governs the xs in there.And the, this, the, the formal terminology of that is “binds.” And so, in the binding rules quantifiers bind everything that comes next to them, and if you want them to bind a disjunction, you have to put them in parentheses. So that has to become a unit to be bound through all, same would be true for exists. In this case, you don’t need parentheses because all you’ve got is one predicate (tall x) , so you’ve got for all x tall x or for all x short x. You might ask yourself if you need parentheses here, and the answer to you in no. Generally, the rule for parentheses is you put them in when you need them to disambiguate, but because this is the firs ttime we’re running through these. Though these statements seem different, they are both true. This statement is talking about something that is highly unlikely to be true in most societies. This statement is certainly true if we’re prepared to say where the tall and short people change at some point. Part D: (forall x) neg At – home (x) Some people might have read the sentence “For every person x, x is not at home “as a universal quantification, that is, as a statement that applies to all cases. neg (exists x) At – home (x) It depends on how you interpret these sentences. You could say that the most natural way of translating this sentence is as a universal quantification: “There is noone at home.” Or, you could say that it is better rendered as an existential quantification: “There is no person who’s home.” Both renderings are correct. (forall x) neg At – home (x) Leftrightarrow neg exists x ( ) At – home (x) As we’ve seen, these two assertions are equivalent. It’s just a matter of choice as to which you think more accurately reflects the nuances of the English language. Part E: Comes (John) rightarrow (forall x) [Woman x ( ) rightarrow Leaves x ( ) ] If John comes, then all the women will leave. This is an if statement, and then there’s a conclusion. And the antecedent of that if statement is John coming. So we’ve got John coming; there’s a consequence here: all the women leave. Our variable x ranges over people so we have to say for every x if x is a woman then x leaves. So that’s our way of saying all women leave. For all x if x is a woman then x leaves. Part F: (exists x) [ Man (x) wedge Comes (x) ] rightarrow (forall x) [Woman x ( ) rightarrow Leaves x ( ) ] In this case, it’s not a single person John, it’s any old man, so we’ll have to say if there is an x who is a man and who comes, then every woman leaves. This is the same as the previous thing but instead of saying John comes, I’m saying there is an x who is a man and who comes. vNotice that number 4 is merely about expressing the statement formally, in this case using quantifiers that range over the set of reels and the natural numbers. The equation x2 + a = 0 has at least one real root for any number a, for any real number a. (forall a in R) (exists x in R) [x^2 + a =0] For all real numbers a, there is a real number x that satisfies the equation. For any real number a, this is a universal quantifier; in other words, it’s a quantifier that applies to all real numbers. Even though that comes at the end of the sentence, which is fine in English, mathematicians find it amusing. However, its placement causes confusion for mathematicians when they read it because it causes them to wonder why we use a quantifier that applies to all real numbers. For some values of a, you will not get an x as we know it. For instance, if a is negative, then this statement is true. However, if you take the negative a’s, the x that solves it depends on the value of a. So you have to have an a before you can find the x. One way of reading this is to say that if you give any value for a and we will find an x depending on the value of a that solves this equation. Quantifying the order of the expression is crucial to solving this problem. Part b actually brings it to the previous one, but except we’re really talking about any negative real number and this is actually going to be true. So there’s a quantifier for any real number and we’re going to capture that as follows, we’ve got the set of real numbers so we have to say for all real numbers a, if it’s the case that a is negative then there is an x that satisfies the equation. For any real number a, if it happens that a is negative, then there is an x which solves the equation. In mathematics, it is critical to be precise. The order of mathematical symbols is used to convey meaning: a comes before x because the a determines (or is necessary for) the value of x. Okay, part c, every real number is rational, so, every real number x. (forall x in R) (exists m in N) (exists n in N) [m = nx lor m = – nx lor x – 0 What we’re trying to say is that, for every statement, there is an equivalent statement that is true or false. For example, this one is false and this one is true. The point is that you can express things in mathematics precisely whether they’re true or false; and sometimes you have to express them formally in order to determine whether they’re true or false. However, it’s a separate issue from whether they’re true or false in itself; truthfulness or falsity is a separate issue from whether you can express it formally. Every real number can be expressed as the quotient of two integers. This is true because every real number can be written as the ratio of two integers, or it can be written as the difference between two integers, or it can be 0. In the natural numbers, there are two operations—addition and multiplication. The property of divisibility also exists in the natural numbers, but division is not always possible. Since m and n can be written by themselves without involving division, it is an elegant way to avoid writing m/n. There is a formula that expresses the relationship between x and m and n in terms of the order of the quantifiers. If you know the values of those three variables, you can solve for the remaining ones. However, if a negation sign is placed before part c, then this formula does not work. (existsx in R) (forall m in N) (forall n in N) [m ne nx lor m ne – nx ] There is a rational number (a number that can be expressed as the ratio of two integers) which satisfies the following property: for all pairs of natural numbers m and n, m divided by n is not equal to x and negative m divides n is not equal to x.Previously, we had this junction because we were talking about a positive thing.There is an x in R. This will be the irrational number we are assuming exists.With the property that for all m in N, m does not equal x nor does m equal negative x. M divided by n is not equal to x and–m divided by n is not equal to x. (forall y in R) (exists x in R) [ (x > y) wedge (forall m in N) (forall n in N) (m ne nx)] There are two ways to define irrational numbers. One way is to say that for all real numbers R, for all real numbers y, there exists a real number z which is not equal to the quotient m/n. And if you’re trying to say that there’s no allowed irrational number, you’re really going up into the positive range. So what happens on the left of zero on the real line is irrelevant. Thus, we do not need to consider negative numbers because we are considering all real numbers. However, we should note that there is no largest real number; every real number can be divided into a positive part and a negative part. Real numbers are what mathematicians call “algebraic”, which means they can be manipulated with addition and multiplication but not subtraction or division. However, it’s fair to say that this is really a statement about just the irrational numbers. Given any irrational number, there is always an even bigger irrational number. Once we get into the realm of real numbers, it gets extremely complicated because you have to say, given any real number r , if that number is irrational then there is an even bigger irrational number. (forall y in R) (exists m in N) (forall n in N) (m ne ny) rightarrow (exists x in R) [ (x > y) wedge (forall m in N) (forall n in N) (m ne nx)]] There are two ways to interpret the sentence, “There is an irrational number bigger than every real number.” One way is as a general statement about irrational numbers. The other way is as a specific statement about all the rational numbers and all the irrational numbers combined. If we interpret it as the latter, then it is equivalent to saying that every real number has an irrational number bigger than it—and this statement is true. Once we have a formal description, it is unambiguous. As long as we express it correctly, it is not ambiguous. It has exactly one interpretation. This has several interpretations. I mean, here are two different ones. They’re equivalent. They’re obviously equivalent, for very obvious reasons. But we’ve cashed them out in different ways. Well question five is our old friend about domestic cars and fallen cars so C is a set of all cars, Dx means x is domestic, Mx means x is badly made. (forall x in C) [D (x) rightarrow M (x) ] If a car is domestic, then it is badly made. All foreign cars are badly made, but we do not have a predicate for foreign so we must take it to mean “not domestic”. In this case, we replace C by negative C and then we get: For all x and if x is not domestic then it is badly made. (forall x in C) [neg D (x) rightarrow M (x) ] And by negating the quantifier in this way, we are able to use the fact that negation binds very tightly. This enables us to apply the quantified statement to whatever follows it. Once you understand how this works, you should be able to follow these kinds of statements more easily. Part C: All badly made cars are domestic. (forall x in C) [M (x) rightarrow D (x) ] For all cars, if the car is badly made, then it’s domestic. This statement is ambiguous and can be understood in several ways. However, there is at least one case in which it is not the case that a car is domestic and badly made. (exists x in C) [D (x) wedge neg M x ( ) ] There is a car called the x, which is domestic and not badly made. When making comparisons between universal and existential quantifiers, we typically compare an implication or a conjunction with an existential quantifier. When making comparisons between a universal quantifier and a conditional, we typically compare a conjunction with a universal quantifier. In order to do this successfully, it’s important to understand what these phrases mean rather than relying on symbolic rules. (exists x in C) [D (x) wedge M x ( ) ] Question six concerns the same kind of concepts we’ve already looked at in earlier questions, including whether certain things are rational or ordered in a set and where they fall on the list of largest rational numbers. However, we’re dealing with different restrictions this time. We are asked to use quantifiers for real numbers. We do have a symbol q of x, meaning x is rational. So we’re going to get a different expression. The focus on what we are trying to make precise has been put elsewhere. We don’t have to talk about things being in reality or whatever because that’s all we’ve got. forall x forall y [ (x <y ) rightarrow exists Z ( Q (z) wedge x (<z <y ))] Now we do have a bracket here because there are many things that follow that depend on x and y. So for all pairs of real numbers x and y with x less than y, there is a z which is rational and lies between them. Reading left to right, for all pairs of real numbers x and y with x less than y, there is a z which is rational and lies between them. Now we didn’t write “exists” or “there exists,” because Q isn’t a set. In this case we have an implication (which means x is rational). Sometimes we have sets, sometimes we have predicates. Sometimes we use quantifiers. Sometimes we use predicate quantifiers. They are all different ways of getting formality and precision into statements. exists t forall p F (p, t) wedge exists p forall t F (p, t) wedge neg forall p forall t F (p, t) Number seven, which is attributed to Abraham Lincoln, is this famous quotation: “You can fool all of the people some of the time; you can even fool some of the people all of the time. But you cannot fool all of the people all of the time. But in mathematics we read strictly left to right, and so the quantifiers must come first. So let’s say f, x, t means you can fool a person Woops. P that should have been a P shouldn’t it. Then let me just change that now. Okay. Alright Fpt meaning you can fool person p at time t. Then let’s do these one by one. You may fool all of the people some of the time. That means there are some times when you can fool all of the people, there are some times when you can’t fool any of them. There are some times when you can fool all of the people—the point is taking this clause, “you may fool all of the people some of the time,” and then putting a comma before “there are times.” The point is that we’re making an argument about this clause and how it relates to other clauses—there’s a comma here because this is not part of our main clause; this is part of a sub-clause or an explanation for our main clause—there are times when you can’t fool any of them: there were sometimes when you could fool all of them. The quantifiers some, every and some are used to express different situations. Some are captured with the phrase there exists at least one. Every can be expressed as there exists exactly one or there exists no more than one. Some is usually used to mean at least two limited cases, whereas every is used to mean all limited cases. Nowadays, it is generally accepted that the word “some” can mean “at least one” in English. However, in mathematics, it is more efficient to focus on a single object rather than multiple objects. The quantifier captures this idea. You can fool all of the people some of the time and some of the people all of the time means there are some people who can be fooled all of the time, at least 1 person can be fooled all of the time. In this clause, see what’s been captured that’s important. In other words, you can argue about whether or not some of the people have been well captured by existence. However, what’s really going on here is that all of the time you’ll be able to find some people who got fooled. You can fool some people all of the time. You can find some people who will believe anything; you can find others who will believe anything. Let’s examine the last example, but it is important to note that the conjunction “but” is merely another form of conjunctions. You cannot fool all the people all the time, and this one is the easiest because you only need two words for this sentence: alls and time. There are times when it is possible to fool all of the people, but there are other times when it is impossible to fool all of the people. This first clause suggests that there are some people who can always be fooled. There are some people who can be fooled some of the time, but not all of the time; we sometimes succeed in fooling these individuals. However, there are also some people who cannot be fooled at all—they will never believe what we say unless they have proof. That’s why it is a good exercise, because it will help you understand how mathematical formulae can capture the kinds of things we say in the real world. And this statement is a real-world statement with some cultural significance. Let’s move to number 8: According to statistics, a driver is involved in an accident every six seconds. exists x exists t (x, t) Then we would rewrite the sentence to make it more accurate by using the expression “every six seconds,” instead of “second.” In this case, we would say that for every six-second interval, there is a driver involved in an accident. forall t exists x A (x, t) As we can see here, the driver changes from one interval to another. For all values of t, there is an x such that X(t) = x, where these are differentiable functions. They are very different from each other. A lot of you had trouble seeing that there was any problem with the American Melanoma Foundation example, but if we make it precise using our formalism and language (language and formalism refer to mathematics or set theory), then we see that the order in which we state things makes a big difference in how we arrive at our conclusions. That was the whole point of this exercise and these others; to make sure that left-to-right ordering of our formulas captures their logical flow. And there is a logic to this. One sentence states that there is a driver who’s in an accident every six seconds, which makes no sense. Another sentence states that for every six seconds, there’s a driver in an accident. When we look at these statements formally, the distinction between them becomes clear.
