How Does Halmos Generalize the Cartesian Product in Set Theory?

[dmuthuk]

Source: Halmos, Naive Set Theory

I ran into a bit of confusion in the way Halmos generalizes the "Cartesian Product" for a family of sets (p.36). I was wondering if someone can shed some light on this. Here is my problem:

Previously, Halmos defines the cartesian product of two sets X and Y as the set of all ordered pairs (x,y) where x\in X and y\in Y. On p.36, in order to generalize the concept, he introduces a new way of looking at cartesian products.

I will stick to our special case of two sets for comparison. First, he considers an arbitrary unordered pair of sets \{a,b\}, and a function z:\{a,b\}\to X\cup Y such that z(a)\in X and z(b)\in Y. He denotes the set of all such functions from \{a,b\} to X\cup Y as Z. Then, he defines a one-to-one function f:Z\to X\times Y by f(z)=(z(a),z(b)) and claims that the sets Z and X\times Y are essentially the same and only differ in notation. However, I don't know why this is the case.

If this is true, then each z\in Z is an ordered pair of the form (x,y)\in X\times Y. Now, since z\in Z itself is a function, we can write z=\{(a,z(a)),(b,z(b))\}=\{\{\{a\},\{a,z(a)\}\},\{\{b\},\{b,z(b)\}\}\} which doesn't look anything like an ordered pair. So, I am not sure what he means exactly.

 

[AKG]

f is 1-1 and onto, so it's a bijection. There's a 1-1 correspondence between Z and XxY, and this means that the two sets, when considered as sets, don't differ in any significant way, i.e. the only significant difference is notation. It takes some getting used to, to sometimes treat two objects the same if there's a bijection between them.

 

[dmuthuk]

f is 1-1 and onto, so it's a bijection. There's a 1-1 correspondence between Z and XxY, and this means that the two sets, when considered as sets, don't differ in any significant way, i.e. the only significant difference is notation. It takes some getting used to, to sometimes treat two objects the same if there's a bijection between them.

Aah, but this has been one of my main concerns; treating two sets the same when there is a bijection between them. I have not been able to convince myself of this concept because I don't understand what we mean by "same". Do we mean "equal"? This cannot be the case here because the Axiom of Extention tells us that these two sets cannot be equal. How do we define the word "same", mathematically?

I mean, we can definitely treat the set Z as the new definition of the Cartesian Product of two sets X and Y. This set certainly exists: Given X and Y, the union X\cup Y exists. The unordered pair \{a,b\}=\{\emptyset,\{\emptyset\}\} exists, and by the old version of the Cartesian Product (i.e. the set of all ordered pairs), \{a,b\}\times X\cup Y exists. Finally, each function z\in Z exists by the Axiom of Specification applied to this Cartesian Product.

But, I can only see this new set Z as a different object. If indeed, Halmos has redfined the Cartesian Product for the purpose of generalization, I will be content. But, even in that case, for each choice of the index set \{a,b\}, we obtain a different set Z, even though they will have the same cardinality. Actually, I have had the same problem with isomorphisms, homeomorphisms, and isometries.

 

[Hurkyl]

"same" depends on context.

Well, the important thing about an ordered pair is that it has a "first element" and a "second element". (And the collection of ordered pairs satisfy a few axioms) The construction (a, b) = {a, {a, b}} is only a model of the notion of ordered pairs; there are many models of the cartesian product.

Generally, the only thing that matters about a set is its size; any two isomorphic sets are essentially interchangible for essentially any application. (By applying any isomorphism¹ to convert between them)

It turns out to be even better than that: the two products are naturally isomorphic, which means that it also interacts seamlessly with functions between sets. (I can elaborate if you want) Because of the natural isomorphism, the products themselves are essentially interchangible for essentially any application.



1: also known as "bijection"

 

[dmuthuk]

"same" depends on context.

Well, the important thing about an ordered pair is that it has a "first element" and a "second element". (And the collection of ordered pairs satisfy a few axioms) The construction (a, b) = {a, {a, b}} is only a model of the notion of ordered pairs; there are many models of the cartesian product.

Generally, the only thing that matters about a set is its size; any two isomorphic sets are essentially interchangible for essentially any application. (By applying any isomorphism¹ to convert between them)

It turns out to be even better than that: the two products are naturally isomorphic, which means that it also interacts seamlessly with functions between sets. (I can elaborate if you want) Because of the natural isomorphism, the products themselves are essentially interchangible for essentially any application.

I assume that each "model" of the ordered pair is essentially some collection of sets that satisfies the defining property of an ordered pair (i.e. (a,b)=(c,d) \mbox{ iff } a=c \mbox{ and } b=d), and a bijection between Z and X\times Y somehow preserves this defining property. Now, I understand that for the purpose of application, it doesn't matter which of the sets Z or X\times Y we use to denote the Cartesian Product of two sets because we are no longer interested in the actual construction of these sets and only interested in their existence and defining properties.

However, as sets alone, disregarding any other special properties, I hope that these two objects are completely different. The reason I want to be sure of this is because when we refer to the "Cartesian Product", I am assuming we are really referring to a particular set rather than a concept. To prove the existence of this set, it is important to know which object we are interested in because the two objects are set-theoretically different. At present, I am approaching this subject with only two concerns in my mind: these predfined objects called sets and the axioms that indirectly tell us about their existence and their properties.

 

[AKG]

Yes, technically they are different, of course. But get used to treating them the same. The set of Dedekind cuts and the set of Cauchy sequences of rationals are different objects, but we treat them as the same thing usually, the set of real numbers.

 

[Hurkyl]

However, as sets alone, disregarding any other special properties, I hope that these two objects are completely different.

The two different products are unequal, but isomorphic constructions.

 

[dmuthuk]

Yes, technically they are different, of course. But get used to treating them the same. The set of Dedekind cuts and the set of Cauchy sequences of rationals are different objects, but we treat them as the same thing usually, the set of real numbers.

Thanks. I have been running into this same problem of "isomorphic" objects over and over again in different fields of mathematics. But, each time, the problem always arises in proving "existence" theorems, which was one of the reasons I started reading up on Set Theory. The problem is that instead of constructing the required object directly, the proofs construct another object which is isomorphic to the object we seek. However, this is a little unsettling sometimes. For instance, in Algebra, Kronecker's Theorem states that for every polynomial over a given field F, there exists an extension of F in which the polynomial has a root. In the proof, I believe that they construct a field that is isomorphic to the extension that is desired. But, then, for a field to be an extension of F, it needs to contain F as a subfield, and in particular, a subset.

So, now here's a question: Suppose you would like prove the existence of some set A. I suppose you start out by assuming A is a class (I don't know much about classes, so I may be on shaky ground). Next, suppose we construct a set B from scratch, and a bijection between A and B (if such a concept makes sense between classes and sets). Then, can we conclude that A is a set, and therefore exists? I mean, is this what happens with those types of existence proofs? Bijection proves existence indirectly? I hope this argument makes some sense.

Oh, and coincidently, I was sort of reading up on Cauchy Sequences and Dedekind Cuts earlier today when I was looking up stuff on bijections and isomorphisms!

 

[Hurkyl]

The axiom of replacement is very convenient:

Let S be a set contained in the domain of the function f. Then,

{ f(x) | x in S }​

is a set.


If f can be represented as a set of ordered pairs, then you can prove this from the other axioms; it's needed for those cases when you do not yet know if f has such a representation.


But even this is overkill for the type of application you're talking about: if you have an injective map f:S --> T, it's easy enough to construct a new set T' by replacing everything in the image of f with its preimage in S. If S and T have additional structure (like a field structure), it's easy enough to invoke f to build the corresponding additional structure on T'.


Incidentally, it is often more convenient to study injective maps f:S-->T rather than the subsets of T. In particular, to define a field extension of K as a homomorphism K --> L, rather than as a field L that contains K as a subset. IMHO, the style of set theoretic proofs seems to put too much emphasis on identity.

 

[AKG]

Thanks. I have been running into this same problem of "isomorphic" objects over and over again in different fields of mathematics. But, each time, the problem always arises in proving "existence" theorems, which was one of the reasons I started reading up on Set Theory. The problem is that instead of constructing the required object directly, the proofs construct another object which is isomorphic to the object we seek. However, this is a little unsettling sometimes. For instance, in Algebra, Kronecker's Theorem states that for every polynomial over a given field F, there exists an extension of F in which the polynomial has a root. In the proof, I believe that they construct a field that is isomorphic to the extension that is desired. But, then, for a field to be an extension of F, it needs to contain F as a subfield, and in particular, a subset.

But there's no significant difference in terms of the algebraic structure. Suppose G is the field that's isomorphic to the extension that's desired. This means that there's some subset F' of G that's isomorphic to F. In your mind, create a new field G' which is the same as G except the elements in F' are replaced with their corresponding elements in F, with the field operations acting on the elements of F as they would on their counterparts in F'.