# Math Help - Discrete Math, Please Help!!

1. ## Discrete Math, Please Help!!

Prove the sets A and B defined below are equal.

A = {(a, b) is a member of Z+ × Z+|a is a factor of b}

B is defined recursively by

Initial Step: (1, 1) is a member of B
Recursive Step: If (a, b) is a member of B and c is a member of Z+ then
(ac, bc) is a member of B and (a, bc) is a member of B

2. Originally Posted by jas05s
Prove the sets A and B defined below are equal.
A = {(a, b) is a member of Z+ × Z+|a is a factor of b}
B is defined recursively by
Initial Step: (1, 1) is a member of B
Recursive Step: If (a, b) is a member of B and c is a member of Z+ then
(ac, bc) is a member of B and (a, bc) is a member of B
We know that $(x,y) \in A \Rightarrow \quad \left( {\exists j \in Z^ + } \right)\left[ {xj = y} \right]$.
So by definition we get $(1,1) \in B \Rightarrow \quad (x,x) \in B,\,\& \,(x,jx) \in B$.
This means that $(x,y) \in B\mbox{ so } A \subseteq B$.

It is simple now to prove $B \subseteq A$.