Unformatted text preview:

Ling 726 Mathematical Linguistics, Index to Homework 9November 5, 2001 p.1Index to Homework 91Questions of Homework 9. [from Lecture 9, with an additional handout withadditional questions.]1. Go back to exercises 1 and 2 of homework 8.2. If you did those successfully, youconvinced yourself that the equivalence relation ≡Mod n “equality modulo n” is acongruence on Nat, for any n. Review the argument.a. Now construct the quotient algebra Nat/≡Mod n corresponding to thiscongruence. (Pick an n, e.g. “equality modulo 4”, as in exercise 1 of homework 8.2.)b. Show that the quotient algebra Nat/≡Mod4 is isomorphic to the algebra Mod4.2. Do the exercise suggested at the very end of this handout (Lecture 9). [Namely, gocarefully through the argument that logical equivalence is a congruence on the algebraWWBA(Atom), using as an example a version of statement logic with just two sententialconstants p and q. You should end up with sixteen equivalence classes (not eight asoriginally stated on the handout.]Homework 9, continued.3. In the handout from Partee (1979) on Boolean algebras, there is a section showing thatwe can make systems of Venn diagrams into Boolean algebras if we define thingscarefully. As it’s done there, there’s a different Boolean algebra for each configuration ofcircles, with the various elements of a given algebra corresponding to the differentpossible shadings of the diagrams. Let’s consider, for instance, the Venn diagrams withtwo overlapping circles (as on p. 130 and on 132 of that handout), and let’s construct analgebra called Venn16 (the reason for this name will be seen in one of the questionsbelow.) We can also consider algebras Venn4 with just one circle, Venn256 with threeoverlapping circles drawn as on p. 131, and others corresponding to how many circles wedraw and how they do or don’t overlap; they are also discussed in that handout. And let’sapply some of the things we’ve been learning to Venn16 and its cousins. Some of thequestions below are very simple and are just a review of terminology; some of them willtake some work. You can do any subset of them.3.0. Venn16 is an algebra on what signature?3.1. What is the carrier Venn16 of Venn16? What is its cardinality, i.e. how manymembers does it contain? What are the operations of Venn16? (Illustrate them.) 1 Meredith, here’s a new idea for how to make annotations about which problems are coming from whomin a way that you and Volodja and I have a key but it’s easy to remove it from the copy you’ll put on theweb. I’ll put all that info in footnotes, and then you can just get rid of all footnotes in the version thatbecomes PDF file.Ling 726 Mathematical Linguistics, Index to Homework 9November 5, 2001 p.23.2. Does Venn16 have any subalgebras? If yes, show at least one, and show that it is asubalgebra.3.3. If you can find a subalgebra of Venn16, can you find a homomorphism fromVenn16 to a subalgebra?3.4. There should be a unique homomorphism from the word algebra WWBool to Venn16,since WWBool is an initial algebra. Find it. [Or is this false because Venn16 involves some“variables” and is not just built from a zero and a one?]3.5. Find a homomorphism from Venn16 to Venn4, and give the kernel ker of thathomomorphism.3.6. Building on 3.5, specify the quotient algebra Venn16/ker. Can you name two otherBoolean algebras to which Venn16/ker is isomorphic, one of them in the Venn family ofalgebras and one of them a power set Boolean algebra?3.7. ... Illustrate more of the algebraic concepts from the past lectures in this Venn familyand in relations of these algebras to other Boolean algebras.More questions, I don’t remember when/where we suggested them, although theyare familiar!, and I am inventing post hoc numbers for them.4. Show the correspondence of Venn16 and Lindenbaum Algebra on Statement Logicwith just {p,q}.5. Review discussion of Venn algebras (in old Partee book) with 21, 23, 25, ... . Can youfind any way to modify the Lindenbaum Algebras to come up with correspondingalgebras with equivalent classes of formulas?Student answers.Solution 1: Question 1. This is one good way to work it out. There is no one canonicalway to do a problem like this one and no single correct way to prove that what you’redoing is correct.Solution 2: Question 1. This is much longer than answer 1; everything about theisomorphism is shown in exhaustive detail. We don’t recommend showing it thisexhaustively, but it’s very pretty and here it is for anyone who wants to see the details,and nice use of graphics to show correspondences.Solution 3: Question 1. Long, careful, done without using tables, also a perfectly fineway to do it.Ling 726 Mathematical Linguistics, Index to Homework 9November 5, 2001 p.3Solution 4: Question 2. Almost correct. A few instructors’ annotations inserted. Nicelyillustrated with a picture of the beginning of an infinitely wide truth-table.Solution 5: Question 2. All correct until the very last step; instructors’ annotations addedthere. Done without “tables”; also a perfectly fine way. Some might find tables easier to‘see’ (I do – BHP), though they may be harder work to create.Solution 6: Question 3. Good working out of all the questions about Venn16. With lotsof pictures.Solution 7: Question 3. Good working out of the first three questions about Venn16.Solution 8: Question 4. Correct.Solution 9: Question 5.


View Full Document

UMass Amherst LINGUIST 726 - LINGUIST 726 Homework

Download LINGUIST 726 Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LINGUIST 726 Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LINGUIST 726 Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?