PHL309 Logic, Language, and Thought Professor: Craig DeLancey

Office: CC212C

Email: delancey@oswego.edu

Past Assignments29 JanuaryRead the selection from Aristotle. Come to class prepared to explain what Aristotle's view is on the infinite.

31 JanuaryReading. Read the selection from Galileo'sTwo New Sciences: First Day. You must read for class from page 35 (page 73 in the original) to page 44 (page 82 in the original). If you have time, read from the begining to page 44 -- you'll like it -- but otherwise just read those 11 pages.

(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....")

I emailed you the prefered translation. If you didn't get that email let me know.

Also, a fair translation is freely available here.

2 FebruaryHomework:Reconstruct as a reductio argument Galileo's argument that we cannot reason about infinity based on the relation of natural numbers to the squares of natural numbers. It occurs on pages 40-41 and following in our translation. Model your reconstruction on our reconstructions in class.

5 FebruaryReview of the arguments by Galileo. We'll discuss Cantor and also introduce set theory.I will have office hours today 1:45-3:00

7 FebruaryHilbert's Hotel. Functions. Are all infinities the same size?I won't have office hours today 1:45-3:00

10 FebruaryWe'll review how Cantor's notion of infinity and cardinality can answer two of Galileo's arguments; then review functions; before turning to the question, "Are all infinities the same size?" First pass at the diagonal argument.

12 FebruaryReview of the Diagonal Argument, and its implications.

14 FebruaryIn class: Galileo's four arguments in light of what we've discovered.

Homeworkdue at the beginning of class. 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.

- For each claim, identify if it is true or false.
a. {a} ∈ {a, b, c}

b. {a} ∈ {{a}, {b}, {c}}

c. 2 ∈ {1, 2, 3}

d. 2 ∈ {{1}, {2}, {3}}

- Which of these are identical? (You can answer "yes" or "no".)
a. {1} and {{1}}

b. {2, 3, 1} and {1, 2, 3}

c. {} and {{}}

d. {7, 7} and {7}

- Give an example of a
propersubset of each of the following sets.a. {a, b, c}

b. {1, 2}

c. {{a}, {b}, {c}}

- 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. Remember also our rule, if a set has n things in it, then it has 2
^{n}subsets.)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....}(Note that for c, the second set contains only one element, namely the number one.)

b. {1, 2, 3, 4, 5....} and {1, 3, 5, 7, 9, ....}

c. {1, 2, 3, 4, 5....} and {1}

19 FebruaryConsideration of the question: when do we know a set exists? And: is there a set of everything?

21 FebruaryBackground on Kant.

24 FebruaryWe will continue the discussion of Kant.

26 FebruaryReview: the diagonal proof; Cantor's theorem; the set theory antinomy; the challenge of the new geometry. How shall we answer these concerns?

28 FebruaryIn case you misplaced it, here is the first two pages of the handout on sets.

Let's do a review homework. Four problems due at the beginning of class.In class, we'll discuss the move towards reviewing foundations.

- What are the powersets of the following sets?

- {a, b}
- {}
- { {1, 2}, {{3}} }
- What are the following sets powersets of? That is, the powerset of what set would be the following?

- {{}, {a}, {b}, {a, b}}
- {{}}
- {{}, {1}}
- {{2}, {4}, {6}, {4, 6}, {2, 4}, {6, 2}, {}, {2, 4, 6}}
- Which of these sets has the largest cardinality -- or are they the same size? Explain what this means and how you know your answer is correct. You'll probably need to define cardinality, and describe an on and onto, 1-to-1 function, and then apply these notions.

- The natural numbers,
N- The even numbers (you can call this
E)- If there were a 1-to-1 function f on
Nthe naturals and ontoRthe reals, how would I construct a number z that was in fact not in the range of f? What is funny about z? (That is, why does it lead to a contradiction for the claim that there is a 1-to-1 function f onNthe naturals and ontoRthe reals?)

7 MarchIn class: review of where we've arrived.

FYI: this is not formally related to our class, but anyone with an interest in philosophy is invited to join us this Friday, March 7, in the philosophy department suite (Campus Center 212), at 4:00 p.m. We'll just talk for an hour or so about a paper, "Refusing the Devil's Bargain," by Kyle Stanford. It is about science and the pessimistic induction. This paper is short (10 pages!) and is here.

As background: over the summer, faculty and students read and discussed a few papers together, over pizza. The goal was to get together informally and think like philosophers do. Students led the discussion or just listened to other students -- whatever they preferred. Philosophy club has asked if we could do this again, at least once this Spring, so that's why we're meeting this Friday.

RSVPs are appreciated, since we like to order pizza and RSVPs give us a way to estimate how much pizza we'll need. So if you might come let us know by emailing me.10 MarchReviewing the ideas of decidability and consistency. Introducing the idea of completeness.

14 MarchMidterm exam. Here are some study questions.

- What is a powerset?
- What is Cantor's theorem? State it and explain it.
- According to Cantor, how do we know if two sets have the same cardinality? (You must explain "domain," "range," "on," "onto," what a function is, and what a "1-to-1" function are. Best to provide an example of two sets and identify an example function that is on, onto and 1-to-1.)
- Describe one of Galileo arguments that we cannot reason about infinity or infinitesimals. Be careful to construct the reductio arguments so that we see the clear contradiction he believes he finds in each case.
- What feature of Cantor's set theory solves a problem that Galileo raises for our reasoning about infinity (e.g., what feature solves the problem of the squares and naturals appearing to be both the same size and not the same size)?
- What feature of Cantor's set theory and modern geometry solves the geometric problems that Galileo raises for infinitesimals?
- What is Cantor's Theorem? What does it tell us?
- Describe Cantor's diagonal argument. For ease, you can show that the reals from 0 to 1 exceed the cardinality of the natural numbers. Feel free to use a fake example, but be clear about the construction of z and state it in a general way.
- Describe the Cantorian antinomy (the paradox with Cantor's first form of his set theory). Derive it.
- According to Kant, how do we know synthetic a priori truths about geometry? What is a synthetic a priori truth? Why is the discovery of non-Euclidean geometry seem to pose a problem for Kant's view?
- Describe Russell's "paradox" (you can describe the set theory version). Explicitly, why is it contradictory?
- What is logicism? Why did Frege's logicist project fail?

24 MarchReadLogicomixif you got it!28 MarchYou should read Casti'sGodelnow if you have it.

We'll review the test problems, and then we'll discuss Godel's proof a bit more. And then we'll talk about Godel's Second Incompleteness theorem!31 MarchHomework due at the beginning of class. I'll hand this homework out on the 28th.

In class: we begin discussing Turing!7 AprilReview of the Halting problem. In class we'll discuss implications of Turing's Halting Problem. In particular, we'll discuss the relation of predictability to determinism. Time permitting, we'll discuss the Lucas-Penrose argument.

If you have time before class, play with a Conway Life world. Here's one.11 AprilReading and a homework.

Reading:read the first 5 parts of Turing's "Computing Machinery and Intelligence." A version is available here. What does Turing mean by "the imitation game"? Be able to describe it. I might give you a quiz on it!

Homework:making two Turing machines. You may work in teams of 3 or fewer people. You are going to make two or three Turing machines (none universal!). You will do this by giving me, for each machine:It is most elegant to make your machine have an alphabet of 1 and 0, but that's not required. You will hand in at least two machines clearly explained that do the following two problems (or three machines, if you attempt the extra credit):

- Your alphabet
- An explanation of how the tape will be interpreted; this includes where the tape head will start, and where it will end (e.g., something like: "two numbers will be represented by quantity of '1s', separated by a single '0', the tape head will start on the leftmost figure of the left number, and end on the leftmost figure of the final output number").
- Your rule table. It will have a header like:

STATE.....INPUT.....OUTPUT.....MOVE.....STATE

and a typical line would look like:

Sn.........1.........0..........R........Sm

(Which means when in state Sn, reading a "1" on the tape, write a "0" and move right and go into state Sm.)Be sure the machine will work for any numbers that meet the requirement. That is, don't make a machine that can add only 2 and 2 for the first problem -- your machine must be able to add

- an addition machine; the machine must be able to handle 0+0, and any other two positive numbers.
- a subtraction machine for two number n and m where n >=m (this restriction makes it easier!).
- extra credit! A multiplication that multiplies two numbers n*m. (This one is much easier if you allow yourself a bigger alphabet than just 1 and 0; but I'll be very impressed if you can do it with 1 and 0.)
anytwo natural numbers.

One way you can test your ideas and get ideas is to play with some of the turing machine simulators that some scholars have written. Here are some:http://math.hws.edu/TMCM/java/xTuringMachine/.And there are others if you google around; let me know if you find a good one. Many won't run on some machines now because browsers are so insidiously rejecting of Java.

http://www.turing.org.uk/turing/scrapbook/tmjava.html .

14 AprilWe'll review your turing machines. Then, we'll introduce Kolmogorov Complexity.