Subsets

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 $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 $X=\lbrace 6k:k\in \mathbb {Z} \rbrace$ is a subset of $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 $x=6k$ for some integer $k$. Now we wish to show that $x=6k$ is an element of the set $Y$. To do this, we need to show that our $x$ satisfies the definition of being an element of $Y$; that is, $x$ must look like $2n$ for some integer $n$. This can be seen by writing $x=6k=2(3k)=2n$ and declaring $3k=n$.

Writing Proofs

How to write a proof that $X\subseteq Y$: In general, to show $X\subseteq Y$ we wish to show that if $x\in X$, then $x\in Y$. This is done in the following format:

Let $x\in X$. (logical argument), thus $x\in Y$. This shows that $X\subseteq Y$.

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:

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 $3k\in \mathbb {Z}$, we also have that $x=2n$ for an integer $n$, thus $x\in Y$. This shows that $X\subseteq Y$.