Thread: 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?

Originally Posted by lovesmath

Can anyone tell me how to get started?

1. Reflexive. For all , has the same truth table than so, .

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?

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.