Transcript 9 February - Michael Johnson's Homepage

9 February
In Class Assignment #1
Set: {2, 4, 6, 8, 10}
MEMBER
2
{4, 6}
{2, 10}
{}
3
{{2, 4}, 6, 8,
10}
SUBSET
NEITHER
Set: {2, 4, 6, 8, 10}
2
{4, 6}
{2, 10}
{}
3
{{2, 4}, 6, 8,
10}
MEMBER
✓
SUBSET
NEITHER
Set: {2, 4, 6, 8, 10}
2
{4, 6}
{2, 10}
{}
3
{{2, 4}, 6, 8,
10}
MEMBER
✓
SUBSET
✓
NEITHER
Set: {2, 4, 6, 8, 10}
2
{4, 6}
{2, 10}
{}
3
{{2, 4}, 6, 8,
10}
MEMBER
✓
SUBSET
✓
✓
NEITHER
Set: {2, 4, 6, 8, 10}
2
{4, 6}
{2, 10}
{}
3
{{2, 4}, 6, 8,
10}
MEMBER
✓
SUBSET
✓
✓
✓
NEITHER
Set: {2, 4, 6, 8, 10}
2
{4, 6}
{2, 10}
{}
3
{{2, 4}, 6, 8,
10}
MEMBER
✓
SUBSET
NEITHER
✓
✓
✓
✓
Set: {2, 4, 6, 8, 10}
2
{4, 6}
{2, 10}
{}
3
{{2, 4}, 6, 8,
10}
MEMBER
✓
SUBSET
NEITHER
✓
✓
✓
✓
✓
In Class Assignment #2
{1, 1} = {1}
Many students thought this was false. It’s not.
For any two sets A and B, A = B iff (for all x)(x ∈ A iff x ∈ B)
Therefore, {1, 1} = {1} iff (for all x)(x ∈ {1, 1} iff x ∈ {1})
Therefore, if (for all x)(x ∈ {1, 1} iff x ∈ {1}), then {1, 1} = {1}
To prove: (for all x)(x ∈ {1, 1} iff x ∈ {1})
To prove: (for all x)(x ∈ {1, 1} iff x ∈ {1})
Let x = 1. Then clearly:
1 ∈ {1, 1}
And 1 ∈ {1}
Therefore, 1 ∈ {1, 1} iff 1 ∈ {1}
(A iff B is true when A and B are both true.)
To prove: (for all x)(x ∈ {1, 1} iff x ∈ {1})
Let x ≠ 1. Then clearly:
x ∉ {1, 1}
And x ∉ {1}
Therefore, x ∈ {1, 1} iff x ∈ {1}
(A iff B is true when A and B are both false.)
For every set S, S ∪ S = S ∩ S
Proof:
A ∪ B = {x: x ∈ A or x ∈ B}
Therefore, S ∪ S = {x: x ∈ S or x ∈ S}
(P or P) iff P
Therefore, S ∪ S = {x: x ∈ S or x ∈ S} = {x: x ∈ S} = S
For every set S, S ∪ S = S ∩ S
Proof, cont’d
A ∩ B = {x: x ∈ A and x ∈ B}
Therefore, S ∩ S = {x: x ∈ S and x ∈ S}
(P and P) iff P
Therefore, S ∩ S = {x: x ∈ S and x ∈ S} = {x: x ∈ S} = S
And so: S ∪ S = S = S ∩ S
Write the Name in Extensive Notation
{Hong Kong, London, New York} ∪ ({London, Sydney} ∩ {Sydney, Tokyo})
{Sydney}
{Hong Kong, London, New York, Sydney}
Some Strange Answers
{Hong Kong, London, New York, Sydney, Tokyo}
{Sydney}
Problem 3b
Write names for the following sets in intensive notation: {Michael}
{x: Michael}
{x: x is the first name of the person teaching this course}
{x: x is a person named “Michael”}
Problem 4a
Write the power set of the following sets: {{}}, i.e. {ø}
Definition: power set of S = set of all subsets of S
{} ⊆ {{}}
{{}} ⊆ {{}}
So: P({{}}) = { {}, {{}} } = { ø, {ø} }
{} ⊆ S, for every S
S ⊆ S, for every S
Remember
If a set has N members, then its power set has 2N members.
So since {{}} has one member, its power set has 21 = 2 members.
And indeed, { {}, {{}} } has 2 members.
Some Answers
{}, {{}}
{}, {}, {{}}
{ {}, ø }
{ {{}} }
{ {}, {{{}}} }
Write the power set of the following sets:
{x: x is a dog}
{ ALL DOGS }
{ x: x is a dog }
{ {}, x: x is a dog }
{ {x: x is a dog} }
{ {}, {x: x is a dog} }
Write the power set of the following sets:
{x: x is a dog}
{ dog }
{ {}, dog }
{ {}, {y: y is the set of dogs} }
{ {x: x has four legs}, {x: x growls}, {x: x runs}, {x: x is a dog}, … }
{ {small dogs}, {medium dogs}, {large dogs}, {hunting dogs}, ….}
Write a sentence that both uses and
mentions the word ‘logic.’
A sentence obeys logic or does not obey logic.
People study logic to train their logic.
One must differentiate between the use of the word ‘logic’ and that of
its token, “logic.”
Write a sentence that both uses and
mentions the word ‘logic.’
Logic is one of the concepts covered in this course.
Elementary logic course teachers use logic.
‘Logic’ has 5 letters and means rational.
Logic is a subject and so is the name ‘logic.’
Some Clever Answers
According to logic, ‘logic’ can’t both have 5 letters and not have 5
letters.
I learned logic in logic class but I learned ‘logic’ in English class.
Using ‘logic’ doesn’t require logic.
Homework #1
True or False
T
T
F
F
T
F
T
F
In binary notation, 1 = 0.111...
There exists a set S that can be paired one-to-one with its
power set.
The rational numbers are the same size as the power set
of the natural numbers.
According to standard set theory, the numerical size of the
real numbers is the next highest number after the
numerical size of the natural numbers.
True or False
T
T
F
F
T
F
T
F
In binary notation, 1 = 0.111...
There exists a set S that can be paired one-to-one with its
power set.
The rational numbers are the same size as the power set
of the natural numbers.
According to standard set theory, the numerical size of the
real numbers is the next highest number after the
numerical size of the natural numbers.
The Power Set Theorem
Suppose that S is a set that CAN be paired 1-to-1 with P(S).
Let’s call the members of S: a, b, c, …
Let’s call the subsets of S: L, M, N, …
The Power Set Theorem
S
a
b
c
P(S)
L
M
N
d
O
e
f
P
…
Q
…
The Power Set Theorem
S
a
b
c
P(S)
L
M
N
K
d
O
e
f
P
…
Q
…
x : x ϵ S & x ϵ x’s pair in P(S)
The Power Set Theorem
K⊆S
So: K ϵ P(S) = {x: x ⊆ S}
But K is not the pair of any member of S
K ≠ L, K ≠ M, K ≠ N, K ≠ O…
Therefore there is no 1-to-1 pairing between S and P(S)
True or False
T
T
F
F
T
F
T
F
In binary notation, 1 = 0.111...
There exists a set S that can be paired one-to-one with its
power set.
The rational numbers are the same size as the power set
of the natural numbers.
According to standard set theory, the numerical size of the
real numbers is the next highest number after the
numerical size of the natural numbers.
N
0
1
2
3
R
1
2
½
⅓
P(N)
x: x ⊆ N
4
3
5
4
…
…
True or False
T
T
F
F
T
F
T
F
In binary notation, 1 = 0.111...
There exists a set S that can be paired one-to-one with its
power set.
The rational numbers are the same size as the power set
of the natural numbers.
According to standard set theory, the numerical size of the
real numbers is the next highest number after the
numerical size of the natural numbers.
Write names for the following sets in
extensive notation
{Hong Kong, London, New York} ∩ ({London, Sydney} ∪ {Sydney, Tokyo})
{London, Sydney, Tokyo}
{London}
Write names for the following sets in
extensive notation
{x: x shaves everyone who doesn’t shave themselves}
NAME: {}
Problem 3
Write two different names for the following set, both in intensive
notation. (Hint: Michael Johnson is the instructor of this class.)
{Michael Johnson}
Example Answers
• {x: x = Michael Johnson}
• {x: x is the instructor of this class}
• {x: x = Michael Johnson or x = Michael Johnson}
• {x: x = Michael Johnson and (P or not-P)}
• {y: y = Michael Johnson}
• {x: x assigned this homework}
• {x: x is named “Michael Johnson” & x is a philosopher at HKU}
• {x: x’s homepage is michaeljohnsonphilosophy.com}
Write the power set of {{{}}}
Cheesy but acceptable answer:
{x: x ⊆ {{{}}} }
Write the power set of {{{}}}
How many members does {{{}}} have?
How many subsets does it have?
When a set S has only 1 member, its power set is a set containing the
null set and S.
Write the power set of the following set.
({Hong Kong, London, New York} ∩ {London, Sydney}) ∪ {Sydney, Tokyo}
{London}
{London, Sydney, Tokyo}
LONDON
LONDON
LONDON
LONDON
-
SYDNEY
SYDNEY
SYDNEY
SYDNEY
-
TOKYO
TOKYO
TOKYO
TOKYO
-
Barber Paradox
The Barber Paradox
Once upon a time there was a
village, and in this village lived a
barber named B.
The Barber Paradox
B shaved all the villagers who did
not shave themselves,
And B shaved none of the villagers
who did shave themselves.
The Barber Paradox
Question, did B shave B, or not?
Suppose B Shaved B
1. B shaved B
Assumption
2. B did not shave any villager X where X shaved X
Assumption
3. B did not shave B
1,2 Logic
Suppose B Did Not Shave B
1. B did not shave B
Assumption
2. B shaved every villager X where X did not shave X
Assumption
3. B shaved B
1,2 Logic
Contradictions with Assumptions
We can derive a contradiction from the assumption that B shaved B.
We can derive a contradiction from the assumption that B did not
shave B.
The Law of Excluded Middle
Everything is either true or not true.
Either P or not-P, for any P.
Either B shaved B or B did not shave B, there is no third option.
It’s the Law
• Either it’s Tuesday or it’s not Tuesday.
• Either it’s Wednesday or it’s not Wednesday.
• Either killing babies is good or killing babies is not good.
• Either this sandwich is good or it is not good.
Disjunction Elimination
A or B
A implies C
B implies C
Therefore, C
Example
Either Michael is dead or he has no legs
If Michael is dead, he can’t run the race.
If Michael has no legs, he can’t run the race.
Therefore, Michael can’t run the race.
Contradiction, No Assumptions
B shaves B or B does not shave B
[Law of Excluded Middle]
If B shaves B, contradiction.
If B does not shave B, contradiction.
Therefore, contradiction
Contradictions
Whenever we are confronted with a contradiction, we need to give up
something that led us into the contradiction.
Give up Logic?
For example, we used Logic in the
proof that B shaved B if and only if
B did not shave B.
So we might consider giving up
logic.
A or B
A implies C
B implies C
Therefore, C
No Barber
In this instance, however, it makes more sense to give up our initial
acquiescence to the story:
We assumed that there was a village with a barber who shaved all and
only the villagers who did not shave themselves.
The Barber Paradox
The paradox shows us that there is
no such barber, and that there
cannot be.
Russell’s Paradox
Set Theoretic Rules
Reduction:
a ∈ {x: COND(x)}
Therefore, COND(a)
Abstraction:
COND(a)
Therefore, a ∈ {x: COND(x)}
Examples
Reduction:
Mt. Everest ∈ {x: x is a mountain}
Therefore, Mt. Everest is a mountain.
Abstraction:
Mt. Everest is a mountain.
Therefore, Mt. Everest ∈ {x: x is a mountain}
Self-Membered Sets
It’s possible that some sets are members of themselves. Let S = {x: x is a
set}. Since S is a set, S ∈ {x: x is a set} (by abstraction), and thus S ∈ S
(by Def of S).
Or consider H = {x: Michael hates x}. Maybe I even hate the set of
things I hate. So H is in H.
Russell’s Paradox Set
Most sets are non-self-membered. The set of mountains is not a
mountain; the set of planets is not a planet; and so on. Define:
R = {x: ¬x ∈ x}
Is R in R?
1. R ∈ R
2. R ∈ {x: ¬x ∈ x}
3. ¬R ∈ R
Yes?
1, Def of R
2, Reduction
4. ¬R ∈ R
5. R ∈ {x: ¬x ∈ x}
6. R ∈ R
No?
4, Abstraction
5, Def of R
Historical Importance
Russell’s paradox was what caused
Frege to stop doing mathematics
and do philosophy of language
instead.
Comparison with the Liar
Russell thought that his paradox
was of a kind with the liar, and
that any solution to one should be
a solution to the other.
Basically, he saw both as arising
from a sort of vicious circularity.
The von Neumann Heirarchy