Notation & Countability?

sponsoredwalk

Hi, I'm sorry to ask but I've got a couple of questions about notation and
eventually about the idea of countable sets. These questions are mainly
based off what I've read in Lang's Undergraduate Analysis, it's all in
the first chapter (0) and can be checked here if what I say
is confusing. I'm just repeating some things I know to clarify that they are
in fact correct and asking some questions as I go along, I'm afraid it's
some issue with the notation that may be holding me back from
understanding this idea of counting, along with what I'll mention there.

A mapping f : S → S' is a rule assigning to every x ∈ S a value f(x) ∈ S'.
A subset A of S is denoted A ⊆ S.
If A ⊆ S and S ⊆ A then A = S.
If A ⊆ S and S ⊆\ A (i.e. A is a subset of S but there are other elements in S
that are not in A) then A ≠ S but A ⊂ S, (A is a proper subset of S).
The collection of all subsets of a given set S is the Power set of S,
denoted P(S).
If S : {1,2}
P(S):{∅,{1},{2},{1,2}}
This exemplifies the idea of cardinality, i.e. if the cardinality of a set
S is n, the cardinality of the power set is 2ⁿ.

Here is where I have some issues.
If f(x) is the value assigned to x by the mapping f : S → S',
the set of all elements f(x) ∈ S' assigned to all x ∈ S is
the image of f. The image is the set of all possible values allowed
by the mapping f. My book doesn't say it but would it be correct
to denote the image of f as f(S)?
For example, my book says that if T ⊂ S then the image of T is
denoted f(T). It doesn't say that you can do this for the general
set S but it seems fair.
Also, am I right in thinking that the image of f is a subset of the
codomain(the set of all possible values in S')?
Like, if the function, say x², cannot output certain values in S' then
the set of all possible values (the image) is just the subset of the
codomain.
i.e. if f : R → R is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. and R⁺ ⊂ R (the image is a proper subset of the codomain).
This means we're mapping from the domain set R into the codomain
set R but the function only allows values from the subset of the
codomain.

If the image of a function f is not only a subset of the codomain but is
also equal to the codomain then the mapping is a surjective one,
right?
If f : R → R is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. and R⁺ ⊂ R (the image is just a subset of the codomain).
Here f is not a surjective mapping.
If f : R → R⁺ is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. but so is the codomain. That means this is a surjective
mapping.

If we were to use this notation to find out if we have a bijective mapping,
would it be fair to do so as follows?
f : R → R is the mapping f : x ↦ (x + 2).
f is both surjective and injective as there is never a point when
f(x₁) = f(x₂) when x₁ = x₂. How do I justify this? Because it's
obvious, but I'm thinking induction.
If x = 1, f(1) = (1 + 2) = 3.
If x₁ = n, f(n) = (n + 2)
If x₂ = (n + 1), f(n) = (n + 1 + 2) = (n + 3).
When x₁ ≠ x₂, f(x₁) ≠ f(x₂) & since the derivative of (x + 2) never changes
from positive to negative as x increase we can assume that as the
function will never decrease thereby assuming previously held values.
Probably just being pedantic there but still...
g : R → R is the mapping f : x ↦ (x - 2), obviously this is the
inverse of f, skipping the pedantic stuff if I show that
g o f = f o g = I (the identity function x), f is bijective. Fair?

There's just one more issue I have with regard to notation before the
countability issue, this is from a linear algebra book.
"Let S be any nonempty set & F be any field. Let f(S,F) denote the set of
all functions from S into F".
f(S,F) is then shown to be a vector space, but what I want to ask is
if it's fair to write this according to the notation I've been using above.
f : S → F where S contains functions and F is the set of values
given by those functions. Is that how you understand this?
It seems odd because inside S all the functions still have got to
have some set of values to go through in order to chug out all these
answers, like if f(x) is in S, is x assumed to be in the set S, there is an
intermediate set S → T to give the function, then T → F gives the
value in R. This makes sense if we think about the idea of a composition
of mappings as Lang uses in the opening chapter. But I could totally be
misunderstanding the meaning of f(S,F). There is no other explanation of
f(S,F) than what I've written in quotes above so it's strange...

---

Assuming all of the above is okay, apart from the last thing I wrote,
then we can get on to what I wanted to ask. I had to mention all of
the above to make sure I have it all correct because I really
misunderstand some of these ideas about countable sets.

"We shall say that S is denumerable if there exists a bijection of S
with the positive intergers Z⁺."

This can be written like this: f :Z⁺ → S right?

So, if S : {3,8,7} I can see there are 3 elements, but how do I write this
according to the notation I've been using? Basically the book takes such
an abstract look at this idea & I'm trying to go from the very foundations
of this idea and build up abstraction. Talking about counting infinite
sets and all, like I've seen youtube videos assigning, pictorially, from
the set of positive intergers to the set of all intergers arrows
indicating we can indeed count the set. You can assign
to 1↦1, 2↦-1, 3↦2, 4↦-2, 5↦3, 6↦-3, etc... and count Z but
not only can I not figure the notation out of how to do this,
there are no examples of how to do this with small sets and all of the
examples in the book are talking about surjectivity and bijectivity
with abstract sets and it's confusing.

Finally, for now, when I wrote:

This can be written like this: f :Z⁺ → S right?

I mean, the book speaks as if this is the correct way to write this and
the example of the mapping n ↦ a_n it gives accord with my understanding
but then Lang goes and says:

"If D is a denumerable set, and f : S → D is a bijection of some set S
with D then S is also denumerable. Ineed there is a bijection
g : D → Z⁺, and hence g o f is a bijection of S with Z⁺".

I understand that I could interpret this as him just confirming that
it doesn't matter which direction the countability goes, but maybe not..?

Enkidu

sponsoredwalk wrote: »

The image is the set of all possible values allowed
by the mapping f. My book doesn't say it but would it be correct
to denote the image of f as f(S)?

That would be correct and is infact quite common in many areas, for example
functional analysis and rigorous quantum mechanics, e.t.c.

Also, am I right in thinking that the image of f is a subset of the
codomain(the set of all possible values in S')?

Yes, that is correct.

Like, if the function, say x², cannot output certain values in S' then
the set of all possible values (the image) is just the subset of the
codomain.
i.e. if f : R → R is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. and R⁺ ⊂ R (the image is a proper subset of the codomain).
This means we're mapping from the domain set R into the codomain
set R but the function only allows values from the subset of the
codomain.

Exactly.

If the image of a function f is not only a subset of the codomain but is
also equal to the codomain then the mapping is a surjective one,
right?

Exactly, one could define a surjective function as one where image=codomain.

If f : R → R is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. and R⁺ ⊂ R (the image is just a subset of the codomain).
Here f is not a surjective mapping.
If f : R → R⁺ is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. but so is the codomain. That means this is a surjective
mapping.

Exactly, you have just stumbled upon how the properties of a function can change depending on exactly what you take to be the codomain. This will be important when you come to more advanced topics.

If we were to use this notation to find out if we have a bijective mapping,
would it be fair to do so as follows?
f : R → R is the mapping f : x ↦ (x + 2).
f is both surjective and injective as there is never a point when
f(x₁) = f(x₂) when x₁ = x₂. How do I justify this? Because it's
obvious, but I'm thinking induction.
If x = 1, f(1) = (1 + 2) = 3.
If x₁ = n, f(n) = (n + 2)
If x₂ = (n + 1), f(n) = (n + 1 + 2) = (n + 3).
When x₁ ≠ x₂, f(x₁) ≠ f(x₂) & since the derivative of (x + 2) never changes
from positive to negative as x increase we can assume that as the
function will never decrease thereby assuming previously held values.
Probably just being pedantic there but still...
g : R → R is the mapping f : x ↦ (x - 2), obviously this is the
inverse of f, skipping the pedantic stuff if I show that
g o f = f o g = I (the identity function x), f is bijective. Fair?

Yes and don't worry about being pedantic, it's maths, which at times is applied pedantry.

There's just one more issue I have with regard to notation before the
countability issue, this is from a linear algebra book.
"Let S be any nonempty set & F be any field. Let f(S,F) denote the set of
all functions from S into F".
f(S,F) is then shown to be a vector space, but what I want to ask is
if it's fair to write this according to the notation I've been using above.
f : S → F where S contains functions and F is the set of values
given by those functions. Is that how you understand this?

In this case we're making the codomain a bit special. Instead of being just some set, it is a field. Fields have more properties than sets in general. So we have functions from S -> F, let's call these functions f. f(S,F) is then the space of all these functions.

For example take S = R and F = R. A function from S->F is just a real-valued function on the real line in this case. f(S,F) is then the space of all real valued functions. It's a giant set which contains every function which obey f:S->F. So you can think of it as a space where each "point" is a function f:S->F.

"We shall say that S is denumerable if there exists a bijection of S
with the positive intergers Z⁺."

This can be written like this: f :Z⁺ → S right?

Yes, but also it has to be surjective and one-to-one. f :Z⁺ → S just indicates it is a function from the positive integers to S, not that it has the additional property of bijection. Also to be denumerable/countable there only has to exist a bijection with a subset of Z⁺, see below.

So, if S : {3,8,7} I can see there are 3 elements, but how do I write this
according to the notation I've been using? Basically the book takes such
an abstract look at this idea & I'm trying to go from the very foundations
of this idea and build up abstraction. Talking about counting infinite
sets and all, like I've seen youtube videos assigning, pictorially, from
the set of positive intergers to the set of all intergers arrows
indicating we can indeed count the set. You can assign
to 1↦1, 2↦-1, 3↦2, 4↦-2, 5↦3, 6↦-3, etc... and count Z but
not only can I not figure the notation out of how to do this,
there are no examples of how to do this with small sets and all of the
examples in the book are talking about surjectivity and bijectivity
with abstract sets and it's confusing.

In truth the notation is really only for the abstract case. For your example above one might write something like this:
S={3,7,8}, is a set. I say this is countable because there exists a bijection with the subset of Z⁺, which I'll call A, where A = {1,2,3}

The bijection is:
f(1) = 3
f(2) = 7
f(3) = 8

This has completely specified a map f:A -> S. It is surjective as all of S is covered and one-to-one since each member of S is only mapped to once. Hence S is countable.

The rest of your post dealing with the set D is only to show that if one set S is countable and it has a bijection with a set D, then D is countable.

Think of it this way, sets can only have bijections between them if they are "the same size". Anything the "same size" as Z⁺ or a subset of it is called countable. Then the with D is basically saying "If D is the same size as S and S is the same size as Z⁺, then D is the same size as Z⁺ and hence is countable."

Fremen

sponsoredwalk wrote: »

Here is where I have some issues.
If f(x) is the value assigned to x by the mapping f : S → S',
the set of all elements f(x) ∈ S' assigned to all x ∈ S is
the image of f. The image is the set of all possible values allowed
by the mapping f. My book doesn't say it but would it be correct
to denote the image of f as f(S)?

That seems reasonable to me, yes. Im(f) is probably more standard, but the notation f(S) is consistent with the f(T) notation.

Also, am I right in thinking that the image of f is a subset of the
codomain(the set of all possible values in S')?
Like, if the function, say x², cannot output certain values in S' then
the set of all possible values (the image) is just the subset of the
codomain.
i.e. if f : R → R is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. and R⁺ ⊂ R (the image is a proper subset of the codomain).
This means we're mapping from the domain set R into the codomain
set R but the function only allows values from the subset of the
codomain.

Yup, that's right. If I've understood you correctly, the two functions in the pictures on the right in this link are examples of what you're talking about:
http://en.wikipedia.org/wiki/Bijection,_injection_and_surjection

If the image of a function f is not only a subset of the codomain but is
also equal to the codomain then the mapping is a surjective one,
right?
If f : R → R is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. and R⁺ ⊂ R (the image is just a subset of the codomain).
Here f is not a surjective mapping.
If f : R → R⁺ is the mapping f : x ↦x², the image of f is R⁺,
i.e. all x ≥ 0. but so is the codomain. That means this is a surjective
mapping.

Yeah, that's right. I still use mental pictures like the ones in the wikipedia page to deal with these concepts.

If we were to use this notation to find out if we have a bijective mapping,
would it be fair to do so as follows?
f : R → R is the mapping f : x ↦ (x + 2).
f is both surjective and injective as there is never a point when
f(x₁) = f(x₂) when x₁ = x₂. How do I justify this? Because it's
obvious, but I'm thinking induction.
If x = 1, f(1) = (1 + 2) = 3.
If x₁ = n, f(n) = (n + 2)
If x₂ = (n + 1), f(n) = (n + 1 + 2) = (n + 3).
When x₁ ≠ x₂, f(x₁) ≠ f(x₂) & since the derivative of (x + 2) never changes
from positive to negative as x increase we can assume that as the
function will never decrease thereby assuming previously held values.
Probably just being pedantic there but still...
g : R → R is the mapping f : x ↦ (x - 2), obviously this is the
inverse of f, skipping the pedantic stuff if I show that
g o f = f o g = I (the identity function x), f is bijective. Fair?

I'm not sure I follow this. What's your definition (or Lang's ) of bijection? Mine is a that a bijective function is one which is surjective and injective.

As a rule, you don't want to deal with induction when you're working with real numbers - this is because of the uncountability of the reals as we'll see. The ussual strategy would be to show that Im(f) = R, (which is fairly straightforward), followed by showing that x+2 = y+2 implies x=y. If you want to strip that right down to the axioms of real numbers, you might have to work a little bit, but otherwise it's pretty easy

There's just one more issue I have with regard to notation before the
countability issue, this is from a linear algebra book.
"Let S be any nonempty set & F be any field. Let f(S,F) denote the set of
all functions from S into F".
f(S,F) is then shown to be a vector space, but what I want to ask is
if it's fair to write this according to the notation I've been using above.
f : S → F where S contains functions and F is the set of values
given by those functions. Is that how you understand this?

Hm, you're "overloading" the notation f here. in the definition above, f(S,F) is not a function, it's a set. Draw a diagram like the ones in the wikipedia page I linked to. S is the set on the left, F is the set on the right, and an element v in f(S,F) is a function - a collection of "arrows" which tell you what element of F each element of S gets mapped into. The set of all collections of arrows is f(S,F).

In summary, the typical set-up is v(a) = b, where a is in S, b is in F, and v is in f(S,F).

"We shall say that S is denumerable if there exists a bijection of S
with the positive intergers Z⁺."

This can be written like this: f :Z⁺ → S right?

So, if S : {3,8,7} I can see there are 3 elements, but how do I write this
according to the notation I've been using?

Does he make a distinction between finite and denumerable? I don't agree with the definition otherwise. There is no bijection between Z⁺ and {3,8,7}, but there is a surjection: the function

f(1) = 3
f(2) = 8
f(n) = 7 for n>= 3,

among many others.
Maybe he says denumerable he means infinite but bijective with Z⁺? (for example, the even numbers via the bijection n -> 2n

Basically the book takes such
an abstract look at this idea & I'm trying to go from the very foundations
of this idea and build up abstraction. Talking about counting infinite
sets and all, like I've seen youtube videos assigning, pictorially, from
the set of positive intergers to the set of all intergers arrows
indicating we can indeed count the set. You can assign
to 1↦1, 2↦-1, 3↦2, 4↦-2, 5↦3, 6↦-3, etc... and count Z but
not only can I not figure the notation out of how to do this,
there are no examples of how to do this with small sets and all of the
examples in the book are talking about surjectivity and bijectivity
with abstract sets and it's confusing.

f(n) = (n+1)/2 if n is odd
f(n) = -n/2 if n is even

describes the pattern you wrote down. Now it's a matter of proving it's surjective and injective
With "small" sets, you usually just write down the values of f one by one, unless there's an obvious pattern.

Finally, for now, when I wrote:

This can be written like this: f :Z⁺ → S right?

I mean, the book speaks as if this is the correct way to write this and
the example of the mapping n ↦ a_n it gives accord with my understanding
but then Lang goes and says:

"If D is a denumerable set, and f : S → D is a bijection of some set S
with D then S is also denumerable. Ineed there is a bijection
g : D → Z⁺, and hence g o f is a bijection of S with Z⁺".

I understand that I could interpret this as him just confirming that
it doesn't matter which direction the countability goes, but maybe not..?

Perhaps the issue here is that if f is a bijection, then f inverse is also a bijection?

I hope this clears some stuff up, but I'm sure you'll still have questions. Feel free to post back and I'll see if I can help out some more.

sponsoredwalk

Thanks a million to both of you for clearing that stuff up, I'm going to mull
some of it over for a day or two and try to get to that part of the
other book I'm reading on analysis to see if I get the section
on countability. I've got some more questions for sure, specifically about
the diagonalization argument which I very hazily understand and some tidbits
but it can wait until I've got this stuff down first.

As for Lang's definitions, well a bijection is an injection and a surjection
and a denumerable set is that which has a bijection with the positive
intergers. Just thinking about it now as you mentioned it, doesn't that
mean that every countable set is defined as infinite? :eek: I mean
he doesn't say it can be a subset of Z⁺, he just says Z⁺. Check the
book in the link in my original post if it's a strange claim, it's section 4 of
chapter 0.

If it's not really infinite sets only that are countable (infinite sets are countable?)
then is S : {3,7,8}, f :Z⁺ → S is a bijection from which we can
count, A:{1,2,3} is the result of counting this, and g : A → S is
like a "counting" map. It's a good example of what I expected, thanks

As for counting the integers, f :Z⁺ → Z is the mapping, like a
piecewise function, assigning n ∈ Z⁺ to n ∈ Z by the rule
n ↦ (n+1)/2 If n is even
n ↦ -(n/2) If n is odd.
This is certainly good too.

I've just got to ask, what good is counting a set? I think the fact Lang
gives no mundane examples hints at the fact the that idea is basically
about infinities, like infinities in the unit interval.

I've got another question I've been dying to ask , I got this little
book Numbers: Rational & Irrational expecting it to be a rigourous
development of all of the number systems with theorems etc... and there
are, so far, only 2, fundamental theorem of arithmetic and that there are
infinite primes, it's good but really non-rigorous, in the book they refer to
some other book in the series that will do this (doesn't exist) & I'm looking
for a good one. As far as I know, analysis deals in the real number system,
and only some books toy with these ideas. The contents of this book go
pretty close to what I'm looking for, but there are no solutions, I wonder
do you guys have any suggestions for this? The more the merrier!

Fremen

I've just got to ask, what good is counting a set? I think the fact Lang
gives no mundane examples hints at the fact the that idea is basically
about infinities, like infinities in the unit interval.

You can prove that the real numbers are uncountable. That means the plane RxR is uncountable too. Power sets of uncountable sets are freaky. You can show that you can't assign a sensible area to every subset the plane - the Vitali construction shows how to decompose the unit disc into two disjoint subsets both of which have the same area as the unit disc.

A real number can be approximated arbitrarily well by a rational number, and it turns out the rational numbers are countable (don't worry about that just yet, it's not obvious). The rationals form a countable dense subset of the reals.
Sets with countable dense subsets are nice to deal with. In order to prove something about the whole set, sometimes it's enough to prove it for the countable dense set, then take a limit.

Lang's is a weird definition of denumerable. The standard one I've seen is that there's a surjection from the positive natural numbers onto a set S. This means that S is "not bigger" than the natural numbers, where as a bijection means S is "the same size" as the naturals.

I'm not really sure where you'd find a nice book on the construction of the reals. I'll keep my eyes open though.

equivariant

Fremen wrote: »

the Vitali construction shows how to decompose the unit disc into two disjoint subsets both of which have the same area as the unit disc.

Is this right? By area, do you mean Lebesgue measure? This violates the additivity of the measure?

Fremen

Yeah, I meant lebesgue measure. The construction is actually on the unit disc without the origin. It implicitly uses the axiom of choice. As far as I know, without the AC, all subsets of R^2 are measurable and you don't run into these problems. You can read about it here (page 684). It's related to the banach-tarski paradox.

equivariant

Fremen wrote: »

Yeah, I meant lebesgue measure. The construction is actually on the unit disc without the origin. It implicitly uses the axiom of choice. As far as I know, without the AC, all subsets of R^2 are measurable and you don't run into these problems. You can read about it here (page 684). It's related to the banach-tarski paradox.

It seems that it is a 2D version of the Banach-Tarski. I still don't see that the Vitali construction it does what was claimed in the earlier post. If you can decompose the unit disc into 2 disjoint measurable sets, both of measure equal to the unit disc then, as far as I can see, this violates the additivity of the measure which is independent of anything to do with the axiom of choice. Maybe I am missing something? Perhaps I misinterpreted your earlier post.

Enkidu

equivariant wrote: »

It seems that it is a 2D version of the Banach-Tarski. I still don't see that the Vitali construction it does what was claimed in the earlier post. If you can decompose the unit disc into 2 disjoint measurable sets, both of measure equal to the unit disc then, as far as I can see, this violates the additivity of the measure which is independent of anything to do with the axiom of choice. Maybe I am missing something? Perhaps I misinterpreted your earlier post.

In most presentations, the sets after the construction are disjoint sets whose union is not the original set, hence they do not break additivity of the measure. Essentially you start with the original set, break it up into unmeasurable sets and then reassemble those sets into to disjoint clones of the original one.

Fremen

I glossed over the measurability aspect a little. Looking at it now, I'm not sure I totally understand it myself. I had assumed the sets E and E_n in the link I gave were non-measurable, but I have no idea how you'd show that.

At any rate, the point I was trying to get across was that subsets of uncountable sets do strange things, whereas subsets of countable sets tend to be more well-behaved.