[Discretefall11] Practice midterm

[Andreas Kloeckner]

Hi Angela,

On Tue, 15 Nov 2011 21:33:35 -0500, Angela Tan <aht243 at nyu.edu> wrote:
> Could you maybe go over question 22 from Section 4.5 (on page 313)?
> 
> 22) Prove that for any relation R on a set A, if R is transitive, then R
> > (composed) R (is a subset of) R.
> >
> 
>  I wanted to translate everything into some nice, recognizable
> propositions, but wasn't sure how to do so. I started with something like:
> 
> Transitive means: For all a,b,c in A, (a,b) in R and (b,c) in R implies
> > (a,c) in R.
> > Subset means: (x,y) in R (composed) R implies (x,y) in R.
> >
> 
> ... and didn't know what to do next. Or whether I was even heading in the
> right direction.
> 
> Any help would be greatly appreciated!

No problem:

Let R be transitive.
To show: R o R transitive.

To show: 
for all a,b,c in A, 
  (a,b) in R o R and (b,c) in R o R 
  -> (a,c) in R o R
  
So let (a,b) in R o R  and (b,c) in R o R.

Then there exist d, e in A such that

(a,d) in R
(d,b) in R
(b,e) in R
(e,c) in R

By transitivity of R, also (a,b) in R and (b,c) in R.

Therefore, there exists an x in A such that
(a,x) in R and (x, c) in R. (that x is our b)

Therefore, (a,c) in R o R.

HTH,
Andreas

-- 
Andreas Kloeckner 
Room 1105A (Warren Weaver Hall), Courant Institute, NYU
http://www.cims.nyu.edu/~kloeckner/
+1-401-648-0599
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.tiker.net/pipermail/discretefall11/attachments/20111116/9a4f3178/attachment.pgp>