Quiz 2

Define the integers ℤ inductively in the following way:

• If n ∈ ℕ, then non-neg(n) ∈ ℤ.

• If n ∈ ℕ, then neg-suc(n) ∈ ℤ.

The idea is that non-neg(n) stands for n, and that neg-suc(n) stands for -(1 + n).

1. (2p) Which of the following proof methods, if any, are correct? (The variable P stands for an arbitrary integer predicate.)

   1. (∀ n ∈ ℕ. P(non-neg(n))) ∧ (∀ n ∈ ℕ. P(neg-suc(n))) ⇒ ∀ i ∈ ℤ. P(i).

   2. (∀ n ∈ ℕ. P(non-neg(n)) ⇒ P(non-neg(n + 1))) ∧
      (∀ n ∈ ℕ. P(neg-suc(n)) ⇒ P(neg-suc(n + 1))) ⇒
      ∀ i ∈ ℤ. P(i).

   3. (∀ n ∈ ℕ. P(non-neg(n)) ⇒ P(non-neg(n + 1))) ∧
      (∀ n ∈ ℕ. n ≥ 1 ∧ P(neg-suc(n)) ⇒ P(neg-suc(n - 1))) ⇒
      ∀ i ∈ ℤ. P(i).

Let us say that we want to prove that ℤ is in bijective correspondence with Bool × ℕ. Define the function f ∈ ℤ → Bool × ℕ in the following way:

• f(non-neg(n)) = (true, n)
  f(neg-suc(n)) = (false, n + 1)

2. (1p) Which of the following functions, if any, are inverses of f?

   1. g(true, n) = non-neg(n)
      g(false, n) = neg-suc(n)

   2. h(true, n) = non-neg(n)
      h(false, 0) = neg-suc(0)
      h(false, n + 1) = neg-suc(n)

   3. i(true, n) = non-neg(n + 1)
      i(false, 0) = non-neg(0)
      i(false, n + 1) = neg-suc(n)

Now on to alphabets, strings and languages:

3. (1p) Which of the following statements, if any, are correct? (Σ is the alphabet {0, 1}, |w| is the length of the string w.)

   1. ε ∈ Σ^*.

   2. ε ∈ Σ⁺.

   3. 11 ∈ Σ¹¹.

   4. 11 ∈ Σ^|11|.

4. (1p) Which of the following statements, if any, are correct? (Σ is the alphabet {0, 1}.)

   1. Σ⁺ ⊆ Σ^*.

   2. {ε} ⊆ ∅.

   3. {ww|w ∈ Σ^*} ⊆ Σ^*.

   4. {ww|w ∈ Σ^*} ⊆ Σ⁺.