5
$\begingroup$

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?

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

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\}.$$

$\endgroup$
3
$\begingroup$

$$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$.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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)\}. $$

$\endgroup$
  • $\begingroup$ The last relation does not define the product however, as it could contain arbitrary sets that are not pairs. $\endgroup$ – Carsten S Jul 10 '17 at 18:35
  • 3
    $\begingroup$ 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) \}$. $\endgroup$ – Daniel Schepler Jul 10 '17 at 19:06
  • 1
    $\begingroup$ The axiom of pairing only asserts the existence of set pairs $\{ a, b \}$. $\endgroup$ – Daniel Schepler Jul 10 '17 at 19:11
  • $\begingroup$ 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. $\endgroup$ – Jonathan Cast Jul 10 '17 at 19:42
  • $\begingroup$ @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. $\endgroup$ – Emanuele Paolini Jul 11 '17 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.