Hmmmm

Last week we talked more about computable functions. On Friday we had another class problem about diagonals. The professor showed that the halting function is not computable because there's a counterexample that uses the halt function. It feels weird because that's a special function that makes the halting function doesn't work. I didn't get it last time too, because if the halting function is well defined, and we know what the output should be for all inputs, then what's the right output for the halting function? I think it would have been cool if they talked about if it was possible to write a halting function for functions that don't try to use the halting function

Hmmmmm

Last week we began talking about the halting function in Danny's section. We also talked about the size of sets, and how to count big sets like the rational numbers. He showed that the size of even numbers is the same as the size of natural numbers. It's not intuitive but I guess it makes sense from the definition. Hmmmmm

Hmmmm

We are learning about using big O notation for algorithms in class. It's mostly the same as our old proofs but we have to count how many steps a function takes. Then we started doing more big O proofs in class. They also seem like our old proofs, except the statements are much longer and there is a similar structure in most big O proofs. Finally we started learning about computability in Larry's class. I'm confused about what a well defined function is. Larry said a well defined function is a function we know what the output should be for every input. Or something like that. And he said that a computable function is a function we know how to get the output. The halting function is supposed to say whether a program or function halts, and he gave an example of a function that loops if the halting function says it halts, and stops if the halting function says it doesn't, so there is a contradiction. But if the halting function is well defined, what is the output supposed to be for this special function? I wish I understood this class better, like those people who always raise their hand and speak really loudly. Someone even took the time in lecture to explain to everyone where the number 42 comes from. That was very helpful, because I would have been confused about the code example otherwise.

Hmmmm

Last class the professor did a full example of proving that insertion sort is O(n^2). I think it made sense, but I'm starting to get confused about all the formats we have to follow. In the tutorial, the quiz was another proof. I'm worried about the formats of my proof in assignment 2. It's also hard to find new things to talk about because I'm not very good at programming algorithms and we've talked a lot about proofs

Hmmmmm

Hi, this week the professor said we were finishing up on proofs. I enjoyed the proofs section of the class. In high school, my teacher said epsilon delta proofs were hard, but they made more sense when the professor in this class did it. But when I tried thinking about it myself, it was frustrating. I felt good about the tutorial quiz this week. Even though I'm not that good with proofs, the problems are usually like the homework problems. I like them because I think they test people's understanding.

We started learning about sorting algorithms in class. To start, the professor asked us how we sort cards in our hands. Other people had specific ways they sort them. I thought about it, and I don't know how I sort my cards. I just move them around until they look sorted. Maybe I would be better if I knew how to sort my cards. My friend laughed and said I used bogosort, but it wasn't one of the algorithms in the lecture slides. Then he showed me it on wikipedia, and I don't think it was a good sorting algorithm. The professor said python uses timsort, so I should try to learn to sort my cards better.

Hmmmm

There was only 1 lecture so far this week because of thanks giving, and there were no tutorials. So I'm not sure what to write about. But I was thinking about something someone said in tutorial, and I thought of an answer this week, and I think it's interesting, so I will write about it.

Someone said that when you do ∃x, y, it should automatically mean x is different from y, because whenever you write ∃x, y you don't want them to be the same thing. It seemed right, but sometimes you don't care if x and y are the same. I thought of this example this week.

I say "The set S of positive even numbers excluding four is closed under addition." You say that's not true, and there's a counterexample: ∃x, y ∈ S, ¬(x + y ∈ S). But I don't think there are counterexamples if x and y are different. But if x and y are the same, 2 + 2 is 4 which is not in S.

So, sometimes when we use ∃x, y, we don't care if x and y are the same. Actually, in this example, it's important that x and y are generic.

This looks kinda short, so I will write about how one of my other classes related to CSC165. There was a question in a past midterm that said "the logic function f is true when any 2 of the inputs are true." My friend and I thought it meant "at least two are true", because if three inputs are true, there are "any 2" inputs that are true. But in the answer, "any" meant "only". In English, people might argue about exactly what things mean. But if I write it symbolically, I think most people would agree that "any two are true" is ∃x, y ∈ S, x not equal to y, x ∧ y. Now, it's clear that if three inputs are true, "any two are true" is still true. It's also clear that P(S) = ∃x, y, z ∈ S, x not equal to y not equal to z, x ∧ y ∧ z is a subset of Q(S) = ∃x, y ∈ S, x not equal to y, x ∧ y (the set of sets such that P holds is a subset of the set of sets such that Q holds). If P is a subset of Q, then P ⇒ Q. If Q(S), then we know three different inputs x, y, z are true. I can pick two for satisfying Q(S). Symbolic notation is good

Hmmmm

In class we started learning about proofs. I saw a cool problem yesterday. I thought I'd try to prove it using the stuff we learned in class.

Prove that f(n) = 1 − n is the only integer-valued function that defined on the integers that satisfies the following conditions:
a) f(f(n)) = n for all integers n
b) f(f(n + 2) + 2) = n for all integers n
c) f(0) = 1

I'm going to try to write it symbolically. Let F be the set of integer valued functions defined on the integers. ∀ f ∈ F, ∀ n ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n

Proof. The indents work in my word processor, but I don't know why my indents didn't work here, so I used dashes.

First I want to prove that f is one to one. I'm going to try to write that symbollically. ∀ x, y ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)

Assume x, y ∈ Z # x, y are generic
- Assume f(f(n)) = n, f(f(n + 2) + 2) = n, f(0) = 1 # assume first antecedent
- - Assume f(x) = f(y) # assume second antecedent
- - - Let z = f(x) = f(y)
- - - z ∈ Z # f is an integer valued function function
- - - f(f(x)) = f(z) = x # f is defined on the integers
- - - f(f(y)) = f(z) = y
- - - Then x = y
- - Then f(x) = f(y) ⇒ x = y
- Then (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)
Then ∀ x, y ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)

Now f is one to one.

Assume f ∈ F, n ∈ Z # f, n are generic
- Assume f(f(n)) = n, f(f(n + 2) + 2) = n, f(0) = 1 # assume the antecedent
- - Assume n | 2 (n is even)
- - - Then ∃ x ∈ Z, n = 2x # definition of even
- - - f(f(2x + 2) + 2) = 2x = f(f(2x))
- - - f(2x + 2) + 2 = f(2x) # f is one to one
- - - f(2(x + 1)) = f(2x) - 2
- - - Let a_x = f(2x)
- - - a_(x + 1) = a_x - 2
- - - a_x forms an arithmetic sequence
- - - a_0 = f(2 * 0) = 1
- - - d = -2
- - - a_x = a_0 + dx = 1 - 2x
- - - f(2x) = 1 - 2x
- - - Then f(n) = 1 - n
- - Then n | 2 ⇒ f(n) = 1 - n
- - Assume ¬(n | 2) (n is odd)
- - - Then ∃ x ∈ Z, n = 2x + 1 # definition of odd
- - - f(f((2x + 1) + 2) + 2) = 2x + 1 = f(f(2x + 1))
- - - f(2(x + 1) + 1) + 2 = f(2x + 1) # f is one to one
- - - Let a_x = f(2x + 1)
- - - a_(x + 1) = a(x) - 2
- - - a_x forms an arithmetic sequence
- - - a_0 = f(2 * 0 + 1) = f(1) = f(f(0)) = 0 # f is one to one
- - - d = -2
- - - a_x = a_0 + dx = -2x
- - - f(2x + 1) = -2x
- - - Then f(n) = 1 - n
- - Then ¬(n | 2) ⇒ f(n) = 1 - n
- - Then (n | 2) ∨ ¬(n | 2) ⇒ f(n) = 1 - n
- - Then f(n) = 1 - n
- Then (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n
Then ∀ f ∈ F, ∀ n ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n

Hmmmm

We did a class problem in lecture last Friday. The problem was to predict the ups and downs of paper after folding it from right to left a number of times. I thought about it but I'm not sure, but I tried. I will write about my guess at a solution.

First I thought that the middle crease is always down. My partner was writing out the ups and downs after folding it 1, 2, 3, 4, 5 times. He tried to find a pattern, and I tried to help, but when I thought about it, it was hard. But I noticed that there are always an odd number of creases.

Then professsor Heap said to think recursively and symmetrically. I'm still kind of confused about recursive, but I know what symmetric means. I thought I should define my functions and domain. My high school math teacher said that's a good place to start when you don't know what to do. So I stated my knowns and unknowns.

P is a function. P(m, n) is 1 when the nth crease from the left after m folds is up, and -1 when the nth crease from the left after m folds is down. m is the number of folds, starting from 1. n is the index of a crease, in [1, 2^m)

2^(m - 1) is the middle crease. Let's say k = 2^(m - 1) because it's easier. I think P(m, k) = -1. The first fold makes the middle crease which is always down.

Then I thought, for n in [1, k), we are looking at the creases on the left side. The left side is always flat on the table, so it is like folding a new piece of paper. So P(m, n) = P(m - 1, n).

Then I thought about the other side. For n in (k, 2^m), we are looking at the creases on the right side. When folded, the right side is like the left side, but upside down. While it is upside down, the right side has the same folds as the left side. But when you flip it back, all the ups become downs, and all the downs become ups. The creases on the left side become the creases on the right side. So P(m, n) = -P(m, 2^m - n)

I tried to write a python program to try it because sometimes professor Heap does python in class. But I kept getting a typeerror. But I wanted to write about my thoughts because I thought it was pretty cool. But I might be wrong. Together, I have

P(m, n) =
-1 if n = 2^(m - 1)
P(m - 1, n) if n in [1, 2^(m - 1))
-P(m, 2^m - n) if n in (2^(m - 1), 2^m)

Trying some simple values seems to work. P(1, 1) = -1. P(2, 1) = -1. P(2, 2) = -1. P(2, 3) = 1. P(3, 1) = -1, P(3, 2) = -1, P(3, 3) = 1, P(3, 4) = -1, P(3, 5) = -1, P(3, 6) = 1, P(3, 7) = 1.

Hmmm

Tutorial was interesting this week. The first interesting thing was question 2. The statement is "every course has a prerequisite." Someone said ∃x ϵ C, ∀ y ϵ C, P(x, y). Someone said that's wrong, and it should be the other way around (∀ y ϵ C, ∃x ϵ C, P(x, y)), and most people agreed. Then someone said that it's still true, and people said "wait, it does work." Because the first expression means that there exists one course that is a prerequisite for every course, and that means that every course has a prerequisite. But the two are not equivalent. x ϵ C, ∀ y ϵ C, P(x, y) ⇒ every course has a prerequisite, but every course has a prerequisite does not imply that there exists a course that is a prerequisite of every course. The second interesting thing was the last question in part 1. "Some courses have the same prerequisites." The first answer was ∃x, y, z ϵ C, x ≠ y, P(z, x) ∧ P(z, y). But this only means that some courses have a common prerequisite. ∃x, y ϵ C, x ≠ y, ∀ z ϵ C, P(z, x) ⇔ P(z, y) means some courses have the exact same prerequisites. The third interesting thing was that someone said in English, "only if" is the same as "if and only if". People said not to use English meaning in logic, but he continued. The English meaning is actually correct too. He said if I say "I will quit only if you report me to the media." He said that if I quit, you must have reported me to the media (P ⇒ Q). It's easy to think that if you report me to the media, I will quit (Q ⇒ P), because being reported to the media is scary. But that doesn't have to be true. But he insisted that was the case. Eventually someone said there will be rainbows only if it rains. There can't be rainbows if it doesn't rain, but if it rains, there don't have to be rainbows. Class discussion in tutorials brings up interesting things.

Hmmmm

Something new I learned in this class is that a statement about a set of elements is true if there are no counterexamples. Any claim about the empty set is true because there are no elements in the set that disprove it. We have to be careful in every day usage, because sometimes we do not know of counterexamples, but that doesn't mean there does not exist a counterexample. I might say "For all elements in the set of living creatures in the universe, none of them are unicorns." Most likely, other people won't have a counterexample to this claim, because there is no reputable evidence of at least one of the living creatures in the universe being a unicorn. However, there could be living creatures in the universe we don't know about, so there might be counterexamples to the claim in the set of all living creatures in the universe.

I feel confident about the material covered this week. Implication, the converse, and contrapositive were covered in Mat188 - Linear algebra. Burbulla was the lecturer. He was cool. The tutorial was good. We reviewed the homework questions. The quiz was interesting. It was like the tutorial preparation questions, but in the quiz question, we don't know if the sets are non empty. In the homework, we know there are three test programs. If T - P must be empty, then T ∩ P must be occupied, because there are three test programs. However, in the quiz, P - L does not imply that P ∩ L is occupied. P may be an empty set, and any claim about the elements of an empty set are true.