1

I am looking for feedback if this would constitute a proof, I feel like it is more a explanation than a rigorous proof:

Please provide feedback where it is wrong/inadequate and how it should be done to become rigorous.

Prove:

$f(A) \subseteq f(B)$ whenever $A \subseteq B$

By def 1: $A \subseteq B: \Leftrightarrow((x \in A)\Rightarrow(x \in B))$

By def 2: $f(A)=\{y \in Y \mid y=f(x)$ whenever $x \in A\}$

But when $x \in A$ if follows that $x \in B$. and since $f(B)=\{y \in Y \mid y=f(x)$ whenever $x \in B\}$

if follows that when $y \in f(A)$ it implies that $y \in f(B)$.

ALEXANDER
  • 2,099
  • This is unclear (at least to me). What is "def 1" and "def 2"? What does $D(x\in B)$ mean? Moreover, what does $(x\in A) = \ldots$ mean? This is not a valid formula. – Snaw Feb 24 '22 at 01:01
  • @Snaw I have updated the typo. D must have hit D and it overwrote the imply. Can you have another look? – ALEXANDER Feb 24 '22 at 01:06
  • The brackets in your definition of $A\subseteq B$ are unnecessary: $A\subseteq B$ simply means $x\in A\implies x\in B$ – user829347 Feb 24 '22 at 01:07
  • @OliverHouse Thanks, just replicating how it is written in the textbook – ALEXANDER Feb 24 '22 at 01:08
  • Now def1 looks almost correct, but you are still missing a $\forall$. It should read $\forall x: (x\in A \implies x\in B)$. Def 2 is more problematic, specifically the word "whenever". You should use either $\forall$ or $\exists$. Here you mean to write ${y\in Y |\exists x: y = f(x)}$. – Snaw Feb 24 '22 at 01:09
  • @ALEXANDER What textbook are you using? The notation seems a bit odd. – user829347 Feb 24 '22 at 01:10
  • @OliverHouse it is actually written by my professor(its more a compendium) – ALEXANDER Feb 24 '22 at 01:10
  • I guess I am more concerned with how I have tried to prove it in the end. It does not feel right to me! In particularly the last sentence! – ALEXANDER Feb 24 '22 at 01:12
  • Until you have a good definition for $f(A)$ this will be difficult to prove rigorously. The proof is incredibly simple (a one liner), but the word "whenever" doesn't allow any sort of mathematical reasoning. When "whenever" is used mathematically it usually means something like "$x\in A \implies y=f(x)$" but this is not the right definition. You need the formulation with $\exists x : \ldots$ that I wrote in a comment above. When you write this correct definition the proof will become very easy. – Snaw Feb 24 '22 at 01:12
  • @Snaw Would you mind giving me the one liner with the correct definition as an answer? – ALEXANDER Feb 24 '22 at 01:18
  • The correct definition is $f(A)={y\in Y|\exists x : y=f(x)}$. – Snaw Feb 24 '22 at 01:22
  • @Snaw Sorry should be more specific,I got that, I more meant the proof. – ALEXANDER Feb 24 '22 at 01:24
  • 1
    Robert Shore's proof below seems fine. (Remove all the explanations and it becomes a one liner: $y\in f(A) \implies \exists x\in A : y=f(x) \implies \exists x\in B: y=f(x) \implies y\in f(B)$.) – Snaw Feb 24 '22 at 01:24

2 Answers2

2

The pieces of the proof are all there, but they're not in order. You're not introducing your variables before you use them, making it unclear what they mean.

First of all, the statement you're proving is incomplete, because it never says what $f$ is, or whether it can be applied to elements of $A$ or $B$. A better statement of what you want to prove would be

Let $f$ be a function $X \to Y$. If $A,B \subseteq X$ with $A \subseteq B$, then $f(A) \subseteq f(B)$.

Your goal is to prove that $f(A) \subseteq f(B)$. The definition of this is that for all $y \in f(A)$, we also have $y \in f(B)$. (Your definitions are missing the "for all", which is important.) The standard structure of such a proof should be:

Let $y$ be an arbitrary element of $f(A)$. Then [...], so $y \in f(B)$. Therefore $f(A) \subseteq f(B)$.

Now it is time to use the definition of $f(A)$. Since $f(A) = \{y \in Y : \exists x \in X, y = f(x)\}$, or more briefly $f(A) = \{f(x) : x \in A\}$, we can now expand on the middle of our proof:

Then, by definition of $f(A)$, we know that there is some $x \in A$ such that $y = f(x)$.

Remember our assumption: that $A \subseteq B$. The definition of this is: every element of $A$ is also an element of $B$. This assumption is useless unless we have an element of $A$ to apply it to. But now we do! That's the $x \in A$ mentioned above. So now we can say:

Since $A \subseteq B$, we also have $x \in B$.

Now we can check that $y \in f(B)$ by checking that the definition holds: that there is some element of $B$ that $f$ sends to $y$. Which element? The element is $x$, of course, because we now know that $x$ is an element of $B$.

Therefore, since $y = f(x)$ and $x \in B$, we have $y \in f(B)$.

Putting these all together:

Let $y$ be an arbitrary element of $f(A)$. Then, by definition of $f(A)$, we know that there is some $x \in A$ such that $y = f(x)$.

Since $A \subseteq B$, we also have $x \in B$. Therefore, since $y = f(x)$ and $x \in B$, we have $y \in f(B)$.

We've shown that an arbitrary element of $f(A)$ is also an element of $f(B)$; therefore $f(A) \subseteq f(B)$.

Note that before we introduce any new variables, we define what they are! This is always important.

Also, before every conclusion we make, we summarize the key details we use to make it. Some of these details can be omitted once you're more comfortable with writing proofs, but you should always include them in the early stages, because you should always be able to include them.

Misha Lavrov
  • 142,276
  • Thank you, this is exactly what I was looking for! Really great, I was also wondering about the fact that I had not defined f and which elements it operates on ... Now it is logical and easy to follow. I found the logic very simple but the writing to be just a mess. This really gives me some hints on how to proceed learning about writing proofs! – ALEXANDER Feb 24 '22 at 01:32
1

You have the right idea. You can write it a little more cleanly.

Choose $y \in f(A)$. Then by the definition of $f(A)$, there is some $x \in A$ such that $y = f(x)$. But $A \subseteq B$, so by the definition of $\subseteq$ we have $x \in A \Rightarrow x \in B$. Thus, $x \in B$ and so $y = f(x)$ for some $x \in B$. By the definition of $f(B)$, since for some $x \in B$ we have $y=f(x)$, we know that $y \in f(B)$.

Thus, if $y \in f(A)$, we can prove that also $y \in f(B)$. Again by the definition of $\subseteq$, this means $f(A) \subseteq f(B)$.

Robert Shore
  • 23,332