# What are all underlying assumptions in the definition of Cartesian Product in Naive Set Theory?

In the book "Naive Set Theory" of Halmos there is a sentence that

... the unique set $A \times B$ that consists exactly of the ordered pairs $(a, b)$ with $a$ in $A$ and $b$ in $B$. This set is called the Cartesian product of $A$ and $B$; it is characterized by the fact that $A \times B = \{ x : x = (a, b) \text{ for some } a \in A \text{ and for some } b \in B\}$

I can't understand several things here and I think I miss some important points.

1. Why "for some" instead of "for all"? Because it implies there may be such $(a, b)$ where actually $a \in A \text{ and } b \in B$ but $(a, b) \notin A \times B$.
2. It is said that "it is characterized by the fact". Which fact? Can you explain? Is applying the axiom of specification called "the fact" if I understand the axiom correctly? In my understanding defining (or specifying) a set using a sentence whose elements are elements of another existing set is what the axiom is about.

Also I noticed such a comment, where the author says that the definition in the question is not actually from naive set theory and rewrote it using "for some" claiming it would be from naive set theory. But I can't understand what is the catch here.

The way you should read $\{x : P(x)\}$ is "The set of all $x$ that satisfy the condition $P(x)$." To define $A \times B$ this way, we ask ourselves "What is the condition that a particular element $x$ must satisfy to be in $A \times B$?"

The answer to that question is "It must be of the form $(a,b)$ for some $a \in A$ and for some $b\in B$." So that's what we write in the set definition.

You want to have a "for all" there of the related statement "For all $a \in A$ and for all $b \in B$, $(a,b)$ is an element of $A \times B$." But that's not the kind of statement we put in a set definition. If you were to write $$\{ x: x = (a,b) \text{ for all a \in A and b\in B}\}$$ then it would mean something different. It would mean that to test if an element $x$ is in this set, we would construct ordered pairs $(a,b)$ for all $a\in A$ and $b \in B$, and test if $x$ is equal to all of them simultaneously. This is impossible unless we're in the exceptional case $|A|=|B|=1$, where there is only one such pair.

(Or unless $|A|=0$ or $|B|=0$, in which case this definition runs into weird "naive set theory doesn't always work well" issues.)

For the second question, the phrase "the fact that" can and should be omitted from all sentences in which it occurs. So you can read the quote as

The set $A \times B$ is characterized by $$A \times B = \{ x: x = (a,b) \text{ for some a \in A and for some b\in B}\}$$

The phrase "is characterized by" means "is the only thing satisfying the description" or "are the only things satisfying the description" depending on context.

• Thank you very much for the great answer! But how was I supposed to know that "is characterized by the fact" means "is the only thing satisfying the description". Is it English language related or it has mathematical/philosophical roots? Apr 14, 2018 at 20:54
• It's somewhere in between those two. The expression "is characterized by" is often used in mathematical writing, where it always means this thing. It has loosely the same meaning to non-mathematicians, but is less precise in a non-mathematical context, where it might just mean "satisfies the description" or "is typical of the description" or other things. (Also, it's fairly formal, so you're unlikely to encounter it in a non-mathematical context.) Apr 14, 2018 at 20:58
• @MishaLavrov It is also the case that if we used "for all" the condition would hold vacuously if $|A|=0$ or $|B|=0$ which would make the set expression be the universal "set" and thus ill-formed in Halmos' somewhat vague "naive" approach. (It is not clear what containing set Halmos intends for this to be explicitly a case of the Axiom of Specification.) Apr 15, 2018 at 2:24
• @DerekElkins Good point. (Also, thank you for fixing my typo.) Apr 15, 2018 at 2:55

(1) The set (for $A,B\ne\emptyset$) $$\{ x : x = (a, b) \text{ for all } a\in A \text{ and for all } b \in B\}$$ will be empty with one exception (what exception?) because $$(a_1,b_1) = (a_2,b_2)\iff a_1 = a_2\land b_1 = b_2$$ (2) The phrase "it is characterized by the fact" means "is defined by".

• with the exception when both $A$ and $B$ have exactly one element? Apr 14, 2018 at 20:49
• Misha Lavrov has already mentioned the exceptional case. Thank you very much! You made me think thoroughly though :) Apr 14, 2018 at 20:52
• @TurkhanBadalov, yes. Apr 14, 2018 at 20:53