Proving Equivalence Relations

• July 22nd 2011, 07:08 PM
lovesmath
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?
• July 22nd 2011, 09:33 PM
FernandoRevilla
Re: Proving Equivalence Relations
Quote:

Originally Posted by lovesmath
Can anyone tell me how to get started?

1. Reflexive. For all $P\in A$ , $P$ has the same truth table than $P$ so, $PRP$ .
• July 24th 2011, 07:32 AM
lovesmath
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?
• July 24th 2011, 08:21 AM
emakarov
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.