Results 1 to 4 of 4

Math Help - Proving Equivalence Relations

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    80

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Proving Equivalence Relations

    Quote Originally Posted by lovesmath View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    80

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765

    Re: Proving Equivalence Relations

    Quote Originally Posted by lovesmath View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  2. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  3. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: October 1st 2009, 03:03 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 1st 2009, 11:14 AM
  5. Equivalence Relations - HELP!!!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2008, 03:55 PM

Search Tags


/mathhelpforum @mathhelpforum