of 2

Blackboard Notes 1 | Mathematical Logic | Psychology & Cognitive Science

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Some notes for class
  Blackboard Stu ff  : 1  /  30 and 2  /  1 M  /  PHL 344K 1. Two principles of naive set theory:(a)  Extensionality : Twosetsareidenticalifandonlyiftheyhaveexactlythe same members. ã ∀ x ∀  y ( x  =  y  ↔ ∀  z (  z  ∈  x  ↔  z  ∈  y )(b)  Comprehension : Given any property P, or any open sentence S inone free variable, there is a set of all and only things having P, orsatisfying S. ã ∃ x ∀  y (  y  ∈  x  ↔  S (  y ))(For the cognoscenti: this is an axiom schema, and hence speci-fiesaninfinitesetofaxioms(oneforeachopensentenceSinourpreferred logical language).)2. A contradiction in naive set theory: ã  Let S be the open sentence  x    x . Then by Comprehension, ∃ x ∀  y (  y  ∈ x  ↔  y    y . By instantiating  y  to  x , we get the contradiction  ∃ x ( x  ∈ x  ↔  x    x ).3. The standard revised axiomatization of set theory (we didn’t go over thisin class, and won’t really need these details, but here they are, in caseyou’re interested):(a)  Extensionality : twosetsareidenticalifandonlyiftheyhaveexactlythe same elements. (As before.)(b)  Pairing : Given any two sets  x  and  y , there is a set  { x ,  y } .(c)  Union : Given any set  x , there is a set of all members of members of  x .(d)  Restricted Comprehension : Given any set  x  and any open sentence S , there is a set of all members of   x  that satisfy  S .(e)  Infinity : There is an infinite set.(f)  Replacement : Given any set  x  and function  f  , there is a set of theimages of the members of   x  under  f  .(g)  Foundation : Every (non-empty) set contains a member with whichit has an empty intersection.1  (h)  Power Set : Given any set  x , there is a set of all subsets of   x .(i)  Choice : Given any set  x , there is a set that contains exactly onemember of every non-empty member of   x .4. Some properties of binary relations (in class, these were given treating  R asasetoforderedpairs. HereIgivethemtreatingRasabinarypredicate):(a)  Reflexive :  ∀ x Rxx (b)  Irreflexive :  ∀ x ¬ Rxx (c)  Symmetric :  ∀ x ∀  y ( Rxy  →  Ryx )(d)  Asymmetric :  ∀ x ∀  y ( Rxy  → ¬ Ryx )(e)  Antisymmetric :  ∀ x ∀  y (( Rxy ∧ Ryx )  →  x  =  y )(f)  Transitive :  ∀ x ∀  y ∀  z (( Rxy ∧ Ryz )  →  Rxz )(g)  Intransitive :  ∀ x ∀  y ∀  z (( Rxy ∧ Ryz )  → ¬ Rxz )5. Equivalence relations:(a) AnequivalencerelationonAisabinaryrelationonAthatisreflexive,symmetric, and transitive.(b) Given an equivalence relation R on A, the  equivalence classes  gen-erated by R are sets of the form  { b  :  b  ∈  A ∧  Rab } , for each  a  ∈  A .(c) A  partition  on A is a collection of non-empty subsets of A which arepairwise disjoint and collectively exhaustive of A.(d)  Fact1 : If  R isanequivalencerelationonA,thenthesetofequivalenceclasses generated by  R  form a partition of A.(e)  Fact 2 : If   P  is a partition of   A , the relation  being in the same partitionelement as  is an equivalence relation on A.(f)  Fact 3 : If   R  is an equivalence relation, then the equivalence relationgenerated by the partition generated by  R  is  R . And if   P  is a parti-tion on  A , then the partition generated by the equivalence relationgenerated by  P  is  P .2
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks