1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence Relations proof

  1. Sep 19, 2009 #1
    Statement:
    Prove or Disprove: A relation ~ on a nonempty set A which is symmetric and transitive must also be reflexive.


    Ideas:
    If our relation ~ is transitive, then we know: a~b, and b~a [tex]\Rightarrow[/tex] a~a.
    Therefore our relation ~ is reflexive, since b~c and c~b [tex]\Rightarrow[/tex] b~b, and c~a and a~c [tex]\Rightarrow[/tex] c~c.


    Proof:
    Can the above (idea) constitute a proof in itself?

    Thanks,

    Jeffrey
     
  2. jcsd
  3. Sep 19, 2009 #2
    Actually I thought about it a little, and came up with a proof. But can someone critique it and let me know if it's actually alright.


    Proof
    We know ~ is symmetric.
    Therefore, [tex]\exists a,b,c \in A[/tex] such that
    if a~b, then b~a,
    and if b~c, then c~b,
    and if c~a, then a~c.​
    But we also know our relation ~ is transitive.
    Therefore,
    if a~b, and b~a, then a~a, (#1)
    and if b~c, and c~b, then b~b, (#2)
    and if c~a, and a~c, then c~c. (#3)​
    By (#1), (#2), and (#3) we know our given relation is reflexive.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Equivalence Relations proof
Loading...