Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I) {${((a,b),(c,d)) ∈ (\Bbb Q × \Bbb Q)² : (a<c) ∨ ( a = c ∧ b ≤ d)}$}
II) {${(f,g) ∈ \Bbb Q→\Bbb Q × \Bbb Q→\Bbb Q: ∀x ∈ \Bbb Q : f(x) ≤ g(x)}$}
III) {(a,b) ∈ $\Bbb Z$ × $\Bbb Z$ : n devides a - b}, n ∈ $\Bbb N$

I have to prove:
a) reflexivity ($a\sim a$)
b) symmetry (if a~b then b~a)
c) antisymmetry (if a ≤ b and b ≤ a then a = b)
d) transitivity (if a~b and b~c then c~a)

If a,b and d are true it's an equivalence relation.
If a,c and d are true it's a partially ordered set.

My problem is on how to get started. I tried a few things, but looking at those three tasks (I found a lot more, but I feel like these could be the best examples) makes me feel like there's always something I'm missing.

I'm preparing for finals, and this is what always bothered me. I'd be really thankful for any kind of help, even if it's by providing the solution (which would be nice (but really not necessary, anything would help me here) as I'm going on a long trip by train in a few hours and therefore I can't do too much work on paper.)

share|improve this question
    
Type \$\{\$ to get $\{$. For $\}$ it is similar. Type \$\Bbb N\$ to get $\Bbb N$. Similarly for $\Bbb {Q, Z}$. –  Git Gud Apr 28 '13 at 10:02
    
Awesome, thanks! I was wondering how to do it, but forgot about it. –  flixMar Apr 28 '13 at 10:03

1 Answer 1

There is really no escape from verifying the definitions.

You just have to take every relation and put it against all four definitions. One useful tip to remember is that if $R$ is a relation on $A$ which is both a partial order and an equivalence relation then $R=\{\langle a,a,\rangle\mid a\in A\}$.

Another method to somewhat circumvent this is to use the following theorem (which you may have seen, or may not):

Theorem: If $A$ is a non-empty set and $E$ is a relation on $A$, then $E$ is an equivalence relation if and only if there exists $B$ and $f$ such that $f\colon A\to B$ and $E=\{\langle x,y\rangle\mid x,y\in A, f(x)=f(y)\}$.

This theorem is often overlooked, but it's a useful one. Even if you are not using it formally, using it to guide your intuition is great. For example the third relation (assuming that $n$ is fixed) can be seen as the equivalence relation of the map $f(k)=\text{rem}(k,n)$, the remainder of $k$ when diving it by $n$.

Of course if you don't know how to find this function to begin with, it won't help you too much, but with practice you will see them more and more easily.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.