1.4.10: The Notion of Size, and Schröder-Bernstein

Sets, Logic, Computation · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    1.4.10: The Notion of Size, and Schröder-Bernstein

    \(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
    \(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
    \(\def\Bin{ {\mathbb{B}} }\)
    \(\def\cardeq#1#2{ { #1 \approx #2 } }\)
    \(\def\cardle#1#2{ { #1 \preceq #2 } }\)
    \(\def\cardless#1#2{ { #1 \prec #2 } }\)
    \(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
    \(\def\comp#1#2{ { #2 \circ #1 } }\)
    \(\def\concat{ { \;\frown\; } }\)
    \(\def\Cut{ { \text{Cut} } }\)
    \(\def\Discharge#1#2{ { [#1]^#2 } }\)
    \(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
    \(\def\dom#1{ {\operatorname{dom}(#1)} }\)
    \(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
    \(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
    \(\newcommand{\Entails}{\vDash}\)
    \(\newcommand{\EntailsN}{\nvDash}\)
    \(\def\eq[#1][#2]{ { #1 = #2 } }\)
    \(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
    \(\def\equivclass#1#2{ { #1/_{#2} } }\)
    \(\def\equivrep#1#2{ { [#1]_{#2} } }\)
    \(\def\Exchange{ { \text{X} } }\)
    \(\def\False{ { \mathbb{F} } }\)
    \(\def\FalseCl{ { \lfalse_C } }\)
    \(\def\FalseInt{ { \lfalse_I } }\)
    \(\def\fCenter{ { \,\Sequent\, } }\)
    \(\def\fdefined{ { \;\downarrow } }\)
    \(\def\fn#1{ { \operatorname{#1} } }\)
    \(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
    \(\def\fundefined{ { \;\uparrow } }\)
    \(\def\funimage#1#2{ { #1[#2] } }\)
    \(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
    \(\newcommand{\ident}{\equiv}\)
    \(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
    \(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
    \(\def\indfrm{ { A } }\)
    \(\def\indfrmp{ { A } }\)
    \(\def\joinrel{\mathrel{\mkern-3mu}}\)
    \(\def\lambd[#1][#2]{\lambda #1 . #2}\)
    \(\def\Lang#1{ { \mathcal{#1} } }\)
    \(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
    \(\def\len#1{ {\operatorname{len}(#1)} }\)
    \(\def\lexists#1#2{ { \exists #1\, #2 } }\)
    \(\def\lfalse{ {\bot} }\)
    \(\def\lforall#1#2{ { \forall#1\, #2 } }\)
    \(\newcommand{\lif}{\rightarrow}\)
    \(\newcommand{\liff}{\leftrightarrow}\)
    \(\def\Log#1{ { \mathbf{#1} } }\)
    \(\def\ltrue{ {\top} }\)
    \(\def\Id#1{ {\operatorname{Id}_#1} }\)
    \(\def\Int{ {\mathbb{Z}} }\)
    \(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
    \(\def\mModel#1{ { \mathfrak{#1} } }\)
    \(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
    \(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
    \(\def\Nat{ {\mathbb{N}} }\)
    \(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
    \(\def\num#1{ { \overline{#1} } }\)
    \(\def\ran#1{ {\operatorname{ran}(#1)} }\)
    \(\newcommand{\Obj}[1]{\mathsf{#1}}\)
    \(\def\Rat{ {\mathbb{Q}} }\)
    \(\def\Real{ {\mathbb{R}} }\)
    \(\def\RightR#1{ { {#1}\mathrm{R} } }\)
    \(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
    \(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
    \(\def\PosInt{ {\mathbb{Z}^+} }\)
    \(\def\Pow#1{ {\wp(#1)} }\)
    \(\newcommand{\Proves}{\vdash}\)
    \(\newcommand{\ProvesN}{\nvdash}\)
    \(\def\Relbar{\mathrel{=}}\)
    \(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
    \(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
    \(\newcommand{\Sequent}{\Rightarrow}\)
    \(\def\Setabs#1#2{ { \{#1:#2\} } }\)
    \(\newcommand{\sFmla}[2]{#1\,#2}\)
    \(\def\Struct#1{ {#1} }\)
    \(\def\subst#1#2{ { #1/#2 } }\)
    \(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
    \(\def\TMblank{ { 0 } }\)
    \(\newcommand{\TMendtape}{\triangleright}\)
    \(\def\TMleft{ { L } }\)
    \(\def\TMright{ { R } }\)
    \(\def\TMstay{ { N } }\)
    \(\def\TMstroke{ { 1 } }\)
    \(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
    \(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
    \(\def\True{ { \mathbb{T} } }\)
    \(\newcommand{\TRule}[2]{#2#1}\)
    \(\def\tuple#1{ {\langle #1 \rangle} }\)
    \(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
    \(\def\Var{ { \mathrm{Var} } }\)
    \(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
    \(\def\Weakening{ { \text{W} } }\)

    Here is an intuitive thought: if \(A\) is no larger than \(B\) and \(B\) is no larger than \(A\), then \(A\) and \(B\) are equinumerous. To be honest, if this thought were wrong, then we could scarcely justify the thought that our defined notion of equinumerosity has anything to do with comparisons of “sizes” between sets! Fortunately, though, the intuitive thought is correct. This is justified by the Schröder-Bernstein Theorem.

    Theorem \(\PageIndex{1}\) (Schröder-Bernstein)

    If \(\cardle{A}{B}\) and \(\cardle{B}{A}\), then \(\cardeq{A}{B}\).

    In other words, if there is an injection from \(A\) to \(B\), and an injection from \(B\) to \(A\), then there is a bijection from \(A\) to \(B\).

    This result, however, is really rather difficult to prove. Indeed, although Cantor stated the result, others proved it.1 For now, you can (and must) take it on trust.

    Fortunately, Schröder-Bernstein is correct, and it vindicates our thinking of the relations we defined, i.e., \(\cardeq{A}{B}\) and \(\cardle{A}{B}\), as having something to do with “size”. Moreover, Schröder-Bernstein is very useful. It can be difficult to think of a bijection between two equinumerous sets. The Schröder-Bernstein Theorem allows us to break the comparison down into cases so we only have to think of an injection from the first to the second, and vice-versa.


    1. For more on the history, see e.g., Potter (2004, pp. 165–6).↩︎

    This page titled 1.4.10: The Notion of Size, and Schröder-Bernstein was last modified on Fri, 08 Mar 2024 05:56:23 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .