By George Milton


2012-11-06 03:12:00 8 Comments

$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?

3 comments

@Marnix Klooster 2013-12-03 19:52:20

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.

@DonAntonio 2012-11-06 03:18:34

$$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 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)$

@George Milton 2012-11-06 20:15:10

this one is easier to understand

@Thomas 2012-11-06 03:16:40

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).

@George Milton 2012-11-06 20:13:01

I don't really understand honestly

Related Questions

Sponsored Content

3 Answered Questions

[SOLVED] Prove that $(A-B)\cup(B-C) = (A\cup(B-C))-(B\cap C)$

3 Answered Questions

[SOLVED] Prove $f(S \cap T) \subseteq f(S) \cap f(T)$

3 Answered Questions

[SOLVED] $A-(B-C) = (A-B) \cup (A \cap B \cap C)$

2 Answered Questions

[SOLVED] Prove that $(A \cup B)−(A \cap B) = (A− B) \cup (B − A)$

2 Answered Questions

[SOLVED] Prove that $ \left( A-B\right) \cup B = A \cup B$

Sponsored Content