{ localUrl: '../page/set_disjoint_union.html', arbitalUrl: 'https://arbital.com/p/set_disjoint_union', rawJsonUrl: '../raw/5z9.json', likeableId: '0', likeableType: 'page', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], pageId: 'set_disjoint_union', edit: '5', editSummary: '', prevEdit: '4', currentEdit: '5', wasPublished: 'true', type: 'wiki', title: 'Disjoint union of sets', clickbait: 'One of the most basic ways we have of joining two sets together.', textLength: '8838', alias: 'set_disjoint_union', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'PatrickStevens', editCreatedAt: '2016-10-23 18:13:25', pageCreatorId: 'PatrickStevens', pageCreatedAt: '2016-08-24 07:05:13', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '0', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '1968', text: '[summary: The *disjoint union* of two [3jz sets] is just the [5s8 union], but with the additional information that the two sets also don't have any elements in common. That is, we can use the phrase "disjoint union" to indicate that we've taken the union of two sets which have empty [5sb intersection]. The phrase can also be used to indicate a very slightly different operation: "do something to the elements of each set to make sure they don't overlap, and then take the union".]\n\n[summary(Technical): The phrase "disjoint union" is used to mean one of two slightly different operations on [3jz sets]. It indicates either "just take the [5s8 union], but also notice that we've been careful to ensure that the sets have empty [5sb intersection]", or "perform a specific operation on each set to ensure that the resulting sets have empty intersection, and then take the union".]\n\nThe *disjoint union* of two [3jz sets] is just the [5s8 union], but with the additional information that the two sets also don't have any elements in common. That is, we can use the phrase "disjoint union" to indicate that we've taken the union of two sets which have empty [5sb intersection]. The phrase can also be used to indicate a very slightly different operation: "do something to the elements of each set to make sure they don't overlap, and then take the union".\n\n# Definition of the disjoint union\n\n"Disjoint union" can mean one of two things:\n\n- The simple [5s8 union], together with the assertion that the two sets don't overlap;\n- The operation "do something to the elements of each set to make sure they don't overlap, and then take the union".\n\n(Mathematicians usually let context decide which of these meanings is intended.)\n\nThe disjoint union has the symbol $\\sqcup$: so the disjoint union of sets $A$ and $B$ is $A \\sqcup B$.\n\n## The first definition\n\nLet's look at $A = \\{6,7\\}$ and $B = \\{8, 9\\}$.\nThese two sets don't overlap: no element of $A$ is in $B$, and no element of $B$ is in $A$.\nSo we can announce that the union of $A$ and $B$ (that is, the set $\\{6,7,8,9\\}$) is in fact a *disjoint* union.\n\nIn this instance, writing $A \\sqcup B = \\{6,7,8,9\\}$ is just giving the reader an extra little hint that $A$ and $B$ are disjoint; I could just have written $A \\cup B$, and the formal meaning would be the same.\nFor the purposes of the first definition, think of $\\sqcup$ as $\\cup$ but with a footnote reading "And, moreover, the union is disjoint".\n\nAs a non-example, we could *not* legitimately write $\\{1,2\\} \\sqcup \\{1,3\\} = \\{1,2,3\\}$, even though $\\{1,2\\} \\cup \\{1,3\\} = \\{1,2,3\\}$; this is because $1$ is in both of the sets we are unioning.\n\n## The second definition\n\nThis is the more interesting definition, and it requires some fleshing out.\n\nLet's think about $A = \\{6,7\\}$ and $B = \\{6,8\\}$ (so the two sets overlap).\nWe want to massage these two sets so that they become disjoint, but are somehow "still recognisably $A$ and $B$".\n\nThere's a clever little trick we can do.\nWe tag every member of $A$ with a little note saying "I'm in $A$", and every member of $B$ with a note saying "I'm in $B$".\nTo turn this into something that fits into set theory, we tag an element $a$ of $A$ by putting it in an ordered pair with the number $1$: $(a, 1)$ is "$a$ with its tag".\nThen our massaged version of $A$ is the set $A'$ consisting of all the elements of $A$, but where we tag them first:\n$$A' = \\{ (a, 1) : a \\in A \\}$$\n\nNow, to tag the elements of $B$ in the same way, we should avoid using the tag $1$ because that means "I'm in $A$"; so we will use the number $2$ instead.\nOur massaged version of $B$ is the set $B'$ consisting of all the elements of $B$, but we tag them first as well:\n$$B' = \\{ (b,2) : b \\in B \\}$$\n\nNotice that $A$ [499 bijects] with $A'$ %%note: Indeed, a bijection from $A$ to $A'$ is the map $a \\mapsto (a,1)$.%%, and $B$ bijects with $B'$, so we've got two sets which are "recognisably $A$ and $B$".\n\nBut magically $A'$ and $B'$ are disjoint, because everything in $A'$ is a tuple with second element equal to $1$, while everything in $B'$ is a tuple with second element equal to $2$.\n\nWe define the *disjoint union of $A$ and $B$* to be $A' \\sqcup B'$ (where $\\sqcup$ now means the first definition: the ordinary union but where we have the extra information that the two sets are disjoint).\nThat is, "make the sets $A$ and $B$ disjoint, and then take their union".\n\n# Examples\n\n## $A = \\{6,7\\}$, $B=\\{6,8\\}$\nTake a specific example where $A = \\{6,7\\}$ and $B=\\{6,8\\}$.\nIn this case, it only makes sense to use $\\sqcup$ in the second sense, because $A$ and $B$ overlap (they both contain the element $6$).\n\nThen $A' = \\{ (6, 1), (7, 1) \\}$ and $B' = \\{ (6, 2), (8, 2) \\}$, and the disjoint union is $$A \\sqcup B = \\{ (6,1), (7,1), (6,2), (8,2) \\}$$\n\nNotice that $A \\cup B = \\{ 6, 7, 8 \\}$ has only three elements, because $6$ is in both $A$ and $B$ and that information has been lost on taking the union.\nOn the other hand, the disjoint union $A \\sqcup B$ has the required four elements because we've retained the information that the two $6$'s are "different": they appear as $(6,1)$ and $(6,2)$ respectively.\n\n## $A = \\{1,2\\}$, $B = \\{3,4\\}$\n\nIn this example, the notation $A \\sqcup B$ is slightly ambiguous, since $A$ and $B$ are disjoint already.\nDepending on context, it could either mean $A \\cup B = \\{1,2,3,4\\}$, or it could mean $A' \\cup B' = \\{(1,1), (2,1), (3,2), (4,2) \\}$ (where $A' = \\{(1,1), (2,1)\\}$ and $B' = \\{(3,2), (4,2) \\}$).\nIt will usually be clear which of the two senses is meant; the former is more common in everyday maths, while the latter is usually intended in set theory.\n\n## Exercise\n\nWhat happens if $A = B = \\{6,7\\}$?\n\n%%hidden(Show): Only the second definition makes sense.\n\nThen $A' = \\{(6,1), (7,1)\\}$ and $B' = \\{(6,2), (7,2)\\}$, so $$A \\sqcup B = \\{(6,1),(7,1),(6,2),(7,2)\\}$$\nwhich has four elements.%%\n\n## $A = \\mathbb{N}$, $B = \\{ 1, 2, x \\}$\n\nLet $A$ be the set $\\mathbb{N}$ of [45h natural numbers] including $0$, and let $B$ be the set $\\{1,2,x\\}$ containing two natural numbers and one symbol $x$ which is not a natural number.\n\nThen $A \\sqcup B$ only makes sense under the second definition; it is the union of $A' = \\{ (0,1), (1,1), (2,1), (3,1), \\dots\\}$ and $B' = \\{(1,2), (2,2), (x,2)\\}$, or $$\\{(0,1), (1,1),(2,1),(3,1), \\dots, (1,2),(2,2),(x,2)\\}$$\n\n## $A = \\mathbb{N}$, $B = \\{x, y\\}$\n\nIn this case, again the notation $A \\sqcup B$ is ambiguous; it could mean $\\{ 0,1,2,\\dots, x, y \\}$, or it could mean $\\{(0,1), (1,1), (2,1), \\dots, (x,2), (y,2)\\}$.\n\n# Multiple operands\n\nWe can generalise the disjoint union so that we can write $A \\sqcup B \\sqcup C$ instead of just $A \\sqcup B$.\n\nTo use the first definition, the generalisation is easy to formulate: it's just $A \\cup B \\cup C$, but with the extra information that $A$, $B$ and $C$ are pairwise disjoint (so there is nothing in any of their intersections: $A$ and $B$ are disjoint, $B$ and $C$ are disjoint, and $A$ and $C$ are disjoin).\n\nTo use the second definition, we just tag each set again: let $A' = \\{(a, 1) : a \\in A \\}$, $B' = \\{ (b, 2) : b \\in B \\}$, and $C' = \\{ (c, 3) : c \\in C \\}$.\nThen $A \\sqcup B \\sqcup C$ is defined to be $A' \\cup B' \\cup C'$.\n\n## Infinite unions\nIn fact, both definitions generalise even further, to unions over arbitrary sets.\nIndeed, in the first sense we can define $$\\bigsqcup_{i \\in I} A_i = \\bigcup_{i \\in I} A_i$$ together with the information that no pair of $A_i$ intersect.\n\nIn the second sense, we can define $$\\bigsqcup_{i \\in I} A_i = \\bigcup_{i \\in I} A'_i$$\nwhere $A'_i = \\{ (a, i) : a \\in A_i \\}$.\n\nFor example, $$\\bigsqcup_{n \\in \\mathbb{N}} \\{0, 1,2,\\dots,n\\} = \\{(0,0)\\} \\cup \\{(0,1), (1,1) \\} \\cup \\{ (0,2), (1,2), (2,2)\\} \\cup \\dots = \\{ (n, m) : n \\leq m \\}$$\n\n# Why are there two definitions?\n\nThe first definition is basically just a notational convenience: it saves a few words when saying "… and moreover the sets are pairwise disjoint".\n\nThe real meat of the idea is the second definition, which provides a way of forcing the sets to be disjoint.\nIt's not necessarily the *only* way we could coherently define a disjoint union (since there's more than one way we could have tagged the sets; if nothing else, $A \\sqcup B$ could be defined the other way round, as $A' \\cup B'$ where $A' = \\{ (a, 2) : a \\in A \\}$ and $B' = \\{ (b,1) : b \\in B \\}$, swapping the tags).\nBut it's the one we use by convention.\nUsually when we're using the second definition we don't much care exactly how we force the sets to be disjoint; we only care that there *is* such a way.\n(For comparison, there is [ordered_pair_formal_definitions more than one way] to define the ordered pair in the [ZF] set theory, but we almost never care really which exact definition we use; only that there is a definition that has the properties we want from it.)', 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: 'true', 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' ], childIds: [ 'disjoint_union_universal_property' ], parentIds: [ 'set_mathematics' ], commentIds: [], questionIds: [], tagIds: [ 'c_class_meta_tag' ], relatedIds: [], markIds: [], explanations: [], learnMore: [], requirements: [ { id: '6255', parentId: 'set_mathematics', childId: 'set_disjoint_union', type: 'requirement', creatorId: 'PatrickStevens', createdAt: '2016-08-24 06:58:09', level: '2', isStrong: 'true', everPublished: 'true' } ], subjects: [], lenses: [ { id: '125', pageId: 'set_disjoint_union', lensId: 'disjoint_union_universal_property', lensIndex: '0', lensName: 'Universal property', lensSubtitle: '', createdBy: '267', createdAt: '2016-09-12 18:23:44', updatedBy: '267', updatedAt: '2016-09-12 18:23:52' } ], 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: '20287', pageId: 'set_disjoint_union', userId: 'EricRogstad', edit: '0', type: 'newTag', createdAt: '2016-10-24 18:50:36', auxPageId: 'c_class_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '20286', pageId: 'set_disjoint_union', userId: 'EricRogstad', edit: '0', type: 'deleteTag', createdAt: '2016-10-24 18:50:30', auxPageId: 'stub_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '20263', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '5', type: 'newEdit', createdAt: '2016-10-23 18:13:25', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '20262', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '4', type: 'newEdit', createdAt: '2016-10-23 18:12:09', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3645', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '20237', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '3', type: 'newEdit', createdAt: '2016-10-21 22:19:29', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3530', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '19684', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '2', type: 'newEdit', createdAt: '2016-09-22 17:26:07', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '19533', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '0', type: 'newChild', createdAt: '2016-09-11 11:24:16', auxPageId: 'disjoint_union_universal_property', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '19089', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '0', type: 'newRequirement', createdAt: '2016-08-24 07:05:16', auxPageId: 'set_mathematics', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '19090', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '0', type: 'newTag', createdAt: '2016-08-24 07:05:16', auxPageId: 'stub_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '19088', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '0', type: 'newParent', createdAt: '2016-08-24 07:05:15', auxPageId: 'set_mathematics', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '3429', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '19086', pageId: 'set_disjoint_union', userId: 'PatrickStevens', edit: '1', type: 'newEdit', createdAt: '2016-08-24 07:05:13', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'true', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }