Difference between revisions of "Cartesian product"
From Maths
(Created page with "{{Todo|Find references}} __TOC__ ==Definition== Given two sets, {{M|X}} and {{M|Y}} their ''Cartesian product'' is the set: * {{M|1=X\times Y:=\{(x,y)\ \vert\ x\in X\wedge y\i...") |
m |
||
| Line 4: | Line 4: | ||
Given two sets, {{M|X}} and {{M|Y}} their ''Cartesian product'' is the set: | Given two sets, {{M|X}} and {{M|Y}} their ''Cartesian product'' is the set: | ||
* {{M|1=X\times Y:=\{(x,y)\ \vert\ x\in X\wedge y\in Y\} }}, note that {{M|(x,y)}} is an ''[[ordered pair]]'' traditionally this means | * {{M|1=X\times Y:=\{(x,y)\ \vert\ x\in X\wedge y\in Y\} }}, note that {{M|(x,y)}} is an ''[[ordered pair]]'' traditionally this means | ||
| − | ** {{M|1=(x,y):=\{x,\{x,y\}\} }} or indeed | + | ** {{M|1=(x,y):=\{\{x\},\{x,y\}\} }} or indeed |
| − | ** {{M|1=X\times Y:=\Big\{\{x,\{x,y\}\}\ \vert\ x\in X\wedge y\in Y\Big\} }} | + | ** {{M|1=X\times Y:=\Big\{\{\{x\},\{x,y\}\}\ \vert\ x\in X\wedge y\in Y\Big\} }} |
| − | + | ===Set construction=== | |
| − | ==Set construction== | + | |
{{Todo|Build a set that contains {{M|\{x,y\} }}s, then build another that contains ordered pairs, then the Cartesian product is a subset of this set}} | {{Todo|Build a set that contains {{M|\{x,y\} }}s, then build another that contains ordered pairs, then the Cartesian product is a subset of this set}} | ||
| + | ===[[Projection|Projections]]=== | ||
| + | With the ''Cartesian product'' of {{M|X}} and {{M|Y}} come two maps: | ||
| + | # {{M|\pi_1:X\times Y\rightarrow X}} given by {{M|\pi_1:(x,y)\mapsto x}} and | ||
| + | # {{M|\pi_2:X\times Y\rightarrow Y}} given by {{M|\pi_2:(x,y)\mapsto y}} | ||
| + | {{Todo|Give explicitly}} | ||
| + | ==Properties== | ||
| + | The ''Cartesian product'' has none of the usual<ref group="Note">By usual I mean common properties of binary operators, eg associativity, commutative sometimes, so forth</ref> properties: | ||
| + | {| class="wikitable" border="1" | ||
| + | |- | ||
| + | ! Property | ||
| + | ! Definition | ||
| + | ! Meaning | ||
| + | ! Comment | ||
| + | |- | ||
| + | ! [[Associative|Associativity]] | ||
| + | | {{M|1=X\times(Y\times Z)=(X\times Y)\times Z}} | ||
| + | | style="background-color:#F23E3E" | No | ||
| + | | We can side-step this with obvious mappings | ||
| + | |- | ||
| + | ! [[Commutative|Commutativity]] | ||
| + | | {{M|1=X\times Y=Y\times X}} | ||
| + | | style="background-color:#F23E3E" | No | ||
| + | |} | ||
| + | ===Associativity=== | ||
| + | Given {{M|X}}, {{M|Y}} and {{M|Z}} notice the two ways of interpreting the ''Cartesian product'' are: | ||
| + | * {{M|(X\times Y)\times Z}} which gives elements of the form {{M|((x,y),z)}} and | ||
| + | * {{M|X\times (Y\times Z)}} which gives elements of the form {{M|(x,(y,z))}} | ||
| + | It is easy to construct a [[bijection]] between these, thus it rarely matters. | ||
| + | ==Notes== | ||
| + | <references group="Note"/> | ||
==References== | ==References== | ||
<references/> | <references/> | ||
{{Definition|Set Theory|Abstract Algebra}} | {{Definition|Set Theory|Abstract Algebra}} | ||
Revision as of 21:57, 8 December 2015
TODO: Find references
Contents
Definition
Given two sets, [ilmath]X[/ilmath] and [ilmath]Y[/ilmath] their Cartesian product is the set:
- [ilmath]X\times Y:=\{(x,y)\ \vert\ x\in X\wedge y\in Y\}[/ilmath], note that [ilmath](x,y)[/ilmath] is an ordered pair traditionally this means
- [ilmath](x,y):=\{\{x\},\{x,y\}\}[/ilmath] or indeed
- [ilmath]X\times Y:=\Big\{\{\{x\},\{x,y\}\}\ \vert\ x\in X\wedge y\in Y\Big\}[/ilmath]
Set construction
TODO: Build a set that contains [ilmath]\{x,y\} [/ilmath]s, then build another that contains ordered pairs, then the Cartesian product is a subset of this set
Projections
With the Cartesian product of [ilmath]X[/ilmath] and [ilmath]Y[/ilmath] come two maps:
- [ilmath]\pi_1:X\times Y\rightarrow X[/ilmath] given by [ilmath]\pi_1:(x,y)\mapsto x[/ilmath] and
- [ilmath]\pi_2:X\times Y\rightarrow Y[/ilmath] given by [ilmath]\pi_2:(x,y)\mapsto y[/ilmath]
TODO: Give explicitly
Properties
The Cartesian product has none of the usual[Note 1] properties:
| Property | Definition | Meaning | Comment |
|---|---|---|---|
| Associativity | [ilmath]X\times(Y\times Z)=(X\times Y)\times Z[/ilmath] | No | We can side-step this with obvious mappings |
| Commutativity | [ilmath]X\times Y=Y\times X[/ilmath] | No |
Associativity
Given [ilmath]X[/ilmath], [ilmath]Y[/ilmath] and [ilmath]Z[/ilmath] notice the two ways of interpreting the Cartesian product are:
- [ilmath](X\times Y)\times Z[/ilmath] which gives elements of the form [ilmath]((x,y),z)[/ilmath] and
- [ilmath]X\times (Y\times Z)[/ilmath] which gives elements of the form [ilmath](x,(y,z))[/ilmath]
It is easy to construct a bijection between these, thus it rarely matters.
Notes
- ↑ By usual I mean common properties of binary operators, eg associativity, commutative sometimes, so forth
