[Discretefall11] Practice midterm
kloeckner at cims.nyu.edu
Tue Nov 15 21:27:56 PST 2011
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!
Let R be transitive.
To show: R o R transitive.
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.
Room 1105A (Warren Weaver Hall), Courant Institute, NYU
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: not available
More information about the Discretefall11