Given (Ax)(Ey)Pxy
Prove: (Ey)(Ex)Pxy

What is the difference between (Ax)(Ey)Pxy  and (Ey)(Ax)Pxy

For the first one:  (Ax)(Ey)Pxy, for every x there exists a y so that Pxy is true, but the y may not be the same y for the different values of x.

Pab, Pbc, Pcc.

(Ey)(Ax)Pxy.  This means that there's some y out there so that Pxy is always true no matter what x you put in.

Pac, Pbc, Pcc

(Ax)(Ay) Pxy <=> (Ay)(Ax) Pxy
(Ex)(Ey) Pxy <=> (Ey)(Ex) Pxy

Given (Ax)(Ey)Pxy

Prove:  (Ey)(Ex)Pxy

1.  Given (Ax)(Ey)Pxy
2.  (Ax)(Ey)Pxy (Given, 1)
3.  (Ey)Puy (AE, 2)
4.  	Assume Puv <== Assumption because I want to use EE on line 3.
5.	Puv (Assumption 4)
6.	(Ex)Pxv (EI, 5)
7.	(Ey)(Ex)Pxy (EI, 6)
8.  (Ey)(Ex)Pxy (EE,3,4-7)

Prove:  A number is a square of a prime if and only if it has exactly three factors.

==>:  Assume n is the square of a prime.  (This means that there exists a number such that this number is prime and that number squared = n.)  Call this number p.  Since n = p^2, n is divisible by 1, by p, and by p^2.  It can't be divisible by anything else due to the Fundamental Theorem of Arithmetic.  Therefore, n has exactly three factors.

<==:  Assume n has exactly three factors.  I already know what two of the factors are:  1 and n.  So there exists a third factor:  Call it p.
p is a factor of n.  There n/p is an integer.  n/p can't be 1.  And n/p can't be n.  Why not?  I've used those already.  (1)(n) = n.  So n/p is 1, then n=p.  And if n/p = n, then n=1, but I've already that p the third factor.  (Appealing here to contradiction.).
So, n/p must be p.  n/p has has to be a factor of n, and it's not n, and it's not 1, so it must be that third one, since we've assumed there are exactly three.  Therefore n = p^2.
Assume p is not prime. [Remember that we know that p is also not 1.] Then there exists a number (call it q) such q divides p, but q is not p, and q is not 1.  This means that q divides n, q is not 1, q is not p, q is not n, so we've found a fourth factor for n.  Contradiction.

Therefore, n is a square of a prime.

Therefore, n is a square of a prime if and only if n has exactly three factors.

Part 1:  Prove that if n is a product of exactly two primes, then n has exactly four factors. [1,p,q,pq].

Part 2:  Is it true that if n has exactly four factors, that n is a product of exactly two primes? [n might be the product of two primes, but it also might be the cube of a prime.] 8:  1,2,4,8.

Prove that there is no rational number whose square is 2.

Assume there IS a rational whose square is 2.  This fraction can therefore be put in reduced form (since all fractions can be), so we will call this fraction p/q .  And we know that (p/q)^2 = 2.  This means that p^2 = 2 q^2.  Thus, p^2 is even (because it's 2 times something else.).  If p^2 is even, then p^2 is divisible by 2, so p must be divisible by 2, since 2 is prime.  So, p = 2r, for some value of r.
p^2 = (2r)^2 = 4r^2.   4r^2 = 2q^2, so that q^2 = 2 r^2.  This means that q^2 must be even, and so q must be even.  Well, p and q are both even, so p/q is not reduced after all, and that's my contradiction.

So, there is no rational number is square for 2.

Turing Machines:  My alphabet is {0,1} (and a space).  Suppose my input tape consists of a string of 0's and 1's, followed by a space (and I don't care what else is on the tape.)  This string of binary digits represents a binary integer, and I want to increment it.  (Add 1 to it.)  So, what I want for my output is to have the incremented number, followed by a space, and my head is on the first character of the answer.

First, move to the space.
Move left one.
Then move to the left flipping 1's to 0', until you find a zero or a space and flip that to 1.

1: '0',L,2
   '1',L,2
   ' ',L,2

2: '0',' ',3
   '1',' ',3
   ' ',' ',3

3: '0',R,4
   '1',R,4
   ' ',R,4

4: '0',R,4
   '1',R,4 <= Moving right until I get to the end of the string
   ' ',L,5

5: '0','1',6
   '1','0',7
   ' ','1',H

6: '0',L,6
   '1',L,6
   ' ',R,H

7: '0',L,5
   '1',L,5
   ' ',L,5