# Thread: Reflexive, Symmetric, Transitive Relation Proof

1. ## Reflexive, Symmetric, Transitive Relation Proof

Let X be a set and let R be the relation "" defined on subsets of X.

Prove whether reflexive, symmetric, transitive.

Is this the right approach?
Proof: (Reflexive)
Suppose S is a subset of X. Suppose y is in S.

(Now I need to show that (y, y) is in R. Can I say that y y, so (y, y) is in R?
I don't understand how to show that elements are in this relation since the relation is in terms of subsets.)

2. ## Re: Reflexive, Symmetric, Transitive Relation Proof

You don't need to show that $(y,y) \in R$, you need to show that for every $S \subseteq X$, that $(S,S) \in R$.

What this amounts to, is showing that for every subset $S$ of $X$, that $S \subseteq S$.

Now to show THIS, we can take any element $y \in S$, and we must show that this implies $y \in S$. Since this is (OBVIOUSLY!) always true, $S \subseteq S$, that is $(S,S) \in R$, so $R$ is reflexive.

3. ## Re: Reflexive, Symmetric, Transitive Relation Proof

MORE QUESTIONS:

Let R be a relation on a set A. Then, R is reflexive iff for all y in A, (y, y) is in R.

In this case, R is still a relation on a set. This set is some set, S, which is a subset of X.
So, wouldn't the proof still have to satisfy the definition of reflexive as defined above.
Something like:

Proof (Reflexive)
Suppose S is a subset of X. Suppose y is in S. Then clearly y is in S, and S ⊆ S. So, R = S X S.
Thus, (y, y) is in R and R is reflexive.

4. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Also, is it important that the problem states "...R be the relation "⊆" defined ON subsets of X?"
As apposed to, "...R be the relation "⊆" defined BETWEEN subsets of X."
If the problem stated BETWEEN, then that would change things right?
In this case, we could have two subsets of X that were disjoint, which would prevent R from being reflexive, right?

5. ## Re: Reflexive, Symmetric, Transitive Relation Proof

I think you are misunderstanding which set $R$ is a relation ON. It is NOT a relation on $X$, but on the set $\mathcal{P}(X)$, the POWER SET of $X$ (also written as $2^{X}$).

If two subsets of $X$, say $A,B$ are disjoint, then sure, $(A,B) \not\in R$, but that says nothing about $(A,A)$ or $(B,B)$.

It is a curious fact about sets: elements of one set (for example, a power set, or "set of subsets" like we have here) can be sets themselves. There is no "inherent" type distinction between sets and elements in set theory, although there IS a distinction between $x$ (whatever object $x$ might be) and $\{x\}$, the set whose only element is $x$, for example, $x \in \{x\}$ but $x \not\in x$.

6. ## Re: Reflexive, Symmetric, Transitive Relation Proof

So, is the way that I suggested proving the reflexive property incorrect? (on post #3)

7. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Never mind. I get it now. It would have been better if the book said:
Let R be the relation "⊆" defined on THE SET OF ALL SUBSETS OF X.
Then I would have better understood that each element in this set is a set.
Which makes sense given the "⊆" property of the relation.
So, R is a set of ordered pairs of sets. Thus, it makes sense to prove the reflexive property as:

Proof:
Suppose S is a subset of X. Suppose y is in S. Then clearly y is in S, and S ⊆ S.
Thus, (S, S) is in R and R is reflexive.

8. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Well it has some parts that are correct, but it is NOT true that $R = S \times S$.

Let me give you a slightly more "targeted example", by actually specifying the set $X$.

So suppose $X = \{a,b\}$ ($X$ has two elements, $a$ and $b$).

The set of all subsets of $X$, is THIS one :$\mathcal{P}(X) = \{\emptyset,\{a\},\{b\},\{a,b\}\}$. We want to show for all sets $S \in \mathcal{P}$ that $S \sim_R S$, that is: $S \subseteq S$.

Fortunately, in this example, $\mathcal{P}(X)$ is pretty small, it only has 4 elements. Let's rename them like so:

$N = \emptyset$
$A = \{a\}$
$B = \{b\}$
$X = \{a,b\}$

To show $R$ is reflexive, we need to show that $(N,N),(A,A),(B,B)$ and $(X,X)$ are all in $R$. The set that $R$ is a relation on is $\mathcal{P}(X)$, NOT $X$.

So let's start with $N$. Since $N$ HAS no elements (it is empty), any element of $N$ (that is to say, none) are automatically in ANY set, including $N$ itself. Hence $N \subseteq N$.

Well, that wasn't very exciting. Let's look at $A$. Now $A$ has only one element, $a$, and (what a coincidence!), $a$ just happens to be in $A$ as well, so $A \subseteq A$.

The proof that $B \subseteq B$ is exactly the same.

$X$ is a little bit more interesting: we have our choice of two elements in $X,\ a$ or $b$. Either way, we can conclude that $a \in \{a,b\}$, and similarly, $b \in \{a,b\}$, so every element of $X$ is also in $X$, and thus $X \subseteq X$.

So in all four cases, we see that $(S,S)$ is in $R$, whether $S = N,A,B$ or $X$.

A different way to say a relation $R$ on a set $S$ is reflexive is to say: $\Delta(S) \subset R$, where $\Delta(S)$ is the DIAGONAL of $S \times S$, consisting of all pairs $(s,s)$ for any element $s$ of $S$. The containment of sets in this case ($R$ is reflexive) goes like this:

$\Delta(S) \subseteq R \subseteq S \times S$.

If a relation $R$ on a set $S$ is actually $S\times S$, that means ANY two elements are related, which isn't a very interesting relation at all.

The relation in this question is not on some subset $S$ of $X$, it is on the set of ALL subsets of $X$ which is "bigger" than just one subset.

9. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Yes, that spells it out quite nicely, thank you.
The big problem I had was in interpreting "on subsets of X" to mean "on the set of all subsets of X."
I am now working through the symmetric and transitive proofs...

10. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Proof (Symmetric)
Counterexample: Suppose X = {a, b}. [Then the set of all subsets is P(X)={∅,{a},{b},{a,b}}.]
Let A = {a} and B = {a, b}. Then A and B are subsets of X. If x is in A, then x = a.
Since a is in B, A ⊆ B. However, b is in B but b is not in A. So, B is not a subset of A.
Thus, R is not symmetric.

11. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Proof (Transitive)
Suppose A, B, and C are all subsets of X and ARB and BRC.
Suppose y is in A. Since ARB, y is in B. Since BRC, y is in C.
Thus, ARC and R is transitive.

12. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Are the two proofs above correct?

13. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Yes, in fact this type of relation is typical of what is called a "partial ordering", which is:

1. reflexive
2. transitive
3. anti-symmetric: by this, we mean that if aRb and bRa, then we have a = b.

Other examples of partial orderings:

"less than or equal to" on the set of real numbers,
"divides" on the set of positive integers,

partial orderings are very important things in the world of mathematics.

14. ## Re: Reflexive, Symmetric, Transitive Relation Proof

I am not familiar with partial ordering, but I will take note of that.
The examples that you gave are helpful in understanding the concept.
This is my first "proof/analysis" type course so this is all new to me.
I heard these concepts are really important in abstract algebra but I'm not sure where else they're used.
Although, I imagine they are found in a variety of contexts.
I'm so used to numerical/graphical expressions that it's taking some time to think more in terms of these principals/concepts.
Fortunately, these are pretty simple. I am taking real analysis next semester, so I need to make sure really understand this stuff.
Well, thanks again, I'm sure I'll have plenty more post floating around soon...

15. ## Re: Reflexive, Symmetric, Transitive Relation Proof

Well sets, and "sets of sets" are very important.

In calculus, one often deals with the real numbers. But what turns out to be important is certain kinds of subsets of real numbers: namely, open intervals. We can use an open interval (a,b) that contains a point x as a way of saying we're "somewhere around x", and this idea of proximity, becomes the basis for ideas like limits and continuity. It turns out that we can order open intervals by inclusion, which captures the notion of "zeroing in on x".

Another way in which relations, especially relations that are reflexive, symmetric and transitive (equivalence relations), are important, is that conceptually, they provide a looser notion of "the same" than "exactly equal". Often, especially when dealing with infinite things, there's just too many to get a good grip on how they behave by looking at every single one. But if we can lump them together into "equivalence classes", we might wind up with few enough "things" to analyze thoroughly.

Here is an equivalence relation you probably have encountered before, even if you didn't realize it. Suppose $f,g$ are two differentiable functions. Define $f \sim g$ if $f' = g'$. In this case, it should be clear that if $f \sim g$, then $f - g$ is a constant function. You implicitly appeal to this equivalence every time you integrate a continuous function, it's what the "+ C" at the end of an indefinite integral equation means.