{ localUrl: '../page/countability.html', arbitalUrl: 'https://arbital.com/p/countability', rawJsonUrl: '../raw/6f8.json', likeableId: '3624', likeableType: 'page', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [ 'EricBruylant' ], pageId: 'countability', edit: '1', editSummary: '', prevEdit: '0', currentEdit: '1', wasPublished: 'true', type: 'wiki', title: 'Countability', clickbait: 'Some infinities are bigger than others. Countable infinities are the smallest infinities.', textLength: '2806', alias: 'countability', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'AlexeiAndreev', editCreatedAt: '2016-10-20 22:56:47', pageCreatorId: 'AlexeiAndreev', pageCreatedAt: '2016-10-20 22:56:47', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '3', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '34', text: 'The [-3jz set] of *counting numbers*, or of *positive integers*, is the set $\\mathbb{Z}^+ = \\{1, 2, 3, 4, \\ldots\\}$.\n\nA set $S$ is called *countable* or *enumerable* if there exists a [4bg surjection] from the counting numbers onto $S$.\n\n### Example: The rational numbers ###\n\nThe set of *rational numbers*, $\\mathbb Q$, is the set of integer fractions $\\frac{p}{q}$ in reduced form; the greatest common divisor of $p$ and $q$ is one, with $q > 0$.\n\n**Theorem** The rational numbers are countable.\n\nThe proof is, essentially, that $\\mathbb Z^+ \\times \\mathbb Z^+$ is isomorphic to $\\mathbb Z$; we count in a roughly spiral pattern centered at zero.\n\n**Proof** Define the *height* of $\\frac{a}{b}$ to be $|a| + |b|$. We may count the rational numbers in order of height, and ordering by $a$, and then $b$, when the heights are the same. The beginning of this counting is $0 / 1$, $-1 / 1$, $1 / 1$, $-2 / 1$, $-1 / 2$, $1 / 2$, $2 / 1$, $\\ldots$ Since there are at most $(2d+1)^2$ rational numbers of height less than or equal to $d$, a rational number with height $d$ is mapped on to by one of the counting numbers up to $(2d+1)^2$; every rational number is mapped onto by this counting. Thus, the rational numbers are countable. $\\square$\n\n*Note*: It is not hard to extend this proof to show that $(\\mathbb Z^+)^n$ is countable for any finite $n$.\n\n**Theorem** If there exists a surjection $f$ from a countable set $A$ to a set $B$, then $B$ is countable.\n**Proof** By definition of countable, there exists an enumeration $E$ of $A$. Now, $E\\circ f$ is an enumeration of $B$, so $B$ is countable.\n\n##Exercises\n\n>Show that the set $\\Sigma^*$ of [ finite words] of an enumerable [ alphabet] is countable.\n\n%%hidden(Show solution):\nFirst, we note that since $\\mathbb N^n$ is countable, the set of words of length $n$ for each $n\\in \\mathbb N$ is countable. \n\nLet $E_n: \\mathbb N \\to \\mathbb N^n$ stand for an enumeration of $\\mathbb N ^n$, and $(J_1,J_2)(n)$ for an enumeration of $\\mathbb N^2$.\n\nConsider the function $E: \\mathbb N \\to \\Sigma^* , n\\hookrightarrow E_{J_1(n)}(J_2(n))$ which maps every number to a word in $\\Sigma^*$. Then a little thought shows that $E$ is an enumeration of $\\Sigma^*$.\n\n$\\square$\n%%\n\n\n\n>Show that the set $P_\\omega(A)$ of finite subsets of an enumerable set $A$ is countable.\n\n%%hidden(Show solution):\nLet $E$ be an enumeration of $A$.\n\nConsider the function $E': \\mathbb N^* \\to P_\\omega(A)$ which relates a word $n_0 n_1 n_2 ... n_r$ made from natural numbers to the set $\\{a\\in A:\\exists m\\le k E(n_m)=a\\}\\subseteq A$. Clearly $E'$ is an enumeration of $P_\\omega(A)$.\n%%\n\n>Show that the set of [ cofinite subsets] of an enumerable set is countable.\n\n%%hidden(Show solution):\nSimply consider the function which relates each cofinite set with its complementary.\n%%', 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: [ 'AlexeiAndreev' ], childIds: [], parentIds: [ 'math' ], commentIds: [], questionIds: [], tagIds: [ 'concept_meta_tag' ], 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: '20206', pageId: 'countability', userId: 'EricBruylant', edit: '0', type: 'newAlias', createdAt: '2016-10-21 11:01:32', auxPageId: '', oldSettingsValue: '6f8', newSettingsValue: 'countability' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '20192', pageId: 'countability', userId: 'AlexeiAndreev', edit: '0', type: 'newTag', createdAt: '2016-10-20 22:56:49', auxPageId: 'concept_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '20191', pageId: 'countability', userId: 'AlexeiAndreev', edit: '0', type: 'newParent', createdAt: '2016-10-20 22:56:48', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3623', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '20189', pageId: 'countability', userId: 'AlexeiAndreev', edit: '1', type: 'newEdit', createdAt: '2016-10-20 22:56:47', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }