Most texts in axiomatic set theory will present arguments *in* the theory in informal language. This is because actual formal proofs would be very large and tend to make it difficult to see the forest for trees -- the point is after all to convey *understanding* to the reader.

Such a text generally assumes that the reader is familiar enough with formal logic to figure out for himself how the informal arguments correspond to formal proofs. That's not just, as mrp makes it sound like, an article of faith -- the author *actually knows* how to formalize the arguments he gives and simply depends on the reader to be able to do the same thing.

In practice what one should do when writing and reading such an informal argument is not to *actually* reduce it to a formal, symbolic proof. What one is supposed to know is how to translate an informal argument for such-and-such *in the theory* into a similarly informal argument *at the metalevel* that a formal proof of such-and-such *exists*.

Cohen's book will not tell you how to do that -- it simply assumes as a prerequisite that you as a reader are familiar enough with *some* proof system for first-order logic that you're comfortable with doing these translations in your head.

One benefit of this is that one can read the book without learning one particular formalization of FOL -- which, no matter which one Cohen chose, would be different from the one some readers already knew. It is more effective to explicitly tell the reader, "you can use whatever standard formalization of logic you want", and there are plenty of introductory texts that *do* teach enough of formal logic to allow Cohen to avoid writing one himself.

Cohen does need to present the particular logical *language* he's working with, because several of the things one needs to do when doing metamathematics about ZFC requires one to quantify over "all formulas", and probably to use induction over their structure -- so one has to select a particular set of connectives to use so one knows which cases those induction proofs need.

But the structure of the *proof system* is much less critical for Cohen's purpose, as long as the entailment relation that it ends up with is the standard one.

So you're not supposed to go via the completeness theorem. However, just for completeness: Many commonly encountered proofs of the completeness theorem are phrased using the axiom of choice, but using AC is not strictly necessary as long as the *language* of the theory has countably many symbols. Only if the vocabulary of the theory can be an *arbitrary set* do we need to use AC (or assume that the vocabulary is well-orderable).

You should start supposing the contrary of the conclusion, that is,
$$\neg(\neg p \vee (\neg q\vee r)))$$
Now, apply twice the De Morgan's law for $\neg(X\vee Y)$:
$$p\wedge q \wedge\neg r$$
Eliminate $\wedge$ to obtain $\neg r$. Now, use the premise and eliminate $\vee$:
$$\neg(\neg p\vee q)$$
Apply again De Morgan's law:
$$p\wedge \neg q$$
Now, eleminate $\wedge$ in two previous formulae to get $q$ and $\neg q$. Insert $\wedge$ and you have the contradiction.

## Best Answer

There are likely prettier ways of going about it, but this was what I saw:

Starting with distribution of disjunction over conjunction ($\vee$ over $\wedge$) on the first expression yields $[(P_2 \wedge \neg P_0) \vee P_0] \wedge [(P_2 \wedge \neg P_0) \vee P_1],$ and distributing the other way yields $(P_2 \vee P_0) \wedge (P_2 \vee P_1) \wedge (\neg P_0 \vee P_1).$

Rewriting this as $(P_0 \to P_1) \wedge (\neg P_0 \to P_2) \wedge (\neg P_2 \to P_1),$ it should be clear that the second expression is a logical consequence of the first by simplification. (aka $\wedge$-elimination) Now we just need to show that the implication goes the other way, which is fairly simple.

$1. \textbf{Assume}\ (P_0 \to P_1) \wedge (\neg P_0 \to P_2)$

$\ \ \ 2. P_0 \to P_1$ ($1,$ simplification)

$\ \ \ 3. \neg P_0 \to P_2$ ($1,$ simplification)

$\ \ \ 4. \neg P_2 \to P_0$ ($3,$ contrapositive)

$\ \ \ 5. \neg P_2 \to P_1$ ($2,4,$ hypothetical syllogism)

$\ \ \ 6. (P_0 \to P_1) \wedge (\neg P_0 \to P_2) \wedge (\neg P_2 \to P_1)$ ($1, 5, \wedge$-introduction)

$7. [(P_0 \to P_1) \wedge (\neg P_0 \to P_2)] \to [(P_0 \to P_1) \wedge (\neg P_0 \to P_2) \wedge (\neg P_2 \to P_1)]$ ($1,6,\to$-introduction)

So, because the implications in both directions are tautologies, the material equivalence is a tautology and the statements are logically equivalent.