Indexed Cartesian Product as sets of functions

[TopCat]

I'm going through the set theory material in the appendix of Knapp's Basic Algebra. I want to make sure that I understand what he says is the set theoretic notion of the indexed cartesian product, \prod_{x\in S}A_{x}.

He says that this can be thought of as the set of all functions f:S\rightarrow \bigcup_{x\in S}A_{x} such that f(x)\in A_{x} for all x\in S. Let's call this set F.

So as an example, let S = \left\{1,2\right\}, A_{1} = \left\{3,4\right\}, and A_{2} = \left\{5,6\right\}. Then \bigcup_{x\in S}A_{x} = \left\{3,4,5,6\right\} and the functions f, being subsets of S\times \bigcup_{x\in S}A_{x}, are f_{1} = \left\{(1,3), (2,5)\right\}, f_{2} = \left\{(1,3), (2,6)\right\}, f_{3} = \left\{(1,4), (2,5)\right\}, f_{4} = \left\{(1,4), (2,6)\right\}.

Then the set F is \left\{\left\{(1,3), (2,5)\right\},\left\{(1,3), (2,6)\right\},\left\{(1,4), (2,5)\right\},\left\{(1,4), (2,6)\right\}\right\}.

Since we can form a bijection g from F to A_{1}\times A_{2} with g:F\rightarrow A_{1}\times A_{2} such that g(f) = (f(1), f(2)) for all f\in F, we can say that F is isomorphic to A_{1}\times A_{2} and thus they are the same set. Is my understanding correct?

 

[SteveL27]

we can say that F is isomorphic to A_{1}\times A_{2} and thus they are the same set. Is my understanding correct?

It looks like you got all the details right, so your understanding is correct.

However, a set of ordered n-tuples is NOT the same set as the set of choice functions. Remember, the axiom of extensionality says that two sets are the same iff they have exactly the same elements. So two sets that have different elements but represent the same structure, are still different sets.

The use of the word isomorphic is true in a casual sense, but you would need to define isomorphism for sets in order for it to be literally true. The idea of isomorphism is typically applied to sets equipped with some algebraic structure, for example addition and/or multiplication defined.

It's true that the two definitions of Cartesian product (n-tuples or choice functions) express the same idea in the case of a finite index set. But I haven't seen the word isomorphism used to express that fact. I could be wrong. What is your definition of isomorphism of sets?

 

[TopCat]

It's true that the two definitions of Cartesian product (n-tuples or choice functions) express the same idea in the case of a finite index set. But I haven't seen the word isomorphism used to express that fact. I could be wrong. What is your definition of isomorphism of sets?

I came across another thread on this forum and stumbled upon the use of isomorphism from a post by Hurkyl: https://www.physicsforums.com/showpost.php?p=1342101&postcount=4

I get that the two sets aren't the same, but are functionally "equivalent" (my choice of words as "same set" was very poor). I, like the OP in that old thread, find it odd that the cartesian product was touted (in this case by Knapp) as exactly the set of all such functions, when it was defined earlier as a set of -tuples. In fact, I realized that I mistyped earlier; Knapp doesn't say that the indexed cartesian product "can be thought of" as the set of all such functions, but that "it is" this set.

However, I'm satisfied with the details given in the other thread on the matter. Thanks for confirming that I wasn't misunderstanding the concept.

 

[SteveL27]

I came across another thread on this forum and stumbled upon the use of isomorphism from a post by Hurkyl: https://www.physicsforums.com/showpost.php?p=1342101&postcount=4

I get that the two sets aren't the same, but are functionally "equivalent" (my choice of words as "same set" was very poor). I, like the OP in that old thread, find it odd that the cartesian product was touted (in this case by Knapp) as exactly the set of all such functions, when it was defined earlier as a set of -tuples. In fact, I realized that I mistyped earlier; Knapp doesn't say that the indexed cartesian product "can be thought of" as the set of all such functions, but that "it is" this set.

However, I'm satisfied with the details given in the other thread on the matter. Thanks for confirming that I wasn't misunderstanding the concept.

In that thread, Hurkyl defined isomorphism as bijection. But that's too weak; because in that case ANY set of cardinality |A| * |B| is isomorphic to the Cartesian product A X B. As excellent as Hurkyl's answers usually are, it is not correct to say that the set of n-tuples is isomorphic to the set of choice functions (for a finite index set) since we do not have a sufficiently strong notion of isomorphism for sets.

The notion of bijection only says two sets have the same cardinality. It's not a strong enough notion to encapsulate the structure of a Cartesian product. And arbitrary sets don't have any additional structure, so we can't use any extra structure to make a precise definition of isomorphism.

I apologize for taking the pedantic route here; but it's always important to understand the exact meaning of things before we get fast and loose with terminology.

By the way the reason for introducing the choice function definition of Cartesian product is to handle the case of an infinite index set. We can't form infinity-tuples via the axioms of set theory; but we CAN form collections of choice sets, even on uncountable index sets. That's why the Cartesian product is defined as the set of choice functions on the index set.

 

[TopCat]

In that thread, Hurkyl defined isomorphism as bijection. But that's too weak; because in that case ANY set of cardinality |A| * |B| is isomorphic to the Cartesian product A X B. As excellent as Hurkyl's answers usually are, it is not correct to say that the set of n-tuples is isomorphic to the set of choice functions (for a finite index set) since we do not have a sufficiently strong notion of isomorphism for sets.

The notion of bijection only says two sets have the same cardinality. It's not a strong enough notion to encapsulate the structure of a Cartesian product. And arbitrary sets don't have any additional structure, so we can't use any extra structure to make a precise definition of isomorphism.

I apologize for taking the pedantic route here; but it's always important to understand the exact meaning of things before we get fast and loose with terminology.

By the way the reason for introducing the choice function definition of Cartesian product is to handle the case of an infinite index set. We can't form infinity-tuples via the axioms of set theory; but we CAN form collections of choice sets, even on uncountable index sets. That's why the Cartesian product is defined as the set of choice functions on the index set.

So you're saying that it's not important that the sets (tuples and choice functions) be the same; they represent two distinct set theoretic notions of the cartesian product. One is limited yet, perhaps, easier to work with. The other is more robust and abstract. That we can, via a bijection, obtain one from the other demonstrates that both definitions are same, though their output sets are not. Is that right?

Also, I greatly appreciate your pedantry here. You've made this very clear for me.

 

[SteveL27]

So you're saying that it's not important that the sets (tuples and choice functions) be the same; they represent two distinct set theoretic notions of the cartesian product.

Yes, exactly.

One is limited yet, perhaps, easier to work with. The other is more robust and abstract.

Yes, exactly.

That we can, via a bijection, obtain one from the other demonstrates that both definitions are same, though their output sets are not. Is that right?

No. The problem is that the notion of bijection is too weak; but we don't have enough structure to define isomorphism.

For example, let S, A1, and A2 be as in your original example. Then A1 X A2 has exactly four elements.

We can think of A1 X A2 as a set of ordered pairs, or as a set of choice functions. Either way, there are four of them, and we can biject the ordered pairs to the choice functions.

However, this does not capture the idea of a Cartesian product. It only captures the idea of fourness. If I give you the set {1, 2, 3, pi}, that's a set of four elements that is bijectively equivalent to the Cartesian product. But it does not have the structure of the Cartesian product.

So the notion of bijection is perfect for characterizing the idea of cardinality, or "how many?" But it's not strong enough to characterize the idea of Cartesian product. All you can conclude from bijecting the ordered pairs to the choice functions is that they have the same number of elements. You have not demonstrated that they have the same structure.

On the other hand, we would like to use the term "isomorphism," but arbitrary sets don't have enough structure to do that.

I don't know offhand if there is some general way to show that the two definitions of Cartesian product are "the same" in the case of a finite index. I might have to think about that a bit. Perhaps there's a category-theoretic characterization. Can anyone help out here? It's an interesting question.

As far as isomorphism, you need some additional structure on sets in order to define that notion. So you need some algebraic structure, such as + or *; or perhaps an order relationship.

Ah ... I think I have an idea. We could partially order a Cartesian product by set or function inclusion; and then we could show that the n-tuples and the choice functions are order-isomorphic as partially ordered sets. Details for the reader I think that gets us a step in the direction of showing that the n-tuples and the choice functions give us the "same" Cartesian product -- in other words, in developing the correct definition of "isomorphism" for the two definitions of Cartesian product.

[Side remark: This illustrates a general idea in math. The interesting part of math is often to come up with the right definition. In the textbooks they GIVE us the definitions; but the historical development is often a long struggle to FIND the right definition. Or as they say: The theorems are easy. The definitions are hard!]

Also, I greatly appreciate your pedantry here. You've made this very clear for me.

So glad this is helpful.

(edit)
Ah I remember now. There is a category-theoretic answer. The Cartesian product is the product in the category of sets. So there IS a way to show that the two definitions of Cartesian product are the same, but you have to use the idea of a universal property.

http://en.wikipedia.org/wiki/Product_(category_theory)

 

[TopCat]

Wow, excellent. Your response is very clear and I totally appreciate the effort you made in explaining it to me.

I know category theory is useful for algebra, so this is good motivation to start looking at some important definitions and theorems before it's delved into in the text.