Existence of Cartesian product

[evinda]

Hello! (Wave)

Sentence:

If $A,B$ are sets, there is the (unique) set, of which the elements are exactly the following: $\langle a,b\rangle: a \in A \wedge b \in B$.

Proof:

Remark: $\langle a,b\rangle:=\{ \{a\},\{a,b\}\}$

If $a \in A$, then $\{ a \} \subset A \rightarrow \{ a \} \in \mathcal{P}A \rightarrow \{a\} \in \mathcal{P}(A \cup B)$

If $b \in B$, then $\{a,b\} \subset A \cup B \rightarrow \{a,b\} \in \mathcal{P}(A \cup B)$

Therefore, $\{ \{a\},\{a,b\}\} \in \mathcal{P}\mathcal{P}(A \cup B)$

Therefore, from the theorem:

"Let $\phi$ type. If there is a set $Y$, such that $\forall x(\phi(x) \rightarrow x \in Y)$, there there is the set $\{x:\phi(x)\}$."

we conclude that there is the set $\{\langle a,b \rangle : a \in A \wedge b \in B \}$

Could you explain me the above proof?

 

[Evgeny.Makarov]

To prove that $\{x:\phi(x)\}$ is a set, we have to specify something that has already been proven to be a set and from where all such $x$'s come from. That is, if $Y$ is known to be a set, then we are allowed to conclude that $\{x\in Y:\phi(x)\}$ is a set. If no such $Y$ is known, then we are not allowed to conclude that $\{x:\phi(x)\}$ is a set.

In the case of Cartesian product, $\phi(x)$ is $\exists a\in A\,\exists b\in B\;x=\langle a,b\rangle$. So the proof constructs a set $Y$ where all ordered pairs $\langle a,b\rangle$ come from. It turns out that one option is $Y=\mathcal{P}\mathcal{P}(A\cup B)$.

If you have further questions, please point out the exact statement that is not clear.

 

[evinda]

To prove that $\{x:\phi(x)\}$ is a set, we have to specify something that has already been proven to be a set and from where all such $x$'s come from. That is, if $Y$ is known to be a set, then we are allowed to conclude that $\{x\in Y:\phi(x)\}$ is a set. If no such $Y$ is known, then we are not allowed to conclude that $\{x:\phi(x)\}$ is a set.

In the case of Cartesian product, $\phi(x)$ is $\exists a\in A\,\exists b\in B\;x=\langle a,b\rangle$. So the proof constructs a set $Y$ where all ordered pairs $\langle a,b\rangle$ come from. It turns out that one option is $Y=\mathcal{P}\mathcal{P}(A\cup B)$.

If you have further questions, please point out the exact statement that is not clear.

I understand... (Smile)
Could you explain me how we conclude, that if $b \in B$, then $\{a,b\} \subset A \cup B \rightarrow \{a,b\} \in \mathcal{P}(A \cup B)$ ?

Also, why $\{ \{a\},\{a,b\}\} \in \mathcal{P}\mathcal{P}(A \cup B)$ ?

 

[Evgeny.Makarov]

Could you explain me how we conclude, that if $b \in B$, then $\{a,b\} \subset A \cup B \rightarrow \{a,b\} \in \mathcal{P}(A \cup B)$ ?

First of all, it is assumed that $a\in A$. Second, these are two conclusions: since $a\in A$ and $b\in B$, we have $\{a,b\} \subset A \cup B$, and this in turn implies that $\{a,b\} \in \mathcal{P}(A \cup B)$. Now, I assume you understand that if John owns a cat and Ellen owns a dog, then the pair {John, Ellen} is a subset of all cat- and dog-owners.

Also, why $\{ \{a\},\{a,b\}\} \in \mathcal{P}\mathcal{P}(A \cup B)$ ?

Because the proof has already established that $\{a\}\in\mathcal{P}(A\cup B)$ and $\{a,b\}\in\mathcal{P}(A\cup B)$, and the unordered pair of those objects is therefore a subset of $\mathcal{P}(A\cup B)$.

 

[evinda]

First of all, it is assumed that $a\in A$. Second, these are two conclusions: since $a\in A$ and $b\in B$, we have $\{a,b\} \subset A \cup B$, and this in turn implies that $\{a,b\} \in \mathcal{P}(A \cup B)$. Now, I assume you understand that if John owns a cat and Ellen owns a dog, then the pair {John, Ellen} is a subset of all cat- and dog-owners.

I understand.. (Nod)

Because the proof has already established that $\{a\}\in\mathcal{P}(A\cup B)$ and $\{a,b\}\in\mathcal{P}(A\cup B)$, and the unordered pair of those objects is therefore a subset of $\mathcal{P}(A\cup B)$.

So, if $c \in \mathcal{P} A$ and $d \in \mathcal{P} A$, is it then $\{c,d\} \in \mathcal{P}\mathcal{P} A$ ?

 

[Evgeny.Makarov]

So, if $c \in \mathcal{P} A$ and $d \in \mathcal{P} A$, is it then $\{c,d\} \in \mathcal{P}\mathcal{P} A$ ?

I'll tell you a more amazing thing: if $u\in X$ and $v\in X$, then $\{u,v\}\in\mathcal{P}(X)$. (Smile) Which is not really amazing: everybody knows that if Smokey and Tigger are cats, then the (unordered) pair {Smokey, Tigger} is a subset of all cats.

 

[evinda]

I'll tell you a more amazing thing: if $u\in X$ and $v\in X$, then $\{u,v\}\in\mathcal{P}(X)$. (Smile) Which is not really amazing: everybody knows that if Smokey and Tigger are cats, then the (unordered) pair {Smokey, Tigger} is a subset of all cats.

A ok... (Nod)

And then, do we use the theorem, because:

$$\phi: \exists a \in A, b \in B \ : \ x=<a,b>$$

$$\forall x(\phi(x) \rightarrow x \in \mathcal{P} \mathcal{P}(A \cup B)$$
? (Thinking)

 

[Evgeny.Makarov]

Yes.

May I also ask you what exactly was unclear to you and how the information I provided helped? I don't think you did not know the facts about cats...

 

[evinda]

Yes.

May I also ask you what exactly was unclear to you and how the information I provided helped? I don't think you did not know the facts about cats...

I didn't notice, for example, that if $u \in X$ and $v \in X$, then $\{u,v\} \in \mathcal{P} X$. I got it, thanks to you examples! (Smile)

After that, there are some examples of Cartesian products. One of the given examples is this:

$$\mathbb{Z} \times \{1,2\}=\{<x,1>: x \in \mathbb{Z}\} \cup \{ <x,2>:x \in \mathbb{Z}\}$$

Could you explain me why we take the union and it isn't like that: $\{<x,1>,<x,2>: x \in \mathbb{Z}\}$ ? (Thinking)

 

[Evgeny.Makarov]

Could you explain me why we take the union and it isn't like that: $\{<x,1>,<x,2>: x \in \mathbb{Z}\}$ ?

$\{\langle x,1\rangle ,\langle x,2\rangle : x \in \mathbb{Z}\}$ is not a well-formed set-builder notation. This notation has the form $\{x:\phi(x)\}$. There are also various extensions and abbreviations, for example $\{x\in A:\phi(x)\}=\{x:x\in A\land \phi(x)\}$ and $\{f(x):\phi(x)\}=\{y:\exists x\,y=f(x)\land \phi(x)\}$. But $\{f(x),g(x):\phi(x)\}$ is not a standard notation.

 

[evinda]

$\{\langle x,1\rangle ,\langle x,2\rangle : x \in \mathbb{Z}\}$ is not a well-formed set-builder notation. This notation has the form $\{x:\phi(x)\}$. There are also various extensions and abbreviations, for example $\{x\in A:\phi(x)\}=\{x:x\in A\land \phi(x)\}$ and $\{f(x):\phi(x)\}=\{y:\exists x\,y=f(x)\land \phi(x)\}$. But $\{f(x),g(x):\phi(x)\}$ is not a standard notation.

I understand.. (Nod) Thanks a lot! (Smile)