Erdős theorem (set theory)

The set of Erdős is a theorem of set theory , one of the branches of mathematics . It goes back to the important Hungarian mathematician Paul Erdős .

formulation

The sentence can be stated as follows:

Be the cardinality of the continuum with designated. ${\displaystyle {\mathfrak {c}}}$

Let further be a subset of the real coordinate plane , which has the following property: ${\displaystyle A}$ ${\displaystyle {\mathbb {R} }^{2}}$

Every straight line from parallel to the abscissa axis only intersects in a finite number of points . ${\displaystyle {\mathbb {R} }^{2}}$ ${\displaystyle A}$

Then, assuming the axiom of choice is valid, the following statement of existence applies :

There is a straight line parallel to the ordinate axis which intersects the complementary set in points. ${\displaystyle {\mathbb {R} }^{2}}$ ${\displaystyle \complement {A}={\mathbb {R} }^{2}\setminus A}$ ${\displaystyle {\mathfrak {c}}}$

proof

In order to derive a contradiction , the assumption is made that the alleged statement about existence is false.

That means: It is considered accepted:

The complementary set is intersected by each parallel to the ordinate axis in fewer than points . ${\displaystyle \complement {A}}$ ${\displaystyle {\mathfrak {c}}}$

This is then especially true for those parallels which contain the straight line equation  :

  ${\displaystyle x=n}$ ${\displaystyle (n\in \mathbb {N} )}$

fulfill.

So one has for everyone ${\displaystyle n\in \mathbb {N} }$

  ${\displaystyle |\{n\}\times {\mathbb {R} }\cap \complement {A}|<{\mathfrak {c}}}$ .

Now be for ${\displaystyle n\in \mathbb {N} }$

  ${\displaystyle Q_{n}=\{y\in \mathbb {R} \mid (n,y)\in \complement {A}\}}$ .

Then applies

  ${\displaystyle \{n\}\times Q_{n}=\{n\}\times {\mathbb {R} }\cap \complement {A}}$

and consequently

  ${\displaystyle |Q_{n}|<{\mathfrak {c}}}$ .

This results from applying König's theorem

${\displaystyle |\bigcup _{n\in \mathbb {N} }Q_{n}|\leq \sum _{n\in \mathbb {N} }|Q_{n}|<\prod _{n\in \mathbb {N} }{\mathfrak {c}}={\mathfrak {c}}}$ .

So must

${\displaystyle \bigcup _{n\in \mathbb {N} }Q_{n}\neq \mathbb {R} }$

be.

Hence, one such exists that for all ${\displaystyle y_{0}\in \mathbb {R} }$ ${\displaystyle n\in \mathbb {N} }$

${\displaystyle y_{0}\notin Q_{n}}$

and thus

${\displaystyle (n,y_{0})\in A}$

applies.

However, this means that the straight line parallel to the abscissa axis

  ${\displaystyle y=y_{0}}$

the subset intersects at an infinite number of points, which contradicts the assumed property of . ${\displaystyle A}$ ${\displaystyle A}$

The above assumption thus proves to be untenable and consequently the claim is valid.

Connection with a result by Sierpiński

The set of Erdős is connected to a classical theorem of Wacław Sierpiński of 1919, which also as a decomposition set of Sierpiński ( English Sierpiński's decomposition theorem is known).

It says the following:

The simple continuum hypothesis

  ${\displaystyle 2^{\aleph _{0}}=\aleph _{1}}$  

is logically equivalent to the following statement:

The real coordinate plane     can be represented as the union of two sets of points   with the property ${\displaystyle {\mathbb {R} }^{2}}$   ${\displaystyle A,B\subseteq {\mathbb {R} }^{2}}$

that     with any parallel to the abscissa axis and also     with any parallel to the ordinate axis ${\displaystyle A}$ ${\displaystyle B}$

have at most a countable infinite number of intersections in common.

Based on this decomposition theorem, Erdős has shown that under the tightened assumption of the validity of the generalized continuum hypothesis, his theorem above   can be generalized to sets of a cardinality   . ${\displaystyle >{\mathfrak {c}}}$

See also

• Continuum hypothesis

literature

• Paul Erdős: Some Remarks on Set Theory IV . In: Michigan Mathematical Journal . tape 2 (1953-54) , pp. 169-173 ( renyi.hu [PDF]). MR0067170
• Péter Komjáth : Set Teory: Geometric and Real . In: Ronald L. Graham , Jaroslav Nešetřil (Eds.): The Mathematics of Paul Erdős (=  Algorithms and Combinatorics ). tape 14 . Springer Verlag, Berlin (among others) 1997, ISBN 3-540-61031-6 , pp. 460-466 .
• Wacław Sierpiński: Cardinal and Ordinal Numbers . Panstwowe Wydawnictwo Naukowe, Warsaw 1958 ( MR0095787 ).
• Wacław Sierpiński: Sur quelques propositions concernant la puissance du continu . In: Fund. Math . tape 38 , 1951, pp. 1–13 ( matwbn.icm.edu.pl [PDF]). MR0048517

References and footnotes

1. ↑ Sierpiński, p. 125.
2. ↑ König's theorem requires the axiom of choice for its proof, which is why this is also assumed here.
3. ↑ Komjáth, p. 460.
4. ↑ Sierpiński: Fund. Math. Band 38 , p. 6 .
5. ^ Erdős: Michigan Mathematical Journal . tape 2 , p. 169 .
6. ^ Theorem 3. In: Michigan Mathematical Journal. Volume 2, p. 170.