# help with proof techniques

Printable View

• Jan 27th 2010, 03:05 AM
lemon721
help with proof techniques
have no idea about this question
• Jan 27th 2010, 04:16 AM
emakarov
I don't know what proof techniques you discussed in class, but one can prove (a), for example. The thing is that every formula that one wants to prove has some form: A and B; A or B; A implies B; for every x, A(x); S is a subset of S', etc. There is a way to prove formulas of each of those forms. E.g., to prove "for every x, A(x)" you fix an arbitrary x and prove that A(x) is true for this x.

The claim you need to prove in (a) has the form "for every $f$, ${O}(f)$ is a subset of $\Gamma(f)$. If you now what it means to prove a formula of each form, you can gradually rewrite the claim and then see what you can do about it. Start with: "Fix some arbitrary $f\in\mathcal{F}$. Need to prove: ${O}(f)\subseteq\Gamma(f)$."