4. Consider the strict divisibility relation 1 on the set of all positive integers N+ = N{0}. Recall that the strict divisibility relation on N+ is defined as follows: ab iff there exists some k > 1 such that b=a.k. Define the following two subsets of N+: S = {qeNt Iq=p" for some prime p and some neN} T = {qENT 19p" for some prime p and some n N such that n 5 p.} Answer the following questions and justify your answers by a proof, rigorous argument or a counterexample. (a) Prove that (S,1") and (T,1") are trees. Following the convention in the Definition 3.10 in the lecture text, we will briefly write just S and T. (b) For each node p" of S, T determine whether it has an immediate predecessor and successor in the respective tree, and determine sets bs(p") and br(p"). (c) For each node p" of T, S which has an immediate successor, describe the set of all immediate successors in the respective tree. (d) For each of the trees ST and each node p" determine the height of p" in the respective tree. (e) For each of the trees ST and each n e N determine the n-th level of the respective tree. (f) For each of the trees S, T determine the set of all infinite branches. (g) Determine ht(S) and ht(T). Also draw a picture that visualizes trees S.T. 4. Consider the strict divisibility relation 1 on the set of all positive integers N+ = N{0}. Recall that the strict divisibility relation on N+ is defined as follows: ab iff there exists some k > 1 such that b=a.k. Define the following two subsets of N+: S = {qeNt Iq=p" for some prime p and some neN} T = {qENT 19p" for some prime p and some n N such that n 5 p.} Answer the following questions and justify your answers by a proof, rigorous argument or a counterexample. (a) Prove that (S,1") and (T,1") are trees. Following the convention in the Definition 3.10 in the lecture text, we will briefly write just S and T. (b) For each node p" of S, T determine whether it has an immediate predecessor and successor in the respective tree, and determine sets bs(p") and br(p"). (c) For each node p" of T, S which has an immediate successor, describe the set of all immediate successors in the respective tree. (d) For each of the trees ST and each node p" determine the height of p" in the respective tree. (e) For each of the trees ST and each n e N determine the n-th level of the respective tree. (f) For each of the trees S, T determine the set of all infinite branches. (g) Determine ht(S) and ht(T). Also draw a picture that visualizes trees S.T
