# Homework Help: Proving irreflexive and symmetric relation

1. Apr 9, 2012

### Aaron7

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 irreﬂexive 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. Apr 9, 2012

### kru_

Irreflexive means not reflexive, yes? Then a possible counter-example might exist when X and Y are not disjoint. Wouldn't it?

3. Apr 10, 2012

### Dansuer

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.

4. Apr 10, 2012

### Dansuer

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.

5. Apr 10, 2012

### Aaron7

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.