MATH 2090  Problem Set #5 (On Ch.14 and earlier)

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #5. Posted March 17, 2002

Due in the Course Box by 2pm. April 5, 2002

Section N

1. Let A be a finite alphabet. As usual, A^{∗} denotes the set of all strings formed using symbols in A.

Let us define string reversal, x^{R}, that is, x^{R} is what you get if you read x backwards (right to left). Throughout, ε is the empty string and ∗ denotes concatenation.

Formal definition:

ε^{R} = ε
(x ∗ a)^{R} = a ∗ x^{R}, for all a ∈ A and x ∈ A^{∗}

We say that x is a substring of y iff (for some u, v) y = u∗x∗v. Clearly, the substring relation has the finite descending chain condition, so that it admits (CVI) induction.

Using the formal definition of x^{R} above and induction on the substring relation prove that for all strings x and y,

(x ∗ y)^{R} = y^{R} ∗ x^{R}

2. Prove by induction on the \underline{subformula relation} that if A is a syntactically well formed formula of propositional calculus, then every proper nonempty prefix of A has more left than right parentheses.

Clarification: If x is any string, then z is a prefix of x iff there is a string y such that x = z ∗ y, where “∗” denotes concatenation. z is a proper prefix iff z ≠ x (equivalently, y ≠ ε, i.e., the “tail” y is not the empty string).

MATH 2090  Problem Set #5 (On Ch.14 and earlier)

3. Let ρ : A → A be given, and A = {1, 2, 3, …, n}. Prove that

ρ^{+} = ⋃_{i=1}^{n} ρ^{i}

Hint. We know that ρ^{+} = ⋃_{i≥1} ρ^{i}. Thus you must prove only ⋃_{i≥1} ρ^{i} ⊆ ⋃_{i=1}^{n} ρ^{i}, the opposite inclusion being trivial. To this end prove

xρ^{k}y ⇒ (∃i ≤ n)xρ^{i}y  (1)

Obviously, the only case that needs work in (1) is when k > n. Well, by a cut-and-paste argument show that if k > n and xρ^{k}y, then there is also a k′ < k such that xρ^{k′}y.

Two things: First, this helps, for you can’t have an infinite sequence of “k” values

n < … < k′′′ < k′′ < k′ < k

Second, recall that xρ^{k}y means (right?)

xρx_{1}ρx_{2}ρx_{3} ⋯ x_{k−1}ρy, for some x_{i} ∈ A, i = 1, …, k − 1

Can all the x_{i} be different? (It is good to split into two cases, x = y and x ≠ y.)

4. Let ρ and A be as above, but moreover, now we assume that ρ is reflexive on A. Prove that

ρ^{+} = ρ^{n−1}

5. Let f : A → B be a partial function. Let X and Y be subsets of A, while U and V are subsets of B. Prove

(a) f[X ∪ Y] = f[X] ∪ f[Y]

(b) f[X ∩ Y] ⊆ f[X] ∩ f[Y]

(c) Can the “⊆” above be “sharpened” into an “=”? WHY? (Do

\underline{not} explain in words if your answer is “no”. Give a counterexample instead. If you said “yes”, prove it.

(d) f^{−1}[U ∩ V] = f^{−1}[U] ∩ f^{−1}[V]

“f^{−1}” above denotes inverse relation. No 1-1ness assumption is being made!