ITEC 420 2020fall ibarland

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

hw01

• Reading: Appendix A of the text.
• Please put your solutions in order and clearly label each with the problem number.
• Always be clear about what kind of object your answer is (e.g. a set, or an ordered pair) and use the right kind of notation (eg {…} for sets and ‹…› for tuples).
• Late assignments not accepted.

part (a)

Due 2020-Aug-21 (Fri) 10:00.

1. Express the set A without using the cross product: A = {1, 2} x {a, b} x {d, e}.

   Hint: What kinds of things are the elements of A? Once you know that, just list the elements, as a set.

2. Express the set B defined below without using the cross product: B = {1, 2} x {a, b} x { }.

   Hint: The last set in the definition is empty. Now apply that fact to the definition of cross product.

3. Draw a diagram that shows the proper-subset relation among the 8 elements of the power set of {1,2,3}. In your diagram, if P ⊂ Q with no proper subsets between them, then write Q somewhere above P and draw a line from P to Q.

   Note: This relation forms what is called a lattice.

4. Describe, in words, the set
   C = {x ∈ ℕ : ∃ y ∈ ℕ (y ≤ 12 ∧ (y+5 = x)}
   Your answer will start “C is the set of natural numbers x such that …”. Recall that ℕ denotes the set of natural numbers (i.e. the nonnegative integers).
5. List the elements, as a set, of the set C from the previous problem (your answer will look something like C = {19, 43, 55}).
6. Let the set of letters P = {a, c, e, g, w, y}. Express the set P using set builder notation.

   Hint: Consider the alphabet position of the letters, and also use some of the other problems in this homework as a pattern. You may use ord¹ to represent a character's ascii value. The expression ord(ch)-ord('a')+1 might be helpful.

7. Let the set A be you and two of your friends, and let the set B be the set of your car and the cars of these friends. (Assume that your friends have different makes of cars and if you or a friend doesn't have a car, simply choose a fantasy car.) Give example relations in A × B that meet the criteria listed below. List the relations as sets of ordered pairs. Each relation must have at least two elements. To save writing, you may use initials or first names for people and abbreviations for cars. For each function, indicate whether it is a total or partial function. If no such relation exists, say so.
   1. A relation that is not a function.
   2. A function that is 1:1 and onto (if possible).
   3. A function that is 1:1 but not onto (if possible).
   4. A function that is onto but not 1:1 (if possible).
   You might want to ponder what each of these relations might represent.

part b

Due 2020-Aug-24 (Mon).

8. Express the proposition below in English:
   ∃ x ∈ ℕ (x = -x).

   Note: Your answer should start: "There exists a natural number x…" or "There is a natural number x…".

9. Express the proposition below in English. ∀ x ∈ ℕ(∀ y ∈ ℕ(∃ z ∈ ℕ(x = y + z)))

   Note: Your answer should start: "For every natural number x…" or "For all natural numbers x…".

10. Express the set below in English:
    G = { x ∈ ℕ: ∃ y ∈ ℕ(∀ z ∈ ℕ(x < y ∧ y < z +20)) }

    Note: Your answer should start: "G is the set of natural numbers x such that…".

    You can answer this with, or without, the +20; I added that only to make the problem slightly less non-practical.
11. Let the set D={1, 4, 7, 10, 13, …}, where the dots represent numbers that follow the obvious pattern. Express this set in the form D = {x ∈ ℕ : P(x)}, where you replace P(x) with some proposition of x (i.e. a statement that is true or false of x, such as x is even∃ y (x=2·y). You answer will look like {x ∈ ℕ: … } where you fill in the … with a mathematical expression, as in the previous problem.
12. Express the result in 5 or fewer symbolscharacters/digits: 2⁶⁰ · 2⁴ = …

    Hint: For Express 10·16 in 3 symbolscharacters (instead of 5), an answer would be 160.

13. Express the result in 5 or fewer characters: How many distinct numbers can be represented with 64 bits?
14. Prove that the set 3ℕ3ℤ (the multiples of 3, i.e. …, -6, -3, 0, 3, 6, …) are countable. Explicitly give a bijection f between ℕ and this 3ℤ. You do not need to prove your function is 1:1,onto, but you should satisfy yourself of that in your head.
15. In class we discussed the fact that |A × B| = |A| · |B|. Although this seems very reasonable, we never proved it. Let's prove something simpler: Use induction to prove that if A = {x,y,z} then |A × B| = 3 · |B|. Make sure that you set up your induction as in the \(\displaystyle\sum_{i=1}^n\) example done in class, including let P(n) be the statment …., and show each step. [Hint: Use induction on the size of B.]

This homework based on Dr. Okie's homework Some problems are based on Appendix A of the text.

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu