1

I need help figuring out where to start a proof that says I should use a proof by contradiction.

$f\colon A\to B$ and $g\colon B\to A$ be functions and each is 1-1. Let $D$ be the range of $f$ (i.e., $D=f(A)$).

Let $x$ and $y$ be natural numbers with $x>y$. Prove: $g(fg)^x (B-D)\cap g(fg)^y (B-D)=\emptyset$.

Alex
  • 23

2 Answers2

0

Maybe start with the simplest case: $x=1$ and $y=0$. (I'm going to consider $0$ to be a "natural number"; not everybody does so.) Then the statement to prove is $$ gfg(B-D)\cap g(B-D) = \emptyset $$ To prove that some set is empty by contradiction, I'd start by assuming the opposite, that is, suppose the set is nonempty. That gives me something concrete to work with: an element in the set. Then I look for things that I can say about that element.

So, to start:

Suppose, on the contrary, that $gfg(B-D)\cap g(B-D)\ne\emptyset$. Let $x\in gfg(B-D)\cap g(B-D)$.

Then... what? What can you say about $x$? What have we already said about $x$?

  • Then x ∈ B? I'm not exactly sure where your leading me right now.. – Alex Dec 11 '13 at 06:52
  • Actually $x\in A$. But yes, that kind of thing. What else can we say? For example, what does it mean when we say that $x\in\text{BLAH}\cap\text{BLEE}$? –  Dec 11 '13 at 06:54
  • That x exists in both BLAH and BLEE – Alex Dec 11 '13 at 06:55
  • And if x exists in BLAH and BLEE then the intersection is not empty. – Alex Dec 11 '13 at 06:56
  • Good. What are BLAH and BLEE here, and what does it mean for $x$ to be in each of them? –  Dec 11 '13 at 06:57
  • That BLAH and BLEE are not empty. – Alex Dec 11 '13 at 06:58
  • No, I mean you told me that $x$ is in BLEE. In the text, BLEE is $g(B-D)$. What does it mean to say $x\in g(B-D)$? (I don't mean "what does it mean" like "what consequences does it have", I mean, "what is the literal meaning of these symbols".) –  Dec 11 '13 at 06:59
  • That x exists in the function g(B-D) – Alex Dec 11 '13 at 07:04
  • And, what does $g(B-D)$ mean? –  Dec 11 '13 at 07:05
  • Hm. Ok, I think we'd better cut it short here; it seems you don't know the notations involved in the question, and addressing that would require quite a bit more time than I have. Maybe you can find someone to work with you in person on this? –  Dec 11 '13 at 07:08
  • Thanks for you help anyways. I think i got it wish i could talk to you in person. I feel it can be hard getting what i'm trying to say through symbols sometimes – Alex Dec 11 '13 at 07:09
0

If $g(fg)^x(B-D)∩g(fg)^y(B-D)≠∅$ let a belong to the intersection of the two sets. Then there are u, v in B-D such that $g(fg)^x(u)=g(fg)^y(v)=a$. Then $(fg)^x(u)=(fg)^y(v)$ because we can multiply each side of the first equality by $g^{-1}$, which is 1-1, and get the second equality. But then $(fg)^{-y}(fg)^x(u)=(fg)^{-y}(fg)^y(v)$ and thus $(fg)^{x-y}(u)=v$. But fg(u) is not in B-D and so also every $(fg)^n(u)$ is not in D-B for every natural number n (because fg is 1-1 and thus it preserves the disjointedness of sets), but v is in B-D so we get a contradiction.

Incidentally, (fg)^x is a (commonly used) misnomer because fg need not be applied again to get to the xth image of a member form B-D.

Arik
  • 86