Skip to main content
Log In | Register

TR Memescape


Topic: less-than-uncool preschool (Read 1762 times) previous topic - next topic

0 Members and 1 Guest are viewing this topic.
  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #150
We have used ℕ as the quintessentially denumerable set.  What about some of our apparently bigger sets of numbers?

Consider ℤ, the set of integers.  We can easily find a bijection f : ℕ → ℤ defined by
f(1) = 0;
f(2n) = n for every n ∈ ℕ;
f(2n + 1) = -n for every n ∈ ℕ.
So ℤ is denumerable.

Perhaps it's easier to see what's going on here if we simply make a list of the numbers f(1), f(2), etc.:
0, 1, -1, 2, -2, 3, -3, ....

More generally, all we need in order to show that an infinite set is denumerable is a scheme for listing the elements of that set, in a sequence, such that every element of the set is guaranteed to appear somewhere in the list exactly once.

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #151
It's pretty easy to show that a union of a finite number of countable sets is countable.

But let's consider Cartesian products.

If A and B are both finite sets, then the Cartesian product A × B is also finite.
In particular, if A ∼ {k ∈ ℕ | km} and B ∼ {k ∈ ℕ | kn}, then A × B ∼ {k ∈ ℕ | kmn}.  That's pretty easy to show.

If A is finite and B is denumerable, or vice-versa, then A × B is denumerable.  That's pretty easy too.

What's more interesting is that if A and B are both denumerable, then again A × B is denumerable.

Let the elements of A be listed as a1, a2, a3, etc.
Let the elements of B be listed as b1, b2, b3, etc.
Then consider the following arrangement of ordered pairs:
(a1, b1), (a2, b1), (a3, b1), ...
(a1, b2), (a2, b2), (a3, b2), ...
(a1, b3), (a2, b3), (a3, b3), ...
  ⋮        ⋮          ⋮      ⋱
We can list these ordered pairs by starting from the upper-left corner, then making a bunch of diagonal stripes from upper right to lower left, with each stripe getting successively further away from the starting corner.  Thus, we get the pairs arranged in the following order:
(a1, b1), (a2, b1), (a1, b2), (a3, b1), (a2, b2), (a1, b3), (a4, b1), (a3, b2), (a2, b3), (a1, b4), ....

So A × B is denumerable.

More generally, a Cartesian product of a finite number of countable sets is countable, as can be shown by induction.

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #152
We know already that any rational number can be expressed as a/b, where a ∈ ℤ and b ∈ ℕ.  Of all the ways to express a rational number, there is one "reduced form", where the denominator is as small as possible.

Let q : ℚ → ℤ × ℕ be defined by q(r) = (k, n) where r = k/n and n is the smallest natural number that can be used as the denominator in expressing r.

Then q is an injection into ℤ × ℕ.  It maps ℚ onto some subset q(ℚ) ⊂ ℤ × ℕ.  So ℚ ∼ q(ℚ).  And q(ℚ), being a subset of a countable set, is countable.  So ℚ is countable.  But of course ℚ is infinite, so it is denumerable.

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #153
What about ℝ?

Before we handle that, here's an important lemma known as the "nested interval principle".

Let {In | n ∈ ℕ} be a set of closed intervals having the properties that
(1) In+1In for all n ∈ ℕ;
(2) For any x ∈ ℝ such that x > 0, there is n ∈ ℕ such that the length of In is less than x.
Then k = 1Ik is a singleton.

Proof:  Say In = [an, bn].
From assumption (1), we have akanbnbk whenever kn (with k, n ∈ ℕ).
Let A = {an | n ∈ ℕ} and let B = {bn | n ∈ ℕ}.
Then each element of A is less than or equal to each element of B.
So A is bounded above, and B is bounded below.
Let a = sup A, and let b = inf B.
We have abn for every n ∈ ℕ, and ban for every n ∈ ℕ.
So ab.
Also aIn and bIn for every n ∈ ℕ.
Therefore k = 1Ik ≠ ∅.
Suppose that this intersection contains two distinct numbers, y and z, with y < z.
Then take x ∈ ℝ such that 0 < x < z - y.
From assumption (2), we have an interval In whose length is less than z - y.  So that interval cannot include both y and z.
This is a contradiction, and we got there by supposing that the intersection of the intervals contains two distinct numbers.  Therefore that intersection is the singleton {a} = {b}.
Done.
  • Last Edit: July 25, 2016, 11:52:10 AM by Brother Daniel

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #154
Now we're in a position to show that ℝ is uncountable.

It suffices to show that the closed interval [a, b] is uncountable, whenever we have a, b ∈ ℝ such that a < b.

Proof (that that closed interval is uncountable):
Consider the function f : ℕ → [a, b] defined by f(n) = a + (b - a)/n.
f is an injection, so it could be expressed as a bijection onto a subset of the interval.
Therefore the interval has an infinite subset, so the interval is itself infinite.
Now let g : ℕ → [a, b] be an injection.
Let's chop the interval into three closed intervals of equal length:  [a, a + (b - a)/3], [a + (b - a)/3, b - (b - a)/3], [b - (b - a)/3, b].
Choose one of those three intervals, calling it I1, such that g(1) ∉ I1.
For each n ∈ ℕ, after In has been chosen, divide that interval into three closed intervals of equal length, and choose one of them, calling it In+1, such that g(n + 1) ∉ In+1.
The set of intervals {In | n ∈ ℕ} fulfills the hypotheses of the nested interval principle (see the previous post).
(It can easily be shown by induction that the length of In is less than (b - a)/n.)
Therefore k = 1Ik = {z} for some z ∈ ℝ.
But for every n ∈ ℕ, we have zIn and g(n) ∉ In, so zg(n).
So z ∈ [a, b], but z ∉ {g(n) | n ∈ ℕ}.
Therefore, [a, b] ⊃ {g(n) | n ∈ ℕ}.  So g is not a surjection.
But g was an arbitrary injection.  So no bijection exists from ℕ onto [a, b].
So that interval is neither finite nor denumerable.  Therefore it is uncountable.  Done.

Note that this is a pretty typical way to show that a set is uncountable:  Take an arbitrary injection from ℕ into the set in question, and find a number that is in the set but is not in the range of the function, thus proving that the function is not a surjection.

Anyway, we have the results that ℚ is countable but ℝ is uncountable.  It follows that ℝ \ ℚ is uncountable.

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #155
Let X be a set.

Let ℙ(X) denote the set of all subsets of X.  (This is called the "power set" of X.)

Let f : X → ℙ(X).
So for any xX, we have f(x) ⊆ X.

Furthermore, let f be an injection.
(We know that such injections exist, because we could always take f(x) = {x}, for example.)

Consider the set E = {xX | xf(x)}.
Clearly EX, so E ∈ ℙ(X).

Suppose that f(u) = E for some uX.

Is u an element of E?  If it is, then it isn't; and if it isn't, then it is.
We have a contradiction.  And we got there by supposing that f(u) = E for some u.
Therefore there is no element of X that maps to E.
So f is not a surjection.

But f was an arbitrary injection.  So no bijection exists from X onto ℙ(X).


[edited to fix the power set symbol.  I had originally picked a fancy script "P", but it's invisible to some computers, so I'm going with this "ℙ" instead.]
  • Last Edit: July 26, 2016, 05:27:49 AM by Brother Daniel

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #156
We've defined the "same cardinality" equivalence relation in terms of the existence of a bijection from one set onto another set.

Let's consider a different relation:  If an injection exists from A into B, let's say that the cardinality of A is equal to or less than the cardinality of B.  Or in other words, that A is the same size as B or smaller.

This relation is reflexive and transitive, but not symmetric.

Or, for yet another different relation:  If an injection exists from A into B but no bijection exists from A onto B, let's say that the cardinality of A is less than the cardinality of B.  Or in other words, that A is smaller than B.

This relation is transitive, but neither reflexive nor symmetric.

This way of speaking of the size of sets certainly makes sense in the case where A and B are both finite.  Suppose that A ∼ {k ∈ ℕ | km} and B ∼ {k ∈ ℕ | kn}.  If m < n then there exists an injection from A into B but no bijection from A onto B, and no injection from B into A.  And if m = n then of course we have bijections in both directions.

(And of course the empty set does not break this pattern.  An "empty function" whose domain is the empty set is an injection into any other set at all, but no other injection into the empty set is possible.)

If A is finite and B is infinite, then again an injection from A into B exists, but no injection exists the other way around.

What if both A and B are infinite?  Does this "smaller" description still make sense?

What we'd like to have is some assurance that if an injection exists from A into B, and an injection also exists from B into A, then a bijection exists from A onto B.  If we have that, then we're most of the way to being able to arrange the possible cardinalities of sets into a hierarchy.

We'd be able to say (for example), based on the result of the previous post, that ℕ is smaller than ℙ(ℕ), which is smaller than ℙ(ℙ(ℕ)), which is smaller than ℙ(ℙ(ℙ(ℕ))), and so on.

If we don't have this result, then we'd be faced with the possibility of having A smaller than B and B smaller than A simultaneously.  And that would mean that our "smaller" terminology is inappropriate.

Fortunately, we do have it.  It's called the Cantor-Bernstein-Schröder theorem.  And it's the subject of my next post.


[edited to fix "ℙ"]
  • Last Edit: July 26, 2016, 05:30:59 AM by Brother Daniel

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #157
If an injection exists from A into B, and an injection also exists from B into A, then a bijection exists from A onto B.

Proof (stolen from here):
Let f be an injection from A into B, and let g be an injection from B into A.
We want to find a bijection h from A onto B.
If f is a bijection, let h = f, and we're done.
Else, if g is a bijection, let h = g-1, and we're done.
Otherwise, we proceed as follows.
Let X0 = A \ g(B).
For each n ∈ ℕ, let Xn = g(f(Xn-1)).
Let X = n = 0Xn.
So XA.
Let Y = A \ X.
Note that A \ g(B) ⊆ X, so Yg(B).
Let h : AB be defined as h(x) = f(x) if xX, and h(x) = g-1(x) if xY.
(The latter case makes sense because Yg(B).)
We need to show that h is both an injection and a surjection.
Suppose that h(x) = h(y) for some x, yA.
Suppose further that xX and yY.
Then we have f(x) = g-1(y).
So g(f(x)) = y.
But this is impossible, because xXn for some n ∈ ℕ, so it would mean that yXn+1, so yX.
So (under the assumption that h(x) = h(y)) we cannot have xX and yY.
Similarly, we cannot have xY and yX.
So we must either have x, yX or x, yY.
In the former case we have f(x) = f(y), which means that x = y because f is an injection.
In the latter case we have g-1(x) = g-1(y), which again tells us that x = y.
Therefore h is an injection.
Now let zB.  We want to find xA such that h(x) = z.
Note that g(z) ∈ A, so either g(z) ∈ X or g(z) ∈ Y.
If g(z) ∈ Y, then h(g(z)) = g-1(g(z)) = z, so let x = g(z), and we have h(x) = z.
If g(z) ∈ X, then we have g(z) ∈ Xn for some n > 0, because we can't have g(z) ∈ X0.
But this means that g(z) = g(f(y)) for some yX.
Since g is an injection, we can say that z = f(y) for some yX.
But then we can let x = y, and we have h(x) = f(x) = z.
Therefore h is a surjection.
Since it's both a surjection and an injection, it's a bijection.  Done.


[edited later:  A big chunk disappeared when it was first posted.  Weird.]
  • Last Edit: July 25, 2016, 12:00:54 PM by Brother Daniel

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #158
Given two sets A and B, are their cardinalities always comparable?  That is:  Does there always exist either an injection from A into B or an injection from B into A?

Intuitively, it seems to me that such an injection (in one direction or the other) should always exist, but I don't have a proof.  I think I read somewhere that it depends on the Axiom of Choice:  Such an injection (in one direction or the other) exists if you take the AoC as true.

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #159
Let A be a set.  Then the notation |A| is often used for the cardinality of the set.  (Yes, this is the same notation that is used for the absolute value of a number.)

So the statement AB (using the equivalence relation that I've been talking about for the last several posts) can be written equivalently as |A| = |B|.

So |A| = |B| if and only if there exists a bijection from A onto B.

And |A| ≤ |B| if and only if there exists an injection from A into B.

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #160
The set of all possible cardinalities can be thought of as another number system, the cardinal numbers.

|∅| = 0.

|{x ∈ ℕ | xn}| = n.

|ℕ| = ℵ0 = ℶ0.  This is the smallest infinite cardinality, greater than any n ∈ ℕ, but less than any other infinite cardinality.

"ℵ" is "alef" (or "aleph") and "ℶ" is "bet" (or "beth"), the first two letters of the Hebrew alphabet.  Both of these letters are used (with subscripts) to describe infinite cardinalities.

I don't really understand how the aleph-numbers are defined, but I'm told that
0 < ℵ1 < ℵ2 < ...
and that no cardinalities exist between two successive aleph-numbers.

Assuming that cardinalities are always comparable (see two posts ago), every infinite set has an aleph-number for its cardinality.

As for the beth-numbers, they're easier to understand:
0 = |ℕ| as already stated;
1 = |ℙ(ℕ)|;
2 = |ℙ(ℙ(ℕ))|;
3 = |ℙ(ℙ(ℙ(ℕ)))|;
...and so on.

So ℶ0 < ℶ1 < ℶ2 < ...

Don't ask me about aleph-numbers or beth-numbers with subscripts that go beyond ℕ.  I have no idea about that stuff.


[edited to fix "ℙ".]
  • Last Edit: July 26, 2016, 05:33:02 AM by Brother Daniel

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #161
Does there exist a set whose cardinality lies between ℶ0 and ℶ1?

The "continuum hypothesis" says that there is no such thing, i.e. that ℶ1 = ℵ1.

But it turns out (or so I'm told) that the continuum hypothesis can't be proved or disproved within any of the sets of axioms that mathematicians generally use.  You can take it or leave it, and it makes no difference to most of mathematics.

The reason it's called the "continuum hypothesis" is that the set of real numbers, ℝ, aka "the continuum", has a cardinality of ℶ1.  I'll show this in the next post.

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #162
ℝ ∼ ℙ(ℕ).  (Remember, ℙ(ℕ) means the set of all subsets of ℕ.)

Proof:
We need only find an injection from ℝ into ℙ(ℕ), and another injection from ℙ(ℕ) into ℝ.  Then we can invoke the Cantor-Bernstein-Schröder theorem.
Let q : ℚ → ℕ be a bijection.  We know that such a thing exists because ℚ is denumerable.
Let c : ℝ → ℙ(ℚ) be defined as c(x) = {z ∈ ℚ | z > x}.
Clearly, c is an injection.
Therefore, we can define f : ℝ → ℙ(ℕ) as f(x) = {q(z) | zc(x)}, and this is also an injection.
To go in the other direction, we define g : ℙ(ℕ) → ℝ as follows.
Let X ∈ ℙ(ℕ).  We find the real number g(X) by the following algorithm.
Let I0 = [0, 1].
For each n ∈ ℕ, once In-1 is specified, let that interval be sliced into three intervals of equal length.
That is, if In-1 = [a, b], then consider the three intervals
[a, a + (b - a)/3], [a + (b - a)/3, b - (b - a)/3], and [b - (b - a)/3, b].
If nX, then let In be the third of those three intervals; and if nX, then let In be the first of those three intervals.
The set of intervals {In | n ∈ ℕ} conforms to the hypotheses of the nested interval principle.
So there is exactly one real number in the intersection of all of those intervals.
Let g(X) be equal to the number found thereby.
Notice that whenever a choice of interval is made, based on whether a given number is or is not an element of X, the two intervals in question are non-intersecting.
So for any two sets X, Y ∈ ℙ(ℕ), if XY then there is a smallest natural number m ∈ (X \ Y) ⋃ (Y \ X).
So the interval chosen at the mth step in the algorithm to find g(X), and the interval chosen at the mth step in the algorithm to find g(Y), have no numbers in common.
So if XY then g(X) ≠ g(Y).  So g is an injection.
Done.

So |ℝ| = ℶ1.  (Remember, we defined ℶ1 as the cardinality of ℙ(ℕ).)


[edited to fix "ℙ".]
  • Last Edit: July 26, 2016, 05:36:05 AM by Brother Daniel

  • Brother Daniel
  • Global Moderator
  • predisposed to antagonism
  • 637

  • 181

Re: less-than-uncool preschool
Reply #163
The "fancy P" character I used for "power set" is invisible on my tablet screen.  I need to find a different fancy P, and edit it in.


[eta:  done]
  • Last Edit: July 26, 2016, 06:19:37 PM by Brother Daniel