1. ## 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?

2. ## Re: Proving Equivalence Relations

Originally Posted by lovesmath
Can anyone tell me how to get started?
1. Reflexive. For all $\displaystyle P\in A$ , $\displaystyle P$ has the same truth table than $\displaystyle P$ so, $\displaystyle PRP$ .

3. ## 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?

4. ## Re: Proving Equivalence Relations

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.