{
localUrl: '../page/poset_lattice_exercise.html',
arbitalUrl: 'https://arbital.com/p/poset_lattice_exercise',
rawJsonUrl: '../raw/5ff.json',
likeableId: '3102',
likeableType: 'page',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [
'NateSoares'
],
pageId: 'poset_lattice_exercise',
edit: '16',
editSummary: '',
prevEdit: '15',
currentEdit: '16',
wasPublished: 'true',
type: 'wiki',
title: 'Lattice: Exercises',
clickbait: '',
textLength: '3601',
alias: 'poset_lattice_exercise',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'KevinClancy',
editCreatedAt: '2017-04-25 00:35:57',
pageCreatorId: 'KevinClancy',
pageCreatedAt: '2016-07-16 18:50:52',
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: '404',
text: 'Try these exercises to test your knowledge of lattices.\n\n## Distributivity\n\nDoes the lattice meet operator distribute over joins? In other words, for all lattices $L$ and all $p, q, r \\in L$, is it necessarily true that $p \\wedge (q \\vee r) = (p \\wedge q) \\vee (p \\wedge r)$? Prove your answer.\n\n%%hidden(Solution):\nThe following counterexample shows that lattice meets do not necessarily distribute over joins.\n\n\n\n%%%comment:\ndot source:\n\ndigraph G {\n node [width = 0.1, height = 0.1]\n edge [arrowhead = "none"]\n\n rankdir = BT;\n t -> p\n t -> q\n t -> r\n p -> s\n q -> s\n r -> s\n}\n%%%\n\nIn the above lattice, $p \\wedge (q \\vee r) = p \\neq t = (p \\wedge q) \\vee (p \\wedge r)$.\n%%\n\n## Common elements\n\nLet $L$ be a lattice, and let $J$ and $K$ be two finite subsets of $L$ with a non-empty intersection. Prove that $\\bigwedge J \\leq \\bigvee K$.\n\n%%hidden(Solution):\nIf $J$ and $K$ have a non-empty intersection, then there exists some lattice element $p$ such that $p \\in J$ and $p \\in K$. Since $\\bigwedge J$ is a lower bound of $J$, we have $\\bigwedge J \\leq p$. Since $\\bigvee K$ is an upper bound of $K$, we have $p \\leq \\bigvee K$. By transitivity, we have $\\bigwedge J \\leq p \\leq \\bigvee K$.\n%%\n\n## Another inequality\n\nLet $L$ be a lattice, and let $J$ and $K$ be two finite subsets of $L$ such that for all $j \\in J$ and $k \\in K$, $j \\leq k$. Prove that $\\bigvee J \\leq \\bigwedge K$.\n\n%%hidden(Solution):\nRephrasing the problem statement, we have that every element of $J$ is a lower bound of $K$ and that every element of $K$ is an upper bound of $J$. It the follows that for $j \\in J$, $j \\leq \\bigwedge K$. Hence, $\\bigwedge K$ is an upper bound of $J$, and therefore it is greater than or equal to the *least* upper bound of $J$: $\\bigvee J \\leq \\bigwedge K$.\n%%\n\n## The minimax theorem\n\nLet $L$ be a lattice and $A$ an $m \\times n$ matrix of elements of $L$. Prove the following inequality: $$\\bigvee_{i=1}^m \\bigwedge_{j=1}^n A_{ij} \\leq \\bigwedge_{j=1}^n \\bigvee_{i=1}^m A_{ij}$$.\n\n%%hidden(Solution):\nTo get an intuitive feel for this theorem, it helps to first consider a small concrete instantiation. Consider the $3 \\times 3$ matrix depicted below, with elements $a,b,c,d,e,f,g,h$, and $i$. The inequality instantiates to $(a \\wedge b \\wedge c) \\vee (d \\wedge e \\wedge f) \\vee (g \\wedge h \\wedge i) \\leq (a \\vee d \\vee g) \\wedge (b \\vee e \\vee h) \\wedge (c \\vee f \\vee i)$. Why would this inequality hold?\n\n$$\\left[ \\begin{array}{ccc}\na & b & c \\\\\nd & e & f \\\\\ng & h & i \\\\\n\\end{array} \\right]$$\n\nNotice that each parenthesized expression on the left hand side of the inequality shares an element with each parenthesized expression on the right hand side of the inequality.This is true because the parenthesized expressions on the left hand side correspond to rows and the parenthesized expressions on the right hand side correspond to columns; each row of a matrix shares an element with each of its columns. The theorem proven in the *Common elements* exercise above then tells us that each parenthesized expression on the left hand side is less than or equal to each parenthesized expression on the right hand side.\n\nLet $J = \\{ a \\wedge b \\wedge c, d \\wedge e \\wedge f, g \\wedge h \\wedge i \\}$ and $K = \\{ a \\vee d \\vee g, b \\vee e \\vee h, c \\vee f \\vee i \\}$. Then the hypothesis for the theorem proven in the *Another inequality* exercise holds, giving us $\\bigvee J \\leq \\bigwedge K$, which is exactly what we wanted to prove. Extending this approach to the general case is straightforward.\n%%\n\n\n',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '',
hasDraft: 'false',
votes: [],
voteSummary: [
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0'
],
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: [
'KevinClancy'
],
childIds: [],
parentIds: [
'order_lattice'
],
commentIds: [],
questionIds: [],
tagIds: [
'exercise_meta_tag'
],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [],
subjects: [],
lenses: [],
lensParentId: 'order_lattice',
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: '22494',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '16',
type: 'newEdit',
createdAt: '2017-04-25 00:35:57',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '3529',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '19683',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '15',
type: 'newEdit',
createdAt: '2016-09-22 16:58:35',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17040',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '14',
type: 'newEdit',
createdAt: '2016-07-17 14:36:37',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17039',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '13',
type: 'newEdit',
createdAt: '2016-07-17 03:07:01',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17033',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '12',
type: 'newEdit',
createdAt: '2016-07-17 01:26:41',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17032',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '11',
type: 'newEdit',
createdAt: '2016-07-17 01:25:10',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17031',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '10',
type: 'newEdit',
createdAt: '2016-07-17 01:13:55',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16993',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '9',
type: 'newEdit',
createdAt: '2016-07-17 00:39:52',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16980',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '7',
type: 'newEdit',
createdAt: '2016-07-16 23:44:59',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: 'Added two new exercises: "Common elements" and "Separation"'
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16944',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '0',
type: 'newTag',
createdAt: '2016-07-16 20:52:54',
auxPageId: 'exercise_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16911',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '6',
type: 'newEdit',
createdAt: '2016-07-16 19:35:31',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16903',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '5',
type: 'newEdit',
createdAt: '2016-07-16 19:05:45',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16902',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '4',
type: 'newEdit',
createdAt: '2016-07-16 19:00:14',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16901',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '3',
type: 'newEdit',
createdAt: '2016-07-16 18:58:59',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16899',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '2',
type: 'newEdit',
createdAt: '2016-07-16 18:56:12',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '16895',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '0',
type: 'newParent',
createdAt: '2016-07-16 18:50:54',
auxPageId: 'order_lattice',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '3087',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '16893',
pageId: 'poset_lattice_exercise',
userId: 'KevinClancy',
edit: '1',
type: 'newEdit',
createdAt: '2016-07-16 18:50:52',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}