# Set theoretic definition of cartesian product of two sets

I am trying to study mathematics rigorously.It is mentioned in my book in the chapter of set theory that the symbol "$:$" stands for the phrase "such that". Then in the next chapter of relations, the cartesian product of two sets $A$ and $B$ is defined as follows:

If $A$ and $B$ be two sets, $A\times B =\{(a,b):\forall (a\in A , b\in B) \}$.

If this symbolic definition is translated into words, it reads:"The cartesian product of two sets $A$ and $B$ is defined as the set of all ordered pairs $(a,b)$ such that for all $a$ belongs to $A$ and $b$ belongs to to $B$.

My concern is about the last part in the symbolic definition, that is, "$:\forall (a\in A , b\in B)$". If this is translated into words it reads "such that for all $a$ belongs to $A$ and all $b$ belongs to to $B$". This sounds incomplete to me.

Is this correct both mathematically and grammatically? Would not it be better to define the cartesian product of $A$ and $B$ as $A\times B =\{(x,y):(x,y)=(a,b)\forall (a\in A , b\in B) \}$ or simply as $A\times B =\{(a,b):a\in A , b\in B) \}$. Among these three which is correct grammatically as well as rigorous mathematically?

• I would write the third solution, without any hesitation. I think like you: syntactically, it sounds incorrect. – Bernard Jul 10 '17 at 10:26
• Why do you not identify the book that that horrible definition is quoted from? – bof Jul 10 '17 at 10:42
• You are right; the def is simly wrong; your 2nd sugegstion: $A×B=\{ (a,b) \mid a ∈ A, b∈B \}$ is the right one. – Mauro ALLEGRANZA Jul 10 '17 at 11:08

The issue is of that of free variables. When you write $\{x : \varphi\}$, it is expected that $x$ is the only free variable of $\varphi$ (there might be parameters fixed in advance).

Once you put a quantifier on $a$ and $b$, they are no longer free, and the formula is now a sentence which is either "always true" or "always false". So the set is either everything or empty.

To add insult to injury, $\forall(a\in A, b\in B)$ is not a well-formed formula to begin with. The comma, while not a valid logical symbol is often taken to mean "and" in the set-builder context.

So indeed the correct way to write this would be, as others and yourself have suggested $$A\times B=\{(a,b): a\in A, b\in B\}.$$

$$A \times B = \{(a,b): a \in A, b \in B\}$$

$A \times B$ is the set of all ordered pairs $(a,b)$ where $a$ belongs to $A$ and $b$ belongs to $B$.

This looks a bit like a typo. $A\times B =\{(a,b):\forall (a\in A , b\in B) \}$ does not make sense, your suggested solution $$A\times B =\{(a,b): a\in A , b\in B \}$$ is the right solution.

Note that $A\times B =\{(x,y):(x,y)=(a,b)\forall a\in A , b\in B \}$ is not the same!

Formally speaking (since you ask for a "set theoretic definition") the cartesian product cannot be defined: it needs its own axiom in set theory.

You cannot define sets with general formulas, otherwise you run the risk of running into Russell's paradox: $$R = \{x\colon x \not \in x\}.$$

To avoid these kinds of open definitions one can only define subsets with a formula, as in: $$A = \{x \in B\colon \phi(x)\}.$$

So the proposed definition (which is correct in naive set theory) $$A \times B := \{(a,b) \colon a \in A, b \in B\}$$ is not actually a valid definition.

The solution is to say that $A \times B$ exists by assumption (precisely the axiom of pairing in ZF and most importantly, as pointed out in the comments, the axiom of power set) and satisfies the following relation (updated): $$x \in A \times B \iff \exists a \in A, \exists b\in B\colon x = (a,b).$$

(added) I write here the nice formal definition given by @daniel-schepler in the comments: assuming you define $(a,b):=\{\{a\},\{a,b\}\}$, then actually you would say $$A \times B := \{ p \in \mathcal P(\mathcal P(A \cup B))\colon \exists a\in A, \exists b\in B\colon p=(a,b)\}.$$

• The last relation does not define the product however, as it could contain arbitrary sets that are not pairs. – Carsten S Jul 10 '17 at 18:35
• Assuming you define $(a, b) := \{ \{ a \}, \{ a, b \} \}$, then actually you would say $A \times B := \{ p \in P(P(A \cup B)) : \exists a, a \in A \wedge \exists b, b \in B \wedge p = (a, b) \}$. – Daniel Schepler Jul 10 '17 at 19:06
• The axiom of pairing only asserts the existence of set pairs $\{ a, b \}$. – Daniel Schepler Jul 10 '17 at 19:11
• The axiom of pairing, at least in the Wikipedia version you linked to, doesn't have anything to do (directly) with the Cartesian product, since it's about un-ordered pairs. Given $(a, b) = \{a, \{a, b\}\}$, a set containing the Cartesian product can be implemented easily enough as $\mathbb P(A \cup \mathbb P(A \cup B))$, which needs pairing for the usual $\cup$ reasons and to guarantee that $(a, b)$ even exists, but not specifically for the cross product. – Jonathan Cast Jul 10 '17 at 19:42
• @DanielSchepler of course you are right. The point is that basic operations with sets have definitions which heavily rely on the axioms, and hence cannot be defined so easily. – Emanuele Paolini Jul 11 '17 at 5:37