Subsets

Definition

An example of a set $Y$ and its subset $X$

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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=6k} for some integer $k$. Now we wish to show that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2n} for some integer Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n} . This can be seen by writing Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=6k=2(3k)=2n} and declaring Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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:

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

Remark

The logical argument portion often begins by giving the definition of $x\in X$ and ends with the definition of $x\in Y$.

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

Proof Let $x\in X$. That is, there exists some $k\in \mathbb {Z}$ such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=6k} . We have Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=6k=2(3k)} . Since Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 3k\in \mathbb {Z} } , we also have that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=2n} for an integer Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n} , thus $x\in Y$. This shows that $X\subseteq Y$.