# Basic set questions

I would really appreciate it if you could explain the set notation here

$$\{n ∈ {\bf N} \mid (n > 1) ∧ (∀x,y ∈ {\bf N})[(xy = n) ⇒ (x = 1 ∨ y = 1)]\}$$

1) What does $∀x$ mean?

2) I understand that $n ∈ {\bf N} \mid (n > 1) ∧ (∀x,y ∈ {\bf N})$ means $n$ is part of set $\bf N$ such that $(n > 1) ∧ (∀x,y ∈ {\bf N})$. What do the $[\;\;]$ and $⇒$ mean?

3) Prove that if $A ⊆ B$ and $B ⊆ C$, then $A ⊆ C$

I could prove it by drawing a Venn diagram but is there a better way?

-

1) It stands for: `for all'

2) The [] are just for readability as () and $\Rightarrow$ stands for implies, formally, it's an abbreviation for $\neg p \lor q$.

3) To be honest, a ven diagram proof is not that bad! However, I would ask your professor whether you are permitted to use them solely as a proof.

-

1) $(\forall x)$ is the universal quantifier. It means "for all $x$".

2) $[ ]$ is the same as a parenthesis. Probably, the author did not want to use too many round parenthesis because it would get too confusing.

$\Rightarrow$ is implies.

3) Suppose $x \in A$. Since $A \subset B$, by definition $x \in B$. Since $B \subset C$, then $x \in C$. So $x \in A$ implies $x \in C$. This is precisely the definition of $A \subset C$.

-

$\forall$ means "for all" or "for each". $\forall x, y \in \mathbb{N} ...$ means that no matter what natural numbers $x, y$ you choose, what follows has to be true. The square brackets are just for grouping things; they behave like parentheses for most purposes. The $\implies$ means "implies". $A \implies B$ means that whenever $A$ is true, $B$ must also be true too.

Knowing all this, let's decipher the notation. All those symbols you posted define a set; let's call it $S$. Then we have $S = \{n \in \mathbb{N}\ |\ (n > 1) \wedge (\forall x, y \in \mathbb{N})[(xy = n) \implies (x = 1 \vee y = 1)] \}$.

The first thing is $n \in \mathbb{N}$. This tells us that whatever the elements of $S$ are, they will be natural numbers. Then comes the vertical bar (a forward slash or a colon are also sometimes used), which tells us that if $n$ is going to be in $S$, then $n$ has to satisfy all the following conditions. We have two conditions joined by an "and" symbol. This means that both have to be true at the same time if $n$ is to be in $S$.

$n > 1$ just means that we exclude $1$ from $S$. The other part is $(\forall x, y \in \mathbb{N})[(xy = n) \implies (x = 1 \vee y = 1)]$. As I said, the square brackets can be replaced by parentheses if you prefer: $(\forall x, y \in \mathbb{N})((xy = n) \implies (x = 1 \vee y = 1))$. The first thing here is $\forall x, y \in \mathbb{N}$. This means that no matter which pair of natural numbers $x,y$ we choose, what follows has to be true. If we manage to find just one pair $x,y$ that don't fulfill the conditions we're about to set, $n$ can't be in $S$.

The condition is: $(xy = n) \implies (x = 1 \vee y = 1)$. So if the product of the $x,y$ we picked is $n$, this means that at least one of them is $1$. This must be true no matter what $x,y$ we use. Therefore, $S$ is the set of prime numbers. Note something: if the $x,y$ we picked don't satisfy $xy = n$, then we don't care what happens next. The definition of $A \implies B$ is that whenever $A$ is true then $B$ must also be true. If $A$ is false, well, we don't care what happens to $B$.

As for your last question: we want to prove that if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$. Let's work from the definition: $A \subseteq B$ means that for every $x \in A$ that we choose, then it also happens that $x \in B$. Likewise, $B \subseteq C$ means that for all $x \in B$, $x \in C$. Let's take some $a \in A$. The fact that $A \subseteq B$ tells us that $a \in B$. But since $a \in B$, $B \subseteq C$ implies that $a \in C$. We have proved that no matter what element of $A$ we pick, it will also belong in $C$. Therefore, $A \subseteq C$.

-
Thank you! This has really clarified my questions very well. –  John Sep 19 '12 at 10:44
1. it means "for all $x$"

2. the right arrow means "imply", if $A$ imply $B$ it means that whenever $A$ is true $B$ is also true (note: when $A$ is false $B$ can be either true or false)

3. We can prove this very easily: Let $a$ be an element in $A$ then since $A$ is contained in $B$ it means (by definition) that $a$ is an element of $B$. since $B$ is contained in $C$ it means (by definition) that every element of $B$ is in $C$ - in particular $a$ that we know is in $B$ is also in $C$ and so by definition (since evry element of $A$ is an element of $C$) we have that $A$ is contained in $C$

-

1.$∀x$ means for every x 2.[] instead of paranthesis a grouping method and $⟹$ means so 3. for the prove you should mention the elemnts in the three sets for example if a $\alpha$ belongs to $C$ so it should be belonged to $A,B$ too and sor the members of the other sets too to find out the smallest set has been included by the bigger ones.

-