Unformatted text preview:

Ling 726: Mathematical Linguistics, Lecture 16 Infinities V. Borschev and B. Partee, November 22, 2004 p. 1 Lecture 16: Infinities 4.1 Equivalent sets and cardinality ............................................................................................................ 1 4.2. Denumerable sets................................................................................................................................ 2 4.3. Nondenumerable sets......................................................................................................................... 3 4.4. Infinite vs. unbounded. ....................................................................................................................... 4 Appendix (separate handout): On the cardinality of natural languages.......................................................... 4 Optional Homework. ...................................................................................................................................... 5 Reading: Chapter 4: “Infinities” of PtMW, pp. 55-73 4.1 Equivalent sets and cardinality The problem: What does “the same size” mean if we want to talk about infinite sets as well as finite sets? The solution: We generalize the notion of ‘number’ to the notion of ‘cardinality’, and we start by defining what it is for two sets to have the same cardinality. Definition: Two sets A and B have the same cardinality iff there is a 1-1 correspondence between them. Review: what does 1-1 correspondence mean? For finite sets, “has the same cardinality as” is an equivalence relation that groups sets according to how many members they have. To each equivalence class we can assign a number, called the cardinal number, or cardinality, indicating the size of each set in the class. The cardinality of a finite set is always a natural number. Suppose A = {a,b,c,d}. Then |A| = 4. For infinite sets, let’s start looking at examples. I won’t try to put all of this in the notes – a lot of it works better at the blackboard. Example 1: The set P of positive integers, and the set E of even positive integers. • Can we find a 1-1 correspondence? • If so, same cardinality! How shall we define infinite? There is more than one way, but here is one (a surprising one): Definition: A set is infinite if it can be put in a 1-1 correspondence with a subset of itself. Example 2: Show that the set N of natural numbers is infinite. Example 3: Consider the set A* of all finite strings of letters on an alphabet A = {a,b}. We include the “empty string”, which is conventionally called e. A* = {e, a, b, aa, ab, ba, bb, aaa, ... } -- Show that A* is infinite. Strategy: consider the subset of all strings that start with b.Ling 726: Mathematical Linguistics, Lecture 16 Infinities V. Borschev and B. Partee, November 22, 2004 p. 2 Caution: We have certainly not claimed that an infinite set can be put in correspondence with every subset of itself. That’s not true – it will never be true for any finite subset, for instance. What is true is that for any infinite set there always exists at least one subset of itself with which it can be put in 1-1 correspondence. 4.2. Denumerable sets We can associate with each finite set a natural number which represents its cardinality. Sets with the same cardinality form an equivalence class. Infinite sets can also be grouped into equivalence classes, such that all the sets in a given equivalence class have the same cardinality. (If it turned out that all infinite sets had the same cardinality, there would be just one equivalence class for all the infinite sets; but it doesn’t.) We use special symbols which are not natural numbers to denote the cardinalities of infinite sets. The most familiar infinite set is probably the set N of natural numbers {0, 1, 2, 3 ... }. The name that has been given to the cardinality of this set and all sets equivalent to it is the first letter of the Hebrew alphabet subscripted with a zero: ℵ0 (“aleph-null”). ℵ0 is not a natural number; it is a cardinal number which is larger than any natural number. If we ask “How many natural numbers are there?”, the answer is ℵ0 . Definition: A set is denumerably infinite (also called denumerable, or countably infinite), if it has cardinality ℵ0 , i.e., if it can be put in 1-1 correspondence with the set of natural numbers. A set is called countable if it is either finite or denumerably infinite. More examples of denumerably infinite sets. (We already have: N, the set of natural numbers. E, the set of even positive integers.) • Z, the set of integers, including positive, negative, and zero. (See 1-1 correspondence, p. 59) • (4-4), p. 60: the set of reciprocals of the natural numbers without zero: {½, 1/3, ¼, 1/5, 1/6, ... } • (4-5) The set of odd positive integers. • The set of rational numbers. Let’s do this one on the blackboard. This one is really surprising, because the rational numbers are “dense”. (Remember what that means?) So shouldn’t that be a “bigger” infinite set if anything is? Surprisingly, it’s not. • General strategy: To show that a set is denumerably infinite, find a way to put it into a 1-1 correspondence with the natural numbers. This is called effectively listing the members of the set, since the natural numbers themselves are thought of as forming an infinite “list”. • A “language” like that of exercise 4 on p. 71.Ling 726: Mathematical Linguistics, Lecture 16 Infinities V. Borschev and B. Partee, November 22, 2004 p. 3 4.3. Nondenumerable sets. We have seen quite a few examples of denumerably infinite sets, and we could come up with many more. (Infinitely many more, of course. “The set of all natural numbers larger than 2”, “... larger than 3”, “... larger than 4”, etc., just for starters.) It was Georg Cantor (1845-1918), one of the main developers of set theory, who proved that the power set of any set A always has a larger cardinality than the set A itself, and therefore that there are infinitely many different infinite cardinalities. We won’t try to go “up the ladder” of cardinalities (life becomes very complicated among the higher infinite cardinalities), but we will look at some sets that are larger than the set of natural numbers, and we’ll learn some ways of proving that a given set is non-denumerable. Cantor’s theorem:


View Full Document

UMass Amherst LINGUIST 726 - Infinities

Download Infinities
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 Infinities 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 Infinities 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?