Difference between revisions of "Subsets"

Revision as of 11:36, 29 June 2015

Definition

Let $X$ and $Y$ be sets. We say that $X$ is a subset of $Y$ if every element of $X$ is also an element of $Y$ , and we write $X\subseteq Y$ or $Y\supseteq X$ . Symbolically, $X\subseteq Y$ means Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\in X} $\Rightarrow$ $x\in Y$ .

Two sets $X$ and $Y$ are said to be equal, $X=Y$ , if both $X\subseteq Y$ and $Y\subseteq X$ . Note that some authors use the symbol $\subset$ in place of the symbol $\subseteq$ .

Example

Show that the set Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle X=\lbrace 6k:k\in \mathbb {Z} \rbrace } is a subset of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Y=\lbrace 2n:n\in \mathbb {Z} \rbrace }

Solution

We want to show that for any $x\in X$ we also have $x\in Y$ . To do this we will let $x$ be an arbitrary element of the set $X$ . This means that $x$ can be written as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=6k} for some integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . Now we wish to show that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=6k} is an element of the set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} . To do this, we need to show that our Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} satisfies the definition of being an element of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} ; that is, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} must look like Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n} for some integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . This can be seen by writing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=6k=2(3k)=2n} and declaring Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3k=n} .

Writing Proofs

How to write a proof that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X\subseteq Y} : In general, to show Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X\subseteq Y} we wish to show that if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in X} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in Y} . This is done in the following format:

Proof Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in X} . (logical argument), thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in Y} . This shows that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X\subseteq Y} .

Remark

The logical argument portion often begins by giving the definition of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in X} and ends with the definition of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in Y} .

The following is a write-up of the solution of Example 1 as a formal proof:

Proof Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in X} . That is, there exists some Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\in\mathbb{Z}} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=6k} . We have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=6k=2(3k)} . Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3k\in\mathbb{Z}} , we also have that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=2n} for an integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in Y} . This shows that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X\subseteq Y} .

@@ Line 16: / Line 16: @@
 '''How to write a proof that <math>X\subseteq Y</math>''': In general, to show <math>X\subseteq Y</math> we wish to show that if <math>x\in X</math>, then <math>x\in Y</math>. This is done in the following format:
-Let <math>x\in X</math>. ''(logical argument)'', thus <math>x\in Y</math>. This shows that <math>X\subseteq Y</math>.
+'''Proof''' Let <math>x\in X</math>. ''(logical argument)'', thus <math>x\in Y</math>. This shows that <math>X\subseteq Y</math>.
+=== Remark ===
 The logical argument portion often begins by giving the definition of <math>x\in X</math> and ends with the definition of <math>x\in Y</math>.
@@ Line 22: / Line 24: @@
 The following is a write-up of the solution of Example 1 as a formal proof:
-Let <math>x\in X</math>. That is, there exists some <math>k\in\mathbb{Z}</math> such that <math>x=6k</math>. We have <math>x=6k=2(3k)</math>. Since <math>3k\in\mathbb{Z}</math>, we also have that <math>x=2n</math> for an integer <math>n</math>, thus <math>x\in Y</math>. This shows that <math>X\subseteq Y</math>.
+'''Proof''' Let <math>x\in X</math>. That is, there exists some <math>k\in\mathbb{Z}</math> such that <math>x=6k</math>. We have <math>x=6k=2(3k)</math>. Since <math>3k\in\mathbb{Z}</math>, we also have that <math>x=2n</math> for an integer <math>n</math>, thus <math>x\in Y</math>. This shows that <math>X\subseteq Y</math>.