math
Mon 01/22/07
Tue 01/23/07
chap 1.1
a proposition is a declarative sentance that is true or false but not both.
ex: today is Jan. 23rd.
statement == proposition
ex: Mohammad was born on a thursday.
true, false, difficult to determine.
2 + 2 = 4 -->
2 + 3 = 7 --> false proposition
x+2 = 5 --> open sentence -- not a proposition.
This sentence is false. --> not a proposition. example of a paradox.
Neither true or false - you get a contradiction.
kinds of propositions
--------------
1) atomic - simple -- you can't break it up into furthur propositions
2) compound - can be broken up.
to produce compound propositions, we use logical connections
Def 1.2 Given propositions P and Q, the _conjunction_ of P and Q, denoted P /\ Q is true exactly when both P is true and Q is true.
ex: Today is Tuesday and the temperature in Green BAy is less than 80 degrees.
Today is Tuesday and 2+3=7. --> false because the 2nd part is false.
Today is Wednesday /\ 2+3=7. --> false!
Truth tables
write possibilities in order
P Q P /\ Q
T T T
T F F
F T F
F F F
conjuction.
Def 1.3 - Given propositions P and Q, the _disjunction_ of P and Q, written P \/ Q is the proposition "P or Q"
P or Q is true exactly when at least one of P or Q is true.
Truth Table
P Q P \/ Q
T T T
T F T
F T T
F F F
inclusive OR.
Today is Tuesday or 2 + 2 = 5. -> true.
The two halves don't have to be related as far as logic is concerned.
Today is Wednesday or 2+2=4 --> true.
Today is Wednesday or 2+2=5 --> false.
Today is Tuesday or 2+2=4. --> true.
Def 1.4 - Given a proposition P, the negation, denoted ~P, is the proposition "not P"
~P is true exactly when P is false.
Truth Table
P ~P
T F
F T
~(Today is tuesday) --> false because P was true.
Propositional form - ex: P or Q.
P \/ /\ Q -- Makes not sense -- in order to use a connector, you have to have propositions on both sides. So this is not a well-formed formula.
Find truth tables for (P and Q) or R
P Q R P & Q (P & Q) or R
t t t t t
t t f t t
t f t f t
t f f f f
----------
f t t f t
f t f f f
f f t f t
f f f f f
(P \/ R) /\ (Q \/ R)
P Q R (P | R) & (Q | R) *
t t t T t t
t t f t t t
t f t t t t
t f f t f f
f t t t t t
f t f f t f
f f t t t t
f f f f f f
Same truth tables -- so these two propositional forms are equivalent.
Def. 1.5 - Two propositional forms are equivalent iff they have the same truth tables.
Show that P is equivalent to ~~P
P P ~(~P) final
T T F T
F F T F
the two truth tables are identical. the law of double negation.
Def. 1.6
A denial of a proposition S is any proposition equivalent to ~S.
ex: S : Math 250 is hard.
~S : It is not the case that math 250 is hard.
That's the negation.
A useful denial (denial in english that you'd actually use) : Math 250 is not hard.
Consider the proposition "the water is cold and the soap is not here"
Let C be the proposition "the water is cold"
and H being "the soap is here"
(make it positive)
C /\ ~ H
Negation is ~( C /\ ~ H).
It is not the case that the water is cold and the soap is not here.
This sentence is ambiguous. Pause at the right places to remove ambiguity.
IN logic we use delimiters (), [], {}
~(C /\ ~H)
~[ C /\ (~H)] - correct but extra work -- Order of Operations --> ~ before /\ before \/ .. but no one remembers the /\ and \/ rule -- use delimiters to avoid any ambiguity.
Find the truth table for P \/ ~P
P P \/ ~P
T T F --> T
F F T --> T
Def. 1.7
tautology a propositional form that is true for every assignment of truth values to its components.
Some have names -- this one's called the law of the excluded middle. either something is true or its negation is true.
Def. 1.8 - a contradiction - is the negation of a tautology -- so truth table would be all false.
for friday: p.8 : 1 (thru l (not *)
2 -> b d f h j
3 (non stared)
4 d f j l
5 non starred
7
10 non starred thru k
12 b
write out and staple.
due 2:00 on friday.
Thu 01/25/07
Def. 1.9.
given the propositions P and Q, th3e conditional sentence P => Q (P implies Q), is the proposition "if P, then Q"
P antecedent
Q consequent
P=>Q is true whenever P is false or Q is true.
Truth table
P Q P=>Q
T T T
T F F
F T T
F F T
P - you get 90%
Q - i give you an A
"am i lieing to you or not?"
if you don't get 90% and i give you an A, then its true.
If 2+2=5, then 2*3=6.
there doesn't have to be any connection between antecedent and consequence.
Def 1.9.1 - P=>Q is equivalent to ~P \/ Q
P Q ~P \/ Q
T T F T
T F F F
F T T T
F F T T
the columns are the same in the truth table.
Suppose you know that P=>Q is true. Suppose you also know that P is true. What about Q? Q is true. This logical process is called modus ponens -- a method of establishing the truth of Q.
If 2+2=5, then the high temperature in Green Bay in January 1st, 1237 was 17 degrees.
True because P is false.
this statement is said to be vacuously true. true because the antecedent is false. Truth but totally worthless.
other conditionals.
Def 1.10
For propositions P and Q, the converse of P=>Q is Q=>P.
The contrapositive is ~Q=>~P
The inverse is ~P=>~Q
converse - interchange
contrapositive - interchange and negate
inverse - negate both.
Therum 1.1 (a)
The propositional form P=>Q is equivalent to its contrapositive ~Q=>~P
(b) P=>Q is not equivalent to Q=>P.
How would you prove part a? -- Truth tables.
truth tables -- easy but important
Proof by truth tables.
Def. 1.11 For propositions P and Q, the biconditional sentence written P<=>Q is the proposition "P iff Q". The sentence P<=>Q is true exactly when P and Q have the same truth values.
Truth table
P Q P<=>Q
T T T
T F F
F T F
F F T
what if we had two propositional forms on each side.
Note:
two propositional forms are equivalent iff the biconditional connecting them is a totalogy
the propositional form P is equivalent to Q iff P<=>Q is a totology.
a statement con always be replaced by an equivalent statement.
ex: 3x +2 = 17 -- true iff 3x=15 -- and that's true iff x=5.
"ex:" x^2 = x iff x=1 works backwards but not forwards. could be 0.
have to make sure they're equivalent.
Therum 1.2
For propositions P and Q
(a) P<=>Q is equivalent to (P=>Q) /\ (Q => P)
(b) ~(P/\Q) is equivalent to ~P\/ ~Q
(c) ~(P \/ Q) is equivalent to ~P /\ ~Q
b & c are called DeMorgan's Laws.
(d) ~(P=>Q) is equivalent to P /\ ~Q -- use this a lot. "definition of conditional" (?)
(e) ~(P /\ Q) is equivalent to P => ~Q
(f) P /\ (Q \/ R) is equivalent to (P /\ Q) \/ (P /\ R) -- distributive
p \/ (Q /\ R) is equivalent to (P \/ Q) /\ (P \/ R)
-- distributive
P/\Q is eqv. Q /\ P
i) P \/ Q is eqivelent to Q \/ P
j) P /\ (Q /\ R) is = to (P/\Q) /\R
k) P\/ (Q \/ R) is = to (P \/ Q) \/ R -- associative.
"prove the associative law for conjunction."
ex: If f is differentiable, then f is continous.
in letters
D = f is differentiable.
C = f is continous
D => C.
ex:
Suppose a, b, and p are integers.
"If p is a prime number that divides ab, then p divides a or P divides b."
P = p is prime
Q = p divides ab
R = p divides a
S = p divides b
(P /\ Q) => (R \/ S)
making proofs easier -> recognize the form, then use various techniques.
homework due tuesday:
p. 17-18
1 - non starred thru i
4 -
5
6 - a & e
8 - (don't get really deep -- put letters in .. see book)
13 - b & i
Fri 01/26/07
P is a necessary condition for Q
make sense out of it
anytime Q is true, P has to be true
Q => P
Q implies P.
P is a sufficient condition for Q.
P => Q.
P is necessary and sufficient for Q
P <=> Q .
Quantifiers
x ≥ 3 . not a proposition
It becomes a proposition if x is replaced by a particular value.
example of an open sentence. / predicate.
Def. 1.12 An open sentence is a sentence containing one or more variables.
ex: x≥ 3 is an open sentence "predicates something about the variables"
P(x) - open sentence with variable x.
with restrictions on the values the variable can take.
ex x^2 + 2 - needs a verb! .. so not an open *sentence*
x[1] + x[2] + ... x[n] = 3 open sentence P(x[1] . . . x[n])
can be true or false depending on what you plug in.
x^2 =1 - find the truth set.
the truth set depends on the universe of discourse.
given a universe of discourse, two open sentences are equivalent if they have the same truth sets.
ex: x+5 = 7
x = 2
these are equivalent for any universe.
x^2 = 1 and x =1
no if the universe is all real numbers.
yes if the universe is all positives.
sometimes depends on the universe.
P(x) - not a proposition.. could be true or false.
P(a) - is a proposition for any little a in the universe. - take a particular value.
another way to make a proposition out of an open sentence is..
Def 1.13 (Quantifiers)
a) The sentence ( upsidedown-A x) P(x) is read
"for all x P(x)."
"for every x, P(x)"
and is true iff the truth set for P(x) is the entire universe.
upsidedown-A -> universal quantifier.
b) The sentence (backwards-E x) P(x) is read
there exists x such that P(x)" and is true iff the truth set for P(x) is non-empty -- has at least one element.
backwards-E - existential quantifier.
ex: Suppose the universe is the set of all real numbers.
upsidedown-A
( for every x) (x^2 +3x =0)
false -- plug in 1!
there exists x (x^2 +3x =0)
true - plug in zero.
there exists x (x^2 = -1)
false in our universe
but true if the universe includes imaginary numbers.
We all use math everyday.
X - > people universe
Y - > days
(for every X) (for every Y X) uses math on day Y
all apples have spots.
universe - fruits
A(x) x is an apple
S(x) x has spots
for every x [A(x) /\ S(x)] -- that says that all fruit is spotted apples.
(for every x) [A(x) => S(x)]
everybody loves somebody.
universe - people
(for every x)(there exists a y)(x loves y).
(for every x)(there exists a y)(y loves x). - for every person, there is someone who loves them.
(there exists y)(for every x)(y loves x) - there is someone who loves everyone
(there exists y)(every x)(x loves y) - there is somebody who is loved by everybody.
Nobody loves everybody
~(there exists x)(for every y)( x loves y)
x ∈ A (x is an element of set A).
consider the following:
"every x ∈ A has property P"
(for every x)(x ∈ A) => P(x)
(for every x ∈ A) P(x)
likewise,
there exists x such that x ∈ A and P(x)
(there exists x ∈ A) P(x)
Def 1.14
(a) Two quantified sentences are equivalent (for a particular universe) iff they have the same truth vales. <- doesn't really help much.
Mon 01/29/07
but = and, but with surprise.
Def 1.14
(a) -- was Friday
(b) Two logical forms of quantified sentences are equivalent iff their truth values are the same for every meaning of their open sentences and every possible universe.
example: (for every x)(p(x))/\ Q(x))
(for every x) ((Q(x) /\ P(x))
these are equivalent.
Therum 1.3 - "quantifier negation"
If A(x) is an open sentence with variable x, then
(a) the negation (for every x)(A(x)) is equivalent to (there exists x)~(A(x))
(b) ~(there exists x)(A(x)) is equivalent to (for every x)~A(x)
prove part A.
~(for every x)(A(x)) is true iff (for every x)A(x) is false.
iff the truth set for A(x) is not the universe
iff the truth set for ~A(x) is non empty
iff (there exists x)~A(x)
for example
find a useful denial for "All primes are odd"
universe: natural numbers
(for every x)(x is prime => x is odd)
Denial:
~(for every x)(x is prime => x is odd)
now make it useful.
(there exists x)~(x is prime => x is odd) [quantifier negation]
negation of a conditional.
(there exists x)(x is prime)/\ ~(x is odd) [definition of a conditional]
important step!
(there exists x)(x is prime /\ x is even)
f is continuous at a iff
(for every ε) {ε > 0 => (there exists a δ)[δ > 0 /\ (for every x)(|x-a| < δ => | f(x) - f(a)| < ε)]}
if we take some little intervol of radius ε, we can find some δ neighborhood such that no matter what x we pick, if x is in this little interval, then f(x) is with ε of f(a)
find the useful denial.
~(for every ε) {ε > 0 => (there exists a δ)[δ > 0 /\ (for every x)(|x-a| < δ => | f(x) - f(a)| < ε)]}
(there exists ε)~{ε > 0 => (there exists a δ)[δ > 0 /\ (for every x)(|x-a| < δ => | f(x) - f(a)| < ε)]}
(there exists ε){ε>0 /\ ~(there exists a δ)[δ > 0 /\ (for every x)(|x-a| < δ => | f(x) - f(a)| < ε)]}
(there exists ε){ε>0 /\ (for every δ)~[δ > 0 /\ (for every x)(|x-a| < δ => | f(x) - f(a)| < ε)]}
(there exists ε){ε>0 /\ (for every δ)[~δ > 0 \/ ~ (for every x)(|x-a| < δ => | f(x) - f(a)| < ε)]} [demorgan's law]
(there exists ε){ε>0 /\ (for every δ)[~δ > 0 \/ (there exists x)~(|x-a| < δ => | f(x) - f(a)| < ε)]}
now take care of negation of conditional
(there exists ε){ε>0 /\ (for every δ)[~δ > 0 \/ (there exists x)(|x-a| < δ /\ ~ | f(x) - f(a)| < ε)]}
(there exists ε){ε>0 /\ (for every δ)[~δ > 0 \/ (there exists x)(|x-a| < δ /\ | f(x) - f(a)| ≥ ε)]}
(there exists ε){ε>0 /\ (for every δ)[δ > 0 => (there exists x)(|x-a| < δ /\ | f(x) - f(a)| ≥ ε)]} - definition of the conditional
there is some ε that's positive such that no matter what δ you pick, if that δ is positive then there is something x that's within δ units of a that gets mapped more than ε units away.
All mathematicians are brilliant.
"All mathematicians are not brilliant." -- useful denial?
this can have two different meanings.
Not all mathematicians are brilliant.
Def. 1.15
For an open sentence P(x), the proposition (there exists !x)(P(x)) is read "there exists a unique x such that P(x)"
This is true when the truth set has exactly one element in the universe.
(there exists !x) - unique existential quantifier -- close to nilism and the only one in the world.
There exists a unique x such that x is standing -- true -- he's the only one standing.
can fail because there is too many or too few.
For Friday:
p. 26
1 parts c,d,e,f
2 c d e f
4 both parts (even starred)
5
6 (not starred)
7 (not starred)
9 b[not excruciating detail] d/c -- find useful denial for limit statement. -- use ε/δ definition of limit.
12 freebee
Tue 01/30/07
Mathematical Proofs
A theorum is a true statement.
If its true, its a theorum --
"Its snowing outside."
2+2=4 is a theorum.
a pwoof is a complete justification of the truth of the theorum
has to be understandable to anybody - a baby should be able to understand the logic.
the reader of the proof should be one of you classmates.
mathematicians proves theorums -- seaking truth
Proofs use axiums, previous theorums, premises of the theorum, and logic.
every step of a proof should express a complete sentence. (there's ways of abbreviating it but it should express a complete sentence -- no verb -> really worried) bad example: "x+3"
P=>Q is a complete sentence -- "implies" is the verb
some limitations:
- you cannot define all terms. (avoid circular definitions) -- ex: a line is . . .
we need some undefined terms. - some terms that are so self evident that there is no way to define them to make more understandable.
- there are no absolute truths!!!
--> you can't prove everything
there must be some initial set of statements that are assumed true. -- these are called axiums. / postulates.
ex: a+b = b+a
use toughtologys to prove theorums.
Some important ones:
P \/ ~P "Law of the excluded middle"
(P => Q) <=> (~P => ~Q) - contrapositive
(P \/ Q) \/ R <=> P \/ (Q \/ R) (for and as well -- associative laws.
P /\ (Q \/ R) <=> (P/\Q) \/ (P /\ R)
P \/ (Q /\ R) <=> (P \/ Q) /\ (P \/ R)
distributive laws
~ P => Q <=> P ^ ~ Q .. definition of the conditional.
~(P /\ Q)<=> ~P \/ ~Q .. demorgan's law 1.
~(P \/ Q) <=> ~p /\ ~Q demorgan's law 2.
P <=> (~P => (Q /\ ~ Q))
if p is true, then ~ p is false and that implys everything
assuming P is false leads to a contradiction, then P has to be true.
Law of contradiction.
[(P => Q) /\ ( Q => R)] => ( P=> R) - transitive law.
[ P /\ ( P => Q)] => Q Modus ponens
[( P => Q) /\ ~Q] => ~P Modus tollens
[( P \/ Q) /\ ~p] => Q
(P /\ Q) <=> (Q /\P)
(p \/ Q) <=> (Q \/P)
dysjunctive syllogism
ex: (1) if the crime did not take place in the billard room, the col. mustard is guilty.
(2) the lead pipe was not the weapon
(3) either col. mustard is not guilty or the weapon use was the lead pipe.
Prove: the crime took place in the billard room.
Lewis Carroll Puzzle.
C. L. Dodgsen 1831 - 1898 (snc!!!) - mathemetician
come up with names for all the simple propositions and keep things positive.
B: the crime took place in the billiard room.
M: colonal mustard is guilty.
L: lead pipe was the weapon.
(1) ~B => M
(2) ~L
(3) ~M \/ L
Prove B.
(4) (~ M \/ L) /\ ~L by 3, 2, and definition of conjunction.
(5) ~M is true by 4 and dysjunctive syllogism
(6) ~(~B) by 1, 5, and Modus tollens
(7) B (6, Double negation)
(homework friday).
Thu 02/01/07
Methods of Proof
Direct proof.
To prove P =>Q, we assume P, go thru a bunch of steps, and end oup with therefore Q. assume P, show Q.
ex: let x and y be integers. Prove that if x and y are even, then x+y is even.
proof
We suppose x and y are both even.
Thus, x = 2k (even) and y = 2m for some integers k and m.
Therefore x+y = 2k + 2m [reason]
Therefore x+y = 2(k +m)
Therefore x+y is even.
Note: a divides b iff b = an for some integer n.
"a goes evenly into b"
2 divides 6 because 6 = 2*3
a|b "a divides b"
example: suppose a and b are positive integers. If a divides b, then a≤b.
Proof.
Suppose a divides b.
Therefore b = an for some natural number n.
therefore n≥1 by definition of natural numbers
multiply both sides by a
an ≥ a (algebra; a>0)
therefore b ≥ a (substitution)
Q. E. D.
that which had to be shown.
Direct proofs where P or Q are compound.
P=> Q \/ R
what do we need to show?!?
1 strategy
assume P /\ ~Q, show R.
alternate:
assume P /\ ~R, show Q.
x + y is odd implies x is odd \/ y is odd
Suppose x+y is odd and x is even.
x+y = 2k-1 for some integer k.
and x=2m for some integer m.
(only use therefore if it comes from the line immediately above)
y = (x + y) - x (algebra)
therefore, y = (2k -1) - 2m (substitution)
y = 2k-2m-1
Therefore y = 2(k-m)-1 (algebra)
Therefore y is odd. OED
example: (P \/ Q) => R
If the "if" part is a disjunction, then treat cases.
Assume P, show R
AND assume Q, show R
use the line "every case gives R, therefore . . ."
example: (x = 2 or x=-2) => x^2 =4
Proof.
Treat cases
Suppose x = 2, therefore
x^2 = 4
Suppose x = -2
therefore, x^2 = 4
Therefore, both cases give x^2=4.
QED
example:
P => (Q /\ R)
can do in two parts
P=>Q, and P=>R
Another form
(P /\ Q) => R
Assume P and Q.
(assume P and assume Q).
example:
If a|b /\ a|c, then a|(b-c)
suppose a|b and a|c.
therefore b=an for some integer n
and also c=am for some integer m
therefore b-c= an - am (substitution)
b-c = a(n-m) (algebra)
Therefore, a|b-c by definition of |
Another form.
(P=>Q)=>R
do not assume P
(assume P=> Q)
kind of messy but rare
ex: P=>(Q=>R)
Assume P and show Q=>R
Therefore assume Q, and show R
Therefore assume P /\ Q, show R
equivalent to (P/\Q) =>R
contrapositive proof of P=>Q
Suppose ~Q
therefore ~P
therefore P=> Q
ex:
Let m be an integer, prove that if m^2 is odd, then m is odd
Proof.
If try a direct proof - its rough.
Suppose m^2 is odd. -- hard to get from m^2 to m.
try contraposition
Suppose m is not odd.
Therefore m is even.
therefore m = 2k for some integer k.
therefore m^2 = 4 k^2
Therefore m^2 = 2(2 k^2)
Therefore m^2 is even.
Therefore if m is even, then m^2 is even.
Therefore is m^2 is odd, m is odd.
Part of the assignment for Tuesday:
page 37
3 - b c d e
4 - (don't reinvent the wheel)
5 - b c
6 - a b c d
(b: |-1|=1, d: ignore the hint in the back of the book .. use the example on the bottom of 36 and also use part e)
7 - e g
8 -
11 -
page 45
3 b d
4 a
9
12
no letters - all non-starrred.
Fri 02/02/07
Indirect proofs
proof by contradiction
Prove R indirectly
Suppose ~R
// the opposite of what you're trying to prove.
put IP for indirect proof.
Therefore S
therefore ~S
but that is a contradiction (-><-)
therefore R
Prove that the set of primes is infinite
suppose that there are finitely many primes (IP)
Suppose there are k of them.
P[1], p[2], ... p[k]
let n = p[1]p[2]* p[k] +1
n does not equal p[1], p[2], p[k]. --> too big.
therefore n is composite
therefore exists q such that q divides n and q is prime.
therefore q > 1
since q is prime it is one of the p[1] .. p[k]'s .
there q divides a product
p[1]p[2] .. p[k]
therefore q divides n- p[1]p[2] .. p[k])
therefore q divides 1 by substitution
therefore q≤1
-><-
therefore the set of primes in infinite.
prove that √2 is irrational
Proof
when you're trying to prove something negative that's a clue that you should use ip
suppose that √2 is rational (IP)
then √2 = s/t for some integers s and t
therefore 2 = s^2/t^2
therefore 2t^2 = s^2
therefore s^2 is even
s^2 and t^2 are perfect squares.
therefore, they both have an even number of 2's in their prime factorization.
but x^2 = 2t^2
so s^2 has an odd number of 2^s
-><-
therefore √2 is irrational .
Proof by exhaustion
-- example every possible case
two-part proof of p<==>q
First show p=>q
2nd show q=>p
occasionally, you can do both ways at once.
p<=> .. <=>Q
only works if what you're trying to prove is almost exactly a law of logic.
#6e
show that |a|≤b iff -b ≤a≤b, where b ≥ 0.
look at the cases and do the two parts within each case
case 1 a≥0
=>
Suppose |a|≤b
but |a|=a
therefore a≤b
also -b≤0
therefore -b≤a
therefore -b≤a≤b
qed case 1
<= of case 1
Suppose -b≤a≤b
therefore -b ≤ |a| ≤ b
therefore |a|≤b
qed case 1.
case 2 a < 0
=>
Suppose |a|≤b
But |a| = -a, since a<0
Therefore -a≤b
Therefore a≥-b
Therefore -b≤a
But a ≤ 0 ≤ b
a≤b
-b≤a≤b
QED
<=
suppose -b≤a≤b
therefore -b≤-|a|≤b
therefore -b≤-|a|
* -1
therefore b≥|a|
therefore |a|≤b
QED
proofs involving quantifiers.
Proof of (there exists x)P(x)
existance theorums
to show that one exists, you find one
constructive proof
- to show that one exists, find one.
example -- prove that 51 is not prime.
in other words, there exists n)(n≠1 /\ n≠ 51 /\ n|51)
proof
let n=3
3 *17 = 51
qed
Proof of (there exists x)(P(x) without exhibiting an answer.
non - constructive proof
Proof of ~(for every x)P(x)
same as (there exists x)~P(x).
Find a counter example to (for every x)(P(x)) .. if you can find one that doesn't work, then you've found a counter example
example:
~(for every x)(x^2 + x + 41)
let x =41
therefore not prime.
---
more frequently
proof of (for every x)p(x) .
direct proof
Let x be an arbitrary object in the universe
therefore p(x) is true
for example, if x is an even integer, then x^2 is even
(for every x)(x even => x^2 is even)
prove this thing
let x be an even integer.
therefore x = 2k for some integer k
then x^2 = 4k^2
= 2*2k^2
therefore x^2 is even.
Mon 02/05/07
Prove or disprove.
If f is continous at x=0, then f is differentiable at x=0.
(for every f)
f(x)=x^2 is continuous and differentiable at x=0, qed.
no! that's "there exists"
you cannot prove a for every with an example
this is not true for absolute value
to disprove you only need one example -- a counter example.
note f(x) = |x| is continuous at zero but not differentiable.
-><-
so we disproved
to disprove a for every statement, find a example.
disproving can be quicker
proof of (there exists! x)P(x)
1) prove there exists x P(x)
2) prove that there's only one. assume t[1] and t[2] are objects such that P(t[1]) and p(t[2]).
. . . .
therefore t[1] = t[2]
for example:
the real numbers have a unique multiplicative identity.
i) prove that there is 1 .. 1 is a multiplicative identity.
ii) assume that 1 and u are multiplicative identity
1 * u = u (1 is a multiplicative identity)
1 * u = 1 (u is a multiplicative identity)
therefore u =1
multiple quantifiers.
for every natural number n, there is a natural number M such that 2n is less than M.
(for every n)(there exists M)(2n < M)
Proof
let n be any (arbitrary) natural number.
Let M = 2n +1
therefore 2n < M, qed.
what if we turn that around - forget that.
quantifier manipulation.
(for every x)(for every y)P(xy) <=> (for every y)(for every x)P(xy) -- order doesnt matter
(there exists x)(there exists y)P(xy) <=> (there exists y)(there exists x)
3 [(for every x )p(x) or (for every x) q(x) => [(for every x) (p(x) or q(x))]
4 for every x)(p(x) => q(x)) => [(for every x) p(x)(for every x) q(x)]
5 [(for every x)P(x) and q(x)] <=> [(for every x)P(x) and (for every x)q(x)]
6 (there exist x)(for every y)P(xy) => (for every y)(there exists x)p(xy)
if there's 1 x that works for every y , then for every y we can find a x
7 (there exists x)[p(x) or q(x)] <=> [(there exists x)p(x) or (there exists x)q(x)]
these all work
here are things that look good but aren't
(there exists x)P(x) => (for every x)p(x)
there exists tan x such that x is odd does not imply that every x is odd.
2).
(for every x)[P(x) or q(x)] => [(for every x)p(x) or (for every x)q(x)]
x is odd, x is even .. the left side is true -- every x is either odd or even .. but right is false.
3)
[(for every x)P(x) => forevery x)q(x)] => (for every x)[(p(x) => q(x)]
take odd and even again -- doesn't work here -- left is vacuously true right is false.
4) (FOR EVery y)(there exists x)P(xy) => (there exists x)(for every y)p(xy)
left: for every woman woman there is a man that the woman's going out with ..
right side: there's a single guy going out with everybody
if there's a for
5)
[(there exists x)P(x) and (there exists x)Q(x)] => (there exists x)(P(x) and q(x))
example: Prove that the sum of two rational numbers is rational.
for every
let x and y be rational numbers.
therefore x = p/q for some integers p and q
therefore y = a/b for some integers a and b
sum of x and y == x + y = p/q + a/b
pb/qb + aq/qb
(pb + aq)/qb
the top is an integer, the bottom is an integer, therefore x + y is rational.
another example
prove that if x≥1, then (3|x-2|)/x ≤ 4
Proof.
Let x be a real number ≥1
prove (3|x-2|)/x ≤ 4
case 1
x-2 ≥ 0
therefore |x-2| = x-2 and also x≥ 2
(3*|x-2|) / x ≤ 4 is true iff 3|x-2| ≤ 4x
iff 3(x-2) ≤ 4x
iff 3x-6 ≤ 4x
iff -x ≤ 6
iff x ≥ -6
Proof.
Let x ≥2
therefore x ≥ -6
therefore -x ≤ 6
therefore 3x-6 ≤ 4x
therefore 3(x-2) ≤ 4x
therefore 3|x-2| ≤ 4x
therefore (3|x-2|/x) ≤ 4
case 2.
x-2 < 0
therefore x < 2
|x-2| = -(x-2)
scrap work
(3|x-2|/x) ≤ 4
iff 3|x-2| ≤ 4x
iff 3(2-x) ≤ 4x
iff 6-3x ≤ 4x
-7x ≤ -6
x≥ 6/7
let x < 2
(we know x ≥ 1)
therefore x ≥ 6/7
dot dot dot
Thu 02/08/07
|ab| = |a||b|
a, b ≥ 0
|a| = a
|b| = b
ab ≥ 0 , since a,b are ≥ 0.
therefore |ab| = ab
then plug in.
...
case 2
a +, b -
4th case:
a <0, b< 0
ab > 0
so |ab| is ab
|ab| = ab
= (-a)(-b)
= |a||b|
...
|b-a| = |-(a-b)|
= | -1 (a-b)|
= | -1| * | a-b| true by part a
= 1|a-b|
= |a-b|
part d.
-|a| ≤ a ≤ |a|
-|b| ≤ b≤ |b|
add them
-|a|-|b| ≤ a+b ≤ |a| + |b| crazy
problem |a+b| ≤ |a| + |b|
-(|a|+|b|) ≤ a+b ≤ |a| + |b|
|a+b| ≤ |a| + |b| by part e
lewis carroll problems
----------------------
j = john is 16
m = mary is 12
t = john is 6 feet tall
h = harry is 5 feet tall
1. J /\ M
2. T \/ H
3. M => H
4. t => j
prove h
5. M (from 1 and definition of conjunction)
6. M /\ (M => H) (3, 5, definition of conjunction)
7. H (6, modus ponens)
Therum 2.1
a.
For any set A, the empty set is a subset of A.
Proof 1.
scrap work = for every x = x element empty => e element A
Let x be given
x element of empty set implies x element of a -- t or f
true
qed
∈
proof 2 = by contradiction
suppose empty set is not a subset of A
therefore not for every x (x ∈ empty set => x ∈a)
therefore (there exists) ~ (x ∈ empty set => x ∈ a)
therefore (there exists x) (x ∈ empty set) /\ (x ∈ a)
therefore there exists x such that x is an element of the empty set
-><-
Therum 2.1
part b.
For any set B, B ≤ B (is a subset)
Proof
Let x ∈ B
Therefore x ∈ B
therefore B ≤ B
QED.
Therum 2.2
If A ≤ B and B≤ C, then A≤C
Proof.
Suppose A ≤ B and B≤ C
Show A≤ C.
Let x ∈ A
therefore x ∈ B ( because A ≤ B)
therefore x ∈ B
therefore x ∈ C
QED
If A is not a subset of B
A subset of b with the subset crossed out
If is a subset of b and a is not equal to b
then we call A a proper subset.
(A subset (without line) B)
⊂ <-- that's what we want
rounded!!
we include the empty set
Def 2.3 Let A be a set. The power set of A is the set who's elements are the subsets of A.
P(A) = {B: B subset A}
Suppose {A: 1}
P(A) = { empty set, {1} "singleton 1"}
Suppose
A = {1, 2}
P(A) = {empty set, {1}, {2}, {1,2}}
add to assignment
Find
power set of empty set
power set of the power set of the empty set
power set , power set, power set of the empty set
power set, power set, power set, power set of the empty set.
test thru 1.5
Mon 02/12/06
Power sets
set 1
the power set of singleton 1 is the empty set and sington 1
two of them
empty, 1, 2, {1,2}
look at the power set of {1,2,3}
smallest set
{}, {1}, {2}, {3}, 1,2 2,3 1,3 1,2,3
use that idea in doing problem zero.
Therum 2.4
If A is a set with n elements, Power(A) has 2^n elements
Proof.
A = { x[1], x[2], ... x[n]}
we have two choices in making the subsets
2 * 2 * 2* 2
thus, we have 2^n subsets.
therum 2.5 -- let A and B be sets
then A is a subset of b iff power(a) subset of powerset(B)
Proof
=>
suppose A subset of B
show power(a) is a subset of power(B)
take an arbiturary X
let X be element P(A)
(big x because P(A) is a set of sets)
therefore X is a subset of A
therefore x is a subset of b (transitivity)
therefore X is an element of the powerset of B.
QED left to right
<=
Suppose p(a) is a subset of p(b). Show A is a subset of b
Two different methods
a) Note: A is a subset of A
Therefore, a is an element of p(a)
Therefore A is an element of the powerset of b - per assumption
thus A is a subset of b.
qed.
2nd proof
Let X be an element of A
singleton X is a subset of A
so singleton X is a element of the power set B
so x is an element of b
....
Set operations
Def. 2.5
Let A and B be sets.
The union of A and Bis defined by
A ∪ B .. is the set of all x such that x is an element of a or x is an element of B
in other words
x is an eelemtn of A ∪ B <=> (x element of a) or (x element of b)
Def. 2.6 The intersection of A and B is defined by A ∩ B is set of all x such that x is an element of A and x is an element of b
x is an element of A ∪ B <=> x element of a and x element of b
Def 2.7
The difference of A and B is defined by: A - B (or A\B) is the set of all x such that x is an element of A and x is not an element of B
in other words
x is an eelement of A- B iff X is an elemmetn of a and a is not an element of b.
"A without B"
Def. 2.8
If a intersect b = the empty set, we say that a and b are disjunct
Let A = {a, b,c,d,e}
B = {a,e,g}
A ∪ B = {a,b,c,d,e,g}
A ∩ B = {a,e}
unions bigger -- intersections .. smaller
A - B {b,c,d}
B-A {g}
A and B are not disjunct
but A and B-A are
Venn diagrams
You cannot! prove by venn diagrams .. you can verify that something works
O.O
A union B has everything in the circules
A intersect B -- "cat's eye"
A - B - everything in a except the stuff that overlaps
ABC diagram
Therem 2.6
Let A, B, and C be sets
a. A is a subset of A union B.
A union b is an object .. not a statement
the union of two sets is bigger than either one.
can say "by therem 2.6a .... or "definition of union"
b)
A interset B is a subset of A
2.6b -- or definition of intersection
proof
Let x be an element of A interset B
Then X is an element of A and X is an element of B (definiton of intersection)
Therefore X is an element of A (by definition of conjuction)
QED
Tue 02/13/07
Part C
A intersect empty set is empty set
proof of this for homework
part d - a union empty set is a
prove it
-----
def 2.3
defintion we need ahead of time: Two sets are equal iff they have the same elements
ie, A=B iff (A subset of B) /\ (B is a subset of A)
----
so we have to prove subset both ways
prove a union empty set equals a
show subset this way (backwards subset)
true by 2.6a -- definition of union -- take the union of something, you get something bigger.
now go the other way.
show that a union empty set is a subset of a
two ways direct and indirect
direct:
let X be an element of A union empty set
therefore x element of a or element of empty set
case 1.
suppose X element of a
there x elemetn of a qed case 1
case 2.
suppose X element of empty set. contradiction
Therefore, the only possible case leads to X is an element of A.
There A union empty set is a subset of A.
Same proof - but indirect proof.
redoing forward subset
Suppose A union empty set is not a subset of A.
Therefore there exists X such that x is an element of A union epty set and X is not an element of A
Therefore X is an element of A or X is an element of the empty set
therefore x is an element of the empty set
-><-
therefore A union empty set is a subset of A.
e) A intersect A = A
proof on homework.
f) A union A = A
g) A union B = B union A
Proof (commutative law)
there are rare times when you can get away with doing an equals sign both ways at a time
x is an element of A union b (no let because were going both ways)
iff x is an element of a or x is an element of b (def. of union)
iff x is an element of b or x is an element of a
(commutative)
iff x is an element of B union A
Therefore A union b = b uion A
h) A interset B = B interset A
i) A - empty set = A
Proof.
subset both ways
way one
let X bet an element of (a - empty set)
therefore x is an element of a and x is not an element of the empty set (definition of minus)
therefore x is an element of a (defintion of conjunction)
the other way.
decaf proof
let x be an element of a
x is not an element of the empty set (by definition)
therefore x is an element of a and x is not an element of the empty set
therefore x is an element of a - empty set (definition)
lets try an indirect proof for this way also.
IP -
Suppose a is not a subset of a- empty set
Therefore there exists an x element of a such that x is not an element of a-empty set
~ (x element of a-empty set)
Therefore ~(x element of A and x eleeetn of the empty set)
Therefore x is not an element of a or x is an element of the empty set
case 1.
x is not an element of a .. contradiction -- we said it was an element of a
case 2.
x is an element of the empty set -- another contradiction
Both cases lead to contradictions
Therefore A is a subset of A - empty set
Part j)
empty set - A = empty set
when you're trying to proof something is empty and proof by contradiction
start with
SUPPOSE ITS NOT EMPTY -- therefore there exists x such that x is an element of empty set minus a.
k) A union (b union c) = (a union b) union c
Proof
x is an element of a union (b union c) iff x is an element of a or x is an element of (b union c) def of union.
iff x is an element of a or (x is an element of b or x element of c) (def of union)
iff (x is an eleemtn of a or x element of b) or x is an elemetn of c (associative property for \/)
iff (x is an element of a union b) or x is an element of c (def of union
iff x is an elemeent of (a union b ) union c
l) a interset ( b interset c) = (a intersect b) intersect c
same proof.
m) a intersect (b union c) = (a intersect b) union (A intersect c) distributive
n0 = a union (b intersect c) = (a union b) intersect (a union c)
o) a is a subset of b iff a union b = b.
p) a is a subset of B iff a intersect b = A
proof.
way one
=>
Suppose a is a subset of b
show a intersect b = a
two subset cases
way one
a intersect of b is a subset of A (Therem 2.6b - def on intersection)
show the other way
Let X be an element of A
Therefore X is an element of b (since A is a subset of B)
therefore x element of a and x element of b (conjunction)
Therefore X is an element of a intersect B (definitin)
right to left
Suppose A intersect B = A
Show A is a subset of B
Let x be an element of A
therefore x is an element of a intersect b (given)
therefore x is an element of a and x is an element of b
therefore x is an element of b.
Therefore A is a subset of B.
q) If A is a subset of B , then a union c is a subset of b union c.
Proof
suppose a is a subset of b
show a union c is a subset of b union c.
Let x be an element of a union c.
therefore x is an element of a or x is an element of c.
case 1.
suppose x is an element of a
then, x is an element of b (given, definitionof subset)
therefore x iS AN element of c) (definition of union)
case 2.
suppose x is an element of C
then, x is an element of b uion c by definition of union
therefore both cases lead to x is an element of b union c therefore
a union c is a subset ob be union c.
r) if a is a subset of b then a intersec is is a subset of be intersects c
homework for friday
page 76
1
3
4
6
9
11
15
19
(non-starred)
Fri 02/16/07
p. 88 -
(non-starred)
1,3,4
8 acejlor
..
9 bg
17 cfgh
U A (a element script a) (there exists a)(a is a subset of script a and x is an element of a)
intersection A
for every a -- a is an element of script a imples x is an element of a
x belings to the union a (a element of script)
we can immediately say that a is an element of script at and x is an element of a
script-a-3 = {(-r,r) and r >0}
union is entire real number line
intersection -- zero.
Therem 2.8
Let b be a set in script a
if we take intersection (a element script a) a is a sbset of b
part b) B is a subset of union (a element of script a) A
c) intersection (a element of script a) A is a subset of union (a eleemtn of script a) A , provided script A is not empty
script a -- collection of sets.
Proof of a.
Let x be an element of the interesection of the collection (as above)
(very important fact -- (for every A)(a element of script-a ==> x element of a)
B is a fixed set in script A , ie B element of Script A (as per original)
(b element of script a imples x is an eleemtn of b) -- not saying that's true by itself
x is an element of B by modus ponens
therefore intersection of (a element of script a) A is a subset of B.
can prove part c by "set algebra" -- use a, then use b, therefore c
but why doesn't pprt c work for the empty set.
Assume script A = empty set
look at the statement
x is an element of the intersection of A (a element of script a) <=> (for every a)(a elemeent of script a implies x is an element of A)
with the empty set A is an element of script A is always false.
says that this statment is always true
thus, the intersection is the universe!!
. . . ...
x is an element of the union of a collection means
(there exists A)(A is an element of scrript A and x is an element of A)
if we plug in any x, its false because the first part is always false.
so the whole think is false. - we don't have an existance to make it true.
so the union is empty set.
so clearly we don't want to say that the intersection is a subset of the union.
index set
- - - - - - - -
Δ = index set
really a set of subscripts
use them to identify the sets in our collection with subscripts
script-A= {A[α] : α element of Δ}
script-a[i] = { {1,2}, {2,3}, {2,5}}
one way to index
Δ = { 1, 3, 5}
A[1] = {1,2}
A[2] = {2,3}
A[3] = {2,5}
A[i] = {2,i}, i = 1,3,5
sometimes we just number them 1,2,3
.. subscripts 1 thru n.
2nd example
Script-A{[n, ∞): n = 1,2, 3 . . . . }
Δ = natural numbers (N)
A[n] = [n, ∞)
then script a = { A[n]: n element of Δ)
third example that we looked at.
script-a[3] = { (-r,r): r>0}
Δ = positive reals
A[r+] = (-r,r)
script-a[3] = {A[r]: r>0}
new notation
take the union notation we had before
now with index set
U (A[α]) (α element of Δ) = (x(there exists α)(α element of Δ and x element of A[α])
for intersection
new notation
intersection (A[α]) (below it -- α element of Δ) = {x: (for every α)(αelement of Δ ==> x is an element of A[α]}
Therem 2.9 -
part a ) intersection A[α] (α element of Δ) is a subset of A[β], for any β element of Δ
b) A[β] is a subset of union A[α] (α elemenn of Δ), for any β element of Δ
b') intersection of A[α] ( α element of Δ) is a subset of union A[α] ( α elemetn of Δ), provided Δ≠ empty set.
still true if Δ={1} and script a contains one element, the empty set
DeMorgan's laws.
compliment of (A intersect B) = A-compliment union B-compliment
compliment(A union B) = compliment-A intersect compliment-B
demorgan's laws for sets
suppose x element of compliment(A intersect B) <=> ~(X element a intersect b)
<=> ~( x element of A and x element of B)
by demorgan's law for statements
~(x element A) or ~(x element B)
<=> x element of A-compliment
or x is element of b-compliment
iff x element of compliment-A union compliment-b
therefore compliment(a intersect b) = compliment-A union compliment-B
we want it to work on infinite
intersection of an indexed family of sets and take the compliment
like to be able to say that this is equal to the union of the compliments
we'll do this monday monday.
Mon 02/19/07
proofs for homework # 11
1st two == direct
let x not be in b
since a is a subset of b, then this statment will be true -
for every y
if y subset of a then y subset of b.
so x element of a implies x element of b.
thus,
(take contrapositive)
x is not in b implies x is not in a
but we have x is not in b
therefore by modus ponens -- x is not in a.
shorter proof
start is x not in b
since a is a subset of b, for every y, y in a imples y in b
and we know that x is in a imples xi s in b
also we have x is not in b
therefore x is not in a. by modus tollens.
3rd approach -- proof by contradiction
assume negation of the statement you're trying to prove.
Assume that x is not in b and is a subset of b, but x is an element of a.
since x is in a and and is a subset of b, x belongs to b.
therefore x is in b and x is not in b. now we have a contradiction.
therefore x not in b and a subset of b implies x is not in a.
---------
section 2.3
proof of a generalization of demorgan's law -- therum 2.9 (in text) part c.
intersection of (α element of Δ) A[α], take the compliment ..
should be equal to union (α element of Δ) compliment-A[α]
ex: A[1] intersect A[2] ccompliment = compliment a[1] union compliment A[2]
we can do this proof by a string of iffs
Let x be arbitrary
Then x element intersection intersection of (α element of Δ) A[α], take the compliment iff it is not the case that x is an element of the intersection of A indexed
iff ~ for every α)(α element of Δ ==> x element of A[α])
iff there exists α)~(α in Δ => x is in A[α])
iff there exists α)(α in Δ and x is not in A[α])
iff there exists α)(α in Δ and x is in compliment A[α])
iff x belongs to union of (α in Δ) compliment(A[α])
therefore the interesection of the compliment is equal to the union of the individual compliments.
-----
HOMEWORK DUE FRIDAY:
92, 93 #1 (not *), 3, 5b, 11c,
...
-----
x is in the union of the compliement iff x is in the intersection of the individual compliments. -- we will do the iff style proof
but lets look at a different method
start out the compliment of the union
= (replace A by the double compliment of A) therem 2.7a
lets look at everything under the the big sqiggle but not the big squiggle.
= compliment compliment of the intersection of the compliments .. by part c
but by 2.7a we can erase the two big compliments
thus, the compliment of a union is the intersection of the compliments.
GET THE HOMEWORK FOR FRIDAY.
Piano's 5th axium
suppose that s is a subset of the natural numbers such that
1) 1 is in s
2) for every N, if n is in s, n+1 is in s
then, s is actually all of the natural numbers.
inductive set
not all inductive sets consist of all the natural numbers]
take s = {3,4,5 ...}
but is is not all the aatural numbers.
so the first assumption -- that 1 is in s .. is very important.
this leads to a proof strategy
(for every natural number n)P(n)
we can use a proof by induction
Proof by induction
------------------
(1) Prove that P(1) is true
(2) Let n be arbitrary, but assume that P(n) is true
.. therefore P(n+1) is true
Let S be the truth set for P(n)
from first part of the proof, we've got 1 in S
(2) (for every n)(n element of S implies n+1 element of S)
therefore S = N.
so for every n, P(n) .. which is what i'm trying to prove.
(for every n)(1+2+n) = (n(n+1))/2
Proof
-----
The proof is by induction
Let n=1.
Then 1 = (1(2))/2 = (1(1+1))/2 .. so the statement is true if n=1
now we go to the inductive part.
Let n be arbitrary. Assume that 1 + + n = (n(n+1))/2 // induction hypothesis -- identify as such.
Then 1+ .. n + n+1 (what do we have to prove using n+1 .. the right hand side must be ((n+1)(n+1+1))/2
= replace summing with
(n(n+1))/2 +(n+1) (true by the induction hypothesis (ih))
= (n(n+1))/2 + (2(n+1))/2
combine
. . .
and we get to above
therefore, for all natural numbers n, sum of 1 to n = (n(n+1))/2
some can be proofed directly
for all n, n^2 + n is even.
Proof by induction
let n = 1
then n^2 + n = 1^2 +1 = 2 and 1 is even
assume n is arbitrary and n^2 + n is even.
Then (n+1)^2 + (n+1) want to show its even
n^2 + 2n +1 +n +1
(n^2 +n) + 2n+2
first part we're assuming is even./
2k + 2n +2 by ih (because we knew that that part was even.
2(k+1+n), which is even
therefore, for all n, n^2 +n is even.
w/o induction
not n^2 + n = n(n+1)
let n be arbitrary
Then
1. n is even or
2. n is odd
If n is even, n = 2k
So n(n+1) = 2(k(n+1)), which is even.
If n is odd, then n = 2k +1
Then n(n+1) = (2k +1)(2k+2), factor out a 2, which is even.
Tue 02/20/07
proof by induction
deal with for every n p(n)
several steps
1. prove P(1) explicily. (basic step)
2. inductive step. Let n be arbitrary. assume that the statment is true for p(n) -- induction hypothesis
using that, prove the statement is true for n+1.
then summerize, therefore by induction, for all n,P(n)
(for all n) (sum of integers = n(n+1)/2
inductive definitions
(1) D(1) [definition for n=1]
2) Define D(n+1) in terms of D(n)
then D(n) is defined for all n.
classic example -- n!
1) 1! = 1
2) (n+1)! = (n+1) (n!) // defined in terms of n!
n! is definited for all natura mumbers
2! = 2 * 1!
3! = 3 * 2!, but we have 2!
etc.
we dont always have to start at 1.
Generalization of principal
imagine S subset of naturals.
1st step
assume there's an integer k in S.
for every n ≥ k, if n is in S, then n +1 is in S.
Thus, {k, k+1 ...} is a subset of S.
Examples.
one use is to take some axium and generalize it.
a(b+c) = ab+ac .. for real numbers a,b,c
that is an axium.
but it seems reasonable to suspect that a(b[1] + b[2] + b[n]) = ab[1] + ab[2] ... ab[n].
can write this as a(b[1] + ... b[n-1] + ab[n] .. etc.
(just keep doing this) :-D this is probably a proof by induction.
want to prove, for all n≥2 (a(b[1] .. + b[n]) = a[1]b[1] .. + a[n]b[n])
Proof
(by generalized induction)
Let n = 2
a(b[1]+b[2]) = ab[1] + ab[2] (by distributivity axium)
Let n ≥ 2 // not just arbitrary now
Assume a(b[1] + b[n]) = a[1]b[1] .. + a[n]b[n]) IH
Then a(b[1] + .. + b[n+1]) = a(b[1] + .. + b[n]) + ab[n+1] (by axium)
= ab[1] + .. + ab[n] + ab[n+1] (by IH)
Therefore, (for all n ≥2) (a(b[1] + .. + b[n]) = ab[1] + .. + ab[n])
QED
page 107 -- 8v.
If a has n elements, then Power(A) has 2^n elements
Proof.
The proof will be by induction on the number of elements in A, starting with the value n=0.
Let n=0.
Then A = empty set
Then Power(A) = { empty set }
so, number of element in Power(a) = 1 = 2^0 .
So statement is true when n=0.
Inductive step.
Assume that n ≥ 0, and that for any set A with n elements, POwer(A) has 2^n elements (ih)
Let B has n+1 elements
Then B ≠ empty set (by n≥0)
Let x[0] be an element of B.
Then the number of subsets of B = then number of subsets with x[0] + the number without x[0].
Call them C and D.
side
-------
C = {x[0]} union D, where D subset of B-{x[0]}
-----
there are 2^n subsets of C + 2^n from D (by induction hypothesis) .. applied to B - {x[0]}
= 2* 2^n
= 2^(n+1)
now we know that for any set A, if A has n elements then Power(A) has 2^n elements.
Principle of complete induction (PCI)
If S is such that S subset of Naturals
Assume it has this property ..
If set of the first n-1 integers belongs to S, then the next one belongs to S.
If you have that property, then S = natural numbers.
where's the base case?
if you start with n+1, then { n-1} = empty set .. we cant start before 1.
empty set is ofcourse a subset of S.
1 is a subset of S.
but usually we have a base case.
Strategy
1) Prove P(1) is true
2) Assume n is arbitrary, but n ≥ 2.
Assume that P(1) /\ P(2) ... P(n-1) is true
then conclude that P(n) is true.
2') Assume n≥1
Assume P(1) /\ P(2) /\ .. P(n)
.... therefore P(n+1) is true.
thing that makes it different from ordinary induction -- on the induction step you get to assume a lot more stuff.
oddly enough the two inductions are logically equivalent.
classic example
using complete induction.
variation on 2nd example in page 112.
Theorem
Every natural number ≥ 2 is either a prime number or a product of prime numbers.
The proof is by complete induction PCI
1. Let n=2. Then 2 is prime.
So n is prime or a product of primes.
So the statement is true when n = 2.
Inductive step.
(2) Assume the statement is true for 2,3,4 . . n
consider n+1. Then
Either
(a) n+1 is prime
(b) n+1 is composite.
If (a) is true,
then n+1 satisfies the statement.
If (b) is true, then n+1 = cd, where
c, d are in {2, .., n}
By induction hypothesis, both c and d are primes or products of primes.
So n +1 = cd will be a product of primes.
Thu 02/22/07
proof by subset inclusion
x element of union of script A
there exists a such that a is an element fo script A and x is an element of A
20c - look at their definitions of intersection and union
12 - family can be a finite family
family can be as few as (no or) 1 sets
first part -- get a set where all the sets have one thing in common
- could probably get by with two sets in the family - lot of correct answers to this problem
b) - any pair of sets are disjoint, so can you take the set X and make some subsets that have four elements so that each pair of subsets don't overlap at all and they make x
make sure that your collection of subsets eaach has four elements and make sure you don't get overlap between any one pair.
no two of them overlap
different from intersection of all of them being disjoint.
this is called a partition.
CORRECTION: chop up into four pieces
part c)- 20 elements -- means 20 sets in the collection .. actually 20 sets and their pair wise disjoint .. there has to be 20 sets so cut up the original set into 20 pieces. - pair wise disjoint.
part b has different answers -- there a different way to partition.
8t - page 107
omg -- morrell.
first, examine the base case n=1 .. what does that statement look like (equation)
i = 0 to 0 when n=1
= ar^0 = a
that's left hand
connect to right hand side
then with induction step, assume for an arbitrary n, if you go i = 0 to n-1 that you do get this equation to be ture -- a(r^n-1)/r-1
then prove statement for n+1 is true.
begin with left hand side and split it up .. then add on the next term.
have left represented by the IH.
---------------------
Mathematical induction vs. complete induction.
complete induction -- can assume from like 1 to n. .. so you have a little more power because you've got more assumptions.
another example
fibonacci sequence.
n=1
n=2
n≥3 definition
a[n] = a[n-1] + a[n-2]
1,1,2,3,5,8,13
lets define a different sequence because because
start with a[1]=1, a[2]=2, a[n] = 2a[n-2] + a[n-1], n≥3
1, 2, 4, 8, 16,
a[n] = 2^(n-1) .. conjecture.
prove by complete induction.
PCI
look at n=1
a[1] = 1 = 2^0 = 2^(1-1)
let n=2
a[2] = 2 = 2^1 = 2^(2-1)
induction step
let n ≥ 3 be arbitrary
have to assume that some stuff before a[n] is true -- we need at least the previous two -- so we need to use a complete inductin because we need more than just the one that came righ before
assume here that a[n-2] = 2 ^ (n-3)
that right there makes it complete induction
and a[n-1] = 2^ (n-2)
Then a[n] = 2a[n-2] + a[n-1]
= 2* 2^(n -3) + 2^(n-2) (by IH
= 2^(n-2) + 2^(n-2)
= 2 * 2^(n-2)
= 2^(n-1)
therefore by PCI, for all n, a[n] = 2^(n-1)
pci pmi are logically equivalent.
3rd logically equivalent principle
well ordering principle
WOP
.. for the natural numbers.
if you take S subset of natural numbers, S≠ empty set.
then S must contain a least element.
least element: (there exists n in set S)(for every m in S) ( n ≤ m)
if you take the natural numbers and list them in their natura order
if you take a subset,
as long as there's at least 2 element
then we can find an element that's the left most eleement.
it turns out that there are other sets that are not well order.
if you take the integers, that set is not well ordered. --
.. the whole thing doesn't have a least element. we've got ....'s
but there is a way to well order it
0, -1, 1, -2, 2, -3, 3 -- now its well-ordered
we'd be able to distinguish a left -most element here.
axium of choice = any set whatsoever can be put into some kind of well - ordering.
can use well ordering in a proof -- but probably 90% of the time PMI used, 9.9% of the time PCI used, .1% .. well ordering used.
one example of it used.
prove thht every natural number n ≥ 1 is divisible by some prime number.
prove it!
let n be arbitrary but greater than 1
n > 1
Let S = { a element n: a >1 and a|n}
we need a not empty set for WOP
since n > 1 and n|n , n element of S
therefore S is non empty.
By WOP, there exists a least element k in S.
// we need to say that k is a prime number, then we've solved it.
claim k is a prime number
Assume k is not prime.
Then k = bc, where 1 < b < k (non trivial factorization)
then b >1, and b | k.
Since k is in S, k|n
Therefore b|n, so b is in s. but b is less than k and k was supposed to be the least element in s
so contradiction
(since k is least element in S)
Therefore, k is prime.
QED
another example:
division algorithm.
Assume we have two natural numbers a & b
and b ≤ a
then there exists a q which is in the natural numbers and an r in N or could be zero.
such that a = bq + r
such that 0 ≤ r < B
third grade division.
integers into integers.
14/3
q = 4 , r = 2
how would we prove this result.
preliminary results
the set of natural numbers union {0} is well ordered.
prove that first.
Proof.
Let S be a subset of natural numbers union 0
and S ≠ empty set
two cases
1. zero is not in S
2. zero is in S
(1) --- 0 not in S
Then S is a subset of N .. but then it has a least elemeent
by well ordering principle, S has a least element.
(2) 0 element S, Then zero is the least element in S.
archimedian principle.
page 105
theorem 2.11
need this principle as well in order to tackle the division alg.
(for every a,b elemetn of naturals)(there exists) natural number S such that a < Sb.
Fri 02/23/07
tue
page 116-117
2, 3a, 9, 10, 14a, 15ac
other page
1abcd, 2acdef, 5, 6
10, 11cd, 13, 14, 15, 17cd
double check.
...
proving 3rd grade long devision
arcimedian principle - for every two natural numbers, lthere exists a natural number S such that a < Sb
let a be arbitrary
Proof is by induction on the value of b
good idea to specify which variable you're inducting
let b = 1
then a < a+ 1 = (a+1)1 = (a+1)b
so if i let s be euqal to a+1, then it works
we get a nnumber bigger than a
for b = 1
that's theebase case
induction step
assume there exists S such that a < Sb
Then a <Sb < Sb + s = s(b+1)
for all b, there exists an S such that a< Sb
division algorithm --
we had a, b naturals b ≤ a ..
there there exists q, r (quotient, remainder), where q is in N and r is in N union 0 and a = qb +r 0≤r<b .
Proof
let T = { S element of naturals : a < Sb}
becuase of archimedian principle, we knw that this is not an empty set.
T≠ empty set
Let w be the smallest element in T, by WOP
Define q = w-1
Let r = a - qb
Then a = qb + r is true
that's easy
but we want r in the right place.
r≥0 claim.
A ≥ qb. Suppose the contrary, ie a < qb
Then q is in T, a contradiction since q < w .. and w is the smallest element of T.
Therefore, a ≥ qb
Therefore r ≥0
now prove that r < b.
Suppose that r ≥ b.
then a-qb ≥ b
a-qb -b ≥ 0
a - (q+1)b ≥ 0
so a - wb ≥0
a ≥ wb
So w not in T, a contradiction.
Therefore r < b
there is an extension of that for negative numbers.
implication of logically eqvivalency of inductions
WOP => PMI
Assume WOP
Assume S a set (subset of N) such that
(1) 1 is in s
2) for every no n element of s imples n +1 element of S
Suppose that S is not the entire set of natural numbers.
Then s-compliment is nonempty
s-compliment is a subset of N.
Let n be the smallest element in s-compliment (wop)
So n-1 is an element of S
Also n - 1 is an element of N.
Since n >1 since 1 belongs to S and not S-compliment.
By assumption 2 and that n-1 is in S, we know that (n-1)+1 is in S. Therefore n is in S
but n is in S-compliment -- so we aave a contradiction.
Therefore S = N.
now we'll start one tht we get to do
PCI => WOP
PCI ..
if you have 1 in a set S .. whenever you get a string of natural numbers in there imples n is in S-- those two imply that s is in the natural numbers.
so we wanna assume that that statement is true.
prove the WOP using that info
Let T ≠ empty set, T subset N.
prove that there's a least element in T.
Let S = N - T (compliment)
S ≠ N (we took something away --- T was not empty)
Suppose that T does not have a least element.
how to get the contradiction
(show S = N -- a contradiction because we said S was not all of the Natural numbers)
we've got the PCI implication.
so if you show the two things for PCI, then you have you contradiction
how do I know that 1 is in S
If 1 were in T, then T woul hhve a least element.
we're assuming that T does not have a least element, so 1 is in S.
so get the rest of it true.
then the assumption msst be false and we've proven the well-ordering principle.
Counting Techniques.
- - - - - - - - - -
how do we determine how many objects are in various sets.
we will just accept these therums - we can't prove them yet.
venn diagram
we have two sets A and B that don't overlap
the number of elements in A = A-double-bar
B-double-bar = elements in b.
and (A or B)-double-bar
sum rule - (theorem 2.16) If a interset B = empty set, then the number of elements in the union = number of elements in first + number of elements in second.
If you have a collection of sets -- Script A, pairwise disjoint.
If we take the Union of those sets = number of elements is Σ of number of elements in each set
Theorem 2.18
(a) If you don't assume disjointedness -- if we were to apply the sum rule, we're making the mistake.
number of elements in A union B = elements in A + elements in B - elements in A intersect B
(b) if you want an interesection, try adding the eleements in the first set, and the second set and then subtract a union b elements.
Mon 02/26/07
2.5 for tomorrow
2.6 for wed.
Tue 02/07/07
fundamental rule of counting -- product rule.
take a procedure that can be done in two steps
if you now the number of way to do both steps, you mltiply n[1] and n[2]
if step one can be done n[1] ways and step 2 can be done n[2] ways, then the procedure can be done n[1] * n[2] ways.
and this generalizes to more than two steps.
theorem that we can't prove at the moment, but it works :-D
tree diagram.
simple application of this
wi liscense plates
###-AAA
how many different possible plates.
this is a procedure that has 6 steps -- 6 chars.
1) 10
2) 10
3) 10
4) 26
5) 26
6) 26
so the total number is 10^3 * 26^3
permutations
list of objects in a certain order
5 * 4 * 3 * 2 * 1 for a family photo - 5!
another application
suppose {a,b,c,d}
we wanna create four letter words
how many words can I create? 4!
5 pick 3
5! / 2!
# of permutations of n elements taken r at a time is n! / ((n-r)!)
suppose that we have a family photograph -- 5 people in the family -- suppose we said "how many ways can we line up the photograph if mom & dad want to stand next to each other"
1. make mom & dad one object. - how many ways can we line up the 4 objects. 4!
2. arrange mom & dad -- 2!
= 4! * 2!
Combinations
combination of n elements taken r at a time
.. we mean a subset of r elements take from a set of n elements.
# of combinations (n over r) .. not a fraction just n over r.
abc
This one combination {a,b,c} produces 3! distinct permutations "words"
permutations in general is much larger than the number of combinations.
# of permutations = 3! * (number of combinations)
# of combinations = permutations / 3!
5 choose 3 = nPr / 3! = 5!/(3!2!)
n choose r = nPr / r! = n!(r!(n-r)!)
applications
the binomial theorem.
(a+b)^n
(a+b)(a+b) .. (a+b) .. you get a lot of partial products.
can select r a's and n-r b's
but we ddon't get just one term of these.
so we've got a set of n -- how many ways could we have getten this.
so we get n choose r!
... (n choose k) a^k b^(n-k)
so (a+b)^n = Σ k=0 to n (no choose k) a^k * b^(n-k)
(a+b)^3 = (3 choose 0) a^0 b ^3 + (3 choose 1) a^1b^2 + ....
3 choose 0 = 3!/(0!3!) = 1
so b^3 + 3ab^2 + 3 choose 2 is the same as 3 choose 1 because when we chooose 1, we've automagically created a subset of 2
pascel's triangle 1 3 3 1
(a + 2b)^12
12 choose 3 a^3 (2b)^9
so 12 choose 3 * 2^9
poker
given five cards
order doesn't matter - flush is the same no matter what order.
52 choose 5 = 2598960
hands of all diamonds - 13 choose 5 -- number of 5 card hands with all diamonds. --
so 13 choose 5 / 52 choose 5 = probability.
flush
1) choose the suit
2) choose five cards.
4(13 choose 5) / (15 choose 5) = probability of flush .
how many different full houses are there?
one way to do it.
1) choose the 3 card kind
2) choose the 2 card kind
3) choose 3 cards from 1.
4) choose 2 cards from 2.
1) -- 13 ways ( 2 - A)
2) 12 ways
3) 4 choose 3
4) (4 choose 2)
(13)(12)(4)(6) / (52 choose 5) = probability
about .1% chance
4 of a kind
1) choose kind
2) pick 4
3) choose a 5th card.
1) -- 13 kinds
2) -- 4 choose 4 - 1
3) -- 48 choose 1 = 48
so 13 * 48
Thu 03/01/07
for next tuesday
p. 142 - 1a, 2, 3df,
4a, 5, 6bgh, 8bdf, 9ag
..double check.
wop for existance -- direct proof
wop for a for every -- need a contradiction
116-117 - #10
let b be arbitrary; show that there exists an integer s such that a < sb.
do induction on a.
classic induction
base case
a = 1
Let s = b+1
Then a < s+1 * b
...
true for a=1
induction
assume a is a natural number and there exists an s such that a < sb
a+1 < (s+1)b based on ih
.. call it s'
a + 1 < sb +1 based on ih
< sb +b
= (s+1)b
2nd set #5
Mon 03/05/07
take to sets a and b
A cross B = {(x,y) : x in A, y in B}
suppose A = (1,2,3)
B = {a,b}
A cross B = {(1,a), (1,b), (2,a), (2,b), 3a, 3b}
B cross A = (a,1), (b, 1), (a,2),(b,2), ....
cartesian crossing
rene descartes
took the real numbers and formed a cross product of them .. that's our coordinate plane.
prove the theorem --
if a is a subset of c and b is a subset of D, then a cross b is a subset of c cross d
assume a subset of c and b is a subst of d
let (x,y) belong to A cross B // we can use x,y .. bcause we're dealing with a cross product
then x belongs to A and y belongs to B.
these two statements are always equivalent
Since x is in A and A is a subset of C, x is in C.
Since y is in B and B is a subset of D, you is in D.
therefore, x is in C and y is in D .. therefore (x,y) belongs to C cross D.
Theorem 3.1 part a.
A cross B union C, you get A cross B union A cross C.
we either do two ways or one string of equivalences.
that's what we'll do.
(x,y) belongs to a cross B union C
iff x is in A and y is in B union C.
iff x is in A and y is in B or y is in C
iff (distributive) x is in a and y is in B or x is in A and y is in C
iff (x,y) belongs to A cross B or (x,y) belongs to A cross C
iff (x,y) belongs to (A cross B) union (A cross C)
therefore (we've proven it).
a relation R from A to B is *any* subset of A cross B.
A = {2,3}, B = {1,4}
A cross B = {(2,1), (2,4), (3,1), (3,4)}
R = {(2,4), (3,4)}
"the less than relation" -- 2 < 4 and 3 < 4
xRy iff (x,y) belongs to R.
so iin this example
xRy iff x <y
or
xRy iff x ≤ y
technically a relation is just a subset of A × B, but we're finding some relationship.
really functions are just special relations
Suppose we have relation R from A to B
Domain: {x in A : (x,y) in R for some y}
so in our example, Domain R = {2,3}
.. list all the first components.
Range R = {y in B : (x,y) in R, for some x in A)
so -- second set of components.
in our case,
Range R = {4}
inverse relation
R is a relation from A to B.
R is a subset of A cross B
R inverse -- the set of ordered pairs in R but reversed
elements
R inverse is a relation from B to A .. subset of B cross A.
the composition of two relations -- generalization of composition of functions.
R is a relation from A to B
S is a relation from B to C.
S composed with R = {(x,z) element of A cross C: (there exists a y) in B((x,y) in R and (y,z) in S}
y is a connector element.
example
suppose A is 1 and 2
B is 3 and 4
C is a and b
R = (1,3) (1,4) (2,4)
S = (3,a) (4,b)
S composed with R = {(1,a), (1,b), (2,b)}
look for gobetweens
that's how I would make the composition.
Tue 03/06/07
for funky