MAT 215 Class Notes sanjum September 2016
I 09/15/2016
I.1 Logic Astatementis something that can be assigned a logical value of True or False
Operations:
{AND:^
{NOT::
{OR:_
Logic Tables:
P Q :P P^Q P_Q
T T F T T
T F F F T
F T T F T
F F T F F
Implication / Conditional: "if A, then B" =A)B, which is true UNLESS A is T AND B is F If A is F, then isA)Bis true?Negated Implication: ":(A)B)"
Same asA^(:B)
Equivalence / Biconditional:A()B(need two proofs)
A if and only if (i) B (A)B,B)A)
Converse:B)A
Logic Tables for These Operations:
P Q P)Q P()Q Q)P:Q) :P:(P)Q)
T T T T T T F
T F F F T F T
F T T F F T F
F F T T T T F
1 1 / 4
Proof by contradiction: To prove thatA)B, assume that A and (not B) is true, and arrive at a contradiction (so basically C and [not C]), so that:(A)B) is F, so that A)Bis T
Logical Quantiers:
{9: Existential = there exists (at least one)
{8: For all
{Ex. IfP x=xis human andMx=xis mortal, then (8x)P x)Mxsays that all objects that are humans are mortal {Ex. If we also addNxxdrinks coee, then (9x)P x^Nxsays that there exist humans that drink coee
DeMorgan's Law (Negation of Logical Quantiers):
{:(P^Q)()(6P)_(6Q)
{:(P_Q)()(:P)^(:Q)
{:[(8x)P x]()(9x)[:(P x)] {:[(9x)P x]()(8x)[:(P x)] I.2 Set Theory Asetis a collection ofelements A set of axioms should be logically independent of each other
Some axioms:
{:A=B()(8x) (x2A),(x2B), sof1;1;2g=
f1;2g
{:ABif8x2A;)x2B
{: (AB)^[(9x2B)^(x =2A)]
{: Given a set S and a logical rule / specication P,
fx2SjP xgis a set (subset of S).
{: Let S be a collection of sets. Then there exists a set called the
unionthat's denoted asB= S A2F
- Basically, (8x)x2B()(9A2Fs.t.x2A)
Just b/c you can dene something doesn't mean it's a set, but if you start w/ a set and a denition / rule, then you still have a set. For instance, given a set S,fx2Sjx6=xg !?, which is a set by the specication axiom (you have to write down that something is a set by the specication rule!!!)
Theorem:f?g 6=?!! Make the distinction b/w an elementxand a set w/ an element
fxg."The set of all sets is not a set." Use a contrapositive to prove it??Theorem: LetFbe a nonempty collection of sets. Then there exists a set B denoted as B= T A2F
As.t. (8x) (x2B)()(8A2F:x2A).
2 2 / 4
Use the specication axiom to prove that something is a set. For instance, here we can say that "sinceFis not empty, there exists at least one elementA2F, so using the specication axiom we getfx2Aj8A2F; x2Agis a set You need to show that ifAA2Fand we dene ~
B=fx2Aj8A2F:x2Ag, need to
show thatB ~ BAND ~ BB
II 09/20/2016
Axioms:
{: GivenSa set, andPa logical rule, thenfx2S:P xgis a set
{ :A=Bif and only if (8x)x2A()x2B
{ : GivenSa collection of sets, there exists a setBcalled the union of the
sets inS, dened by:x2B()(9A2S:x2A) (B= [ A2S A)
Intersection(theorem): Given a non-empty collection of setsS( has at least one
setS), there exists a setB, called the intersection of the sets inS, that's dened by:
x2B()(8A2S:x2A)
The specciation rule, equality rule, and union rule all constituteaxiomsb/c they are all independent on each other and cannot be proven / disproven, but the statement about intersections is atheoremb/c it assumesSis nonempty, and relies on the specication rule (an axiom) to construct a set
Disjoint(a denition):AandBaredisjointifA\B=?
{Thedierenceof setsAandB, denoted asAnB=fx:x2A; x =2Bg
{Thesymmetric dierenceofAandBis denoted asA4B= (AnB)[(BnA)
A\(B[C) = (A\B)[(A\C) (so call left sideXand right sideY):
{Prove thatXYandYX {x2X!(x2A)^(x2B[C)!(x2A)^[(x2B)_(x2C)]!(x2A^x2 B)_(x2A^x2C)!(x2A\B)_(x2A\C)!XY
Axiom of the Cartesian Product: Given two setsAandB, there exists a setAB
which consists of all ordered pairs (a; b) witha2Aandb2B
{Wrote:AB=f(a; b)ja2A; b2Bg
{Ex. For setsA=f0;1g; B=fcat;dogg, we see thatAB=f(0; cat); (0; dog); (1; cat); (1; dog)g {Notice that none of the pairs start w/ an elementb(in this case, animals); the ORDERED part is very important
{Remark: IfAhasmelements, andBhasnelements, thenABhasmnelements
(but both sets must be nite)
Relation(a denition): ArelationRb/w setsAandBis any subset ofAB
{Ex.R=f(0; cat); (1; dog)g {(a; b)2R {A relation issymmetricif (a; b)2R)(b; a)2R
3 3 / 4
{A relation isreexiveif8A2A;(a; a)2R {A relation istransitiveif for (a; b)2R^(b; c)2R)(a; c)2R {Ex. ForA=f0;1g, anRdened onAAisf(0;0); (1;0); (0;1)g
Equivalence relation: It is a relationRon a setAAwhich is symmetric, reexive,
and transitive is called ((a; b)2Ris sometimes denoted asab)
Equivalence classofa: Given an equivalence relationRonAand an elementa2A,
dene [a]R=fb2A: (a; b)2Rg
{Given a set of natural numbersA=f0;1;2; :::g 2N,abifaborbais even {Then, [1]R=fall the odd natural numbersg;while [0]R=fall the even natural numbersg {For now, we are treating the equivalence class as a set
Proposition: IfRis an equivalence relation onAA, anda1; a22A, theneither
[a1]R= [a2]Ror[a1]R\[a2]R=?(below is the proof):
1.a12[a1]Rsince (a1; a1)2R, a22[a2]Rsince (a2; a2)2R.Thus, if [a1]R= [a2]R, thena22[a1]R!a22[a1]R\[a2]R6=?
2.a1]R\[a2]R=?, then [a1]R\[a2]R6= ?) 9b s:t:b2[a1]R; b2[a2]R 3.a1; b)2R, (a2; b)2R)(b; a2)2R!(a1; a2)2R
We claim that [a1]R= [a2]R:
{To prove, let's takec2[a1]R. This means that (a1; c)2R;(a2; a1)2R, so (a2; c)2R)(c; a2)2R!c2[a2]R {To prove, takingc2[a2]R, we get (a2; c)2R;(a1; a2)2R!(a1; c)2R!c2 [a1]R
Partition(a denition): ApartitionofAis a collection of setsSwith the properties
that:
{ S B2S B=A {IfB1; B22S, then eitherB1=B2orB1\B2=?Function(a denition): Given two setsAandB, afunctionf:A!Bis a relationF onAB(a subset ofAB) with the property that (a; b1)2F^(a; b2)2F)b1=b2 {In other words,adoesn't HAVE to have an elementbassociated w/ it, but ifahas a bassociated w/ it, it has only one (acan be single, but ifadates,adates only once) {Ex.A=f1;2;3;4;5g; B=f1;2;3;4;5g, we haveF=f(1;2); (2;3); (3;4); (4;5)g {f(x) =x+ 1, but you need to specify a relation, which implicitly species a domain Domain(a denition): Given a functionFAB(so a functionf:A!B), the domainoff=fx2Aj9b2Bs.t. (a; b)2Fg
Range(a denition): therangeoff=fb2Bj9a2As.t. (a; b)2Fg
The domain / range are denotated by (a; b)2F()f(a) =b
- / 4