ITEC 420 2021fall ibarland

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

hw01

• Reading: Appendix A of the text.
• 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).
• Exercises refer to the textbook pdf.

Due 2021-Sep-11 (Sat) 23:59.

1. Recall that a cross-product of three sets is a set-of-3tuples.
   1. List the elements of A, as a set:
      A = {1, 2} x {a, b} x {d, e}.
   2. List the elements of B, as a set:
      B = {1, 2} x {a, b} x { }.
2. 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.
3. Express the proposition below in English:
   ∃ y ∈ ℕ (y < 20).

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

4. Consider the set C = {n ∈ ℕ : ∃ m ∈ ℕ (m≤10 ∧ 2n=m+3)}.
   1. Describe C in English.
      Your answer will start C is the set of natural numbers n such that …, but your answer should not mention m. By doing algebra, we know we can re-phrase this as "the set of all natural numbers less than 13/2", which we can solve for the explicit set given next.
   2. List the elements of C. (your answer will look something like C = {19, 43, 55}).
5. Express the proposition below in English. ∀ x ∈ ℕ (∀ y ∈ ℕ (∃ z ∈ ℕ (x = y + z)))

   Note: Your answer should start: "For all natural number x…" or better "Every natural number x…".

   Is the statement true?
6. 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∃ k (x=2·k). You answer will look like {x ∈ ℕ: … } where you fill in the … with a mathematical expression.
7. Express the result in 5 or fewer characters/digits: 2⁶⁰ · 2⁴ =         

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

8. Express the result in 5 or fewer characters: How many distinct numbers can be represented with 64 bits?
9. Exercise 2.3.2, p.14+15=29(pdf).
10. Let L₁ = {apple, pear} and L₂ = {pie, cake, ε} (over the alphabet Σ = [a-z]). List the elements of L₁L₂ in lexicographic order¹. This is just Exercise 2.3.2, p.14+15=29(pdf) made a bit less-busy-ish.
11. Exercise 2.3.6, p.14+15=29(pdf). Do not simply restate the math; instead describe, in English, the strings in each language so that an ITEC friend could understand. None of your answers should include the word prefix.

    For convenience: Your answers may take as understood that the underlying alphabet is Σ = {a,b} — you don't need to repeat that.

12. Exercise 2.3.7, p.14+15=29(pdf), only parts b,c.

    Reminder: We say a set A is closed under an operation f iff ∀ a ∈ A, f(a) ∈ A. For example, the integers are closed under squaring (any integer squared is still an integer), but not closed under square-rooting (the square root of 2 is not an integer).

13. Exercise 2.3.8, p.14+15=29(pdf), only parts c–e. You can just assert whether the statement is true or false; you do not need to provide a proof for true but you should give a counterexample if false.

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