Free Republic
Browse · Search
General/Chat
Topics · Post Article

To: grey_whiskers
Sure. It means both 1-1 and onto. 1-1 means x ≠ y ⇒ f(x) ≠ f(y) -- geometrically, this means it "passes the horizontal line test: exactly one point of intersection for any horizontal line." Onto means every f(x) in the image has some x in the pre-image. [all points of f(x) are mapped from somewhere.]

So the upshot is that a 1-1+onto or bijective function has a unique inverse.

Thus this is a way of extending the ordinary notion of counting elements to infinite sets. When we count finite collections, we are putting them into 1-1 correspondence with a subset of the integers. To extend that notion to infinite sets, two sets have the same cardinality or "size" if there is a bijection between them.

The cardinality of the even integers is the same as the cardinality of the integers. Why? Here is a bijection f(N) = 2N.

Every non-empty open subinterval of the real line, no matter how small, has the same cardinality as the whole real line. Why? Here is a bijection: f(x) = arctan(αx); with "α" some suitable scaling factor that maps the arbitrary interval into (-π/2, π/2).

To prove the reals do not have the same cardinality as the integers, produce an enumeration of the reals, then show there is always a real number it doesn't contain. That's Cantor's Diagonalization Theorem.

Here's another way, more abstract but actually less difficult. Define the powerset of a set to be the set of all subsets of a set. So the powerset of {1, 2} is the set {{1}, {2}, {1, 2}, {}} [It's called the powerset because if a finite set has "S" elements, the set of all its subsets has 2S elements.]

Show that there is no bijection between any set and its powerset. Cantor did this already. It's the so-called "who shaves the barber" proof. Then show that there is a bijection between the reals and the powerset of the integers. Since there's a bijection between the reals and the powerset of the integers, there can't be one between the reals and the integers themselves.

In this extended sense [that there is no bijection] there are "more" reals than there are integers.

86 posted on 02/20/2015 11:16:41 PM PST by FredZarguna (Mit der Dummheit kämpfen Götter selbst vergebens.)
[ Post Reply | Private Reply | To 83 | View Replies ]


To: FredZarguna; grey_whiskers
Sorry. The bijection is either f(x) = αArctan(x) or f(x) = tan(αx), depending on which way you're going: from (-∞, +∞) to a finite subinterval, or from a finite subinterval to (-∞, +∞). That's what I get for shooting from the hip.
87 posted on 02/20/2015 11:37:36 PM PST by FredZarguna (Mit der Dummheit kämpfen Götter selbst vergebens.)
[ Post Reply | Private Reply | To 86 | View Replies ]

Free Republic
Browse · Search
General/Chat
Topics · Post Article


FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson