PHL309 Logic, Language, and Thought
Professor: Craig DeLancey
Office: CC212C
Email: delancey@oswego.edu
Past Assignments
30 January
Read the selection from Aristotle. Come to class
prepared to explain what Aristotle's view on the
infinite.
1 February
Get a head start and begin reading the selection from Galileo's
Two New Sciences: First Day.
I emailed you the prefered translation. If you didn't get that
email let me know.
But, if that isn't up yet, an fair translation is freely available
here.
Our goal is to ultimately read up to but not past the passage
by Simplicio that in this translation begins "I cannot help
admiring your discussion; but I fear that this parallelism...."
In the version I'm trying to get back onto e-reserves it is
page 44 (or, original edition page numbers are on the side
margins, and by those we would like to get to 82.) You're
welcome to read farther, but we won't need to discuss past this
point and I won't require that anyone read past this point.
4 February
Read from the Galileo selection. You are welcome to start
at the beginning if you can, but I only need you to read
from page 35 to 42. I think there are at least five arguments
that we cannot reason about infinity. Try to identify them,
and see if you can understand them. We'll go over the first
few. I will ask you to explain the last several.
6 February
Homework. On page 40 (editor's number 78), Salviato explains
a paradox having to do with squares and roots of numbers.
Write out this argument as a reductio argument. This means:
What is the conclusion? What is the assumption for reductio?
What are the necessary steps of the argument? What is the
contradiction that Galileo finds? (After Monday, we'll have
several examples of doing this, so you'll have a model to
copy.) You should be able to do this on a page, or at most
two. Hand it in at the beginning of class.
Several people asked me for a model. Here is how we reconstructed
the soupdish argument in class.
Galileo wants to show we cannot reason about actual
infinities, so he sets out to show if we could then we would
contradict ourselves.
- Assumption for reductio ad absurdum: We can reason
about actual infinities.
- If we can reason about actual infinities, then reason
tells us that the following are true:
- There is a geometric figure, called the soupdish, such
that a planar cut perpendicular to the axis yields two
figures of the same volume (a cone and a ring).
- Volume is composed of quantity of points, so if two
figures have the same volume then they have the same
number of points.
- From steps 3 and 4, we know that the two figures from some
cut across the soupdish yield a ring and cone that have
the same number of points.
- The last cut across the soupdish yields a circle and a
point.
- Steps 3 and 6 tells us that the circle and point have the same
volume.
- A circle has infinitely many points. A point has one point.
- Step 8 tells us that the two figures have different number
of points.
- Step 7 and 4 tell us that the circle and point have the
same number of points.
- Steps 9 and 10 are a contradiction. [This means we put
something false into our argument. Galileo concludes that
the false thing we put in was:]
- Step 1, the assumption for reductio, is the false claim
that caused the contradiction. Therefore: we cannot reason
about actual infinities.
Your argument will likely start in a similar way (steps 1 and
2 can be the same), but you must identify the explicit
contradiction (some statement and also the denial of that
statement).
Here's how I graded this: 1 point for identifying a plausible
conclusion; 1 point for identifying the assumption for
reductio (this is just the denial of the conclusion, so it's a
freebie); 2 points to identifying the essential steps of the
argument; 2 points for explicitly identifying the contradiction
of the argument.
February 8
We'll look at Galileo's version of how we can reason about
something like potential infinities; this is at the end of
our selection.
Remember that this day I cannot have office hours. Sorry.
February 11, 13
A basic introduction to set theory! And cool facts about Cantor.
February 15
Howework. Answer the following questions. Work on your own,
since the point here is to determine where you still need work
on set theory. Write up your answers and bring them to class.
- Which of these are true?
a. {1} ∈ {1, 2, 3}
b. 2 ∈ {1, 2, 3}
c. {1} ∈ {{1}, {2}, {3}}
d. 1 ∈ {{1}, {2}, {3}}
- Which of these are identical?
a. {1} and {{1}}
b. {2, 3, 1} and {1, 2, 3}
c. {} and {{}}
d. {7, 7} and {7}
- Give an example of a proper subset of
each of the following sets.
a. {1, 2, 3}
b. {a, b}
c. {{1}, {2}, {3}}
- For each of the following sets, list all
of its subsets. (Remember: if we do not require
that the subsets be proper, you can include as a
subset the set itself.)
a. {1}
b. {1, 2, 3}
c. {}
c. {{}}
- Assume these sets continue in the simplest way as
listed. For problems a and b, can you give an example of a
function that relates the first to the second in a 1-to-1
correspondence (an on and onto function that would also be
a function if it went backwards -- what mathematicians call
an inverse)? For problem c, can you find a function that is
on and onto, even if it were not 1-to-1? (You can answer
these using some basic arithmetic -- no need to get fancy;
for example, the function relating the naturals to the even
numbers would look like: f(x) = 2x.)
a. {2, 4, 6, 8, 10....} and {20, 40, 60, 80, 100....}
b. {1, 2, 3, 4, 5....} and {1, 3, 5, 7, 9, ....}
c. {1, 2, 3, 4, 5....} and {0}
(Note that for c, the second set contains only one element,
namely the number zero.)
- Opinion question: if Cantor is right that sets of
infinite cardinality can have infinite proper subsets,
then does it follow that all infinite sets are the same
size?
February 20
We will review Cantor's claim; review in a more formal way
Cantor's diagonal argument; and introduce Cantor's Theorem.
February 22
A review of functions; a review of powersets; and then
introduction of Cantor's theorem. We can do a fun proof of this,
before we state the proof more formally.
Also: There were typos and a mistake in my handout on set
theory, so I rewrote it. And there's a bonus! I added a little
set of drawings that I think make 1-to-1 more clear than I was
making it before (quite a few times I mistated it). I'll bring
this to class, but I'll also post it here.
February 25
Homework due at the beginning of class.
These are some more problems meant to help us think more about
sets and powersets. Write up your answers to these and bring
them to class to hand in.
- What are the powersets of the following sets?
- {1, 2}
- {}
- {a, b, c, d}
- { {a, b}, {{7}} }
- What are the following sets powersets of? That
is, the powerset of what set would be the following?
- {{}, {a}, {b}, {a, b}}
- {} [<-- Typo! I meant to write: {{}} ]
- {{}, {1}}
- {{2}, {4}, {6}, {4, 6}, {2, 4}, {6, 2}, {}, {2, 4, 6}}
- Which of these sets has the largest cardinality?
Explain what this means and how you know your answer is
correct. You'll probably need to define cardinality, and
describe a one-to-one function, and then apply these
notions.
- The natural numbers, N
- The even numbers (you can call this E)
- Simplicio argued that a line segment AB that is twice as
long as a line segment CD has twice as many points; but also
AB and CD have infinitely many points, and infinitely many
points is as many as infinitely many points, so AB and CD
have the same number of points. Thus, the segments have
differenly quantities of points (AB has twice as many points
as CD) and the same quantity of points (AB and CD have the
same number of points -- namely infinitely many). If we
agree with Cantor, how many points are on the line segment CD?
How many are on the line segment AB if it is twice as long as
CD? What does this tell us about Simplicio's argument? Does
Cantor's Claim matter here? (Hint: in modern geometry, every
line segment has the same cardinality of points -- namely,
aleph1.)
Meanwhile, in class, we will review Cantor's theorem, and
then discuss what this means for the infinities.
27 February
In class:Review of the homework. Review of all of our
set theory. We will finally begin to answer directly each of
Galileo's objections to reasoning about infinity!
Regarding last class: we reviewed in the last class a
reductio proof of Cantor's Theorem. I described a
hopefully-easier-to-understand case for
N and R, but promised to write out a more general
proof. A more general proof would look like this.
Cantor's Theorem says that, for any set S, |P(S)| > |S|.
We can easily see that |S| ≤ |P(S)|, because there is a
function from P(S) and onto S. This function has as its
domain the singleton members of P(S), and maps each of these
onto (or, if you prefer, points each of these at) its member
in S. That is, {x} in P(S) will be mapped onto x member of
S. (Look back at your handout: you'll see that if we have a
function from a set A and onto a set B, then we know at least
that |A| > |B|; that's the principle I used here.)
So, since |S| ≤ |P(S)|, is |S| < |P(S)|, or is |S| =
|P(S)|? We rule out the latter case.
Suppose |S| = |P(S)|. Then, there is a function F on S and
onto P(S), and this function is 1-to-1. Let F be such a
function. We claim that if F existed we would get a
contradiction.
Let NPS be the set of all members of S such that x is not the
output of F(x). This is the set of all those elements of S
that when put into the function F, put out some member of
P(S) that the member does not belong to (I chose the long
name NPS to helps us think,
Not-Pointing-at-a-Subset-we-belong-to). Our fancy way of
writing this with set theory notation is:
NPS = {x ∈ S | x ∉ F(x) }
Note that NPS must be in P(S), since P(S) contains every
possible subset of S.
But now we have a problem. What member of S is mapped to NPS?
Call this m. Is m ∈ NPS? If m is, then m is in the
set of elements of S that do not point at a set that they are
in; so that contradicts that F(m) = NPS (to say that F(m) =
NPS is just to say F maps m to NPS, or that F makes m point
at NPS). So consider the only other alternative: m ∉
NPS. But since F(m) = NPS, this means m points at a set that
m does not belong to; and so by definition m should be in NPS!
Either option yields a contradiction. The source of our
contradiction, we conclude, is the assumption that |S| =
|P(S)|. So, since we already knew that |S| ≤ |P(S)|, we
conclude |P(S)| > |S|.
This proof is general. We said nothing about the particular
contents of S.
1 March
Continuing to review Galileo's objections to reasoning about
infinity, and Cantorian replies.
I promised to put my reconstruction of Galileo's arguments
here.
Galileo's Reductio Arguments (DeLancey's Interpretation)
I. The soupdish.
1. We cannot reason about actual infinities.
2. For (assumption for reductio ad absurdum): suppose we could reason about actual infinities.
3. If we could reason about actual infinities, then reason would tell us:
4. There is a geometric figure which we have called "the soupdish": every cut with a plane above the intersection of the cone and dish perpendicular to the axis yield a ring and cone of the same volume.
5. The last cut of the soupdish yields a point and a circle.
6. A point has one point, a circle has infinitely many points, so the circle has greater volume than the point (and so the circle is not the same volume as the point).
7. But 4 and 5 tell us that the point and circle have the same volume.
II. Composition of indivisibles.
1. We cannot reason about actual infinitesimals.
2. For (assumption for reductio ad absurdum): suppose we could reason about actual infinitesimals.
3. If we could reason about actual infinitesimals, then reason would tell us:
4. Every line can be cut in two equal halves.
5. Three points (or any odd number of points) together would form a line.
6. By 4 and 5, we could divide a line composed of an odd number of points in half.
7. But that means we must cut a point in half, since an odd number of points will have a point at its center.
8. But by definition we cannot cut a point in half.
III. Comparing sizes of infinities on lines.
1. We cannot reason about actual infinities.
2. For (assumption for reductio ad absurdum): suppose we could reason about actual infinities.
3. If we could reason about actual infinities, then reason would tell us:
4. There are lines which are longer than other lines (for example, suppose AB is half as long as a line ABC that contains AB).
5. Each line has infinitely many points (for example, AB and ABC both have infinitely many points).
6. A line twice as long as another line has twice as many points (for example, AB has half as many points as ABC); so the two lines have a different number of points.
7. But by 5, any two lines have the same number of points: namely, infinitely many (so AB has infinitely many points, and ABC has infinitely many points).
IV. Comparing naturals and squares: correspondence argument.
1. We cannot reason about actual infinities.
2. For (assumption for reductio ad absurdum): suppose we could reason about actual infinities.
3. If we could reason about actual infinities, then reason would tell us:
4. We can identify a 1-to-1 function on the natural numbers and onto the squares of the natural numbers.
5. From 4, we conclude there are exactly as many natural numbers as squares of natural numbers.
6. The squares of the natural numbers are a proper subset of the natural numbers.
7. From 6 we conclude that the squares of the natural numbers is smaller than the natural numbers (and so there are not exactly as many natural numbers as squares of the natural numbers).
V. Comparing naturals and squares: growth argument.
1. We cannot reason about actual infinities.
2. For (assumption for reductio ad absurdum): suppose we could reason about actual infinities.
3. If we could reason about actual infinities, then reason would tell us:
4. We can identify a 1-to-1 function on the natural numbers and onto the squares of the natural numbers.
5. From 4, we conclude there are exactly as many natural numbers as squares of natural numbers.
6. From 5, we conclude that the quantity of naturals and squares grow towards infinite quantities at the same rate as we count through the numbers.
7. But for each square matched to a natural number, as we count through the numbers, more and more natural numbers are left out of the set of squares.
8. From 7, we conclude that the quantities of naturals and squares do not grow towards infinite
Our task was to see which of the premises Cantor and those who agree
with Cantor would reject, if we do not agree that the problem is the
assumption for reductio. Keep in mind two principles of modern
geometry: that all geometric figures (other than a point) have aleph-1
many points; and that measures like length, area, and volume are not
determined by the quantities of points (all lengths, areas, and
volumes have aleph-1 points). Combine those observations with
Cantor's Claim, and it becomes clear what Cantor would reject in each
argument.
4 March
In class: Some review. Then, a question: when do we
know if a set exists? Consider the special case of the set
of everything. Does that exist?
Optional homework: The last two problems on the last
homework were harder than I expected, and I did not phrase
them as easily as I could have. So here's a chance to do
them over. If you do this, just staple this to your old
homework. I'll just replace those points on your last
homework. (E.g., these 7 points will replace those 7 points
on the last homework.)
- What are the comparative cardinalities of these two
sets (is one larger than the other, or are they the same
size)?
- The natural numbers, N
- The odd numbers (you can call this O)
If you say they are the same size, identify a 1-to-1
function on N and onto O. If you say
they are different sizes, explain why you think they
are (for example, is one the power set of the other?).
- Simplicio (one of the character's in Galileo's dialogue)
argued that a line segment AB that is twice as long as a
line segment CD has twice as many points; but also AB and
CD have infinitely many points, and infinitely many points
is as many as infinitely many points, so AB and CD have the
same number of points. Thus, the segments have differenly
quantities of points (AB has twice as many points as CD)
and the same quantity of points (AB and CD have the same
number of points -- namely infinitely many). This
contradiction led him to conclude we cannot reason about
actual infinities.
However, if we agree with Cantor, there is no contradiction
here (and Simplicio/Galileo made a mistake in that argument
above). For Cantor: How many points are on the line segment
CD? How many are on the line segment AB if it is twice as
long as CD? What does this tell us about Simplicio's
argument?
6 March
Taking stock of where we are at. Maybe some set theory review
and practice, including the set-theory antinomy. Review of
where we've come to -- and how should we respond to the
set-theory antinomy?
I will answer any questions you might have about the
test.
Frege! Logicism!
11 March
We can review anything you would like to review in preparation for
the test, but you have to bring questions to class in order for us
to be able to do that. If that doesn't take all our time, we'll
return to Frege.
13 March
Quiz on: basic concepts of set theory; reconstructing Cantor's
diagonal argument; reconstructing Galileo's arguments that we
cannot reason about infinity; Cantorian replies to Galileo's
arguments; Cantor's Claim, and how it answers some of Galileo's
challenges; Cantor's Theorem, and how it led to the set-theory
antinomy.
I'll include with your test the handout on sets, so that you
have with you the definitions we've been given.
15 March
We will review the test. The average (mean) was 28; but the
average (mean) for those who skipped one or more homeworks
was 19. I've given you all midterm grades, which I assume are
available online. Those are distorted because they count a
few homeworks as half your grade. But we'll strive to have
at least five more homeworks, in order to bring more balance
to that. The midterm grades are approximate.
I can share later my grading key.
After our review, time allowing, we'll talk about Russell's
postcard to Frege.
25 March
Hilbert's problems!
27 March
We will review the concepts of: consistency, decidability,
completeness. We will also discuss a brief detour into
intuitionism. And then: more paradoxes!
If you purchased Logicomix, now is a good time to read the
first 3 sections. This would take you to page 154. There are
many historical inaccuracies in here, which the authors took in
order to simplify and dramatize the story. The basic thrust is
not inaccurate, however; so don't treat it as a primary source but
rather as a dramatic introduction to the portion of our potted
history that we are discussing now. It's a fun book.
Some of you have asked me if there are other classes on this kind
of stuff. If you like logic or these kinds of weird discoveries
(such as those about infinity), you might want to consider a minor
in logic. The requirements for the minor are available here.
1 April
Principia Mathematica!
If you purchased Logicomix, finish it.
3 April
Introduction to Godel.
If you got the book by Casti, Godel, read chapters 1-4.
Additional resources include the Stanford Encyclopedia
entry on Godel; this is often technical, but the first few
sections provide some accessible background.
5 April
If you chose to buy Godel, now is a good time to read
(up to and including) chapters 6 and 7.
8 April
Homework due. I'll bring the homework to class on 3 April,
but also you can download it
here.
10 April
We'll review again some questions that have
come up about Godel; then return to Turing's
brilliant idea and get ourselves comfortable
with it.
It can be helpful to use a Turing machine simulation, to play
with a machin and get a feel for it. Here's one that may
work for you:
http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html.
You could test your machine on it. You'll have to turn on Java
in your browser for it to work.
The Wikipedia entry on Turing
machines is actually quite thorough, if you want another
resource. The Stanford
Philosophy Encyclopedia is more technical, and specifies
the machine slightly differently.
12 April
We'll review some more machines, and introduce the idea
of a universal Turing machine.
15 April
Homework due. Working alone, you will write descriptions for
2 turing machines. You will need to provide for each: the
rule table, a description of how the tape will be interpreted
and configured (including how to interpret the output), and
where the head starts on the tape.
The machines should not be universal!
It can be helpful to use a Turing machine simulation. Here's
one that may work for you:
http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html.
You could test your machine on it.
Try to do the machines with only 1s, 0s (or 1s and blanks),
and as few other characters as you need as your alphabet
(sometimes it makes things a lot easier to add a character,
for example to mark the end of a number, so do that if it
helps you!).
The machines should be:
- A machine that tells us whether a number is odd or
even. (You can write a number n as n "1"s on the tape;
that's the easiest way to do it; then your machine would
tell is if the number is odd or even.)
- An addition machine for numbers n, m where always m >
0 but n could be 0. (You can write a number n as n "1"s
on the tape and m as m "1"s on the tape; that's the
easiest way to do it. Consider always starting with n.)
For each problem, clearly describe the proper input and its
interpretation, and the expected output and its
interpretation. That is, where does the tape head start and
finish in relation to the data, the answer, etc.
In class this day, we'll review the idea of a UTM, and then
return to Hilbert's Question about effective procedures.
Have we now answered that question?
17 April
I'll have office hours 1-2, trying to fit to Quest's schedule.
I hope that works for you.
19 April
We will review our homework; review Turing's diagonal
argument that we saw on Monday; then we'll look at
the crazy machine version of the Halting Problem.
22 April
We will review the Halting Problem. Then, our topic
will be: a surprising observation: what the Halting
Problem Result tells us about prediction.
Before class, play with a version of the LifeWorld; a
good one can be found here.
Can you identify a structure that stays the same over
time? Can you identify a structure that "moves"
across the world?
24 April
Homework due. You may work in teams; write the name
of every team member on the homework. Due at the
beginning of class. You are going to make two Turing
machines (none universal!) and write up their
specification. You'll hand in that specification.
It will be very helpful to use a Turing machine
simulation. Here's one that may work for you:
http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html.
Try to do the machines with only 1s and 0s (or 1s and
blanks), and as few other characters as you need as
your alphabet (sometimes it makes things a lot easier
to add a character, for example to mark the end of a
number, so do that if it helps you!).
The machines should be:
- an addition machine; it should be able to handle
0+0 or 0+ any number or any number + 0. (If you are
using 1s and blanks, then a zero may be a blank; and 0+5
might be written on the tape as (starting leftmost
under the tape head) "blank blank 11111". That is,
the first blank is zero, the second is interpreted as
separating your two numbers. 0+0 would be "blank
blank blank".)
- A subtraction machine, where the rightmost number
is always smaller than or equal to the left number.
For both problems, clearly describe the proper input
and its interpretation, and the expected output and
its interpretation, and where does the tape head
starts and finishes in relation to the data, and your
rule table.
In the past, I gave extra credit to teams that made
also a multiplication machine.
26 April
Read Turing's paper on artificial intelligence, "Computing
Machinery and Intelligence," available here.
Focus on sections 1, 2, and 6. (Skim sections 3, 4, and 5;
they provide a not-very-clear presentation of Turing
machines; skim section 7, which considers learning for
machines.)
While reading, ask yourself the following (there may be a
quiz asking these questions):
- What is the "imitation game" he describes?
How is it set up? What problem is it meant to
side-step? (This game is what is now called the
"Turing Test.") There are two versions, one with
humans, one including a machine. Why two?
- What are the 9 objections he considers to the
claim that computers can be intelligent? (#9 is nuts!)
- Of the 9 objections, which do you consider
strongest? (Don't say #9!) Why?
If you have a minute, you might play with one of the Elizas,
like
this one.
29 April
Continuing our discussion of Turing's paper on artificial
intelligence, "Computing Machinery and Intelligence,"
available here.
We'll likely have a quiz asking: What are the 9 objections
to artificial intelligence that Turing considers. Which is
strongest, in your opinion? Why?
We may also consider the Lucas-Penrose argument.
1 May
We'll continue a brief review of the objections that Turing
considers, and also our discussion of the Lucas-Penrose
argument. Then, on to our next topic: we will introduce the
formal definition of Kolmogorov Complexity and Chaitin
Randomness.
Your homework: read
Chaitin's Introduction to his book, The Limits of
Mathematics. This is very good because it reviews
much of the material we have discussed in the last half of the
semester!
Remember that I'm still taking revisions of Turing Machines.
3 May
Continuing our introduction of Kolmogorov Complexity.
6 May
I've gotten some panicked emails about this, so if you want to
take till Wednesday, that's OK.
Team project. You will write and hand in 2 (or 3) Turing-machine
and tape specifications. Each machine must do just one thing:
print a particular string on the tape. So, your first machine
should print 1 below; your second machine should print 2 below;
and the third is extra-credit but if you do it your machine must
print 3 below. Most importantly, for each of the following
strings, create the smallest turing machine and
starting-tape-contents that can print the string.
- 10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010....(and so on, forever)
- 10010101010010111110010000001110110110010010010110100101001000011001001001011101001001000110100100010110101010001001001110110000010101010101011001001000001110100111100000001101111101100100101101001111
- 10110111011110111110111111011111110111111110111111111011111111110111111111110111111111111011111111111110111111111111110111111111111111011111111111111110....(and so on, forever)
Remember, number 3 is extra credit.
To really demonstrate Kolmogorov complexity, we should be using a
universal turing machine, and writing programs for it; but that
would be a bit tricky for us since it would require learning to
program some UTM; so we'll just get the flavor of Kolmogorov
complexity by using raw Turing machines. We will define the
"size" of your program to be the number of rules you use, plus the
number of characters in your alphabet, plus the number of
characters on your tape before you start. Extra credit to the
team with the smallest program, so defined.
The second machine must halt with a tape that shows exactly this
string to get full credit; to make things easier for you I'm not
asking that the first and last machines halt (we can think of them
this way: if we stop them at some time ourselves, it will have the
pattern we want in progress of being constructed).
You'll need to hand in a sheet with your rule table, and with your
tape's starting contents (you get to decide these, in these
problems), and with information about how the tape and machine
are at the start, and information about where (for the second
problem) the head will be when it is done.
Remember: your task is foremost to get the string on the tape!
For example: for problem 2, when your machine is in halt if the
answer is on the tape, you've done it. When in doubt, just
remember that.
Also, remember that, because some find problem 3 to be hard, it is
optional extra-credit. But it's not so hard if you allow yourself
an extra symbol, like x, to mark the 1s you've counted already.
In class, we'll look at our last result: the undecidability of
randomness.
May 8
I will accept paper drafts up till and including on this
day.
May 10
We'll review your homework, and then discuss
the undecidability of randomness.
Review of all our major results. Discussion of formal
reasoning as akin to empirical work.