Cartesian product
The Cartesian product or quantity of product is in the set theory a basic structure from given amounts to generate a new set. The ambiguous term “ cross product ” is occasionally used for the Cartesian product . The Cartesian product of two sets is the set of all ordered pairs of elements of the two sets, where the first component is an element of the first set and the second component is an element of the second set. More generally, the Cartesian product of several sets consists of the set of all tuples of elements of the sets, the sequence of the sets and thus of the corresponding elements being fixed. The result set of the Cartesian product is also product quantity , Cross quantity or amount of compound called. The Cartesian product is named after the French mathematician René Descartes , who used it to describe the Cartesian coordinate system and thus established analytic geometry .
Product of two sets
definition
The Cartesian product (read "A cross B") of two sets and is defined as the set of all ordered pairs , where one element is out and one element is out. Each element is made with each item of combined. Formally, the Cartesian product is through
Are defined. In particular, it is also possible to form the Cartesian product of a set with itself and then write
- .
Occasionally the term “cross product” is also used for the Cartesian product, but this has other meanings, see cross product .
The above definition is any problem (real) on classes and extensible. In particular, pairs are only formed for elements of and ; these cannot be real classes and have no special requirements for pair formation.
Examples
The Cartesian product of the two sets and is
- .
The Cartesian product , on the other hand, is a different set, namely
- ,
because the order of the elements plays a role in ordered pairs. The Cartesian product of with itself is
- .
The real number level arises from the Cartesian product of the real numbers with themselves:
- .
The tuples are also called Cartesian coordinates . The Cartesian product of two real intervals and gives the rectangle
- .
properties
Number of elements
a | b | c | d | e | f | G | H | ||
8th | 8th | ||||||||
7th | 7th | ||||||||
6th | 6th | ||||||||
5 | 5 | ||||||||
4th | 4th | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | G | H |
If the sets and are finite , then their Cartesian product is a finite set of ordered pairs. The number of pairs corresponds to the product of the numbers of the elements of the initial sets, that is
In the special case that is, applies
- .
If at least one of the two sets and contains an infinite number of elements and the other is not empty, then its Cartesian product consists of an infinite number of pairs. The Cartesian product of two countably infinite sets is also countable according to Cantor's first diagonal argument . If at least one of the two sets is uncountable , then its product set is also uncountable.
Empty set
Since no element can be selected from the empty set , the Cartesian product of the empty set with any set results in the empty set. More generally applies
- ,
that is, the Cartesian product of two sets is empty if and only if at least one of the two sets is empty.
Non-commutativity
The Cartesian product is not commutative , that is, for nonempty sets and with is
- ,
for in the pairs of the set the first element is off and the second is off , while in the pairs of the set the first element is off and the second is off. There is, however, a canonical bijection between the two sets, namely
- ,
with which the quantities can be identified with one another.
Non-associativity
The Cartesian product is also non- associative , that is, for non-empty sets , and holds in general
- ,
because the set on the left side contains pairs whose first element is off and whose second element is a pair off , whereas the set on the right side contains pairs whose first element is a pair off and whose second element is off. Here, too, there is a canonical bijection between these two sets, namely
- .
Some authors identify the pairs and with the ordered triple , which also makes the Cartesian product associative.
Distributivity
The following distributive laws regarding union , intersection and subtraction of sets apply to the Cartesian product :
Monotony and complement
The Cartesian product behaves monotonically with respect to the formation of subsets , that is, if the sets and are not empty, then the following applies
- .
In particular, equality applies
- .
If we consider the set as the basic set of and the set as the basic set of , then has the complement of in the representation
- .
Further calculation rules
It is true
- ,
but in general is
- ,
because the set on the left contains pairs and that are not included in the set on the right.
Product of finitely many quantities
definition
More generally, the Cartesian product of sets is defined as the set of all - tuples , where for each one element is from the set . Formally, the multiple Cartesian product is through
Are defined. With the help of the product symbol , the multiple Cartesian product is also through
written down. The -fold Cartesian product of a set with itself is also written as
- .
Empty product
The Cartesian product of zero sets is the set that contains the empty tuple as the only element , that is
In particular, is for any set
- .
This is used when constants of a mathematical structure are viewed as zero-digit operations.
Association of all products
With denotes the union of all -fold Cartesian products of a set with itself (for all ), i.e. the set of all tuples with elements of A, including the empty tuple:
.
Examples
Is then is
- .
The Euclidean space consists of three times the Cartesian product of the real numbers :
- .
The 3-tuples are the three-dimensional Cartesian coordinates. The Cartesian product of three real intervals , and gives the cuboid
- .
In general, the -fold Cartesian product of the real numbers gives the space and the Cartesian product of real intervals gives a hyper rectangle .
properties
Number of elements
If the sets are all finite, then their Cartesian product is also a finite set, where the number of elements of equals the product of the element numbers of the initial sets , that is
or in a different notation
- .
In the special case that all sets are equal to one set , the following applies
- .
The Cartesian product of a finite number of countably infinite sets is also countable, as can be shown by iterating the argument for the Cartesian product of two sets with the help of Cantor's tuple function .
monotony
If the sets and are not empty, then, as with the Cartesian product of two sets, monotony applies
and equality
- .
Product of infinitely many quantities
definition
It is also possible to define the Cartesian product of an infinite number of sets. If there is an index set and a family of sets for this, then the Cartesian product of the sets is defined by
- .
This is the set of all images of the union of the sets for which the image in lies. If all are equal to a set , then that is the Cartesian product
the set of all functions from to . If the quantities are different, however, the Cartesian product is much less clear. Even the question of whether any Cartesian product of non-empty sets is non-empty can not be decided with the Zermelo-Fraenkel set theory ZF; the assertion that it is not empty is a formulation of the axiom of choice which is added to ZF in order to obtain the set theory ZFC (“Zermelo-Fraenkel + Choice”).
Special cases
An important special case of an infinite Cartesian product arises from the choice of natural numbers as the index set. The Cartesian product of a sequence of sets
then corresponds to the set of all sequences whose -th sequence member is in the set . For example, if all are , then is
the set of all real number sequences. The countable Cartesian product can be mapped bijectively onto the generally defined Cartesian product, because every sequence defines a function with and, conversely, every such function can be written as a sequence . The Cartesian product of finitely many sets can also be understood as a special case of the general definition using finite sequences.
Universal property of the Cartesian product
The family of projections belongs to the Cartesian product . The Cartesian product together with the family has the following property: If there is an arbitrary set and is a family of images, then there is exactly one image with for all . That is, the following diagram is commutative:
If this quality is also common with the family , then there is a bijective mapping .
Derived terms
- A binary relation between two sets is a subset of the Cartesian product of the two sets. In particular, each mapping is therefore a subset of the Cartesian product of the definition and target set of the mapping. More generally, a -digit relation is a subset of the Cartesian product of sets.
- A projection is a mapping of the Cartesian product of two sets back into one of these sets. More generally, a projection is a mapping from the Cartesian product of a family of sets onto the Cartesian product of a subfamily of these sets that selects elements with certain indices.
- A two-digit link is a mapping of the Cartesian product of two sets into another set. More generally, a -digit link is a mapping of the Cartesian product of sets into another set. Every -digit link can therefore also be understood as a -digit relation.
- A direct product is a product of algebraic structures , such as groups or vector spaces , which consists of the Cartesian product of the carrier sets and is additionally provided with one or more component-wise links. A direct sum is a subset of the direct product that differs from the direct product only for products of infinitely many quantities; it consists of all tuples that differ from a certain element (usually the neutral element of a link) only in a finite number of places .
- The categorical product corresponds to the Cartesian product in the category of sets and to the direct product in the category of groups and in other categories of algebraic structures.
- In relational databases , the Cartesian product of tables and the join operations based on them are used to link database tables .
literature
- Oliver Deiser: Introduction to set theory. Georg Cantor's set theory and its axiomatization by Ernst Zermelo. 2nd improved and enlarged edition. Springer, Berlin a. a. 2004, ISBN 3-540-20401-6 .
Web links
- M. Sh. Tsalenko: Direct product . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
- Eric W. Weisstein : Cartesian product . In: MathWorld (English).
- David Jao: Cartesian product . In: PlanetMath . (English)
- Thomas Foregger, David Jao, Andrew Archibald: Generalized cartesian product . In: PlanetMath . (English)