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!

Homework Help: Proving irreflexive and symmetric relation

  1. Apr 9, 2012 #1
    1. The problem statement, all variables and given/known data
    I am on the final part of a question and I have to prove that the following is a irreflexive symmetric relation over A or if it is not then give a counter example.

    R is given as an irreflexive symmetric relation over A.

    Relation: {(X, Y) | X ⊆ A ∧ Y ⊆ A ∧ ∀x ∈ X.∀y ∈ Y.(x, y) ∈ R}

    2. Relevant equations
    See above.

    3. The attempt at a solution
    I have worked out the if X x Y ⊆ R then (X,Y) is put into the relation.
    I worked out a simple example to see if it was worth trying to prove and it seems to be correct.
    I am having trouble getting my head around trying to make a start to prove this.

    Many thanks.
  2. jcsd
  3. Apr 9, 2012 #2
    Irreflexive means not reflexive, yes? Then a possible counter-example might exist when X and Y are not disjoint. Wouldn't it?
  4. Apr 10, 2012 #3
    I think your counterexample is incorrect.
    R needs to be irreflexive, so if two sets have an element in common, R is not irreflexive and so the sets don't belong to the relation.
  5. Apr 10, 2012 #4
    Let's call your relation J.

    To prove the symmetric part. Assume X J Y, this means
    X ⊆ A ∧ Y ⊆ A ∧ ∀x ∈ X.∀y ∈ Y.(x, y) ∈ R and (X,Y) belongs to J
    use the fact that R is symmetric to arrive at
    Y ⊆ A ∧ X ⊆ A ∧ ∀y ∈ Y.∀x ∈ X.(y, x) ∈ R and (Y,X) belongs to J
    which means Y J X

    To prove the irreflexive part i would go for a contradiction. Since the statement you have to prove is a negative one. Which is: "for any set X, (X,X) does not belong to J". So assume the contrary and reach a contradiction.
  6. Apr 10, 2012 #5
    Thank you for the help. I think I was too worried about the complexity of the set rather than using the definition to simply prove it. I should be able to move on to some more complex ones now.

    Thanks again.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook