1. May 13, 2006

### samh

Right now in my class we're being given a short introduction to theoretical CS. We're learning not from a book but from our teacher's Ph.D. thesis! The thesis is HEAVY on formal math and I can't follow it... I've been trying for DAYS and have spent many, many hours reading around but it's not making sense. I'm officially desperate now and so I've come here to ask if I could possibly get some help from you guys.

Here's the part I'm stuck on, it's about Turing machines:

http://img105.imageshack.us/img105/5915/help27ib.th.jpg [Broken]

I've been reading a lot and I now understand the distinction between an Urelement and natural numbers as defined with sets (with the axiom of infinity). It's the rest of the paper that I don't get. If any of you could explain to me what the paper is saying possibly with some examples (especially of the Sq thing) then I would be very greatful. If you're pressed for time then here are the parts I'm most confused about:

• What does the Sq(w)(A) thing mean!?!? If A is, say, { a, b, c }, then what would Sq(w)(A) be? Can you lay it out for me (i.e. write out the elements of the set in set notation { ... })?
• In the definition part, when it says "Let A be a set, u, v in Sq(w)(A)" what does that really mean? If something is an element of Sq(w)(A) then what does it look like?

Last edited by a moderator: May 2, 2017
2. May 13, 2006

### StatusX

An is the set of all n-tuples of elements of A, ie, ordered sets of n elements from A. For example, if A=R, the set of real numbers, then Rn is just n-dimensional Euclidean space (you're probably familiar with this as a vector space, although here it is just a set, with no extra structure). For example, (1,2,6) is an element of R3.

Sq(w)(A) is the union of the An for n=0,1,2,.... In other words, it is the set of lists of elements of A of any finite length. (1), (1,2,3), and (12,12,12,12,12) are all elements of Sq(w)(R).

Last edited: May 13, 2006
3. May 13, 2006

### AKG

No, nA is the set of lists of elements of A of size n, An is the set of functions from n = {0, 1, ..., n-1} to A. Of course, there is a natural bijection between the two, but nA never really comes up on that page, except when it is defined. Sq(w)(A) is the union of all An, so it is the set of all functions from a natural number to A. If u, v are in Sq(w)(A), then u and v are functions, each whose domain is a natural number (although u and v need not have the same domain) and both of whose codomain is A.

So if A is {a,b,c}, and u is an element in Sq(w)(A), then u is a function u : n -> A where n is some natural number. If n were 5, say, then u could be the function defined by:

u(0) = u(1) = u(2) = u(4) = c; u(3) = b

In general, a function from X to Y can be written as a set of ordered pairs, where for each x in X, there is a unique y in Y such that (x,y) is in this function. For example, the squaring function on the reals is the set:

{(x,x2) | x in R}

So the function u above could be written as:

u = {(0,c), (1,c), (3,b), (3,b), (2,c), (4,c)}

Note that the repetition of (3,b) has no significance, nor does the order of the elements of u, so u could have been written as you'd expect to see it:

u = {(0,c), (1,c), (2,c), (3,b), (4,c)}

Last edited: May 13, 2006
4. May 13, 2006

### samh

I don't get it... The paper says nA but StatusX is saying An and AKG is saying An. Is there something I'm missing?

Edit:

I see now! AKG what you're saying is now making sense to me. Sq(w)(A) is an infinite set of functions. Therefore u and v being members of Sq(w)(A) means that they themselves are functions too, and that set of ordered pairs is actually a function specification. And now I see what they mean by u(0) since u is actually a function. After all this time it finally makes sense... Thanks guys.

Last edited: May 13, 2006
5. May 13, 2006

### AKG

Sorry, An was a typo, I meant An. Anyways, it seems like you understand it now.