Proving Equivalence Relations

I don't understand how to prove that a relation is an equivalence relation. Here is the problem:

Let A be the set of all statement forms in three variables p, q and r. R is the relation defined on A as follows: For all P and Q in A,

P R Q <=> P and Q have the same truth table.

I am supposed to a) prove that the relation is an equivalence relation, and b) describe the distinct equivalence classes of each relation.

Can anyone tell me how to get started?

Re: Proving Equivalence Relations

Re: Proving Equivalence Relations

So next do I say it is symmetric and transitive? Symmetric: For all P and Q in A, P and Q have the same truth table, so P R Q and Q R P. Transitive: Let S be an element in A. Then, for all P, Q and S in A, P, Q and S have the same truth table, so P R Q and Q R Z, which means that P R Z.

Is that correct? Then how do I describe the distinct equivalence classes of each relation?

Re: Proving Equivalence Relations

Quote:

Originally Posted by

**lovesmath** Symmetric: For all P and Q in A, P and Q have the same truth table, so P R Q and Q R P.

No, not all P and Q have the same truth table. For example, take P to be p and Q to be q.

What you said has the form

for all P and Q, P R Q and Q R P.

What you need to show instead, i.e., the property of symmetry of R, is

for all P and Q, *if* P R Q, *then* Q R P.

A similar remark applies to transitivity.