## CS 5315 Homework #10

**Date Assigned:** Thursday, February 17, 2005
**Due Date:** Tuesday, February 22, 2005

Let A be an oracle. By an A-algorithm, we mean an algorithm that uses
A as an oracle. Correspondingly, we can define A-decidable and
A-r.e. sets.

1. Prove that if the two sets S and T are A-decidable, their union,
intersection, and a complement to S are also A-decidable.

2. Prove that if S and T are A-r.e., then their union and intersection
is also A-r.e.