{
localUrl: '../page/cantor_schroeder_bernstein_theorem.html',
arbitalUrl: 'https://arbital.com/p/cantor_schroeder_bernstein_theorem',
rawJsonUrl: '../raw/5sh.json',
likeableId: '3473',
likeableType: 'page',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [
'JaimeSevillaMolina'
],
pageId: 'cantor_schroeder_bernstein_theorem',
edit: '3',
editSummary: 'updated link to cardinality',
prevEdit: '2',
currentEdit: '3',
wasPublished: 'true',
type: 'wiki',
title: 'Cantor-Schröder-Bernstein theorem',
clickbait: 'This theorem tells us that comparing sizes of sets makes sense: if one set is smaller than another, and the other is smaller than the one, then they are the same size.',
textLength: '7139',
alias: 'cantor_schroeder_bernstein_theorem',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'EricBruylant',
editCreatedAt: '2016-08-27 14:12:19',
pageCreatorId: 'PatrickStevens',
pageCreatedAt: '2016-08-06 12:02:39',
seeDomainId: '0',
editDomainId: 'AlexeiAndreev',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '1',
isEditorComment: 'false',
isApprovedComment: 'true',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '38',
text: '[summary: The Cantor-Schröder-Bernstein theorem tells us that if one [3jz set] is [4w5 smaller-than-or-equal-to] another, and the other is smaller-than-or-equal-to the one, then they are the same size. That is, "comparison of set sizes" behaves itself, analogously to the fact in the [45h natural numbers] that it can't be the case that both $1 < 2$ and $2<1$.]\n\n[summary(Technical): The Cantor-Schröder-Bernstein theorem states that the [class_set_theory class] of [4w5 cardinals] forms a [540 total order]. (Though not a totally ordered *set*, because [cardinals_form_a_proper_class there is no set of all cardinals]).]\n\nRecall that we say a [3jz set] $A$ is *smaller than or equal to* a set $B$ if there is an [4b7 injection] from $A$ to $B$.\nThe set $A$ *has the same [4w5 size]* as $B$ if there is a [499 bijection] between $A$ and $B$.\n\nThe Cantor-Schröder-Bernstein theorem states that if $A$ is smaller than or equal to $B$, and $B$ is smaller than or equal to $A$, then $A$ and $B$ have the same size.\nThis tells us that the arithmetic of [4w5 cardinals] is well-behaved in that it behaves like a [540 total order].\nIt is similar to the arithmetic of the [45h natural numbers] in that it can never be the case that simultaneously $a < b$ and $b < a$.\n\n# Proofs\n\nThere are several proofs, some concrete and some less so.\n\n## Concrete proof\n\nA clear explanation of the intuition of this proof [has been written](https://www.math.brown.edu/~res/infinity.pdf) by Richard Evan Schwartz; see page 61 of the linked PDF, or search on the word "dog" (which appears in the first page of the explanation).\n[comment: The intuition is Math0 suitable.]\n\nLet $f: A \\to B$ and $g: B \\to A$ be injections; we will define a bijective function $h: A \\to B$.\n\nBecause $f$ is injective, if $f$ ever hits $b$ (that is, if there is $a \\in A$ such that $f(a) = b$) then it is possible to define $f^{-1}(b)$ to be the *unique* $a \\in A$ such that $f(a) = b$; similarly with $g$.\nThe slogan is "if $f^{-1}(a)$ exists, then it is well-defined: there is no leeway about which element we might choose to be $f^{-1}(a)$".\n\nFix some $a \\in A$, and consider the sequence $$\\dots, f^{-1}(g^{-1}(a)), g^{-1}(a), a, f(a), g(f(a)), \\dots$$\nNow, this sequence might not extend infinitely to the left; it may not even get past $a$ to the left (if $g^{-1}(a)$ doesn't exist, for instance). %%note:On the other hand, perhaps the sequence does extend infinitely to the left.%%\nAlso, the sequence might duplicate elements: it might be the case that $gfgf(a) = a$, for instance. %%note:And maybe there is a repeat somewhere to the left, too.%%\n\nSimilarly, we can fix some $b \\in B$, and consider $$\\dots g^{-1} f^{-1}(b), f^{-1}(b), b, g(b), f(g(b)), \\dots$$\n\nEvery element of $A$, and every element of $B$, appears in one of these chains.\nMoreover, if $a \\in A$ appears in two different chains, then in fact the two chains are the same %%note:Though maybe we're looking at a different place on the same chain. If we compare the $g^{-1} f^{-1}(b)$-chain with the $b$-chain, we see they're the same chain viewed two different ways: one viewing is two places offset from the other viewing.%%, because each element of the chain specifies and is specified by the previous element in the chain (if it exists) and each element of the chain specifies and is specified by the next element of the chain.\n\nSo every element of $A$ and every element of $B$ is in exactly one chain.\nNow, it turns out that there are exactly four distinct "types" of chain.\n\n- It could extend infinitely in both directions without repeats. In this case, we define $h(a) = f(a)$ for each element of $A$ in the chain. (Basically assigning to each element of $A$ the element of $B$ which is next in the chain.)\n- It could extend infinitely off to the right, but it has a hard barrier at the left, and has no repeats: the chain stops at an element of $A$. In this case, again we define $h(a) = f(a)$ for each element of $A$ in the chain. (Again, basically assigning to each element of $A$ the element of $B$ which is next in the chain.)\n- It could extend infinitely off to the right, but it has a hard barrier at the left, and has no repeats: the chain stops at an element of $B$. In this case, we define $h(a) = g^{-1}(a)$ for each element of $A$ in the chain. (Basically assigning to each element of $A$ the element of $B$ which is *previous* in the chain.)\n- It could have repeats. Then it must actually be a cycle of even length (unrolled into an infinite line), because each element of the chain only depends on the one before it, and because we can't have two successive elements of $A$ (since the elements are alternating between $A$ and $B$). In this case, we define $h(a) = f(a)$ for each element of $A$ in the chain. (Basically assigning to each element of $A$ the element of $B$ which is next in the chain.)\n\nHave we actually made a bijection?\nCertainly our function is well-defined: every element of $A$ appears in exactly one chain, and we've specified where every element of $A$ in any chain goes, so we've specified where every element of $A$ goes.\n\nOur function is [4bg surjective], because every element of $B$ is in a chain; if $b \\in B$ has an element $a$ of $A$ before it in its chain, then we specified that $h$ takes $a$ to $b$, while if $b \\in B$ is at the leftmost end of its chain, we specified that $h$ takes $g(b)$ (that is, the following element in the chain) to $b$.\n\nOur function is injective.\nSince the chains don't overlap, and the first three cases of "what a chain might look like" have no repeats at all, the only possible way an element of $B$ can be hit twice by $h$ is if that element lies in one of the cyclical chains.\nBut then to elements of $A$ in that chain, $h$ assigns the following element of $B$; so $b \\in B$ is hit only by the preceding element of $A$, which is the same in all cases because the chain is a cycle.\n%%note:The picture in the linked intuitive document makes this much clearer.%%\n\n## Proof from the [knaster_tarski_theorem Knaster-Tarski theorem]\nThis proof is very quick, but almost completely opaque.\nIt relies on the [knaster_tarski_theorem Knaster-Tarski fixed point theorem], which states that if $X$ is a [complete_poset complete poset] and $f: X \\to X$ is [order_preserving_map order-preserving], then $f$ has a [-fixed_point] (i.e. $x$ such that $f(x) = x$).\n\nLet $f: A \\to B$ and $g: B \\to A$ be injective.\n\nWe are looking for a [set_partition partition] $P \\cup Q$ of $A$, and a partition $R \\cup S$ of $B$, such that $f$ is injective from $P$ to $R$, and $g$ is injective from $S$ to $Q$.\n(Then we can just define our bijection $A \\to B$ by "do $f$ on $P$, and do $g^{-1}$ on $Q$".)\n\nNow, the function $P \\mapsto A \\setminus g(B \\setminus f(P))$ is order-preserving from the [-power_set] $\\mathcal{P}(A)$ to $\\mathcal{P}(A)$ (ordered by inclusion), because there is an even number of complements.\n\nBut $\\mathcal{P}(A)$ is complete as a poset ([power_set_poset_is_complete proof]), so by Knaster-Tarski there is a set $P$ such that $P = A \\setminus g(B \\setminus f(P))$.\n\nThis yields our partition as required. [todo: spell this out]',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '',
hasDraft: 'false',
votes: [],
voteSummary: 'null',
muVoteSummary: '0',
voteScaling: '0',
currentUserVote: '-2',
voteCount: '0',
lockedVoteType: '',
maxEditEver: '0',
redLinkCount: '0',
lockedBy: '',
lockedUntil: '',
nextPageId: '',
prevPageId: '',
usedAsMastery: 'false',
proposalEditNum: '0',
permissions: {
edit: {
has: 'false',
reason: 'You don't have domain permission to edit this page'
},
proposeEdit: {
has: 'true',
reason: ''
},
delete: {
has: 'false',
reason: 'You don't have domain permission to delete this page'
},
comment: {
has: 'false',
reason: 'You can't comment in this domain because you are not a member'
},
proposeComment: {
has: 'true',
reason: ''
}
},
summaries: {},
creatorIds: [
'PatrickStevens',
'EricBruylant'
],
childIds: [],
parentIds: [
'set_mathematics'
],
commentIds: [],
questionIds: [],
tagIds: [],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [],
subjects: [],
lenses: [],
lensParentId: '',
pathPages: [],
learnMoreTaughtMap: {},
learnMoreCoveredMap: {},
learnMoreRequiredMap: {},
editHistory: {},
domainSubmissions: {},
answers: [],
answerCount: '0',
commentCount: '0',
newCommentCount: '0',
linkedMarkCount: '0',
changeLogs: [
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '19294',
pageId: 'cantor_schroeder_bernstein_theorem',
userId: 'EricBruylant',
edit: '3',
type: 'newEdit',
createdAt: '2016-08-27 14:12:19',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: 'updated link to cardinality'
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18496',
pageId: 'cantor_schroeder_bernstein_theorem',
userId: 'PatrickStevens',
edit: '2',
type: 'newEdit',
createdAt: '2016-08-06 13:11:09',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18492',
pageId: 'cantor_schroeder_bernstein_theorem',
userId: 'PatrickStevens',
edit: '0',
type: 'newParent',
createdAt: '2016-08-06 12:02:41',
auxPageId: 'set_mathematics',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '3349',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '18490',
pageId: 'cantor_schroeder_bernstein_theorem',
userId: 'PatrickStevens',
edit: '1',
type: 'newEdit',
createdAt: '2016-08-06 12:02:39',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}