1
$\begingroup$

I'm given that x, y, and A, B are sets, and must prove that the Cartesian product

A x B := {(x, y) | x $\in$ A and y $\in$ B} is a set.

I'm certain that I need to use AC somehow, but I'm having trouble understanding what exactly it would even mean for me to apply it, or how I should go about it.

Here is what believe to understand about AC: if I have a set, say Z = {a, b, c} then applying AC means that I have a function:

f:Z $\mapsto$ $\cup$Z, i.e., f:{a, b, c} $\mapsto$ {{a}, {b}, {c}}

And we have that $\forall$z $\in$ Z (f(z) $\in$ z)

Unfortunately I'm having trouble seeing the consequences of this and how I can extend it to prove that the Cartesian product between A and B is indeed a set. But it could be as well that I've totally misinterpreted the axiom and so obviously can't draw any meaningful conclusions. I would really appreciate if someone could clear the air for me and hopefully set me in the right direction.

$\endgroup$
1
  • $\begingroup$ See here for duplicates as well as elaborations as to why choice is not required. $\endgroup$ Sep 5 '19 at 23:02
1
$\begingroup$

Use the definition of a pair along with Comprehension.

No need for Choice.

$\endgroup$
5
  • $\begingroup$ Would the approach then be to define a function which pulls an element from A, another which takes one from B, use the axiom of pairing to create an ordered pair, then take the union of all of them? $\endgroup$
    – Luke
    Sep 5 '19 at 23:03
  • $\begingroup$ Let’s ignore functions first, as their existence is proved with the proof of existence of the Cartesian product. Can you first describe what an ordered pair is? $\endgroup$
    – Metric
    Sep 5 '19 at 23:11
  • $\begingroup$ The previous question in my assignment asked me to prove that an ordered pair is a set, which my prof defined as (x, y) : {{x}, {x, y}}. In all honest I'm not sure whether he wants us to continue under that same definition or if it's supposed to mean something else. I'm not sure how or why that definition makes sense either. $\endgroup$
    – Luke
    Sep 5 '19 at 23:14
  • $\begingroup$ That definition is a possible encoding of an ordered pair, and it's working fine because we can prove $(x,y)=(x', y') \iff (x=x') \land (y=y')$, and that's all we want in the end. $\endgroup$
    – Berci
    Sep 5 '19 at 23:18
  • $\begingroup$ Yes, that's the typical definition, and I think it's safe to assume that he does want you to continue with that same definition. There's a reason why that definition is suitable. $\endgroup$
    – Metric
    Sep 5 '19 at 23:19

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