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.16 AprilWe'll discuss some features of Kolmogorov Complexity a.k.a. descriptive complexity:

- A review of Chaitin Random vs. Compressibility vs. Information
- What yardstick should we use?
- Do different yardsticks give us different measures?
- Is this measure decidable?
- How many strings are Chaitin Random?
21 AprilK-complexity and randomness

23, 25 AprilWhile I'm in Tucson, meet in class and work on these problems! You can work in teams of 4 or less people for this one and hand in a single homework for the whole team. We're going toapproximateKolmogorov Complexity. We don't have a UTM, so we'll instead count characters on the tape and states. Using for each as small an alphabet as you can manage, make three turing machines and start tapes that can "print" (that is, will leave the tape such that on it there is) the following three strings. Of course, that meansyou hand in (1) a rule table and (2) a start tape condition for each string. Try to do so with as short a program and as few things on the tape as you can manage; extra credit to the team that has the lowest total count for a problem. If you like, assume that the tape comes completely full of 0s before you add anything to it (that is, each square has on it already a 0, so they don't count unless they are between other characters -- as if you bought the tape pre-zeroed). The three strings are:

- "10101010..." forever. (Extra credit, print also just "1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010", that is, make a machine that will instead just print "10" fifty times only.)
- "10110111011110111110..." forever.
- "10010101010010111110010000001110110110010010010110100101001000011001001001011101001001010110100100010".

28 AprilReview! Time willing, we'll introduce the incompressibility result. Your Turing machines are due at the beginning of class.30 AprilReview of your Turing machines. Continuation of the incompressibility result. Introduction of the complexity cost principle.2 MayWrap up of Kolmogorov complexity.5 MaySome review, probably focusing on Cantor and set theory. Then:

Implications I. Do our results have any implications for the prospects of artificial intelligence?7 MaySome review, probably of Kant and Turing. Then:

Implications II. What do our results mean for mathematical knowledge?

BTW: some people asked me for example Turing machines. Here's my machine for the problem that prints all the natural numbers, interpreting quantity of 1s as the number.Tape condition: the tape is full of blanks, except for the single string 010.

Start condition: the machine starts on the blank immediately right of the 010.

Start state: S_{0}.

Halt state: S_{h}(not needed here).

Rule table, in order, in-state/reading/write/move/go-into-state:0 # 1 L 1Here "#" means blank. I cheated and wrote just a number for the state -- "4" instead of S

0 1 1 r 0

1 0 0 L 2

1 1 1 L 1

2 $ $ L 2

2 0 0 R 4

2 1 $ R 3

3 # 1 L 1

3 $ $ R 3

3 0 0 R 3

3 1 1 R 3

4 # 0 R 0

4 $ 1 R 4

4 0 0 R 4

4 1 1 R 4

_{4}.

If you want to copy my machine, try to have it work on just a blank tape (so have it first print "010" on the tape before running as above).9 MayReview! Then:

Implications III. Is there an actual infinity?