Due 2007.Oct.09 (Tue) 17:00.

See some sample problems.

Although you are welcome to typeset your work nicely (using Microsoft Word or LaTeX or whatever to get nice logic symbols), it's probably much easier to write formulas by hand.

Remember that to prove a ∀ requires showing that something holds for all possible value. Disproving a ∀ is easier; you simply show one counterexample. Conversely, to disprove a &exists; requires showing that something never holds, and proving an ∃ is easier; you simply show a witness making the statement true.

Rosen p.85 #10: Prove that Q is closed under multiplication (that is: the product of two rational numbers is rational).
You'll of course need to use the definition of Q = { x | ∃p,q such that x=p/q, p ∈ Z, q ∈ Z-{0} }. Let x and y be any rational numbers; we show that x·y is also rational. 1 ∃p,q such that x=p/q, p∈Z, q∈Z, q≠0 Definition of x∈Q. 2 ∃r,s such that y=r/s, r∈Z, s∈Z, s≠0 Definition of y∈Q. 3 x·y = (p/q)·(r/s) = (p·r)/(q·s) algebra 4 p·r ∈ Z, and q·s ∈Z, Z is closed under multiplication 5 q·s ≠ 0 q≠0 and s≠0; multiplying non-zero numbers can't result in zero. 6 x·y is rational definition of rational: lines 3,4,5. lines
Rosen p.85 #30 (an equivalent variant): Show that a<b if and only if a is less than the average of a and b.
Hint: your answer should be a series of inequalities, joined by "is equivalent to".

An if and only if requires two parts; we're sure to clearly bullet each part, to make the outline of our proof evident.

Part I, if: We show that if a<(a+b)/2, then a<b:
a<(a+b)/2
≡ 2a<(a+b) (multiply each side by 2)
≡ a<b (subtract a from each side)

Part II, only if: We show that if a<b, then a<(a+b)/2.
(Since each step of part I is reversible, we can actually just take those same steps in reverse:)
a<b
≡ 2a<(a+b) (add a to each side)
≡ a<(a+b)/2 (divide each side by 2)

Prove that Q is dense: that is, between any two (different) rational numbers there exists another rational number.
(Does this problem relate to the previous one?) Is the function stringLength: Σ* → N … one-to-one? onto? You may abbreviate stringLength as L. In each case, prove your answer (whether yes or no). (You'll of course need to use the exact definition of one-to-one and onto from the book.) Rosen p.103 #18: uniqueness of floor.

If you see a few other problems in Rosen which catch your eye, and you'd like to do them for extra credit, you are welcome to (though you can ask me for how much; extra-credit is harder to earn point-per-point than regular credit).

If you write your own html, you might be interested in this page of useful html math (and other) entities