Another Question About Sets (Proof)

MarkusD · 2007-09-20 15:32:51

Im dealing with the following Theorem:

Suppose R is a relation on A, and deinfe a relation S on P(A) as follows:

S={(X,Y)in P(A)xP(A)| Ex in X, Ey in Y(xRy)}

If R is symmetric and transitive, then R is reflexive.

Note: P is a power set, and E=exist

Is this theorem correct? If not why?

Last edited by MarkusD (2007-09-20 15:36:07)

MarkusD · 2007-09-20 15:39:18

Also, I wrote the following proof to say it is but can someone check my work to see if I wrote a correct proof?

Let x be an arbitrary element of A. Let y be any element of A such that xRy. Since R is symmetric, it follows that yRx. But then by transitivity, since xRy and yRy, then xRX. Also, since x was random, the proposition xRx for all x in A holds. Thus R is relfexive.

Ricky · 2007-09-20 17:36:11

You've got a bit of a typo, but I'm assuming you meant yRx there.

So it's time to reflect on your proof. What did your proof use? Remember, one of the most common pitfalls is to assume the existence of something that might not exist.

MarkusD · 2007-09-21 12:20:27

Ricky wrote:

You've got a bit of a typo, but I'm assuming you meant yRx there.

No thats the way its given. Part of the problem is to see if the theorem is correct.

Next, write a proof.

So it's time to reflect on your proof. What did your proof use? Remember, one of the most common pitfalls is to assume the existence of something that might not exist.

Not sure what you mean by what my proof used. I took the part that said If R is symmetric and transitive and assumed to try and come to a conclusion. I drag at writing proofs

HallsofIvy · 2007-09-22 01:00:25

Im dealing with the following Theorem:
Suppose R is a relation on A, and deinfe a relation S on P(A) as follows:
S={(X,Y)in P(A)xP(A)| Ex in X, Ey in Y(xRy)}
If R is symmetric and transitive, then R is reflexive.

Surely you mean "then S is reflexive". Otherwise, there would be no point in defining S. (And the statement, as given, is obvously not true- not every symmetric and transitive relation is reflexive.)

Even then, it's not true. Let A= set of natural numbers and define R= {(1,2), (2,1), (1,1), (2,2)}. Then R is certainly both symmetric and transitive but not reflexive (it does not contain, for example, (3,3)). Since the only sets on which S can be applied are those that contain only 1 or 2, it is NOT true that XSX if X= {3}.

Ricky · 2007-09-22 07:02:36

The typo I was referring to is here:

But then by transitivity, since xRy and yRy

Now back to the problem with your proof.

Let y be any element of A such that xRy.

What if such a y doesn't exist? Perhaps there is a reason that it must, but you certainly haven't given it.

MarkusD · 2007-09-22 09:36:55

Ricky wrote:

The typo I was referring to is here:
But then by transitivity, since xRy and yRy
Now back to the problem with your proof.

Ahh ok, youre right, that was a typo.

Let y be any element of A such that xRy.
What if such a y doesn't exist? Perhaps there is a reason that it must, but you certainly haven't given it.

So do I have to try to prove that theres a y in A such that xRy or should I be trying an avenue when trying to prove that R is reflexive?

Ricky · 2007-09-22 11:09:45

First, make sure you have the question right. Are you trying to prove R or S is reflexive? I don't see any reason to define S if you are just trying to prove that R is reflexive. In either case, the statement is false. So you find a counter example, like Halls has done.

MarkusD · 2007-09-22 11:43:08

Ricky wrote:

First, make sure you have the question right. Are you trying to prove R or S is reflexive? I don't see any reason to define S if you are just trying to prove that R is reflexive. In either case, the statement is false. So you find a counter example, like Halls has done.

Its R in this case because the question has multiple parts that relate to S. Im just stuck on this part regarding the proof.

Ricky · 2007-09-22 13:43:42

For questions like this in the future, keep in mind that mathematicians are minimalists. We try to cut definitions down to be as small as possible but big enough so that we can prove the theorems we want to hold. That is, we won't add things into a definition we don't essentially need. For example, a ring is a set combined with two operators (just like addition or multiplication) with a few properties. An element acts as a 0:

0 + a = a for all elements a of the ring

And another property is distribution:

a(b + c) = ab + ac

One thing that is not in the definition is that a*0 = 0. This is a theorem:

First note that 0 + 0 = 0. Then multiplying by a on both sides leaves a(0 + 0) = a0. By distribution, a0 + a0 = a0. Subtracting a0 from both sides gives a0 = a0 - a0 = 0. Therefore, a0 = 0.

Now on your question, the definition of an equivalence relation is that it is a relation that is reflexive, symmetric, and transitive. You are asked to show that symmetric and transitive implies reflexive. The answer to this implication should be immediate to you, a resounding false. As one of my professors always says, "That's a psychology question, not math."

JaneFairfax · 2007-09-23 00:06:43

MarkusD wrote:

Its R in this case because the question has multiple parts that relate to S. Im just stuck on this part regarding the proof.

Perhaps you might like to post the WHOLE question rather than part of it?

Last edited by JaneFairfax (2007-09-23 07:02:24)

MarkusD · 2007-09-23 06:24:43

OK here is the full question:

Suppose R is a relation on A, and deinfe a relation S on P(A) as follows:

S={(X,Y)in P(A)xP(A)| Ex in X, Ey in Y(xRy)}

Note: P is a power set, and E=exist

If R is transitive, then R then so is S.

Part A) Is the theorem correct? Prove the theorem above or provide a counter example.

Part B) Now suppose R is still a relation on A. If R is symmetric and transitive then R is reflexive. Is this theorem correct? Verify by proof.

Im concerned with part B.

I wrote a proof but clearly its wrong (can it be fixed?). Apparently the theorem is wrong too right?

Ivy, is the example you provided not relfexive also because of the first two ordered pairs?

JaneFairfax · 2007-09-23 07:24:02

Both theorems are false. For (A), If XSY and YSZ, all we can say is that ∃x ∈ X, y[sub]1[/sub] ∈ Y such that xRy[sub]1[/sub] and ∃y[sub]2[/sub] ∈ Y, z ∈ Z such that y[sub]2[/sub]Rz, but theres no guarantee that y[sub]1[/sub] = y[sub]2[/sub].

As a counterexample, take A to be the set of natural numbers and let R = {(1,2), (3,4)}. Then R is transitive (vacuously so), but S is not, because {1}S{2,3} and {2,3}S{4} but it is not true that {1}S{4}.

For (B), the relation R defined in HallsofIvys example is symmetric and transitive but not reflexive. For the relation R to be reflexive on A, you must have xRx for all x ∈ A, not just for some x ∈ A. Since A is chosen as the set of natural numbers, in order for R to be reflexive on A, you must have nRn for all natural numbers n, not just for 1 and 2.

Last edited by JaneFairfax (2007-09-23 07:31:46)

MarkusD · 2007-09-23 09:18:48

JaneFairfax wrote:

For (B), the relation R defined in HallsofIvys example is symmetric and transitive but not reflexive. For the relation R to be reflexive on A, you must have xRx for all x ∈ A, not just for some x ∈ A. Since A is chosen as the set of natural numbers, in order for R to be reflexive on A, you must have nRn for all natural numbers n, not just for 1 and 2.

Im confused with Ivy's example:

My book says that symmetry is having xRY->yRx.
Transitive is xRy ^ yRz -> xRz
Reflexive is xRx

And so far I have been using relations like >, <, =, U, etc. to verify things. I havent yet had to define a R specifically in any of the work that Ive done.

Ivy defined R as some ordered pairs but Im not seeing how 1R2->2R1 unless R is the equality operator (which is transitive adn reflexive).

Last edited by MarkusD (2007-09-23 09:19:55)

Ricky · 2007-09-23 09:22:27

He did a piece wise defintion:

R= {(1,2), (2,1), (1,1), (2,2)}.

This literally means:

1R2
2R1
1R1
2R2

We can see that if aRb for any element in there, then it must be that bRa. The only elements in there are 1 and 2, and both 1R2 and 2R1. Likewise, you can verify transitivity. But 3 is not related to 3. Anything that doesn't appear as a tuple in R is not related.

MarkusD · 2007-09-23 09:39:30

Also, just to be sure, the problem with the proof is the bolded phrase?

Let x be an arbitrary element of A. Let y be any element of A such that xRy. Since R is symmetric, it follows that yRx. But then by transitivity, since xRy and yRy, then xRX. Also, since x was random, the proposition xRx for all x in A holds. Thus R is relfexive.

Because I was looking at it further and Im wonder if the phrase "But then by transitivity, since xRy and yRy, then xRX. " is also incorrect. Ive been looking at definitions of transitivity and they always have at least 3 elements (x,y,z) when writing the out the definition. Does transitivity work with two elements as Ive written above?

Last edited by MarkusD (2007-09-23 09:41:45)

MarkusD · 2007-09-23 09:45:38

Ricky wrote:

He did a piece wise defintion:
R= {(1,2), (2,1), (1,1), (2,2)}.
This literally means:
1R2
2R1
1R1
2R2
We can see that if aRb for any element in there, then it must be that bRa. The only elements in there are 1 and 2, and both 1R2 and 2R1. Likewise, you can verify transitivity. But 3 is not related to 3. Anything that doesn't appear as a tuple in R is not related.

Do you have another example that uses only operators or something non-piece wise. Im just asking because I havent covered piece-wise definitions and am having a hard time with the current tools that I have.

Ricky · 2007-09-23 18:08:54

Ive been looking at definitions of transitivity and they always have at least 3 elements (x,y,z) when writing the out the definition. Does transitivity work with two elements as Ive written above?

It holds for any elements x, y, and z, and does not place any restrictions on what these elements are. So it could be that x = z. Or it could be that y = z. Or it could be that x = y = z.

Do you have another example that uses only operators or something non-piece wise. Im just asking because I havent covered piece-wise definitions and am having a hard time with the current tools that I have.

You aren't going to find any "real" relations which are both symmetric and transitive and not reflexive. The reason for this is because for it to occur, some element must be left out of the relation entirely (i.e. it's not related to anything). A relation that does so would probably be pretty useless. But I could be wrong.

Really though, you should have gone over the definition of a relation, and the example given comes straight from that. It's just a set of tuples. That is by definition a relation. There should be nothing mysterious about it.

Math Is Fun Forum

#1 2007-09-20 15:32:51

Another Question About Sets (Proof)

#2 2007-09-20 15:39:18

Re: Another Question About Sets (Proof)

#3 2007-09-20 17:36:11

Re: Another Question About Sets (Proof)

#4 2007-09-21 12:20:27

Re: Another Question About Sets (Proof)

#5 2007-09-22 01:00:25

Re: Another Question About Sets (Proof)

#6 2007-09-22 07:02:36

Re: Another Question About Sets (Proof)

#7 2007-09-22 09:36:55

Re: Another Question About Sets (Proof)

#8 2007-09-22 11:09:45

Re: Another Question About Sets (Proof)

#9 2007-09-22 11:43:08

Re: Another Question About Sets (Proof)

#10 2007-09-22 13:43:42

Re: Another Question About Sets (Proof)

#11 2007-09-23 00:06:43

Re: Another Question About Sets (Proof)

#12 2007-09-23 06:24:43

Re: Another Question About Sets (Proof)

#13 2007-09-23 07:24:02

Re: Another Question About Sets (Proof)

#14 2007-09-23 09:18:48

Re: Another Question About Sets (Proof)

#15 2007-09-23 09:22:27

Re: Another Question About Sets (Proof)

#16 2007-09-23 09:39:30

Re: Another Question About Sets (Proof)

#17 2007-09-23 09:45:38

Re: Another Question About Sets (Proof)

#18 2007-09-23 18:08:54

Re: Another Question About Sets (Proof)

Board footer