Is the Relation R Complete Given Asymmetry in P?

[Kolmin]

Homework Statement

Assume a relation [itex]P[/itex] that is asymmetric on a set [itex]X[/itex] that is not empty.
Define the binary relation [itex]R[/itex] on [itex]X[/itex] by [itex]xRy[/itex] iff [itex] y P x [/itex] is false.

Prove that [itex]R[/itex] is complete

Homework Equations

Asymmetry: [itex]xRy \rightarrow \neg (yRx) [/itex]

Now, I think I got a proof, but I am not sure how well I can express it. So my problem is both about contents and style.

The Attempt at a Solution

PROOF:
Let [itex]x[/itex], [itex]y[/itex] be arbitrary. Assume that [itex]xRy[/itex] is false.
Thus, by definition of [itex]R[/itex], it follows that [itex]yPx[/itex].
Since [itex]P[/itex] is an asymmetric relation, if follows that [itex]xPy[/itex] is false.
Therefore, since [itex]x[/itex] and [itex]y[/itex] are arbitrary, it follows from the definition of [itex]R[/itex] that the relation is complete.

Does it look perspicuous or there is something not clear? Maybe the last sentence?
Thanks a lot in advance.

 

[pasmith]

PROOF:
Let [itex]x[/itex], [itex]y[/itex] be arbitrary.

This is a good start.

Assume that [itex]xRy[/itex] is false.

This is not a promising approach if you want to prove something about R, because at the moment you don't know anything about R, except its definition in terms of P, which you know to be antisymmetric.

Thus, by definition of [itex]R[/itex], it follows that [itex]yPx[/itex].
Since [itex]P[/itex] is an asymmetric relation, if follows that [itex]xPy[/itex] is false.

Correct. You've shown that [itex]\neg(xRy)[/itex] implies [itex]\neg(xPy)[/itex]. But how does that help prove that R is complete?

Therefore, since [itex]x[/itex] and [itex]y[/itex] are arbitrary,

But they aren't, because you assumed that [itex]\neg(xRy)[/itex].

it follows from the definition of [itex]R[/itex] that the relation is complete.

I don't think that this, if true, is an obvious conclusion.

You need to start from the assumption that P is asymmetric and show that R is complete, ie. that for all x and y, either xRy or yRx (or both).

Clearly for all x,y, either [itex]xPy[/itex] or [itex]\neg(xPy)[/itex].

Assume xPy. What does that tell you about xRy?
Now assume instead [itex]\neg(xPy)[/itex]. What does that tell you about yRx?

 

[Kolmin]

[itex]\![/itex]First of all, thanks a lot for your feedback.

I kinda guess that I cannot really express what I find out, so I am going to write the "proof" with logical symbols (I "learned" how to prove something froma book that strongly emphasize this kind of approach).
Maybe this should clear I came out with what I wrote, in order to find out if the problem is with my thoughts or with my way of expressing thoughts.

So, that's what we have (in that book, those are called givens):

1. [itex]\forall x,y \in X (xPy \rightarrow \neg yPx) [/itex] [Asymmetry] [1.]

2. [itex]\forall x,y \in X (xRy \leftrightarrow \neg yPx) [/itex] [Definition of R] [2.]

What we have to prove (let's call it our goal):

[itex] \forall x,y \in X (xRy \vee yRx) [/itex] [G1]

So let's take [itex]x[/itex] and [itex]y[/itex] arbitrary. Let's call them [itex]a[/itex] and [itex]b[/itex].

Our goal is now [itex]aRb \vee bRa[/itex], which is the same as [itex]\neg aRb \rightarrow bRa[/itex]. So, assuming [itex]\neg aRb[/itex] (it goes in the list of our givens as [3]), we have to prove [itex]bRa[/itex], from now on the new goal [G2].

So, from now on, we play with Universal instantiation and Modus Tollens:

i) we take [itex]a[/itex] and [itex]b[/itex] and we put them in the second given (the definition of R). The result is

[itex]aRb \leftrightarrow \neg bPa [/itex], [4.1]

which can be split in the two other givens

[itex]aRb \rightarrow \neg bPa[/itex] [4.1a]
[itex]\neg bPa \rightarrow aRb[/itex] [4.1b]

Considering our assumption [itex]\neg aRb [/itex], we get from [4.1b] with Modus Tollens [itex]bPa[/itex], that becomes our given [5.].

ii) we take our given [1.], which is the asymmetric property, and again we use universal instantiation, obtaining

[itex] aPb \rightarrow \neg bPa [/itex],

that along with our given [5.], using Modus Tollens again, gives us the new given

[itex] \neg aPb [/itex] [6.]

The last step is to use Universal Instantiation in our given [2.] the other way around. So we get

[itex]bRa \leftrightarrow \neg aPb [/itex]

Usign Modus Pollens in this case give us our desired result, which is [itex] bRa [/itex].

 

[Kolmin]

So I put the way in which I work out proofs in order to show how I approach those kind of problems. If it looks mechanical... well, it is, but not all are natural-born-Gauss, and I am definitely not in that group.

So, I checked-rechecked it and I guess it should work, even if I guess there are some more straightforward way.

But I can I put in words...THAT? (obviously, assuming it is ok).

 

[Michael Redei]

Your proof looks okay, but for one formal mistake: you actually have only two "givens", which you number [1.] and [2.]. All your other numbered statements are "conclusions" or "results" of these givens and your deductions.

You're showing that R is complete by assuming ¬aRb and deducing bRa. I'd probably do so less formally:

Assume ¬aRb. Then (by definition of R) we have bPa, from which follows (with the antisymmetry of P) that ¬aPb, so that bRa (again, by definition of R).

This shows that either aRb or bRa, and since a,b can be chosen arbitrarily, this proves that R is complete.​

 

[pasmith]

So I put the way in which I work out proofs in order to show how I approach those kind of problems. If it looks mechanical... well, it is, but not all are natural-born-Gauss, and I am definitely not in that group.

So, I checked-rechecked it and I guess it should work, even if I guess there are some more straightforward way.

But I can I put in words...THAT? (obviously, assuming it is ok).

I think you're making it rather harder than it should be.

We want to prove something for all x and y. The first sentence of the proof is therefore:

"Let [itex]x \in X[/itex] and [itex]y \in X[/itex] be arbitrary."

Now we need to generate some information about x and y. We haven't mentioned P yet, so let's start with an obviously true statement:

"Then either [itex]xPy[/itex] or [itex]\neg(xPy)[/itex]."

Now we can deal with each case.

For the first: We want to say something about R, but our definition of R is in terms of [itex]\neg P[/itex], so we first have to produce something involving that. Fortunately P is asymmetric, so [itex]xPy[/itex] gives us [itex]\neg(yPx)[/itex]. So:

"If [itex]xPy[/itex] then by asymmetry of P we have [itex]\neg(yPx)[/itex], which by definition of R implies [itex]xRy[/itex]."

For the second case we can use the definition of R directly:

"Alternatively, if [itex]\neg(xPy)[/itex] then by definition of R we have [itex]yRx[/itex]."

Drawing these together:

"Therefore either [itex]xRy[/itex] or [itex]yRx[/itex]. Since x and y are arbitrary, R is complete."

And the complete proof:

Let [itex]x \in X[/itex] and [itex]y \in X[/itex] be arbitrary. Then either [itex]xPy[/itex] or [itex]\neg(xPy)[/itex]. If [itex]xPy[/itex] then by asymmetry of P we have [itex]\neg(yPx)[/itex], which by definition of R implies [itex]xRy[/itex]. Alternatively, if [itex]\neg(xPy)[/itex] then by definition of R we have [itex]yRx[/itex]. Therefore either [itex]xRy[/itex] or [itex]yRx[/itex]. Since x and y are arbitrary, R is complete.

You may find Tim Gowers's series of posts on basic logic helpful.

 

[Kolmin]

Your proof looks okay, but for one formal mistake: you actually have only two "givens", which you number [1.] and [2.]. All your other numbered statements are "conclusions" or "results" of these givens and your deductions.

I know what you mean. The fact is that in the book I studied consider all of them sort of new givens (they are actually put in a specific list of givens, opposed to that of goals, and they are both evolving. This book is related to a java app and they both give you this dynamic idea of list of givens that becomes bigger after each step.

You're showing that R is complete by assuming ¬aRb and deducing bRa. I'd probably do so less formally:

Assume ¬aRb. Then (by definition of R) we have bPa, from which follows (with the antisymmetry of P) that ¬aPb, so that bRa (again, by definition of R).

This shows that either aRb or bRa, and since a,b can be chosen arbitrarily, this proves that R is complete.​

So here there is the trick when I write down to proof. Even if I used a direct proof rephrasing the disjunction, when I write down is much easier to express it in the original way, right?

 

[Kolmin]

Let [itex]x \in X[/itex] and [itex]y \in X[/itex] be arbitrary. Then either [itex]xPy[/itex] or [itex]\neg(xPy)[/itex]. If [itex]xPy[/itex] then by asymmetry of P we have [itex]\neg(yPx)[/itex], which by definition of R implies [itex]xRy[/itex]. Alternatively, if [itex]\neg(xPy)[/itex] then by definition of R we have [itex]yRx[/itex]. Therefore either [itex]xRy[/itex] or [itex]yRx[/itex]. Since x and y are arbitrary, R is complete.

So, your post kinda confirms me that the best way to write those kind of disjunction proofs is to stick to that kind of formulation, even if you get (as I did) the result with a direct proof.

It looks to me that both yours and Michael Redei's proofs are clear cut and share the same approach to express the result.

You may find Tim Gowers's series of posts on basic logic helpful.

Well, the book I keep on mentioning is "How to prove it: a structured approach", by Velleman. I liked it a lot, because there was a lot of logic AND a java app that gives you the possibility to literally think like a machine. So it's really a step by step approach towards mathematical proofs. I really liked it.

Anyway, I don't want to sound like a commercial: I liked it and I it is the book that influenced me the most, but I think I read almost all books on proof writing that can be found on the market.

 

[Michael Redei]

My opinion on writing down proofs (and you don't have to agree with that) is that you should explain only what's necessary, otherwise you'll bore your reader, but include all important parts (or you'll leave him asking himself "Why was that so?").

Your very rigorous proof does looks rather mechanical, and you spell out some steps that are probably obvious to your readers, like when you use modus tollens. If I have no "audience" specified (someone either "higher" or "lower" than me, like my teacher, or my student), I imagine what it would be like explaining a proof to someone just like myself. And on the telephone, so I'll need to avoid long lists of steps that he will forget before I'm at the end of them.

If you look at my version of this proof, you'll see that I begin with "Assume ¬aRb." Then comes a longish chain of thoughts, and since at the end my listener may have forgotten what I began with and where I wanted to go, I connect the "¬aRb" part with my last conclusion, "bRa" by saying "This shows that either aRb or bRa".

Getting a style of your own in writing proofs is a bit like developing a feeling for poetry. You should read a lot of it, especially bad stuff, to find out what styles you prefer and what you consider beast to express your thoughts.