Cartesian product

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Cartesian product of assemblies

In mathematics, the Cartesian product of two sets is an operation, which results in another set, whose elements are all the ordered pairs that can be formed such that the first element of the ordered pair belongs to the set. first set and the second element belongs to the second set.

The Cartesian product is named after René Descartes, whose formulation of analytic geometry gave rise to this concept.

Example

For example, given the sets:

${displaystyle A={1,2,3,4}}$

and

${displaystyle B={a,b}}$

your cartesian product of A times B is:

${displaystyle {begin{array}{r|cccc}b&(1,b)&(2,b)&(3,b)&(4,b)\a&(1,a)&(2,a)&(3,a)&(4,a)\hline Atimes B&1&2&3&4\end{array}}}$

what is rendered:

${displaystyle Atimes B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b),(4,a),(4,b)}}$

and the Cartesian product of B times A is:

${displaystyle {begin{array}{r|cc}4&(a,4)&(b,4)\3&(a,3)&(b,3)\2&(a,2)&(b,2)\1&(a,1)&(b,1)\hline Btimes A&a&b\end{array}}}$

what is rendered:

${displaystyle Btimes A={(a,1),(a,2),(a,3),(a,4),(b,1),(b,2),(b,3),(b,4)}}$

See that:

${displaystyle (1,a)neq (a,1)}$

Since they are ordered pairs.

Definition

Is a collection of two distinguished objects as first and second, and is denoted as $(a, b)$ , where $a$ is the "first element" and $b$ the “second element”. Given two sets $A$ and $B$ , their Cartesian product is the set of all ordered pairs that can be formed with these two sets:

The Cartesian product of $A$ and $B$ is the whole $A \times B$ whose elements are the ordered pairs $(a, b)$ Where $a$ is an element of $A$ and $b$ an element of $B$ :
${displaystyle Atimes B={(a,b):ain A;;{text{y}};;bin B}}$

The Cartesian square of a set can then be defined as $A 2 = A \times A$ .

The whole

Z 2

can be visualized as the set of points in the plane whose coordinates are integers.

Examples

Integer numbers

Let also be the set of all integers $Z = {..., -2, -1, 0, +1, +2,...}$ . The Cartesian product of $Z$ with itself is $Z 2 = Z \times Z = { (0,0), (0, +1), (0, -1), (0, +2),..., (+1, 0),... (-1, 0),... }$ , that is, the set of ordered pairs whose components are integers. To represent the integers, the number line is used, and to represent the set $Z 2$ , a Cartesian plane is used (in the image).

Painting and brushes

Let the sets be $T$ of paint tubes, and $P$ of brushes:

{displaystyle T={,}

{displaystyle },}

{displaystyle P={,}

{displaystyle },}

The Cartesian product of these two sets, $T \times P$ , contains all possible pairings of paint tubes and brushes. Similar to the case of a Cartesian plane in the previous example, this set can be represented by a table:

Properties

The empty set acts as the zero of the Cartesian product, since it does not have elements to build ordered pairs:

A Cartesian product where some factor is the empty set is empty. In particular:
${displaystyle Atimes varnothing =varnothing times A=varnothing }$

The Cartesian product of two sets is not commutative in general, except in very special cases. The same goes for the associative property.

Generally:
${displaystyle Atimes Bneq Btimes Aquadquad Atimes (Btimes C)neq (Atimes B)times C}$

Since the cartesian product can be represented as a table or a cartesian plane, it is easy to see that the product set is the product of the cardinals of each factor:

The Cartesian product of a finite number of finite sets is finite in turn. In particular, its cardinal is the product of the cardinals of each factor:
${displaystyle |A_{1}times ldots times A_{n}|=|A_{1}|cdot ldots cdot |A_{n}|}$
The Cartesian product of a family of non-empty assemblies that includes some infinite set is infinite in turn.

In set theory, the previous formula of the cardinal of the Cartesian product as the product of the cardinals of each factor, still holds true using infinite cardinals.

Generalizations

Finite case

Given a finite number of sets $A 1$ , $A 2$ ,..., $A n$ , its Cartesian product is defined as the set n-tuples whose first element is in $A 1$ , whose second element is in $A 2$ , etc.

Cartesian product of a finite number of sets $A 1$ ,... $A n$ is the set of n-tuplas whose element $k$ - that belongs to $A k$ for each $1 \leq k \leq n$ :
${displaystyle A_{1}times ldots times A_{n}={(a_{1},ldotsa_{n}):a_{1}in A_{1},,ldots,a_{n}in A_{n}}}$

We can then define Cartesian powers of order higher than 2, as $A 3 = A \times A \times A$ , etc. Depending on the definition of n-tuple that is adopted, this generalization can be built from the basic definition as:

{displaystyle A_{1}times ldots times A_{n}=A_{1}times (A_{2}times (ldots times A_{n})ldots)}

or similar constructs.

Infinite case

In the case of an arbitrary (possibly infinite) family of sets, the way to define the Cartesian product is to change the tuple concept to a more comfortable one. If the family is indexed, an application traversing the index set is the object that distinguishes who is the " $k$ th entry":

The Cartesian product of an indexed family of sets $F = A i! i 한 I$ is the set of applications $f : I \to F$ whose domain is the index set $I$ and their images are elements of some $A i$ who fulfill that for each $i 한 I$ Got it. $f (i) 한 A i$ :
${displaystyle prod _{iin I}A_{i}=left{f:Ito bigcup F |{text{ para cada }}iin I,,f(i)in A_{i}right}}$

where $\cup F$ denotes the union of all $A i$ . Given a $j \in I$ , the projection onto the $j$ coordinate is the map:

{displaystyle pi _{j}:prod _{iin I}A_{i}to A_{j}\ pi _{j}(f)=f(j)}

In the case of a finite family of sets ${A 1,..., A n}$ indexed by the set $I n = {1,..., n}$ , depending on the definition of n-tuple adopted, or the applications $f : I n \to \cup i A i$ of the previous definition are precisely n-tuples, or there is a natural identification between both objects; Therefore, the previous definition can be considered as the most general.

Unlike the finite case, however, the existence of such applications is not justified by the most basic hypotheses of set theory. These maps are in fact choice functions whose existence can only be shown in general if the axiom of choice is assumed. In fact, the existence of choice functions (when all members of $F$ are non-empty) is equivalent to such an axiom.

Contenido relacionado

Más resultados...