CMSC 250 Lecture Notes - Lecture 7: Subset, Empty Set

• School: University of Maryland
• Department: Computer Science
• Course: CMSC 250
• Professor: William Gasarch

Document Summary

To prove an existential statement true: find one number that works. Prove false: prove (cid:4666) (cid:1876) (cid:4667)[ (cid:1828)(cid:1864)(cid:1853) (cid:1876)] is false: if finite, scan entire domain and so for no x in d does blah(x) hold, if d is infinite that is the point of the course! Prove true: similar to proving existential statement false: proving universal statements true is pretty much all of math. Examples: there exists an even number that can be written in two ways as a sum of two prime numbers. 5,3,7 are all prime numbers: there exists an integer (cid:1863) such that (cid:884)(cid:884)(cid:1875)+(cid:883)(cid:890)(cid:1877)=(cid:884)(cid:1863) Then (cid:884)(cid:1863)=(cid:884)(cid:884)(cid:1875)+(cid:883)(cid:890)(cid:1877) by distribution: for all real numbers, if (cid:1853)(cid:2870)=(cid:1854)(cid:2870), then (cid:1853)=(cid:1854) Let (cid:1853)=(cid:883) and (cid:1854)= (cid:883). (cid:1853)(cid:2870)=(cid:1854)(cid:2870)=(cid:883), but -1 is not equal to 1. A set is a collection of distinct elements. A is a subset of b if all the elements of a can also be found in b: b is automatically a superset of a.