5
$\begingroup$

$f(S \cup T) = f(S) \cup f(T)$

$f(S)$ encompasses all $x$ that is in $S$ $f(T)$ encompasses all $x$ that is in $T$

Thus the domain being the same, both the LHS and RHS map to the same $y$, since the function $f$ is the same for both.

Can you post the solution?

$\endgroup$
1
  • 1
    $\begingroup$ You have correct intuition about why the result is true. The language you use is a bit fuzzy. At this stage of the game, I suggest you divide the argument into two parts: (1) if $y\in f(S\cup T)$ then $y\in f(S) \cup f(T)$; (2) the other direction. $\endgroup$ Commented Nov 6, 2012 at 3:17

3 Answers 3

5
$\begingroup$

$$y\in f(S\cup T)\Longrightarrow \exists\,x\in S\cup T\,\,s.t.\,\,f(x)=y$$

and now:

$$x\in S\Longrightarrow\,y=f(x)\in f(S)\;\;;\;\; x\in T\Longrightarrow\,y=f(x)\in f(T)$$

so that anyway $\,y=f(x)\in f(S)\cup f(T)\,\Longrightarrow f(S\cup T)\subset f(S)\cup f(T)$

Now you try to do the other way around: $\,f(S)\cup f(T)\subset f(S\cup T)$

$\endgroup$
1
  • $\begingroup$ this one is easier to understand $\endgroup$ Commented Nov 6, 2012 at 20:15
4
$\begingroup$

Let $x\in f(S\cup T)$. Then there is a $y\in S\cup T$ such that $f(y) = x$. Assume without loss of generality that $y\in S$. Then $x = f(y)\in f(S) \subseteq f(S)\cup f(T)$. Hence you have proved on of the directions of your inclusion.

For the other one you do similarly. Hence start with $x\in f(S)\cup f(T)$. Say that $x\in f(S)$. Then there is a $y\in S \subseteq S\cup T$ ... (you can probably finish the argument).

$\endgroup$
1
  • $\begingroup$ I don't really understand honestly $\endgroup$ Commented Nov 6, 2012 at 20:13
0
$\begingroup$

Here is how I would do this, with a slightly different notation to prevent confusion: start with the most complex side $\;f[S] \cup f[T]\;$, and determine which elements $\;y\;$ are in that set by expanding the definitions and simplifying using predicate logic.

So we calculate, for every $\;y\;$: \begin{align} & y \in f[S] \cup f[T] \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cup\;$"} \\ & y \in f[S] \;\lor\; y \in f[T] \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cdot[\cdot]\;$, twice"} \\ & \langle \exists x :: x \in S \land f(x) = y \rangle \;\lor\; \langle \exists x :: x \in T \land f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify, using the fact that $\;\lor\;$ distributes over $\;\exists\;$"} \\ & \langle \exists x :: (x \in S \land f(x) = y) \;\lor\; (x \in T \land f(x) = y) \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify by extracting common conjunct"} \\ & \langle \exists x :: (x \in S \;\lor\; x \in T) \land f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;\cup\;$ using its definition"} \\ & \langle \exists x :: x \in S \cup T \land f(x) = y \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;\cdot[\cdot]\;$ using its definition"} \\ & y \in f[S \cup T] \\ \end{align}

By set extensionality, this proves the statement.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.