### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Introduction to Mathematical Thought MATH 124

BSU

GPA 3.72

### View Full Document

## 43

## 0

## Popular in Course

## Popular in Mathematics (M)

This 288 page Class Notes was uploaded by Breanne Schaden PhD on Saturday October 3, 2015. The Class Notes belongs to MATH 124 at Boise State University taught by Staff in Fall. Since its upload, it has received 43 views. For similar materials see /class/218011/math-124-boise-state-university in Mathematics (M) at Boise State University.

## Popular in Mathematics (M)

## Reviews for Introduction to Mathematical Thought

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/03/15

M124 Logic Lec rure 11 Cardinality Uncountability of the real numbers Uncountoble Sets Recall that a set A is countable if and only if there exists a bijection f N gtA Equivalently A is countable if it can be written as a list lfA is not countable ie no bijection f N gtA exists then A is called uncountable The Real Numbers R The set of real numbers R contains the set of rational numbers as a subset Q C R Real numbers which are not rational are called irrational Let R Q Examples J e Intuitiver you might think that there are not many of them you would be wrong Uncountobility of R In fact there are uncountany many irrational numbers To see this we shall show that R is uncountable Then since RQu 50 50 must be uncountable In this case R gt Q The cardinality of R is denoted by N1 pronounced aleph one Contor39s Proof The uncountability of R was demonstrated by the mathematician George Cantor Cantor s proof is a proof by contradiction We assume that R is countable and show that this leads to a contradiction Contor39s Proof So suppose that R is countable Then there is a bijection f N R In particular f is onto surjective so for every real numberx e R there exists n e N such that fn X Contor39s Proof cont Cantor showed how to construct a real number y such that there is m n e N such that fn y This will contradict the fact that f is surjective SO assuming that R is countable leads to a contradiction Therefore R must be uncountable Contor39s construction Suppose R is countable Then 01 is certainly countable Let f N gt 01 be a bijection Use fto write 01 as a list KnM Km Km Can ror39s cons rruc rion coan Write f1 x1 Od11d12dfdf kth digit in decimal f2x Od1d2d3 dk expansion ofxn 2 2 2 2 2 f3 x3 0d31d32d d3k Contor39s construction contd The number y is constructed as follows Consider the decimal expansion of y For each n choose the number in the nth position in the decimal expansion ofyto be different to the number in the nth position in the decimal expansion of fn Can ror39s Cons rruc rion coan y Id11 Id22 Id33 Contor39s Proof cont By construction y differs from fn in at least the nth decimal place for eve n This contradicts the assertion that fmaps N onto R ie that fis a surjection Note Some care is needed in the construction ofy For example 9 s should not be chosen in the expansion to avoid rounding Summary of LecTure 10 Cardinality Uncountability Cantor s proof of the uncountability of R Definition of N1 Confidence Interval Estimation Topics Estimation process Point estimates 5 V Interval estimates V Confidence interval estimation for the mean 039 known Determining sample size Confidence interval estimation for the mean 0 unknown Topics contWed Confidence interval estimation for the proportion Confidence interval estimation for population total Confidence interval estimation for total difference in the population Estimation and sample size determination for finite population Confidence interval estimation and ethical considerations Estimation Process I am 95 con dent that u is between 40 amp 60 Mean u is unknown Point Estimates Estimate Population with Sample Parameters Statistics Mean y f Proportion p p5 Variance 0392 52 Difference u1 u2 X1f2 Interval Estimates Provides range of values Takes into consideration variation in sample statistics from sample to sample ls based on observation from one sample Gives information about closeness to unknown population parameters ls stated in terms of level of confidence Never 100 certain Confidence Interval Estimates Confidence Intervals I 4 amp Mean Proportion 39 039 Known 039 Unknown Confidence Interval foru 039 Known Assumptions Population standard deviation is known Population is normally distributed lf population is not normal use large sample Confidence interval estimate X ZaziSJSZ i n 052 J Elements of Confidence Interval Estimation Level of confidence Confidence in which the interval will contain the unknown population parameter Precision range Closeness to the unknown parameter Cost Cost required to obtain a sample of size n Level of Confidence Denoted by 1001 a A relative frequency interpretation In the long run 1001a of all the confidence intervals that can be constructed will contain the unknown parameter A specific interval will either contain or not contain the parameter No probability involved in a specific interval 10 Interval and Level of Confidence Sampling istrilod ion of the Mean Iu 0520 Intervals extend from y l 39u 1a100 X Z7 I of intervals to constructed contain X Z7 A 100a d0 I Confidence Intervals not Factors Affecting Interval Width Precision Data variation Measured by 0 Sample size O O J J Levelofcon dence 1001 a Determining Sample Size Cost if Too small 0 Requiiiees 39 39 e hWQnt do tee mew e J0 Keeewmee 13 Determining Sample Size for Mean r x ii being wryiridium piie etur iy ner the e enrdierrdi iewiie ien 45 220 2 16452 452 52 2192 E 220 Round Up n 2 Error 14 Confidence Interval forlu O39Unknown Assumptions Population standard deviation is unknown Population is normally distributed If population is not normal use large sample Use student st distribution Confidence interval estimate S n X tor2114 gygfg S 2n 1 E 15 Student s 1 Distribution BellShaped S y111metric Fatter Trails l 16 Degrees of Freedom df Number of observations that are free to vary after sample mean has been calculated M degrees of freedom Example 1 Mean of 3 numbers is 2 X1 1 or any number X 2 2 or any number X 3 3 cannot vary Student s 1 Table 1 Values Example S 502O639i 27 u 19 Confidence Interval Estimate for Proportion Assumptions Two categorical outcomes Population follows binomial distribution Normal approximation can be used if anSand n1 p25 Confidence interval estimate Ego HS pS1pS n n p5 2052 3 p 3 p5 2052 20 Example A W mmm 4m mwt W 8 399 g t W A mi dmc l x W7l m um 1 1 081 08 081 08 08 196 Sp S08196 400 400 053 s p s 107 Determining Sample Size for Proportion Out of a population of 1000 we randomly selected 100 of which 30 were defective What sample size is needed to be within 1 5 with 90 confidence Z2p1 p 16452 0307 n Error2 0052 2273 2 228 Round Up 22 Confidence Interval for Population Total Amount Point estimate N Confidence interval estimate NXiNfa2n1 23 Confidence Interval for Population Total Example An auditor is faced with a population of 1000 vouchers and wants to estimate the total value of the population A sample of 50 vouchers is selected with average voucher amount of 107639 standard deviation of 27362 Set up the 95 confidence interval estimate of the total amount for the population of vouchers 24 Example Solution N1000 n50 X107639 S27362 S N n NXiNt a2n l 1000107639 i 1000 20096 27362 W 100 1 076390 i 75 83085 The 95 confidence interval for the population total amount of the vouchers is between 100055915 and 115222085 Confidence Interval for Total Difference in the Population Point estimate ill ND Where DL is the sample average difference n Confidence interval estimate SD Iv n N13 r Nta23n1 n N 1 I Z ZDi52 Where SD i1 11 1 26 Estimation for Finite Population Samples are selected without replacement Confidence interval for the means unknown S N n XitaZm l Confidence interval for ro ortion PS 1 175 AI n i2 0 pS 052 n 27 Sample Size Determination for Finite Population Samples are selected without replacement When estimating the mean 052 2 Z 2 0392 no 2 e When estimating the proportion 252170 p 0 2 e 28 Ethical Considerations Report confidence interval reflect sampling error along with the point estimate Report the level of confidence Report the sample size as Provide an interpretation A 7 at n z of the confidence Interval estIm 29 Summary Illustrated estimation process Discussed point estimates Addressed interval estimates Discussed confidence interval estimation for the mean 039 known Addressed determining sample size Discussed confidence interval estimation for the mean 0 unknown 30 Summary contWed Discussed confidence interval estimation for the proportion Addressed confidence interval estimation for population total Discussed confidence interval estimation for total difference in the population Addressed estimation and sample size determination for finite population Addressed confidence interval estimation and ethical issues 31 M124 Logic Lecture 13 Number theory Mathematical induction Proof by induction Examples Integers and Number Theory Recall that the Z denotes the set of integers 2 1 O 1 2 We take for granted the fact that it X and y are integers then X y and X x y are also integers Mathematicians say that the set of integers is closed under addition and multiplication Number Theory is concerned with properties of the integers with the operations and gtlt Properties of and x Z together with and x has several properties which we take for granted Ifxa and yb then Xayb and Xgtltyagtltb ab ba and a x bb x a Commutative Laws abcabc and abcabc Associative Laws a gtltbCa x b a x C Distributive Law Properties of and x cont There exist unique integers O and 1 such that Vae Z a00aa and a X11Xaa 0 is called the additive identity 1 is called the multiplicative identity For every a there is an integer a such that aaaa0 a is the additive inverse of a If a x ba x c and a 0 then bc Z x Sometimes use the notation Z x as a reminder that number theory is concerned notjust with the integers but also with and x Z x is a common domain of discourse for Predicate Logic Example Suppose PX X is even Then VxPX gt PX2 VxPX2 gt PX are statements in Predicate Logic for which the domain of discourse is Z gtlt Proofs in Number Theory Consider the statement VxPX gt PX2 A formal proof of the validity of this statement requires many steps see for example Anderson p 106 In practice many of these steps are missed out and a typical acceptable proof might look as follows Proof of VxPx 3 P062 Let X be even Then there exists yeZ such that x2gtlty this is the definition of an even number Therefore X22gtlty22gtltyx 2Xy 2gtlt2gtlty2 So if 2 2gtlty2 then X222 Therefore X2 is even Proof Of VxPx2 3 PX In this case we ll use Equivalence of Contrapositive 39 eagtbE Ibgt Ia So proving PX2 gt PX is equivalent to proving PX gt PX2 Proof of Px 2 Px2 Assume PX In other words X is w Then there exists yeZ such that x2gtlty1 SO X22gtlty124gtlty2 4gtlty 1 Let z2gtlty2 2x y Then X22gtltZ 1 so X2 is odd e PX2 is true So PX gt PX2 hence PX2 gt PX Mathematical Induction Let Pn be the predicate PQO123nnEQ 2 This is true for particular values of n eg 1223229il1 1236a ig 123410 Mathematical Induction Want to show that Pn is true for all integers n e VnPn The easiest way to prove such a statement is to use the method of groof by induc on Mathematical Induction P1 Vk Pk gt Pk gt Vn Pn If P1 is true and for all k Pk gtPk1 Then Pn is true for all values of n This is the principle of mathematical induc on SnrhWNr Proof by Induction Intuitively Show that Pk gt Pk1 for any R Show that P1 is true Then from 1 and 2 P2 is true and from 1 and 3 P3 is true and from 1 and 4 P4 is true etc Example 1 PnSn123n quotn1n21 Case n1 S11 so P1 is true Now assume Pk is true Need to show Pk1 is true e need to show tha ltk1gt k12k2 Example 1 continued Sk112kk1 Skk1 2 kk1 39 k1 Step 1 Write Sk1 in terms of Sk kk 1 2k 1 2 2 k 1k 2 Step 2 Use the fact that Pk is true Step 3 Manipulate to get the right formula Example 1 concluded So Sk1 k1k2 Therefore Pk1 is true Therefore by the principle of mathematical induction VnPn Example 2 Let Pn be the predicate defined by Pn n3n is divisible by 3 Show that VnPn Case n1 n3n110 which is divisible by 3 Hence P1 is true Now assume that Pk holds Need to prove that Pk1 holds Example 2 con rinued Case nk1 k13k1 k33k23k1 k1 k3k3k23k k3k 3k2k Divisible by 3 since Pk is true Clearly divisible by 3 Example 2 concluded Hence if k3k is divisible by 3 then k13k1 is also divisible by 3 In other words VkPk gt Pk1 Also P1 is true Therefore by mathematical induction VnPn Example 3 Let Pn be the predicate if S is a finite set such that S n then PS2quot Claim VnPn This is another way of saying that for any finite set S PS 2S See lecture 7 slide18 Example 3 continued Case n1 If S1 then S hasjust one element X say Then S X In this case PS S so PS2272S Hence P1 is true Now assume Pk is true for some k In other words if S is a set such that S k then PS2k Example 3 continued Let SW be a set such that Sk1k1 Write SW X1 X2Xk1 Sku Xk1 where Sk X1 X2 Xk We can write PSk1 Pk U PM where Pk is the set of subsets of S which don t include Xk1 W is the set of subsets of S which do include Xk1 But PkPSk so I PkPSk2k by assumption Example 3 continued Now consider PM the set of subsets which include Xk1 Every subset in PM must arise by taking a subset of SK and adding Xk1 to it SO I Pk1 PSk 2k Hence PSk1 IF kI U I39Dml 2k 2quot 2X2k 2k Example 3 concluded Hence P1 is true and if Pk is true then Pk1 is also true Hence by mathematical induction VnPn Notes Mathematical induction can only be used to prove arguments for which the domain of discourse is the positive whole numbers For example if Pb is the predicate the roots of the equation X2bX1 are given by br b2 4 x f Then VbPb is true but cannot be proved by induc on Summary Properties of the integers Proof by induction A Mathematical Sampler APPENDIX A BASIC LOGIC APPENDIX A1 Statements and Their Negations De nitions statement a statement is a declarative sentence that is either true or false but not both compound statement statements formed with connectors anal or not if then and if anal only if universal statement asserts that all things of a certain kind satisfy some condition existential statement asserts the existence of at least one thing that satis es some condition particular statement refer to properties of speci cally designated things truth value The truth value of a statement is true T if the statement is true and false F if the statement is false truth table A truth table is a table that shows the truth value of a statement for ALL possible truth values of its components logically equivalent means that the truth values are the same negation a statement which says the opposite of another statement typically but not always formed with a N conditional a statement formed with if then 3 biconditional a statement formed with if anal only if if 9 cgt existential quanti er statements formed with pre xes some there exists or at least one universal quantifer statements formed with pre xes none no all or every Law of the Excluded Middle there are ONLY TWO truth values true and false Law of Contradiction no statement can be both true and false at the same time The Negation of a Statement that contains a Quanifier Original Statement Negation All are Some are not None Some Some are not All are Some None Table of Symbols Symbol Meaning E is equivalent to V for every El there exists or not negation and v or gt implies conditional The Universal Quanti er The universe of discourse of a propositional function Px is the set of values which x is allowed to take It will be denoted by D The statement Px is true for all values of x in the universe of discourse is said to be a universally quanti ed statement The mathematical representation is Vx Px where V which is read as for all or for every is known as the universal quanti er V is closely related to the connective Note that the statement Vx Px is true if Px is true for every value of x in the universe of discourse The statement Vx Px is false if Px is false for at least one value of x in the universe of discourse This means that Vx Px is a proposition When a quantifier such as V is applied the variable X becomes bound Otherwise x is a free variable Examples 1 The statement Vx xl gt x where the universe of discourse is the set of real numbers is true because the statement xl gt x is true for every possible value of x 2 The statement Vx x2 l gt 0 where the universe of discourse is the set of real numbers is false because when x 0 the statement x2 l gt 0 is false This x 0 is known as a counterexample There are many counterexamples here but only one is required to show that a universally quanti ed statement is false The Existential Quanti er The statement Px is true for some value of x in the universe of discourse39 is said to be an eXistentially quantified statement The mathematical representation is Elx Px where El which is read as there exists39 or some is known as the existential quanti er Note that El is closely related to the v connective Note that the statement Elx Px is true if Px is true for at least one value of x in the universe of discourse The statement Elx Px is false if Px is false for every value of x in the universe of discourse Thus the variable x has been bound and Elx Px is a proposition Examples 1 The statement Elx x2 4 where the universe of discourse is the set of real numbers is true because when x 2 the statement x2 4 is true It is also true when x 2 but only one example is required to show that an eXistentially quantified statement is true 2 The statement Elx x lt 2 where the universe of discourse is the set of real numbers is false because x2 lt 0 is false for every possible value of x Note that V and El can be treated like unary connectives and as such they have higher precedence than the binary connectives Example involving connectives Let Px be the statement 39x1 gt 139 and Qx be the statement 39x1 S 139 and the universe of discourse be the set of real numbers The statement Vx Px Qx is false because for each value of X at least one of Px and Qx is false The statement Vx Pxv Qx is true because for each value of x at least one of Px and Qx is true The statement Vx Px is false because there is a value of x for which Px is true Negating quanti ers The generalized de Morgan39s laws state that Vx Px E Elx Px It is not the case that Px is true for every value of x is the same as There is some value of x for which Px is false and Elx Px E Vx Px There is no value of x for which Px is true is the same as 39Px is false for every value of x Note that 1 Vx Px E Elx Px is 0 true when there is an X for which Px is false 0 false when Px is true for every X 2 Elx Px E Vx Px is 0 true when Px is false for every X 0 false when there is an X for which Px is true APPENDIX A2 Conjunctions and Disjunctions De nitions conjunction a statement formed with and disjunction a statement formed with v or tautology a statement that is always true contradiction a statement that is always false Original Statement not p p and q P 0 q if pthen q p if and onlyz39f q Logic Symbols Connective not and or if then if and onlyz39f Statement in Symbolic Form NP PAq PVq P99 P99 Type of Compound Statement negation conjunction disjunction conditional biconditional Truth Value of a Conjunction The conjunction p q is true if and only if both p and q are true Truth Table for p q P T T F F q man1a PAq T F F F Truth Value of a Disjunction The disjunctionp v q is true ifp is true or ifq is true or bothp and q are true Truth Table for p v q P q P V q T T T T F T F T T F F F APPENDIX A3 Conditionals and Deduction De nitions statement a statement is a declarative sentence that is either true or false but not both compound statement statements formed with connectors and or not if then and if and only if conditional a statement formed with if then 3 biconditional a statement formed with if and only if if 9 cgt In Mathematical Systems A proposition is a statement which is either true or false A premiseaxiom is a proposition which is assumed to be true A hypothesis is a proposition which is to be shown to be true A theorem is a proposition which can be proved to be true A conclusion is a proposition which has been shown to be true using the hypothesis the premises and a correct logical arg A proof is a correct logical argument which shows that a proposition is true A lemma is a simple theorem usually used as part of the proof of a more complicated theorem A corollary is a proposition which can be established directly from a given theorem A conjecture is a proposition which has yet to be proved or disproved e g Goldbach s conjecture Conditional Statements Conditional statements can be written in quotif p then qquot or by quotif p qquot form The statement p is called the hypothesis or antecedent The statement q is called the conclusion or consequent quotifp then qquot can be written quotp gt qquot in a1row notation Truth Table for the conditional p gt q P mmaa q P gtq T T F F T T F T An Equivalent Form of the conditional p gt q p gtqEpvq disjunctive form The negation of the conditional p gt q in gt q E 1 617 Common Forms of p gt q Every conditional statement p gt q can be written in an equivalent form If p then q HP 9 p only if q p implies q Not p or q Every p is a q q if p q provided p q is a necessary condition for p p is a suf cient condition for q Styatements related to the Conditional Statement p gt q Ifthe statement is p gt q The converse ofp gt q is q gt p The inverse ofp gt q is p N q The contrapositive ofp gt q is g p Truth Tables for the Conditional and Related Statements Conditional Converse Inverse Contrapositive P q P gtq q gtP NP gt q Nq gt P T T T T T T T F F T T F F T T F F T F F T T T T the conditional is equivalent to the contrapositive p gt q E q gt p the converse is equivalent to the inverse q gt p E p gt q An argument consists of a set of statements called premises and another statement called the conclusion An argument is valid if the conclusion is true whenever all the premises are asumed to be true An argument is invalid if it is not a valid argument Example of an argument lst Premise All men are mortal 2nd Premise Socrates is a man Conclusion Socrates is mortal Truth Table Procedure to Determine the Validity of an Argument Write the argument in symbolic form Construct a truth table that shows the truth value of each premise and the truth value of N the conclusion for all combinations of truth values of the component statements E Ifthe conclusion is true in every row of the truth table in which all the premises are true the argument is valid Ifthe conclusion is false in any row in which all of the premises are true the conclusion is invalid Standard Forms of Four Valid Arguments Modus Modus Law of Disjunctive ponens tollens syllogism syllogism premise p gtq p gtq p gtq pvq prem1se p q q gt r p conclusion q p p gt r q Two Forms of Invalid Arguments Fallacy of the Fallacy of the converse inverse premise p gt q p gt q premise q p conclusion p q An argument is valid if it is built upon correct rules of inference A proof is correct if and only if it uses valid arguments and all of the premises used are true The premises then lead via the argument to a correct conclusion If one or more of the premises is false then a valid argument can lead to an incorrect conclusion A fallacy is an incorrect argument The reasoning used often closely resembles a correct rule of inference but is in fact based on a contingency instead of atautology Logic and Proof Mathematical Systems A proposition is a statement which is either true or false A premiseaxiom is a proposition which is assumed to be true A hypothesis is a proposition which is to be shown to be true A theorem is a proposition which can be proved to be true A conclusion is a proposition which has been shown to be true using the hypothesis the premises and a correct logical a A proof is a correct logical argument which shows that a proposition is true A lemma is a simple theorem usually used as part of the proof of a more complicated theorem A corollary is a proposition which can be established directly from a given theorem A conjecture is a proposition which has yet to be proved or disproved e g Goldbach s conjecture Every even number greater than 2 can be written as the sum of two prime numbers Rules of Inference Rules of inference are the means by which conclusions can be drawn They form the basic steps of any proof 0 Each rule of inference requires specied hypotheses to be true and gives a logical conclusion from these hypotheses The conclusion must be true because it is the logical consequence of an associated tautology indicates that the conclusion is a logical consequence of the hypotheses for lture reference Addition p p v q quotpr is true thenp or q is true or bothquot Simpli cation pA q p quotpr and q is true thenp is truequot Combination Conjunction p q pA q quotpr is true and q is true thenp and q is truequot Hypothetical syllogism p gt q q gt I p gt r quotpr implies q is true and q implies r is true thenp implies r is truequot Modus ponens p gt q p q quotpr implies q is true andp is true then q is truequot Modus tollens p gt q N q p quotpr implies q is true and q is false thenp is falsequot Note that 0 Each rule of inference has an associated tautology eg modus ponens relates to p p gt q gt q o All ofthese rules can be proved using truth tables Modus tollens can be deduced from modus ponens using the contrapositive of p gt q Resolution p v q pvr q v r quotpr or q is true andp is false or r is true then q or r is truequot Disjunctive syllogism p v q N P q quotpr or q is true andp is false then q is truequot Note that The disjunctive syllogism is a special case of resolution with r E F Resolution is often used repeatedly in a chain to reach the desired conclusion Examples State the rule of inference illustrated by each of the following Ifit is night then I switch the light on It is night Therefore I switch the light on Modus ponens N If it is cold then I switch the heating on The heating is not on Therefore it is not cold Modus tollens LA It is night or it is cold It is not night Therefore it is cold Disjunctive syllogism Proofs using rules of inference 1 Assume the following to be true COPq bPV9 gtV and use them to prove that r is true Proof Statements Reasons 1 p q premise a 2 p l and simpli cation 3 p v q 2 and addition 4 p v q gt r premise b r 3 4 and modus ponens 2 Assume the following to be true ap gtq b l gtr cr and use them to prove that p is true Validity of Arguments An argument is valid if it is built upon correct rules of inference A proof is correct if and only if it uses valid arguments and all of the premises used are true The premises then lead via the argument to a correct conclusion If one or more of the premises is false then a valid argument can lead to an incorrect conclusion A fallacy is an incorrect argument The reasoning used often closely resembles a correct rule of inference but is in fact based on a contingency instead of a tautology Disproving Arguments Examples 1 Show that the following argument is invalid P gt q q p Proof P q P gt q T T T T F F F T T F F T When the premises are true we get two different conclusions The argument is invalid 2 Using a truth table determine the validity of vwer 9 p gt r Proof P 9 V PV 9 N P T T T T F T T F T F T F T T F T F F T F F T T T T F T F T T F F T F T F F F F T qu gt I ma arma T p gtr T T T T T F T T When the premises are true the conclusion is true the argument is valid Note that Arguments can also be disproved by deducing a contradiction eg pA p 0 Example 1 is known as the fallacy of affirming the conclusion It is commonly mistaken for modus ponens but p gt q q gt p is not a tautology It is easy to make a similar error with modus tollens the fallacy of denying the hypothesis 0 Another common fallacy is quotcircular reasoningquot the proof assumes the truth of a statement equivalent to that being proved Examples Some common fallacies are illustrated by the following Affirming the conclusion Ifit is night then I switch the light on I switch the light on Therefore it is night N Denying the hypothesis If it is cold then I switch the heating on It is not cold Therefore I don t switch the heating on LA Circular reasoning It is cold It is December Therefore if it is cold then it is winter Proofs involving Quanti ers To prove that Elx Px is true use an arbitrary x ie never assign it a speci c value in the universe of discourse and verify Px To prove Vx Px and a speci c value for x which satis es Px To disprove Elx Px and a speci c value for x a counterexample which satis es Px ie prove Vx Px To disprove VX PX use an arbitrary x in the universe of discourse and verify Px ie prove Elx Px Direct proof A direct proof assumes that p is true and uses this along with other true statements r to deduce that q is true Note that o if p is false it doesn39t matter whether q is true or false the implication still holds 0 Direct proofs establish that p gt q is true and apply modus ponens There is often repeated application of the hypothetical syllogism Example 39 l Prove that if n is an odd integer then r2 is also an odd integer Note that 0 An integer n is even if and only if it can be written as n 2k where k is some integer An integer n is odd if and only if it can be written as n 2k l where k is some integer Proof Let n is an odd integer Then Elk such that n 2k l where k is an integer Thus n2 2k12 4k24k1 22k22k1 2m1 meZ Hence Elm such that n2 2m 1 where m is an integer n2 is an odd integer QED Rules of Inference Revisited The previous example can be related to rules of inference Example 1 again Given the propositions P n is an odd integer R n2 2m 1 for some integer m Q n2 is an odd integer an outline proof might be given by Statement Reason 1 P hypothesis 2 P gt R proved 3 R l 2 and modus ponens 4 R gt Q by de nition 3 4 and modus ponens QED This could be split up further in to simpler component propositions For you Example 2 Let a and b be integers Prove that if a divides b and a divides c then a divides b 0 Note that An integer a is said to divide an integer b if and only if there eXists some integer a such that b aq b 1e is an integer a Proof Proof by contradiction A proof by contradiction assumes that p is true and q is false and uses these along with other true statements to deduce a contradiction This is a type of indirect proof Note that Every proposition used apart from q must be true Proofs by contradiction establish that m q a m 0 is true for some related proposition r use the fact that it is equivalent to p gt q being true and apply modus ponens It is related to the application of modus tollens Examples 39 l Prove that if 5n 2 is an odd integer then 71 is an odd integer where the universe of discourse for n is the integers Proof Let 5n 2 be an odd integer Assume that n is an even integer ie n is not odd We only consider cases where n is an integer Since 71 is even Elk such that n 2k where k is an integer Thus 5n2 52k2 10k 2 25k1 2m meZ 5n 2 is an even integer This contradicts the fact that 5n 2 is odd therefore the assumption that n is even is wrong leaving only one possibility 71 must be odd QED For you 2 Let x andy be real numbers Prove that ifxy Z 2 then x Z l ory 21 Proof Proof by contraposition A proof by contraposition assumes that q is false and uses this along with other true statements to deduce that p is also false ie the contrapositive of p gt q is proved This is another type of indirect proof Note that o This is a special type of proof by contradiction see previous examples 0 Proofs by contraposition establish that q gt p is true use the fact that it is equivalent to p gt q being true and apply modus ponens Proof by cases Proof by cases splits p up into a number of different components p1 p2 p3 p which together cover every possible situation It then assumes for each case in turn that pl is true and uses this along with other true statements to deduce that q is true For you Example Prove that for any integer n n2 n is an even integer Proof Proving equivalences When proving equivalences p gt q it is necessary to prove both p gt q and q gt p This is based on the tautologyp lt gt q E p gt q q gt p For you Example 39 Prove that n is an odd integer if and only if n2 is an odd integer where the universe of discourse for n is the integers Proof What is Mathematical Induction Consider the following sums lll2 13422 135932 13571642 135792552 A pattern can be seen It appeals that the sum of the rst 71 odd positive integers is equal to 712 ie n Z2i ln2 i1 How can this quoteducated guessquot be proved Mathematical induction is a technique that can be used to prove theorems which state that a propositional function Pn is true for all positive integers In other words it is used to prove Vn Pn where the universe of discourse is the positive integers or something similar It is commonly used for analyzing algorithm complexity proving correctness of programs analysing graph and tree structures proving a range of identities and inequalities Proof by Induction To prove that the statement Pn is true for every positive integer n apply the following two steps Basis step prove that the proposition Pl is true Inductive step prove the implication P n gt P n l to be true for an arbitrary positive integer n Pn is known as the inductive hypothesis A proof of this form can be expressed by the rule of inference 131 Vn Pn gt Pn 1 Vn Pn where the universe of discourse for n is the positive integers Examples 39 1 Use mathematical induction to prove that the sum of the rst 71 odd positive integers is 712 Proof Let Pn be the proposition quotthe sum of the rst 71 odd positive integers is n2quot Basis step prove that P1 is true This is true because when n 1 the sum of the rst 71 odd positive integers there is only 1 is 1 n2 Inductive step prove that P n gt P n 1 is true for all integers n 2 1 Suppose that Pn is true where n is an arbitrary positive integer noting that if Pn is false then the implication is trivially true In other words assume that 1 3 5 2n 1 n2 and use this to prove that 13 52n 1 2n1 71 12 Now assuming Pn leads to LHS 1352n 12n1 1352n 12n1 n2 2n1 n2 2n1 n12 RHS Thus Pn 1 is implied byPn Since P1 is true and Pn gt Pn 1 is true for all positive integers n then Pn is true for all positive integers n 2 2 by the principle of mathematical induction QED 2 Use mathematical induction to prove the inequality n2 gt n1 for all integers n gt 2 Proof Let Pn be the proposition n2 gt n1 Basis step prove that P2 is true Inductive step prove that P n gt P n l is true for all integers n gt 2 Suppose that Pn is true where n is an arbitrary positive integer In other words assume that n2 gt n1 and use this to prove that 71 12 gt 71 1 1 As before the Principle of Mathematical Induction implies that Pn is true for all positive integers n QED For you 3 Use mathematical induction to prove that n3 n is divisible by 6 for every positive integer 71 Proof Note 0 The second proof illustrates that the basis step need not be to prove Pl In fact any integer k could be chosen for the rst step but the resulting proof would only be valid for all integers n gt k 0 It is also possible to use more than one proposition in the basis step This often makes the proof of the inductive step much simpler Supplementary example For you Use mathematical induction to prove that every amount of postage of 12 pence or more can be formed using only 4 and 5 pence stamps Proof Let Pn be the proposition quotpostage ofn pence can be formed using only 4 and 5 pence stampsquot Basis step prove that P12 Pl3 Pl4 and Pl 5 are true Inductive step prove that Pn 3 Pn 2 Pn l Pn gt Pn l is true Vn Z 15 Molecular Symmetry Symmetry impacts 59 Physical properties 59 Reactions 59 Molecular orbitals 5 Electronic structure 59 Molecular Vibrations Group theory 5 Behavior of molecule based on symmetry Symmetry analysis Applications of symmetry Orbital symmetry Vibrational symmetry 4 1 Introduction to symmetry analysis Symmetry operation be Action which molecular symmetry unchanged IIIv Rotation through an angle IIIv Re ection Symmetry element be location of symmetry operation IIIv Point ml Line nu Plane 59 Operation leaves at least one point in molecule unchanged ml Point group symmetry 4 2 Symmetry analysis Identity operation E 5 Leaves entire molecule unchanged 7 um All molecules have at least this operation a 7 11 fold symmetry axis Cu 180 l 5 360 n rotation mm H20 180 n2 gtllt C2 39 nu NH3 120 n3 C gtxlt c3 0 Mirror plane 039 02 gt0 Vertical 6V horizontal ch or dihedral 6a to rotation of fold symmetry axis s V Re ection 4 quotD Molecule can have different levels of mirror plane Gd Symmetry analysis 0 Inversion operation i 5O 5O A B i C D a E CZ A i B c D b Projection through a F3 5 center point in the 4P molecule sFquot 31 6F 3 HI Center of an octahedron HI No AB4 tetrahedron has a center of inversion Need to differentiate 630 3 mock HJ H2 inversion 0 7 H 1393 between C2 and i gt 0 on mc s Vcoom 2H 0H5 H 0H5 45 D C B A B A D C Symmetry analysis Improper rotation Sn 55 consist of two separate operations quotquot9 nfold rotation rotation by 360 n about an axis followed by Hquot re ection in a plane perpendicular to that axis Each operation is needed to achieve the proper reflection ml Individual operation does not result in proper reflection Improper axes are often the most difficult symmetry elements to spot S1 Hquot C1 and 0h is oh Sz Hquot C2 and Chis i A l I I I H2 r H2 H1 I J 2 Agobu Innaa 1 total on 4H4 H I rquot 34 x Iquot 2 reflection m a plane unpr oper B perdendicu zu39 rotation H3 2H IHCH 4 46 Symmetry analysis summary 0 Molecule can have a number of symmetry operations 0 Each operation has associated element Table 41 Important symmetry operations and symmetry elements Symmetry element Symmetry operation Symbol dentity E n Fold symmetry axis Rotation by 27tn Cn Mirror plane Reflection a Center of inversion Inversion i n Fold axis of Rotation by 27tn Sn improper rotation r followed by reflection perpendicular to rotation axis The symmetry element can be thought of as the whole of space TNote the equivalences S1 6 and S2 i Point Groups 0 Point group can be assigned to each element 5 Based on symmetry elements possessed by molecule and compare to element that define group 5 Strong relationship between molecule geometry and point group quotW Linear With center D00h 0 quotW Linear no center C00v 3 D m See previous lecture for more information Point Groups H quotquot I 1 Cl H I B F H B H F F pr B as 3 39H F F H F B H 4 9 lit n szI 42 Th mmlmsman uf same mmmnn gmups Point Symmetry elements Shape Examples group E r 7 susrcm 3 561 H70P a E w xv E3977rr H30 sum CO HCL 0C5 3 5mm V NHl PCIJ PomX 7 0 172 N20 am nh E 33923rrwrr53 l m PG n ErhCyZC yZQ39CnSrrh2rrZad my rrnnerAAB owh 51 Javr sw 1 Hr cow cm T E33934bzm4SK CH SwCL 0 56L41Ly 4515i3ahm 5 411 3 mgrwwnl m m n m nu rm mucan u lmlmuugqu mumvmam Point Groups a a 0 H20 point group bu Know it is sz from table bu Symmetry elements quotW E C2 180 rotation 2 vertical mirror planes 6V E C2 0quot GV NH3 point group 5 C3V point group bu Elements quotW E C3 each NH three vertical mirror plane through each NH 30V E C3 36V 0 Apply to identi cation tree Application of symmetry Construction and labeling of molecular orbitals Molecular properties 56 Polarity 56 Chirality 0 Polar 5 Permanent dipole 5 Cannot set up dipole on molecule with symmetry elements that exchange dipole over molecule quotW Cannot have dipole with following symmetry elements Center of inversion Perpendicular to mirror plane or axis of rotation quotW D point groups Td Oh Ih do not have dipoles Polar molecules Consider Ruthenocene 55 55 Is point group D or cubic What is the point group mu C5 C2 perpendicular with C5 6h mirror plane D511 Molecule is non polar Chiral Molecules Chirality 5 Cannot be superimposed on mirror image ml Enantiomers 5 Optically active quotID Rotate light 5 Chiral molecules do not have Sn symmetry element quotw Dnd9 Dnh9 Td9 Oh Orbitals and symmetry Correlate symmetry with orbital characteristics Character tables be Sigma quotW No sign change with rotation 1 on table be Pi quotW Sign change with rotation 1 on table be pz has sigma symmetry Orbital Symmetry Symmetry adapted linear combination 55 55 SALC Combination of orbitals with symmetry considerations HN3 I 1153 1sb Insc NguyenI lineii39poi 39 quot quot 0 C 39 U i ydtL mu molecule 1 0 39 39 quot 3 0 y r l N all V lt oldnmte h stem 1 B 439 0V lEl th the beryllium 2A orbital a 39 1 H BrH x s if V V j a J I I 1 1L 2 7 1 h Figure 52 Overlap of he hydrogen ix Ul39hllHlu 1104 A Character table element Table 43 The C3V character tabe E 2C3 30 A1 1 1 1 z x2 y222 A2 1 1 71 R2 E 2 71 0 x7y x2 7y27xy7 ZX7yZ Rx7Ry a7b denotes a degenerate pair of orbitals the characters in the table refer to the symmetry of the pair jointly The symbol Rq denotes a rotation around the axis q Orbitals are symmetry types Symmetry based on center point of molecule Angular variation of orbitals represented by directions Element operation gt9 E give degeneracy ab e t gt9 1 1 symmetry in Only symmetry similar orbitals can overlap in Evaluate D3h of BF3 418 A xzfyz 22 xiy any 36 W Character tables E and T are sum gt5 Can be0 Consider H20 gt5 gt5 What is the pz orbital 0n 0 C2 changes sign m 1 6v does not change sign m B1 CZV E C2 oVxz h 4 2mm A1 1 1 1 1 2 x2 y2 22 A2 1 171 71 R2 xy B1 1 71 1 71 x Ryxz B 1 7171 1 y nyz Molecular orbitals Based on SALC of atomic orbitals of same symmetry 5 0 and pZ can combine to form molecular orbital Consider H on H20 be What are the symmetry labels for H1s and which 0 orbitals overlap III A1s IB1s I IA1s IB1s for H orbitals nu for E C2 oV oV 1 for C2 039V 1 E and 6V 1 nu A1 and B2 from table 0s and Opz orbitals with H form wal Opy With H I form wbz Construction Molecular orbitals Assign point group to molecule Look up shapes from SALC Arrange SALCs based on energy and number of nodes 55 sltpltd Combine N SALC into N molecular orbitals Estimate energy and compare with data Molecular Vibration Polar molecules IR active Vs x H20 HCl NO I ml Most molecules will absorb IR VHS gt5 IIomonuclear species IR I inactive quotquot l 02 N2 C12 Vibrations gt5 Stretching I Symmetric and asymmetric 51gt Bending Hquot Rocking HI Scissoring HI Wagging HI Twisting Th ry EXample CO2 OCO linear 4 i 4 gt Only some modes IR m N0 net dipole moment change Model based on Hooke s lt gt law 9 0 9 M 5 25 t 5 59 F inoliifeiillgliiilge ml Fforce ke0nstant 6 Oi 9 5 25 5 Net dipole moment change Vs not IR active Vas bend IR active 5 Change in energy related to F dE de i r dE no overall dipole E 3quot c113 k j ydy 0 0 0 0 0 4 h ik 2 424 2 y Theory Harmonic oscillator derived gt5 mdzydt2ky quotquot9 Substitute yACO 27Eth V E ky2 Vibrational Frequency 2 55 Fma nu gt5 ad2yldt2 g L E quot39 27 y gt5 111 goes to reduced mass o 0 Displacement y wgt mlmZ m1m2 Theory Quantum treatment 59 h is Planck constant EVli Vlhvm 2 27 y 2 5 v is Vibrational quantum number IIIv Integer 3 0 1 3 E E 0 2 m 1 2 m Solve forv vVmi f 27 u Express in wavenumbers AEthi E 27 u be In cm39l k in Nm c in ms u in kg K 38E2 for single bonds 5 163 double 1563 triple EiE53E 12E 27w 426 Theory Calculate stretching frequency of CO 5 Calculate mass in kg nu mc2e26 kg nu m027e26 kg nu u27x2x1e2627211E26 kg 1E3 16E3cm391 LIE 26 53E 12 5 Experimental value 1600 cm391 to 1800 cm391 Actual system is anharmonic 5 Selection rules AviZ and 3 are observed Theory Electron repulsion Bond breaking Vibrational modes 5 Depends upon number of atoms and degrees of freedom w 3N total W N number to atoms Constraints due to 5 Translational and rotational motion of molecule A v1 3652 cmquot 0 AJ v2 1595 cmquot v3 3756 cm l 5 Motion of atoms relative to each other W Non linear 3N6 w Linear 3N 5 5 C02 4 modes w 2 bend symmetric stretch asymmetric retch HZO 3 modes SF6 15 modes 6 Raman Theory Excitation be From ground or 1st vibrationally excited state IIIv Population of excited state from Boltzmann s equa on Molecule populates Virtual states with energy from photon Can be effected by temperature 5 Elastic scattering is Rayleigh In Energy scatteredenergy incident be Energy difference due to A ground and 1st excited state nu hv AE is Stokes scattering nu HVAE is antiStokes scattering 429 Theory 3 types of scanered radiation gt Stok s Rnyimgh scumring vi 1w cmquot 1 xx 0 nm e m Lower energy than Anti Stokes Named from W uorescence behavior Mmloh quot More intense mm quot Used for Raman asurements gt Antiistokes m No uorescence 39n e erence Welwly 1 t ri gt6 Ray ei m r 00 n 4w 4 quot Most Intense 4 A m m Sm 5 made mm mm 134 mm mm onch mm by m S litpatterns Independent of mumhnnofA Mnmmm w m 1 192 I incident radiation wavelength number above the peak 1 me Human 5mm Au v 7 w anquot WWW mm pmnmnm ran p lmmmm mm K WWW Am m walnut172 MW 1731 imam Mmi drnrlnc WWW mu Virtual 5 2 39l quot Matti mund elemnnic 5mm Lquot h39r39 I J I Raymhgh smattering E JI39I39 Statm E uh 1quot A Human mamring E Irv i 5 3 if I if Filliii39 li k h 1 gure 132 Dijgm mquot lm131311 and aman attening Theory Variation in polarizability of bond with length Electric eld E due to excitation frequency With E0 E 2 EO cos27rvext Dipole moment m based on polarizability of bond 0 m 2 05E 2 aEO cos27rvext For Raman activity 0L must vary with distarge alon bond 05 g o o a2a0rreq 5 0L0 lS polarlzablllty at real 8r r req rmax cos27rvvt Theory E 8 m aOEO cos27rvext 70 rm 8 cos27rvex VV t E0 805 r cos 7zv 2 Jar ex Equation has Ra leigh Stokes and An Stokes component Complementary to IR absorbance 51gt Overlap not complete CH Mcslrlcne n l L l L l 1 1 4000 3500 3000 2500 2000 18001600 HEIDWZOL A 1000 800 600 4m 2m 0 J J l 1 77 l J l JUUU 35m 1000 2500 2000 800160040011001000 800 600 400 200 Fum cm U Figure 183 Comparison 01 anan and Infrared spzma Kaunas Pilkirlr mrr Carp unvu ZT Vibrational spectroscopy and group Molecules with inversion cannot be both IR and Raman active 55 For C02 symmetric stretch is IR inactive In No net change of dipole mu Raman active A vibrational mode is IR active if it is symmetric with electric dipole vector 55 Causes change in dipole Mode is Raman active if it has component of molecular polarizability Vibrational spectroscopy Consider cis CZV and trans D211 PdClzNH32 be Both have Pd Cl stretch be For CZV all 1 is symmetric mu A1 be Asymmetric mode N H a cis quotW C2 and oquot are 1 B group Same information can be used to assign symmetry A g Bzu b trans Symmetry and vibration A1 1 1 1 1 2 X2 yZ 22 A2 1 1 1 1 R xy B1 1 1 1 1 X XZ B2 1 1 1 1 y RX yz a1 vibration generates a changing dipole moment in the zdirection b1 vibration generates a changing dipole moment in the Xdirection b2 vibration generates a changing dipole moment in the ydirection a2 vibration does not generate a changing dipole moment in any direction no X y or z in the a2 row Thus a1 b1 and b2 vibrations give rise to changing dipole moments and are IR active However a2 vibrations do not give rise to changing dipole moments and are IR inactive 437 Symmetry and vibration Which bonds are IR active in CCl4 59 Symmetry is Td be From table which bonds are dipole active in x y or 2 quotID t2 is active in xy and 2 quotID What do these bonds look like 55 xz yz xy X2 yz 22 are Raman active III From table a1 and t2 are Raman active A Short History of Probability French Society in the 1650 s 0 Gambling was popular and fashionable 0 Not restricted by law 0 As the games became more complicated and the stakes became larger there was a need for mathematical methods for computing chances tat Enter the Mathematicians A wellknown gambler the chevalier De Mere consulted Blaise Pascal in Paris about a some questions about some games of chance Pascal began to correspond with his friend Pierre Fermat about these problems Classical Probability The correspondence between Pascal and Fermat is the origin of the mathematical study of probability The method they developed is now called the classical approach to computing probabilities The method Suppose a game has n equally likely outcomes of which m outcomes correspond to winning Then the probability of winning is mn Problems with the Classical Method The classical method requires a game to be broken down into equally likely outcomes It is not always possible to do this It is not always clear when possibilities are equally likely Expenence Another method known as the frequency method had also been used for some time This method consists of repeating a game a large number of times under the same conditions The probability of winning is then approximately equal to the proportion of wins in the repeats This method was used by Pascal and Fermat to verify results obtained by the classical method Early Generalizations James Bernoulli proved that the frequency method and the classical method are consistent with one another in his book 1713 Early Generalizations Abraham De Moivre provided many tools to make the classical method more useful including the multiplication rule in his book in 1 71 8 The book was popular eventually going through three editions From Games to Science Throughout the 18th century the application of probability moved from games of chance to scientific problems Mathematical theory of life insurance life tables Biological problems what is the probability of being born female or male Applied Probability PierreSimon Laplace presented a mathematical theory of probability with an emphasis on scientific applications in his 1812 book275lfgictjzi Unfortunately Laplace only considered the classical method leaving no indication on how the method was to be applied to general problems Stagnation and Frustration After the publication of Laplace s book the mathematical development of probability stagnated for many years By 1850 many mathematicians found the classical method to be unrealistic for general use and were attempting to redefine probability in terms of the frequency method These attempts were never fully accepted and the stagnation continued Axiomatic Development Andrey Kolmogorov developed the first rigorous approach to probability in his 1933 monograph Grundbegriffe der Wahrscheinichkeitsrechnun He built up probability theory from fundamental axioms in a way comparable with Euclid39s treatment of geometry Probability Today Modern research in probability theory is closely related to the mathematical field of measure theory Modern innovators in the field include Patrick Billingsley University of Chicago Yuan Shih Chow Columbia Kai Lai Chung Stanford Samuel Karlin Stanford RolfDieter Reiss Sheldon Ross Berkeley Henry Teicher Rutgers and many many more MATHEMATICS OF PATTERNS NUMBER THEORY NOTES What Is Number Theory Number theory is basically the investigation of patterns and relationships in the natural numbers 1 2 3 4 It rst began as a specialized discipline of mathematics in the 17th century as a result of the work of Pierre Fermat and Karl Friedrich Gauss But their work followed the work of the Greeks during 600 BC to 400 A D While the Greeks appeared to do only geometry they investigated number theory by letting xed length line segments represent numbers Number theory is particularly interested in prime numbers those numbers whose only factors are 1 and themselves The sum of consecutive odd numbers starting with 1 is the square of the number of odd numbers added or the sum of the first It odd numbers is n2 or 13 5 7 2n 1 n2 Note that any odd number can be represented by 2n 1 The Greeks approached this by using a diagram probably made with pebbles o o I o I o I O I Each quotrow columnquot represents the next odd number 0 o o I o I o I counting the total pebbles gives you the sum of the first It odd numbers 0 o o o I o I These are also quotsquare numbersquot 0 o o o o I notice that 16 pebbles is made of 4 rows and 4 columns notice that 25 pebbles is made of 5 rows and 5 columns and so forth Example Problems 1 What is the 100th even number 2 What is the 994th odd number 3 6 9 12 15 18 3 What is the next number in the sequence 4 What is the 10th number in the sequence 5 Determine an expression for the nth number in the sequence 6 What is the 200th number in the sequence 1 4 7 10 13 16 7 What is the next number in the sequence 8 What is the 10th number in the sequence 9 Determine an expression for the nth number in the sequence 10 What is the 200th number in the sequence 10 17 24 31 38 45 11 What is the next number in the sequence 12 What is the 10th number in the sequence 13 Determine an expression for the nth number in the sequence 14 What is the 200th number in the sequence Triangular Numbers 1 3 6 10 15 21 11 What is the next triangular number in the sequence 12 What is the 10th triangular number in the sequence 13 Determine an expression for the nth triangular number in the sequence 14 What is the 200th triangular number in the sequence Square Numbers 1 4 9 16 25 36 11 What is the next square number in the sequence 12 What is the 10th square number in the sequence 13 Determine an expression for the nth square number in the sequence 14 What is the 200th square number in the sequence Hexagonal Numbers 1 6 15 28 45 66 11 What is the next hexagonal number in the sequence 12 What is the 10th hexagonal number in the sequence 13 Determine an expression for the nth hexagonal number in the sequence 14 What is the 200th hexagonal number in the sequence Divisibility Ify x is a natural number then we say that x divides y or x is a divisor ofy or x is a factor ofy or y is a multiple of x or y is divisible by x Symbolically we denote this with x y read quotx divides yquot xly is equivalent to quotFor some natural number z x z y The following statements are true xly if and only if there is some natural number z such that x z y If xly then i is a ntural number and l y x x 1y yly If xly and ylz then xz If xly and xlz then xy z If xly then xS y Example Problems True or False 5 9 L L 939 L L 1 7s9 s300 15525 57 107 Ifxly andylx thenx y Ifxlty thenxly 57 75 Explain why the product of any two consecutive numbers is even Fill in the blanks to create an accurate de nition If divides then It is an even number Counting Divisors The number of divisors of n will be denoted by Dn read quotD of nquot A prime number is a number that has exactly two divisors A factorization of a number n ia a representation of n as a product of two or more primes A composite number is a number with three or more divisors Fundamental Theorem of Arithmetic Every number greater than one has a unique prime factorization For any numbers In and n m n if and only if iff every power of a prime factor of m also divides n Example 8 24 8 23 so 2122 and 23 all divide 24 The number of divisors of n is represented by Dn HP is a prime number then the number of divisors ofpk Dpk k 1 Example 3 is a prime number the number of factors of 81 which is 3quot is D81 D3quot 41 5 the divisors of 81 are 1 3 9 27 and 81 There are 5 divisors Example What is D216 2162333 SoD216 D23D33 44 16 Example Problems n Divisors Dn 10 2 5 4 28 22 7 6 278 2139 4 463 1 463 4 10000 2quot 54 25 25025 52 7 11 13 24 Summing Divisors The sum of the divisors of a number n is denoted by Sn Note that if n is prime then S n n 1 k1 1 Ifngt1 then 1n1n2n3nk1nk n 1 Example The sum of the divisors of 24 S24 The divisors of 24 are 1 2 3 4 6 8 12 and 24 so S24123468122460 Example Determine S 172 S172 1 17 172 using the formula with n 17 k 2 21 3 117172 uu 307 17 1 17 1 16 16 so S289 S172 1 17 172 1 17 289 307 Example What is S35 The divisors of 35 are 1 31 32 33 3quot 35 So s 351392781243364 3 1 using the formula S35 u E 364 3 1 3 1 2 Example Determine S 60 S60 S223151 S23S31S51 using the formula with n 2 k 2 12122 2t1 17 2 1 2 1 1 1 soS60S233151S23S31S51 746168 123456101215203060168 Example Problems n 10 28 278 463 10000 25025 Divisors 25 227 2139 1463 2quot54 5271113 Dn 4 25 24 S00 18 56 420 464 24211 26 328 Proper Divisors A number x is a proper divisor of y provided that x y and x lt y The sum of the proper divisors of s number n is denoted by Pn Sn n IfPn gt n then It is abundant If Pn lt n then It is de cient IfPn n then It is perfect further The number n is de cient if and only if S n lt Zn The number n is abundant if and only if S n gt Zn The number n is perfect if and only ifSn 2n Example Problems n Divisors D n S n Pn Type 10 2 5 4 18 8 De cient 28 22 7 6 56 28 Perfect 278 2 139 4 420 141 De cient 463 1 463 4 464 1 De cient 10000 2quot 54 25 24211 14211 Abundant 25025 52 7 1113 24 26328 1303 De cient Even Perfect Numbers Some perfect numbers are 6 28 496 Are these the only perfect numbers Are all perfect numbers even Example Determine whether the following numbers are perfect 46 P46 26 P46 lt 46 46 is de cient 48 P48 76 48 lt P48 48 is abundant 50 P50 43 P50 lt 50 50 is de cient 52 P52 46 P52 lt 52 52 is de cient 54 P54 66 54 lt P54 54 is abundant None are perfect Let39s look at the prime factorization of our three perfect numbers 6 28 496 62131 282271 4962quot311 Is there a pattern here It looks like a power of two times a prime might be a pattern Further it looks like the exponent of two is increasing as is the prime What happened to 23 Let39s try numbers that look like 23 x p where p is a prime p n 23 x p Pn Classi cation Pn n 11 88 92 Abundant 4 13 104 106 Abundant 2 17 136 134 De cient 2 19 152 148 De cient 4 23 152 176 De cient 8 29 232 21 8 De cient 1 4 So it doesn39t look like we have a perfect number with 23 as a factor but notice that Pn It goes from to as the prime changes from 13 to 17 Its almost like if there were a prime halfway between 13 and 17 then 23 times that prime would be a perfect number Notice that the numbers 3 7 15 31 are all of the form 2quot 1 where each number is twice the prior plus one So the next number that ts that description is 63 63 26 1 and 63 2 31 1 But 63 is composite so we probably should go to the next number We nd that the next number that ts the description is 127 127 27 1 and 127 2 63 1 And 127 is a prime number So our quotformulaquot gives us 26 x 127 8128 S8128 S2 x S127 27 1 x 128 127 x 128 16256 P8128 16 56 8128 8128 So 8128 is a perfect number So we can make these statements If 2quot 1 is prime then 2k12quot 1 is perfect A number of the form 2k3912k 1 is called a Euclidean number and is denoted by Ek If 2quot 1 is prime then the Euclidean number Ek is perfect Ifn is an even perfect number it is of the form 2k3912k 1 where 2quot 1 is prime Example Problems What is E5 E 2 1 E5 2539125 1 2 25 1 1631 396 What is El E 2k1x2k1 k E1 2H21 12 21 1 11 1 Mersenne Primes A number of the form 2quot 1 is called a Mersenne number and is denoted by M k If Mk is prime then Ek is perfect If c k then ME M k If k is composite then Mk is composite But if M k is composite then is k composite Example Problems What number can be multipied by M 89 to produce a perfect number A perfect number has the form 2k3912k 1 where 2quot 1 is a Mersenne number If 2quot 1 is prime then 2k3912k 1 is perfect M 89 239 1 and it must be multiplied by 239391 288 to yield a perfect number So 2 239 1 is a perfect number What odd number can be multipied by 212 to produce a perfect number A perfect number has the form 2k3912k 1 So 2 213 14096s19133550336 is a perfect number Number Theory and Cryptography Examples Set Theory Relation A set of ordered pairs is called a relation In symbols this can be written as follows plp xy x1232 xyny A relation designates a set of ordered pairs Relation ny The set of values of the first component of the ordered pairs in a relation is called the domain of the relation and is designated as DomR xlEly ny xlEly xye R The set of values of the second component of the ordered pairs in a relation is called the range of the relation and is designated as RngR ylElxny ylElxxye R Here R means the given relation not the set of real numbers Relation Inverse Given any relation we can define its inverse by reversing each ordered pair The inverse of R usually designated by Rquot In general we define the inverse of a relation as follows 13 1 xyny xyyx E R Relation A relation R is called reflexive on a set A if and only if Vxxe A gtxRx A relation R is called symmetric if and only if Vx v y ny gt ny A relation R is called transitive if and only if Vx v y v z ny yRZ gt sz Relation A Relation between1 andB ny ADomR Func on A function f A gt 5 f is not 11 f is not unto 1quot f0 x 11 injection Function A mction f A E f is not onto 1 x A Since fis a 11 function an inverse function f1 exits Onto surjection Function Afunctinn fAB fisnutll Ffx 11 Onto bijection Function A function f A B f is a bijection Ff 1 Infinite Sets Russell s Paradox Damn barbers It could have worked But set theory has some flaws especially when it comes to infinite The paradox considers a town with a male barber who shaves daily every man who does not shave himself and no one else Such a town cannot exist If the barber does not shave himself he must abide by the rule and shave himself If he does shave himself according to the rule he will not shave himself httpenwikipediaorgwikiBarbegparadox http p1usmathsorgissueZOXfile The real Russell s paradox cont Consider the setM to be quot The set of all sets that do not contain themselves as membersquot Does M contain itself lIf it does it is not a member of M according to the de nition 20n the other hand if we assume thatM does not contain itself then it has to be a member of M again according to the very de nition of M Therefore the statements quotM is a member of Mquot and quotM is not a member of Mquot both lead to contradictions A set of sets of bananas A set of bananas The set of all the sets of bananas contains itself bananal banana35 htt wwwtutor i comenc clo edia etdefnfs ke wordsRussell39s aradox htt Wwwtutor i comenc clo edia etdefnfs ke wordsBarber aradox Paradoxes of Infinity Because set theory is conter intuitive sometimes we better get familiar with it so that we can understand the roots of computer science and develop new mental tools to navigate around when solving problems httpplat0stanfordeduentriesparadoxzeno Zeno s paradox Achilles and the Tortoise How many parts are there in a nite object mm 12 14 18 Zizo 12i 1 Infinity Hilbert s Hotel I No Vacancies f 1 Infinity E No Vacancies 2 Infinity Infinity Remember the Hotel Infinity So the even numbers are as many as the natural numbers Or N E even if E is a proper subset of N Infinity What about sets being quotIargerthanquot N For example Z the set of all integers l1012 The onetoone correspondence bijection here is 1 2 3 4 5 6 O 1 1 2 2 3 which is given by fn n2 if n even n12 if n odd So the integer numbers are as many as the natural numbers Or N W even ifN is a proper subset of Z ll Infinity What about Q the set of all rational numbers ie fractions which is clearly much bigger than N L runern rqJ film l quotl39i rH r 39 39h x J lra 1 x a x Ll e ILo quotx 393 2 4 r H I v leg e Ircs x 39 Mm 411 rtx L mlm 411 Ls39Ilw CirQ wll l39 I t Infinity The bijection here is 1 2 3 4 5 6 11 12 21 31 22 13 So also the rational numbers are as many as the natural numbers Or N Q even if Q is a proper subset of N ll Infinity The results so far N W IEvean IZI IQI What about R the set of all real numbers What is its cardinality Maybe the whole R is too BIG so why don t we start with the interval 01 which is a subset of R and try to see if we can de ne a bij ection from natural numbers onto O1 Infinity Cantor s diagonalization The COMPLETE list of Great Mathematicians GEB De Morgan Abel Boole Brouwer Sierpinski Weirestrass Infinity The diagonal reads Dboups1gtCantor But Cantor was not in the list Hence the list was not complete Can we extend this idea to infinite lists or sets Infinity Cantor s diagonalization We can try and make a list of all the real numbers in 01 and give each one an index a natural number 0000000000000000000000000 01204832092002000283932 023430054500000123090050 0260380505005031930960329 030805040530313093273920 CDU lbOONA O50389325540760985939282 Infinity Is this list complete We can try to show a real number that is not in the table To do that we take the diagonal of the table 0013009 0000000000000000000000000 011204832092002000283932 0123430054500000123090050 01680380505005031930960329 0305805040530313093273920 CDU lbOONA 0 510389325540760985939282 Infinity Then we change each digit with the next digit 1gt2 This number cannot be in the table 9gt0 0013009 gt 0124110 0000000000000000000000000 011204832092002000283932 O123430054500000123090050 O1680380505005031930960329 0305805040530313093273920 KKKXKK CDU lbOONA 0510389325540760985939282 0124110 0124110 0124110 0124110 0124110 0124110 Infinity Conclusion It is impossible to make a complete list of real numbers in 01 and count them with natural numbers Using the diagonalargument we can show that the list is never complete so Real numbers even the interval 01 are MORE lNFlNTE than natural numbers So we can say that N N0 lt N1 R I N1 is also called the continuum I Cantor s Theorem LetA be any cardinal number with reference set A and let S be the set of all subsets of A lfS is the cardinal number that represents the size of S then A is smaller than S There are infinitely many different sizes of infinity The Continuum Hypothesis If a set has size N0 then the set of its subsets the power set has size N1 More generally if a set has size anor some n then the set of all its subsets has size NM The Continuum Hypothesis The Continuum Hypothesis remains undecided to this day despite 100 years of effort Three Foundations and their corresponding philosophies Logicism realism Intuitionism conceptualism Formalism nominalism The Failure of Logicism The purpose of logicism was to show that classical mathematics is part of logic to show that all classical mathematics known in their time can be derived from set theory from Principia Mathematica or ZF Since at least two axiom of infinity and axiom of choice out of the nine axioms of ZF are not logical propositions in the sense of logicism it is fair to say that this school failed by about 20 in its effort to give mathematics a firm foundation The Failure of Intuitionism The second crisis was in the failure of the intuitionistic school to make intuitionism acceptable to at least the majority of mathematicians Mathematics is the mental activity which consists in carrying out constructs one after the other As a result several theorems and axioms are ruled not valid since they are not constructible Law of the excluded middle Fixed Point Theorem of Topology All classical math cannot be constructed The Failure of Formalism The quotHilbert programquot was the idea was to formalize the various branches of mathematics and then to prove mathematically that each one of them is free of contradictions In fact if by means of this technique the formalists could have just shown that ZF is free of contradictions they would thereby already have shown that all of classical mathematics is free of contradictions since classical mathematics can be done axiomatically in terms of the nine axioms of ZF The Failure of Formalism In 1931 Kurt Godel showed that formalization cannot be considered as a mathematical technique by means of which one can prove that mathematics is free of contradictions Godel s theorem says in nontechnical language quotNo sentence of L which can be interpreted as asserting that T is free of contradictions can be proven formally within the language Lquot Kurt Godel 1940 Proved that the Continuum Hypothesis is consistent with the axioms of set theory Assumption that the Continuum Hypothesis is true will not lead to any contradictions within set theory Paul Cohen 1963 Proved that the assumption Continuum Hypothesis is false will not lead to any contradictions within set theory It may be treated as a separate axiom that provides information not found in the other axioms of set theory M124 Logic Lecture 9 Equivalence relations on sets Function between sets Types of function Relations Suppose A 0123 An example of a relation on A is lt This relation is defined by the set R 0lt1 0lt2 0lt3 1lt2 1lt3 2lt3 or equivalently R 01 02 03 12 13 23g AgtltA So a relation on A is a subset of R g A x A Equivalence relations A relation is an equivalence relation on a set S if and only if a a for every a eS reflexive If ab then ba ab eS symmetric If ab and bC then aC transitive abc ES If is an equivalence relation and ab then we can say that a is equivalent to b Examples 8 is the set of all people in the UK R1 Xy e S Xy if and only ifX and y are the same age This is an equivalence relation on 8 R2 Xy e S Xy if and only ifX and y own a copy of the same book This is not an equivalence relation Why R3Xy e S Xy if and only ifX and y both own a copy of War and Peace This is an equivalence relation on S Partitions Suppose A is a set A partition P ofA is a set of subsets of A P P1PN such that anPmZ if n m P1UP2UUPN A Partitions example 131132133 IS a partition 9 of S P 131132133 n0t a partition P1P2P3isnot P20P3 Q a partition PIUngP3 S Partitions amp Equivalence Relations 1 Let be an equivalence relation on A For aeA let Pa be the set of elements of A which are equivalent to a e Pa b EA ba P PaaeA is a partition ofA Partitions amp Equivalence Relations 2 Let PPa be a partition of A Define an equivalence relation on A by ab if and only if both a and b belong to Pa for some a is an equivalence relation on A Partitions amp Equivalence Relations 3 So for a set A there is a onetoone correspondence between Equivalence relations on A Partitions ofA Relations More Terminology Let A be a set R a relation on A The domain of R domA is the set domAa 3ba b eR The range of R rangeA is the set rangeAb Eaab eR If R is a relation on A then the inverse relation R397 is given by R1ba a beR Example Let S be the set of all people in the world Define a relation R on S by leyES then XyE R if and only ifX and y are siblings The domain of R is the set of all people who have brothers or sisters The range of R is the same as its domain Example 2 Let S be the set of all people in the world Define a relation R on S by IfXyES then XyE R if and only ifX is y s younger sibling The domain of R is the set of all people who have an older brother or sister The range of R is the set of all people who have a younger brother or sister Example 3 S 1 479 Define a relation R on S by IfXy e S then XyE R ifand only ifX lt y The domain of R is 147 The range of R is 479 ls R an equivalence relation Functions You probably have preconceived ideas of what a function is fXX22X2 fXsinX fXeXpX These are all functions which associate a member X of R unambiguously with another member fX of R They can all be written in settheoretic notation as f XfX X e R FuncTion more examples Some functions require more care fXlogX only defined for X gt O f X fX X e R Xgt0 g ImmAwM xo x Examples conTinued fX1X Not defined when X 1 f X fX X e R X 0 Functions Also X and fX need not be members of the same set For example consider the function positive square root fXgtO then flexg eeaXialued function OthenNise fis a complexvalued function Functions A function f from a set A to a set B is a subset of PAgtltB such that if a1b1efand 32b2ef then 6317532 This ensures that fis welldefined As before domfa 3babef rangeAb EaabeR If aedomf then there is a unique berangef such that abef In this case we normally write fab Func rions If fis a function from A to B and Adomf then we write fAaB Functions In formal mathematics it is important to take care with this notation in particular to be sure about the domain and range in the definition of a function fR R fx J is not welldefined f0oo R f x 5 positive root is a well defined function f Re C fx J is a welldefined function and is different from either of the previous func ons Special Types of FuncTion Let fAeB be a function fis called a surjection or fis onto if VbbeB3aaeAfab fis called an injection or fis 11 one toone if fa1bfa2bgta1a2 fis a bijection if and only if fis 11 and onto fis a surjection and an injection Special Types of FuncTion E E f not 11 or onto f 0nt0 but HOt 11 WI m f 11 and onto bijection f E but not onto Isomorphism If AeB is a bijection then A and B are basically the 5 same set 5 Mathematicians say that A and B are f 1391 and onto him isomorphic Examples Let A 01 23 and B abcd The function fA gt B defined by Oa1b2c3d is a bijection The sets A and B are isomorphic B is just a re Iabelled version ofA More examples Well defined Injection Surjection BUec on f R gt R fX cosX f R gt 11 fX sinX f Tc7c gt 11 fX sinX f R gt R fX IogX f R gt R fX 1XifX 0 f0 O f N gt Z fn n2 ifn is even fnn12 ifn is odd The Image of a Subset A and B sets f39A a B be a function Suppose XgA Xis a subset of A Then fX is the subset of B defined by fXbfX b for some XEX called the image ofX under f A X f fX The InverseImage of a Subset A and B sets fA a B a function Suppose YgB Y is a subset of B Then f391Y is the subset ofA defined by f391Yafay for some ye Y Ca w e inverse39 of Yunder f Inverse Functions A B sets f39A a B a function f ab39 bfa aeA Is f397 ba39 bfa aeAa function In order for f 7 to be a function if bae f 7 and bCe f 7 then ac ie if abe f and Cbe f then ac ie fmust be 11 Inverse Functions In other words if AeB then the inverse function f 7fAeA exists if and only if fis 11 If fAB and fis 11 then f 7BeA exists In other words f 7BeA exists if and only if f is a bijection In this case f 7 is also a bijection and A and B are isomorphic Cor39dinolify Revisited Recall that for a finite set Aa1an the cardinality ofA is simply the number of members which A has In this case An For infinite sets the notion of cardinality is more complex But if two infinite sets A and B are isomorphic then surely AB Summary of Lecture 8 Relations on sets Equivalence relations and partitions Introduction to functions Injections or 11 functions Surjections or onto functions Bijections Cardinality revisited M124 Logic Lec rure 6 Analysis of argumen rs continued Mor39e example proofs For39malisa rion of argumen rs in natural language Pr39oof by con rr39adic rion Logical Consequence Le r I be a set of formulae and f a formula f is a logical consequence of I if for39 any assignment of Tr39u rh values To a romic pr39oposi rions for39 which all of The members of 1 True 1 is also Tr39ue If f is a logical consequence of 1 wife cIgtIf NoTe This is consis ren r wi rh If when 1 is a Tau rology ArgumenTs An argumenT consisTs of A seT I of formulae called The assumpTions or hypoTheses A formula 1 called The conclusion If IIf Then The argumenT is a m argumenT In oTher words an argumenT is valid if iTs conclusion is a logical consequence of iTs assumpTions NoToTion An in rui rive way To write on orgumen r wi rh o se r of hypo rheses I and conclusion 1 is as follows h otheses 1 YD conclusion Example proof 4 Show Tha r is a valid argument q Proof 4 1 p v q 2 p A l 3 r 4 p v r from 2 I I r 2 Ip fI39OI 6 r gt p from 5 7 Ip gt q from 1 8 r gt q from 6 and 7 9 q from 8 and 3 AlTernaTive proof p v q 1 p A l 2 r 3 q Assume ThaT The conclusion is false ie q is False Therefore p musT be True from 1 BuT p and r cannoT boTh be True by 2 Therefore r is false BuT This conTradicTs 3 so assumpTion musT have been wrong Proof by ConTrodicTion This is an example of proof by conTr39odicTion Basic idea is Assume ThoT The conclusion is false Use This To deduce o conTr39odicTion Hence The conclusion musT be Tr39ue Proof by Con rmdic rion Pr39oof by contradiction is ono rher39 powerful Technique To show Tho r on orgumen r is valid 39Pr39oof by con rr39odic rion39 is also known as reduc 0 ad absurdum Recac 0 ad Absurdum You39ve already me r 39proof by con rr39adic rion39 as a rule of deduc rion pgtI 1 This is also known as 39Rea ucfo ad Absurdum39 24415 Dl 50d 0 0M mat1 10 lLQSQJd 5J2quau g apt1 Jan121 91214 mat1 papaum 5014 624 22w 214 1 achaJazi 9Jl539 Dl5390d a mu 5 mat1 z asapup u pauucyu uaaq axing Vl 5J2quau pan 4 ua5ad 5J2quau g 4502 w 2J0 mat1 4014 papA Odd 2 won 5 1 auxon 5 4 para aaLmIpp Ll pauucyu 2J0 5J2quau p z asp0 am up 5w 22w 211 U2LUI15JV un to sgsAIDuv IdenTificoTion of oTomic proposi rions A romic propositions are m fbe mee ng fakes place a a members have been informed in advance 1 fbere are of leasf 15 members presem q fbe mee ng is quorafe p fhere is a posfa sfrl39ke Formalisa rion of assumpTions The mee fng can fake place if a members are informed In advance and if is quorafe becomes a q gt m I f is quorafe pro Vl39ded fnaf fnere are af leasf 15 members presen f and members will have been Informed In advance if fnere 539 nof a posfa sfrke becomes39rgtqA pgta Formalisa rion of assumptions con rinued So ltIgtaAqgtmTgtq pgt 0 These are The assumptions FormolisoTion of conclusion The orgumen r concludes Therefore if ve mee ng was canceled fvere were fewer fvcm 15 members presem or fvere was a posfa sfrl39ke which becomes m gt 39r v p Sof mgt 39rvp Is f a logical consequence of I Formal noTaTion In our39 formal no ra rion The argument becomes aAqgtm tgtq pgta Is This argumen r valid 2 assumptions a A q gt m gtqA pgta 1conclusion m gt n v p 5 a romic pr39oposi rions implies 25 32 different alloca rions of Truth values To a romic pr39oposi rions Proof by ConTradicTion Proof by contradiction Assume IIf is false Then There is an allocaTion of Tr39uTh values To aTomic pr39oposiTions for39 which all of The formulae in I are Tr39ue buT f is false called a counTerexample Show ThaT The exisTence of a counTer39 example leads To a conTr39adicTion eg ThaT one of The formulae in I musT be false Proof by conTr39adicTion is NOT where you prove Tha r some rhing is ne by proving Tha r if is falsequot Example Pr39oof Tha r 5 is no r a rational number Example Proof by Con rmdic rion 1 Suppose There exis rs an assignmen r of rr39u rh values To m a 1 q and p such ThaT aAqgtmandfqA pgta ar39e bo rh True bu r m z n v p is false 2 Im 2 I39l39 V p is false Then m mus r be True and n v p mus r be false Proof conTinued 3 IT follows ThaT m is false T is True and p is false 4 Now consider The firsT formula in Igtnamely TgtqA pgt 0 5 Since This is True T 2 q and p gt a musT boTh be True 6 Hence a and q are True because T and p are True from above Proof conTinued 7 Finally consider The second formula in 1 namely a A q gt m 8 Since q is True and a is True from 6 on The previous slide a A q is True 9 Hence m musT be True 10 BuT This conTradicTs The asserTion ThaT m is false in parT 3 on The previous slide Summary In summary we have shown Tha r The exis rence of an assignment of Tr39u rh values for39 which I is True and f is false leads To a con rr39adic rion Hence such an assignmen r canno r exis r Hence Igtlf wag07m 5 A10an 6205 55 21 paJSXQ bunMun 21071 aq eta1 ou 5014 2421 71 24071 24211 39pua up 01 away zou VI pJOVl 211 39pua up 0 away VI pJOVl 21 J0 palSjX2 bunMun adogaq eta1 0 0M mat1 J21l2 LIan 4 32110 5 A10an 6205 55 21 1 z aldumxa IdenTificoTion of oTomic proposi rions A romic pr39oposi rions b ve big bang fheory is correcf 139 fhere was a me before anyfvng eXsfea w ve world will come 7 0 an end Formal s ro remen r of premises b gt 139 v w IW For39mol s ro remen r of conclusion 139 gt b Proof by conTr39adicTion Formally if d b gt 1 v w w 1 is f z b Is if The case Tha r d I f 7 Assume Tha r f is not a logical consequence of q Then There is an assignment of T and F To The a romic pr39oposi rions such Tha r each formula in d is True and f is false Proof conTinued 1 If T 2 b is false Then T is True and b is false Hence T is false and b is True 2 Now use The facT ThaT by assumpTion b 2 T v w is True 3 Since b is True T v w musT be True 4 BuT T is false Hence w musT be True This conTradicTs asserTion ThaT w is True 5 Hence I I f Summary In summary we have shown Tha r The exis rence of an assignment of Tr39u rh values for39 which I is True and f is false leads To a con rr39adic rion Hence such an assignmen r canno r exis r Hence Igtlf Adequacy A seT of pr39oposiTional connecTives is adequaTe if For any seT of aTomic pr39oposiTions p1pN and For39 any Tr39uTh Table for39 These pr39oposiTions There is a formula involving only The given connecTives which has The given Tr39uTh Table Adequacy The goal of The nex r lec rur39e will be To show Tha r The se r m A v gt is adequa re and con rains redundancy in The sense Tha r i r con rains subse rs which are Themselves adequa re We shall also in rr39oduce o rher39 se rs of adequa re connec rives Summary More analysis of arguments Pr39oof by contradiction Birth of the Mathematical Spirit The mathematics that existed before Greek times has already been characterized as a collection ofempirical conclusions Its formulas were the accretion of ages of experience much as many medical practices and remedies are today Though experience is no doubt a good teacher in many situations it would be a most inefficient way of obtaining knowledge Fortunately there is a method of reasoning that does guarantee the certainty of the conclusions it produces The method is known as deduction Let us consider some examples If we accept the facts that all apples are perishable and that the object before us is an apple we must conclude that this object is perishable As another example if all good people are charitable and if I am good then I must be charitable And if I am not charitable lam not good Again we may argue deductiver from the premises that all poets are intelligent and that no intelligent people deride mathematics to the inevitable conclusion that no poet derides mathematics It does not matter in so far as the reasoning is concerned whether we agree with the premises What is pertinent is that if we accept the premises we must accept the conclusion Unfortunately many people confuse the acceptability or truth of a conclusion with the validity ofthe reasoning that leads to this conclusion From the premises that all intelligent beings are humans and that readers ofthis book are human beings we might conclude that all readers ofthis book are intelligent The conclusion is undoubtedly true but the purported deductive reasoning is invalid because the conclusion does not necessarily follow from the premises A moment39s re ection shows that even though all intelligent beings are humans there may be human beings who are not intelligent and nothing in the premises tells us to which group ofhuman beings the readers of this book belong Deductive reasoning then consists of those ways of deriving new statements from accepted facts that compel the acceptance of the derived statements We shall not pursue at this point the question ofwhy it is that we experience this mental conviction What is important now is that man has this method of arriving at new conclusions and that these conclusions are unquestionable if the facts we start with are also unquestionable Deduction as a method of obtaining conclusions has many advantages over trial and error or reasoning by induction and analogy The outstanding advantage is the one we have already mentioned namely that the conclusions are unquestionable if the premises are Truth if it can be obtained at all must come from certainties and not from doubtful or approximate inferences Second in contrast to experimentation deduction can be carried on without the use or loss of expensive equipment Before the bridge is built and before the longrange gun is red deductive reasoning can be applied to decide the outcome Sometimes deduction has the advantage of being the only available method The calculation of astronomical distances cannot be carried out by applying a yardstick Moreover whereas experience confines us to tiny portions of time and space deductive reasoning may range over countless universes and aeons V th all of its advantages deductive reasoning does not supersede experience induction or reasoning by analogy It is true that 100 per cent certainty can be attached to the conclusions of deduction when the premises can be vouched for 100 per cent But such unquestionable premises are not necessarily available No one unfortunately has been able to vouchsafe the premises from which a cure for cancer could be deduced For practical purposes moreover the certainty deduction grants is sometimes super uous A high degree of probability may suffice For centuries the Egyptians used mathematical formulas drawn from experience Had they waited for deductive proofthe pyramids at Giza would not be squatting in the desert today Each ofthese various ways ofobtaining knowledge then has its advantages and disadvantages Despite this fact the Greeks insisted that all mathematical conclusions be established only by deductive reasoning By their insistence on this method the Greeks were discarding all rules formulas and procedures that had been obtained by experience induction or any other non deductive method and that had been accepted in the body of mathematics for thousands of years preceding their civilization It would seem then that the Greeks were destroying rather than building but let us withhold judgment forthe present Why did the Greeks insist on the exclusive use of deductive proof in mathematics Why abandon such expedient and fruitful ways of obtaining knowledge as induction experience and analogy The answer can be found in the nature oftheir mentality and society The Greeks were gifted philosophers Their love of reason and their delight in mental activity distinguished them from other peoples The educated Athenians were as much devoted to philosophy as our smartset is to nightclubbing and preChristian fthcentury Athens was as deeply concerned with the problems of life and death immortality the nature of the soul and the distinction between good and evil as twentiethcentury America is with material progress Philosophers do not reason as do scientists on the basis of personally conducted experimentation or observation Rather their reasoning centers about abstract concepts and broad generalizations It is dif cult after all to experiment with souls in order to arrive at truths about them The natural tool of philosophers is deductive reasoning and hence the Greeks gave preference to this method when they turned to mathematics Philosophers are moreover concerned with truths the few immaterial wisps of eternity that can be sifted from the bewildering maze of experiences observations and sensations Certainty is the indispensable element of truth To the Greeks therefore the mathematical knowledge accumulated by the Egyptians and Babylonians was a house of sand lt crumbled to the touch The Greeks sought a palace built of ageless indestructible marble The Greek preference for deduction was surprisingly a facet of the Hellenic love for beauty Just as the music lover hears music as structure interval and counterpoint so the Greek saw beauty as order consistency completeness and definiteness Beauty was an intellectual as well as an emotional experience Indeed the Greek sought the rational element in every emotional experience In a famous eulogy Pericles praises the Athenians who died in battle at Samos not merely because they were courageous and patriotic but because reason sanctioned their deeds To people who identified beauty and reason deductive arguments naturally appealed because they are planned consistent and complete while conviction in the conclusions offers the beauty oftruth It is no wonder then that the Greeks regarded mathematics as an art as architecture is and though its principles may be used to build warehouses Another explanation of the Greek preference for deduction is found in the organization of their society The philosophers mathematicians and artists were members of the highest social class This upper stratum either completely disdained commercial pursuits and manual work or regarded them as unfortunate necessities Work injured the body and took time from intellectual and social activities and the duties of citizenship Famous Greeks spoke out unequivocally about their disdain of work and business The Pythagoreans an influential school of philosophers and religionists we shall soon meet boasted that they had raised arithmetic the tool of commerce above the needs of merchants They sought knowledge not wealth Arithmetic said Plato should be pursued for knowledge and not fortrade Moreover he declared the trade of a shopkeeper to be a degradation for a freeman and wished the pursuit of it to be punished as a crime Aristotle declared that in a perfect state no citizen should practice any mechanical art Even Archimedes who contributed extraordinary practical inventions cherished his discoveries in pure science and considered every kind of skill connected with daily needs ignoble and vulgar Among the Boeotians there was a very decided contempt for work Those who defiled themselves with commerce were excluded from state of ce for ten years The Greek attitude toward work might have had little in uence on their culture were it not for the fact that they did possess a large slave class to whom they could 39pass the buck39 Slaves ran the businesses did the households did unskilled and technical work managed the industries and practiced even the most important professions such as medicine The slave basis of classical Greek society fostered a divorce of theory from practice and the development of the speculative and abstract side of science and mathematics with a consequent neglect of experimentation and practical applications In view of the eschewal of commerce and trade by the Greek upper class certainly a contrast to the preoccupation ofour highest social class with nance and industry it is not hard to understand the preference for deduction lfa person does not 39live39 in the world about him experience teaches him very little Similarly in orderto reason inductively or by analogy he must be willing to go about and observe the real world Experimentation would certainly be alien to thinkers who frowned upon the use of the hands Since the Greeks were not idlers they fell quite naturally into the mode of inquiry that suited theirtastes and social attitudes Nevertheless Greek insistence on deductive reasoning as the sole method of proof in mathematics was a contribution of the first magnitude lt removed mathematics from the carpenter39s tool box the farmer39s shed and the surveyor39s kit and installed it as a system of thought in man39s mind Man39s reason not his senses was to decide thenceforth what was correct By this very decision reason effected an entrance into Western civilization and thus the Greeks revealed more clearly than in any other manner the supreme importance they attached to the rational powers of man The exclusive use of deduction has moreover been the source of the surprising power of mathematics and has differentiated that subject from all other fields of knowledge In particular therein lies one sharp distinction between mathematics and science for science also uses conclusions obtained by experimentation and induction Consequently the conclusions of science occasionally need revision and sometimes must be thrown overboard entirely whereas the conclusions of mathematics have stood for thousands of years even though the reasoning in some cases has had to be supplemented Had the Greeks done no more to the character of mathematics than to convert it from an empirical science into a deductive system of thought their influence on history would still have been enormous But their contributions only began there A second vital contribution of the Greeks consisted in their having made mathematics abstract Earlier civilizations learned to think about numbers and operations with numbers somewhat abstractly but only in the unconscious manner in which we as children learned to think about and manipulate them Geometrical thinking before Greek times was even less advanced To the Egyptians for example a straight line was quite literally no more than either a stretched rope or a line traced in sand A rectangle was a fence bounding a eld V th the Greeks not only was the concept of number consciously recognized but also they developed arithmetica the higher arithmetic or theory of numbers at the same time mere computation which they called logistica and which involved hardly any appreciation of abstractions was deprecated as a skill in much the same way as we look down upon typing today Similarly in geometry the words point line triangle and the like became mental concepts merely suggested by physical objects but differing from them as the concept ofwealth differs from land buildings and jewelry and as the concept of time differs from a measure ofthe passage ofthe sun across the sky The Greeks eliminated the physical substance from mathematical concepts and left mere husks They removed the Cheshire cat and left the grin Why did they do it Surely it is far more difficult to think about abstractions than about concrete things One advantage is immediately apparent the gain in generality A theorem proved about the abstract triangle applies to the gure formed by three match sticks the triangular boundary of a piece of land and the triangle formed by the Earth sun and moon at any instant The Greeks preferred the abstract concept because it was to them permanent idea and perfect whereas physical objects are shortlived imperfect and corruptible The physical world was unimportant except in so far as it suggested an ideal one man was more important than men The strong preference for abstractions will be evident from a briefglance at the leading doctrine of Greece39s greatest philosopher Plato was born in Athens about 428 BC of a distinguished and active Greek family at a time when that city was at the height of her power While still a youth he met Socrates and later supported him in the defense ofthe aristocracy39s leadership of Athens When the democratic party took power Socrates was sentenced to drink poison and Plato became persona non grata in Athens Convinced that there was no place in politics for a man of conscience of course politics was different in those days he decided to leave the city After traveling extensively in Egypt and visiting the Pythagoreans in lower ltaly he returned to Athens about 387 BC where he founded his academy for philosophy and scienti c research Plato devoted the latter forty of his eighty years of life to teaching writing and the making of mathematicians His pupils friends and followers were the greatest men of his age and of many succeeding generations and among them could be found every noteworthy mathematician of the fourth century BC There is Plato maintained the world of matter the Earth and the objects on it which we perceive through our senses There is also the world of spirit of divine manifestations and of ideas such as Beauty Justice Intelligence Goodness Perfection and the State These abstractions were to Plato as the Godhead is to the mystic the Nirvana to the Buddhist and the spirit of God to the Christian Whereas our senses grasp the passing and the concrete only the mind can attain the contemplation ofthese eternal ideas It is the duty of every intelligent man to use his mind toward this end for these ideas alone and not the daily affairs of man are worthy of attention These idealizations which are the core of Plato39s philosophy are on exactly the same mental level as the abstract concepts of mathematics To learn how to think about the one is to learn how to think about the other Plato seized upon this relationship In order to pass from a knowledge of the world of matter to the world of ideas he said man must prepare himself Light from the highest realities reside in the divine sphere blinds the person who is not trained to face it He is to use Plato39s own famous gure like one who lives continually in the deep shadows ofa cave and is suddenly brought out into the sunlight To make the transition from darkness to light mathematics is the ideal means On the one hand it belongs to the world of the senses for mathematical knowledge pertains to objects on this Earth It is after all the representation of properties of matter On the other hand considered solely as idealization solely as an intellectual pursuit mathematics is indeed distinct from the physical objects it describes Moreover in the making of proofs physical meanings must be shut out Hence mathematical thinking prepares the mind to consider higher forms of thought It purifies the mind by drawing it away from the contemplation of the sensible and perishable to the eternal The path to salvation then to the understanding of Truth Beauty and Goodness led through mathematics This study was an initiation into the Mind of God In Plato39s words 39 geometry will draw the soul towards truth and create the spirit of philosophy For geometry is concerned not with material things but with points lines triangles squares and so on as objects of pure thought Arithmetic too said Plato 39has a very great and elevating effect compelling the soul to reason about abstract numbers and rebelling against the introduction ofvisible ortangible objects into the argument He advised 39the principal men ofour State to go and learn arithmetic not as amateur but they must carry on the study until they see the nature of numbers with the mind only39 To sum up Plato39s position a modicum of geometry and calculation suf ce for practical needs however the higher and more advanced portions tend to lift the mind above mundane considerations and enable it to apprehend the nal aim of philosophy the idea of the Good For this reason Plato recommended that the future philosopherkings be trained for ten years from the age of twenty to the age of thirty in the study of the exact sciences arithmetic plane geometry solid geometry astronomy and harmonics In his stress on mathematics as a preparation for philosophy Plato spoke not merely for his followers and or his generation but for the whole classical Greek age The Greek preference for idealizations and abstractions expressed itself in philosophy and mathematics It showed itselfjust as clearly in art Greek sculpture of the classical period dwelt not on particular men and women but on ideal types plates and II This idealization extended to standardization of the ratios of the parts of the body to each other No finger or toenail was overlooked in Polyclitus39 prescriptions ofthese ratios The modern practice in beauty contests of awarding the prize to the girl whose measurements most closely approximate an established standard is a continuation ofthe Greek interest in an ideal gure The Greeks put their stamp on mathematics in still another way that has had a marked effect on its development namely by their emphasis on geometry Plane and solid geometry were thoroughly explored A convenient method of representing quantities however was never developed nor were ef cient methods of reckoning with numbers Indeed in computational work they even failed to utilize techniques the Babylonians had created Algebra in our present sense of a highly ef cient symbolism and numerous established procedures for the solution of problems was not even envisioned 80 marked was this disparity of emphasisthat we are impelled to seek the reasons for it There are several We mentioned earlierthat in the classical period industry commerce and finance were conducted by slaves Hence the educated people who might have produced new ideas and new methods for handling numbers did not concern themselves with such problems Why worry about the use of numbers in measurement ifone doesn39t measure or in trading ifone dislikes trade Nor do philosophers need the numerical dimensions of even one rectangle to speculate about the properties ofall rectangles Like most philosophers the Greeks were stargazers They studied the heavens to penetrate the mysteries of the universe But the use of astronomy in navigation and calendar reckoning hardly concerned the Greeks of the classical period For their purposes shapes and forms were more relevant than measurements and calculations and so geometry was favored Of these forms the circle and sphere suggested of course by super cial observation ofthe sun moon and planets received the major share of attention Hence their astronomical interests too led the classical Greeks to favor geometry The twentieth century seeks reality by breaking matter down witness our atomic theories The Greeks preferred to build matter up For Aristotle and other Greek philosophers the form ofan object is the reality to be found in it Matter as such is primitive and shapeless it is significant only when it has shape It is no wonder then that geometry the study of forms was the special concern ofthe Greeks Finally it was the solution of a vital mathematical problem that drove the Greek mathematicians into the camp of the geometers Irrational numbers We have already spoken of the fact that the Babylonian civilization as well as earlier ones used integers and fractions The Babylonians were familiar also with a third type of number which arose though the application ofa theorem on right triangles When most people describe the Greek contributions to modern civilization they talk in terms of art philosophy and literature No doubt the Greeks deserve the highest praise for what they bequeathed to us in these elds Greek philosophy is as alive and signi cant today as it was then Greek architecture and sculpture especially the latter are more beautiful to the average educated person ofthe twentieth century than the creations of his own age Greek plays still appear on Broadway Nevertheless the contribution of the Greeks that did most to determine the character of presentday civilization was their mathematics By altering the nature ofthe subject in the manner we have related they were able to proffer their supreme gift This we proceed to examine What is Geometry The nature and interrelationship of various geometries Having evolved from antiquity from often used methods for measurement of figures drawn mainly on plain surfaces the methods and principles became distilled for ready reference and use as mathematical propositions particularly in Greece in the peace and prosperity of the few centuries following the rule of Pericles Then Euclid in around 300 BC gathered improved and systematically wrote down all that was known in Geometry to his day The work called The Elements attempted to develop Geometry from the firm foundation of axioms and succeeded in great measure to provide rigorous demonstrations proof of the mathematical results loosely proved by his predecesors While most of the proofs in Euclid39s work were correct blemishes were discovered in some proofs one of which being the very first proposition in the Elements However these blemishes were not due to erroneous deduction but tacit assumptions or quotintuitively obviousquot facts that were not justified by the axioms Considerations of these blemishes culminated in 1899 AD with David Hilbert39s proposal ofa revised axiom system that would not only preserve the validity of the proofs in the Elements but which was in conformity with the modern notion of the axiomatic method as proceeding from a set of undefined terms definitions and the axiom statements on the undefined terms The Euclidean Geometry of today is the Geometry based on this revised axiom system or other equivalent systems since proposed The beauty of Euclid39s version of Geometry Although Euclid39s axioms needed to be revised to make all his proofs correct Euclid39s Geometry remained for two millenia as the example and model of the deductive method of mathematics But the beauty of Euclid39s Geometry is that it does not make use of numbers to measure lengths or angles or areas or volumes Instead it deals with points lines triangles circles and the relationships among these Neutral Geomet Euclid39s axioms without the fifth which is the parallel axiom often referred to simply as the Fifth or Hilbert39s axioms without Euclid39s Fifth is today called Neutral Geometry In this geometry the most important theorem is the Exterior Angle Theorem that the measure of the exterior angle of a triangle is greater than either of the non adjacent interior angles Compare this to the case in Euclidean Geometry which is Neutral Geometry Euclid39s Fifth axiom In Euclidean Geometry the measure of the exterior angle is equal to the sum of the measures of the nonadjacent interior angles The weak looking Exterior Angle Theorem of Neutral Geometry implies the Alternate Interior Angle Theorem That is if two lines are intersected by a transversal such that a pair of alternate interior angles formed are congruent then the lines are parallel This theorem has the immediate corollary that two lines perpendicular to the same line are parallel This gives the following theorem which can be said to be the culminating result of Neutral Geometry Theorem There is at least one line parallel to a given line through a point not on that line PROOF Let y be a straight line and P a point not on y From P draw line m perpendicular to y and line n perpendicular to m This construction is possible in Neutral Geometry By the previous corollary to the Alternate Interior Angle Theorem the line n is parallel to the line y QED An important result of Neutral Geometry is also that the angle sum in a triangle is atmost two right angles The corresponding situation in Euclidean Gemoetry is that the angle sum in a triangle is two rig ht angles Hyperbolic Geometry In the two millenia since Euclid the greatest ongoing mathematical discussion was not on the blemishes in some of Euclid39s proofs but on the independence of the Fifth Axiom of Euclid which meant that given a line and a point not on it exactly one line can be drawn through the point and parallel to the line Gauss Bolyaiand Lobachevsky separately and independently discovered the new geometry Hyperbolic Geometry that assumed the negation of the Fifth Axiom This established the independence of the Fifth axiom of Euclidean Geometry and laid to rest the longest discussion in the history of mathematics to that date The Geometry of Ren Descart s Even as the discussion on the Parallel Postulate of Euclid was raging on Ren Descart s in the year 1637 discovered that the ruler and compass constructions of Euclidean Geometry correspond to the solution of linear and quadratic equations in algebra on a Real Cartesian Plane constructed as follows Apoint is an ordered pair of real numbers The set of all such pairs is the Cartesian Plane The set of points a0 is called the x axis and the set of points 0b is called the y axis The intersection of these axes is called the origin A line in this plane is the subset defined by an equation of the form ax by c 0 with a and b not both zero Descart s gave the followng four constructions using compass and unmarked ruler starting with line segments a and b to contruct ab ab ab and xa Since these suffice to construct the solution of linear and quadratic equations all construction problems of Euclidean Geometry can be done in his Cartesian Plane Since this geometry in the Real Cartesian Plane satisfies all the axioms of Hilbert it follows that the Cartesian Plane is Euclidean Geometry using numbers The method of solution used in finding points from given points in the Real Cartesian Plane is called Analytic Geometry But Analytic Geometry is not a Geometry in the sense of a theory like Euclidean Geometry that is derived from an axiom set Rather Analytic Geometry is a method of doing geometry problems using algebra In this sense Analytic Geometry is like Trigonometry which is a method of doing geometric problems involving angles The geometry taught today in school is a confused mixture of Euclid39s and Descartes39 But the teacher is not to blame The geometer of antiquity drew diagrams on the Euclidean Plane that was the sand surface The teacher in the classroom uses the blackboard to represent the Euclidean Plane The blackboard is also used to represent the real Cartesian Plane The theorems of Euclidean Geometry can be proved either in the Euclidean Plane or algebraically using numbers in the Cartesian Pane This encourages us to think that the Cartesian Plane and the Euclidean Plane are equivalent Not so While all theorems in the Euclidean Plane can be proved algebraically in the Cartesian Plane there are theorems in the latter that can not be proved in the Euclidean Plane Examples are Desargues Theorem and Pappus Theorem Geometries defined over Fields We have seeen that the Real Cartesian Plane satisfies all the axioms of Euclidean Geometry The word quotRealquot is important here The points in the Cartesian Plane we discussed were ordered pairs of real numbers The set of Real Numbers is an example of an algebraic structure called a eld So we could ask if we can use any field in place of the Real Numbers It turns out depending on the field only some of the Hilbert axioms may hold in the associated Cartesian Plane However all of these various Cartesian Planes provide various geometries A natural question to ask is this What are the fields whose associated Cartesian Planes give exactly Euclidean Geometries It turns out that the smallest such field is obtained from the set of rational numbers by adjoining square roots as well as the addition multiplication and square roots of the rationals 2 The resulting field is called a Hilbert39s Field and the Cartesian Plane associcated with this field is called a Hilbert Plane Finite Geometries These are systems comprising a finite number of points and satisfying some of the axioms of Euclidean Geometry An example is Fano Geometry Elliptic Geometry A non Euclidean Geometry is a Geometry that has the negation of the Parallel Postulate as one of its axioms An example is hyperbolic geometry It turns out that hyperbolic geometry allows more than one parallel line through a point off a given line Elliptic Geometry allows no parallel line to a given line The name quotellipticquot is misleading for it has no direct connection with the curve called ellipse The name is used as an analogy of the following result quotA central conic is called an ellipse or hyperbola according as it has no asymptote or two asymptotes Analogously a non Euclidean plane is said to be elliptic or hyperbolic according as each of its lines contains no point at infinity or two points at infinityquot1 A model of Elliptic Geometry is the surface of a sphere with great circles as lines and antipodal points identified Note that if Elliptic Geometry allows no parallel lines it can not have Neutral Geometry inside it as is the case with hyperbolic geometry For in Neutral Geometry we have the Alternate Interior Angle Theorem which implies that there is at least one parallel line through a point off a given line If we can not have Neutral Geometry as part of Elliptic Geometry we ask what axiom of Neutral Geometry is requiring the existence of parallel lines Since the Alternate Interior Angle Theorem of Neutral Geometry makes parallel lines necessary we investigate its proof We noted above that its proof depended on the Exterior Angle Theorem So we ask quotwhat does the proof of the Exterior Angle Theorem depend onquot It turns out it relies on three major components triangle congruence angle addition and plane separation Since triangle congruence and angle addition are at the core of geometry we do not seek to modify these The remaining candiate for removal is plane separation So we remove those axioms that imply plane separation That would result in a geometry where we are able to pass from one side of a line to the other without crossing the line And that is the geometry on the surface of the sphere with great circles as lines Since the model identifies antipodal points on great circles it is called a single elliptic geometry Affine Geometry Affine Geometry takes for its axioms only Euclid39s axioms I and II This Geometry is motivated by the fact that its results hold not only in Euclidean Geometry but also in Hyperbolic Geometry and the Minkowskian Geometry of time and space The propositions that hold in Affine Geometry are those that are preserved by parallel projection from one plane to another 1 for example the first 28 propositions of Euclid then 29 and 33 45 and some others in books III1 192528 30 IV4 9 and VI12491024 26 Since Affine Geometry is built on only two of the axioms of Euclidean Geometry the latter is a specialization of Affine Geometry Projective Geomet This is the parent of all infinite geometries above in that one can get all those geometries by appropriate restrictions and modifications of projective geometry For instance an Affine Plane can be obtained from a Projective Plane by picking out any line in the latter and requiring all other lines to meet this line at a unique point with the provision that any two parallel lines will meet the special line is a single point The line so picked out is called the quotline at infinityquot Not that this does not mean that the line is situated at infinity but is forced to behave as though it is The projective geometry in the plane begins with the following four axioms 1 There exists at least one line 2 Every line contains at least three points 3 Any two distinct points lie on a unique line 4 Any two lines meet in at least one point 5 There exist three noncollinear points The most elegant property of projective geometry is the principle of duality which means that every definition remains relevant and every theorem remains valid when we consistently interchange the words point and line and simultaneously interchange lie on and pass throughjoin and intersection collinear and concurrent etc1 To establish the duality it suffices to verify that the axioms imply their own duals As a result given a theorem and its proof we immediately can assert the dual theorem It is a useful exercize to verify that the dual of an axiom is itself either an axiom or a theorem derivable from the remaining axioms The purpose of our discussion was just to give a view of the various geometries and how they are related We rest our discussion of geometries here REFERENCES 1 Coxeter HSM Introduction to Geometry John Wiley Inc 1989 2 Hartshorne Robin Geometry Euclid and Beyond SpringerNew York 2000 GRT httpwwwmathpathorgconceptsgeometrieshtm The Normal Distribution and Other Continuous Distributions Topics The normal distribution The standardized normal distribution Evaluating the normality assumption The exponential distribution Continuous Probability Distributions Continuous random variable Values from interval of numbers Absence of gaps Continuous probability distribution Distribution of continuous random variable Most important continuous probability distribution The normal distribution The Normal Distribution Bell shaped Symmetrical Mean median and mode are equal Interquartile range equals 133 0 Random variable has infinite range The Mathematical Model 1 2 X M l f X W e f X density of random variable X 7r314159 62271828 y population mean 039 population standard deviation X value of random variable 00 lt X lt oo 5 Many Normal Distributions There are an infinite number of normal distributions By varying the parameters 6 and u we obtain afferent normai distributions 6 Finding Probabilities Pmb biii w Which Table to Use An infinite number of normal distributions means an infinite number of tables to look up Solution The Cumulative Standardized Normal Distribution Normal Distribution Table Portion 5080 Cumulative Standardized Shaded Area Exaggerated 5438 5832 871 0 I 6217 6255 Z 012 Only One Table is Needed 9 Standardizing Example EMEQEQEZ Standardized Normal Distribution Normal Distribution 7le Example P 29ng 711664 20221 a M Standardized 7 Normal Distribution Normal Distribution 010 J 7 G gt U t 0 J C O J l k N

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.