{
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: '19',
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: {}
}