Transcript MGF 1107
MGF 1107 Mathematics of Social Choice Part 1a – Introduction, Deductive and Inductive Reasoning Topics Covered • • • • • Voting Weighted voting systems Apportionment Game Theory Fair division • Textbook: For All Practical Purposes, by COMAP (the Consortium for Mathematics and its Applications), 7th edition Voting Topics • • • • Deductive and inductive reasoning Voting criteria Voting methods Which methods satisfy and fail which criteria? • Fundamental theorems of voting theory Deductive and Inductive Reasoning • Deductive reasoning is the process of making specific conclusions based on general principles. • Inductive reasoning is the process of making general conclusions based on specific examples. Examples of Deductive Reasoning The following are examples of deductive reasoning… 1) If 6x = 18 then x = 3 2) Here given 6x = 18 we can make the deductive conclusion that x = 3 because we can use the general principle that dividing both sides of an equation by the same number (namely 6) will yield an equivalent equation from which we can identify the solution. The measure of angle x is 30 degrees. x 60◦ Here we can make the deductive conclusion that the unknown angle will measure 30 degrees because we can use the general principle that the sum of the angles of any triangle is always 180 degrees. Examples of Deductive Reasoning More examples of deductive reasoning… 3) All men are mortal. Socrates is a man. Therefore, Socrates is mortal. Socrates men mortal things This argument is an example of valid deductive reasoning. The conclusion is valid because it is based on a fundamental principle regarding a basic form of deductive logic. Examples of Deductive Reasoning More examples of deductive reasoning… 4) If a fair division method is envy-free then it is proportional. The Selfridge-Conway fair division method is envy-free. Therefore the Selfridge-Conway fair division method is proportional. Selfridge-Conway method methods that are envy-free methods that are proportional Again, this is a valid deduction. The validity of the deduction is based on the same general principle of logical deduction as the previous example. Math = Deductive Reasoning • Mathematics is essentially deductive reasoning applied to relations among patterns, structures, forms, shapes, and change. • Most people think of mathematics as only about numbers. But we are doing mathematics in this course when we apply general principles to make deductive conclusions. This course is entitled Social Choice Mathematics because we use deductive reasoning in the study of topics that involve decisions among groups of people – from voting to strategies in games. • Deductive reasoning is difficult! For most people it does not come naturally. To make correct deductions requires a complete understanding of the relevant abstract principles. • Deductive reasoning is always valid. However, errors can occur either by starting with incorrect assumptions or by incorrectly applying the relevant principles. Math = Deductive Reasoning • We use deductive reasoning basically because we learn some rules, or some formula, then, when asked a question, we apply the rules or formula and get a specific answer to the question. • That’s why this is mathematics. You learn a rule, a formula, learn to apply the principles correctly, and get the right answer. Examples of Inductive Reasoning The following are examples of inductive reasoning… 1) 2) 3) 4) 5) Every swan I have ever seen is white. Therefore all swans are white. The teacher used powerpoint in the first few classes. Therefore, the teacher will use powerpoint tomorrow. Every object that I release from my hand falls to the ground. Therefore, the next object I release from my hand will fall to the ground. Every fall there have been hurricanes in the tropics. Therefore, there will be hurricanes in the tropics next fall. Based on the most accurate modern observations, the Earth has rotated around the Sun in an elliptical curve for millions of years. Therefore, the Earth will continue to rotate around the sun in an elliptical curve next year. Science = Inductive Reasoning • Science is essentially the application of inductive reasoning to form knowledge based on evidence observed in the natural world. • Every scientific theory must explain all observable evidence and must make falsifiable predictions. A falsifiable prediction is a prediction that can be proven false by future evidence. • Every statement in science is theory. For example, even the statement that the Earth orbits around the sun is a theory based on evidence and the statement that germs cause disease is a theory based on evidence. Every scientific theory must be supported by evidence, must be falsifiable and could be proven wrong but future evidence. • Inductive reasoning is not logically valid in the same way that deductive reasoning is valid. In other words, even if a statement of inductive reasoning (or science) is ultimately true the only way to “prove” that it is true is to collect more evidence to support the statement. Nevertheless, regardless of the strength of the evidence for a particular inductive conclusion, it will always remain possible that future evidence could prove the conclusion false. Side-Tracked on Scientific Theory • The science taught in college is based on very well established evidence and is not likely to be altered by future evidence. The evidence is so well established that it is considered “fact”. • The theory of gravitation and the theory of germs, the theory of light, atomic theory, for example, the fundamentals of these theories are no longer questioned. • Of course evolution is also a scientific theory. Some people refer to it as “only a theory” not understanding that, of course, everything in science is theory, and, to be good science that theory must be supported by lots of evidence and make falsifiable predictions. Elements of a Deductive System • Undefined terms • Defined terms – formally defined terms are made using undefined terms. • Axioms – fundamental assumptions that are self-evident and need not be proven. • Theorems – statements of fact proven to be true based on deductive logic. An Example from Geometry We define vertical angles to be the nonadjacent angles formed by intersecting lines. <A and <B are vertical angles. A B C In this example, the term “vertical angles” is a formally defined term. However, “nonadjacent angles” and “intersecting lines” are undefined terms. The statement that the sum of the measures of angles A and C is 180 is based on the axiom that a line forms a straight angle measuring 180 degrees. The same axiom implies that the sum of angles B and C is 180 degrees. An Example from Geometry Based on the relevant definitions and axioms – that is, based on the relevant abstract principles we can make the following deductions… 1) m<A + m<C = 180 and m<C + m<B = 180 ( here m<A means measure of angle A ) 2) Therefore m<A + m<C = m<C + m<B A B C 3) Therefore m<A = m<B 4) Therefore vertical angles have the same measure. Now we have an deductively proven a new fact – an example of a theorem: Vertical angles have the same measure. Social Choice Math • When we study the mathematics of social choice, we will learn … – Undefined terms – Defined terms – Axioms – Theorems • And we will make deductive conclusions based on relevant general principles.