One or two more pieces of information.

We're going to, in order to simplify the
proof, we're not going to prove initially,

it does prove it as a corollary,
but we're not going to immediately prove

that all, the set of all real numbers is
countable.

We're going to show that a subset of the
real numbers is countable.

And if that smaller set is countable and
certainly is uncountable, rather.

So you can't count the
smaller set, so you certainly

can't count the bigger set,
which also contains them.

So we're going to
concentrate on the real

numbers between zero
and one, not including one.

The reason we're going to
do this is because the decimal

point, as we mentioned
in the first class, is a pain.

The fact is that the underlying memory
doesn't have a decimal point.

And then you're going to
have to deal with a simulation

of interpretation of how
to represent real numbers.

A conversation that's interesting,
but not really relevant to this class.

In architecture and hardware, et cetera,
they discuss that more.

But anyway, so we're going to deal with
the real numbers between zero and one,

including zero, not including one.

So we don't have to deal with the decimal
point.

That's the first simplification.

The second simplification, and this proof
would work without the second one as well.

But it makes life so much simpler for us,
easier to grasp, because I'm going to

minimize the number of digits we have to
think about.

I'm going to write these real numbers in
binary.

Okay?

So that's going to simplify everything,
as you'll see in the proof.

You could do it in base 10 also,
and you could do it in any base.

But if we write it in binary, so that will
simplify things a bit.

Let me just take a little drink here.

One second.

My throat.

Okay, thank you.

All right, so let's now look at this
matrix, this chart.

And the way it works is the following.

Let's line up the real numbers,
okay?

Let's line up the real numbers.

Now, I realize that, you know,
technically, according to the proofs and

our discussion I just said,
we should really start from

zero as the first position
in the row and the column.

For reasons that would be easier for us to
grab onto the proof, another

simplification, I'm starting from the
number one.

It's relevant.

The actual position
number, when you start

from zero, one, is not
relevant to the proof.

So if you went after understanding the
proof, you could change it back to zero,

one, two, zero, one, two.

But it's easier to relate from one,
two, three.

Okay, so now, each
row, it represents a single

real number, one of
the real numbers, okay?

And the row number, column A, represents
the counting, the natural number that

we're going to associate with that
particular real number.

So each row has to be different.

You can't count the same item twice.

And counting also implies that you don't
leave anything out, right?

Okay, so the row 27 in Excel contains real
number one.

And then we count in Excel row 28,
number two, dot, dot, dot.

And then in row 32, we count real number
six.

And then in row 36, generically,
I, the ith real number.

Okay, what are the columns?

The columns are the digits, all right?

So the first row is all zeros.

And then I changed one digit.

Now, because I, again, it's simpler
because I use binary.

So I changed the first digit.

So now we have a one followed by all
zeros.

Okay.

And then I, well, you know, it's,
it's more than changing a digit.

What I'm doing is
counting, I'm generating

this, not necessarily
by the true real numbers.

Well, they are the true
real numbers, but not

necessarily doing sequential
sorted real numbers.

And what I'm doing, if you
notice how I generated this, and

it's not necessarily for the
proof that you do it this way.

It's just, it's simpler for me to write this
chart this way, which is basically zero.

And then if you
notice, going from left to

right, row number two
contains the value one.

And then row number three contains the
binary of the value two.

And then row number four contains the,
the binary of the value three.

And then the row number, you know,
et cetera.

If I started with zero, then the, it would
be in the actual expansion of the row.

Anyway, the point is I'm filling up,
I'm filling up this chart with every

possible sequence of, you know,
of zeros and ones.

Okay.

All right.

So now, so now we have this chart.

Okay.

So this chart contains every real number.

And again, one real number per row.

And the columns are just the digits.

So if I ask you what's
the third digit in the

fifth real number,
we go to call a row 31.

And we go to, oh, you want to,
you can answer it if you want.

Then say, oh, present.

Okay.

If we go ask you, what is the third digit
of the fifth real number in our count?

So we go to the fifth real numbers on
Excel row 31.

And then the third digit is in Excel
column D.

So if we go to D31, we see it's a one.

And for us, it would be five, five comma
three in the internal matrix there.

Okay.

And in general, it's I comma J,
the ith real number in our count,

and the jth real number in the,
the jth digit of that ith real number.

Okay.

Now we're going to suggest that we're
going to construct a new real number.

Now, obviously, that's a little bit of a
game we're playing right away,

because we just
pointed out that if you

count, you have to
count all the real numbers.

But I'm going to claim, I can't believe
what I'm about to suggest is on that chart.

I think this is such a convoluted new real
number, it can't be there.

But we're going to check.

And that checking for that new real number
is going to prove to have a contradiction.

And that contradiction is going to show
that our assumption that the real numbers

are countable, that you could list them in
this manner, is not possible.

Okay.

So here's what we're going to do.

The matrix, once we have this matrix,
ignore where the matrix came from.

And that's, again, an assumption I
mentioned from day number one.

Turing, at the point that
you store it into memory,

Turing doesn't care what you
think that memory represents.

Turing doesn't care what you say the value
stored at that memory is.

Turing only cares to the fact that there
is some configuration of memory,

zeros and ones, whatever machine language
you have.

All right?

So now this is all stored in memory.

So ignore the fact where it came from.

So this is now a matrix.

And this matrix has a diagonal.

The diagonal is where the row and the
column is the same position.

So row one, column one is the first piece
of the diagonal.

Row two, column two.

Row three, column three.

Row four, column four.

Five comma five.

Six comma six.

I comma I.

J comma J.

Et cetera.

K comma K.

M comma M.

Blah blah blah.

Right?

That's the diagonal.

And this, it happens to be the way I set
it up.

It's all zeros.

It'd be interesting to prove whether the
way I did it, it's always all zeros.

But that's not really relevant to our
proof.

That's just a cute discrete mathematics
analysis or number theory problem.

Anyway, but it's not
relevant whether all the

numbers on my diagonal
will always be zeros or not.

But the fact is that this matrix has a
diagonal.

Okay.

Now I'm going to create a real number.

What does it mean to be a real number?

I don't need to give meaning to my real
number.

I'm going to create a real number by
simply listing its digits.

If I list to you a sequence of digits
continuously.

Right?

Digit one, digit two, digit three,
four, five, six.

Right?

All the digits.

Then you have a real number.

That's what it takes to be a real number.

And the digits that we're dealing with are
only zeros and or ones.

Okay?

All right.

So here's how we're going to build this
digit.

And this new real number.

I claim it's a new real number.

And then we're going to test whether it's
new or not.

So let's go to the first diagonal.

Well, as I said, in this case,
it'll be a little funny.

But okay.

In this matrix, row one, column one is a
zero.

And what you're going to do is you're
going to flip the bit, not in the matrix,

separately.

I'm building a new real number in a
separate memory located, in a separate

single dimensional array containing the
digits of the real number.

So what I'm going to do is
every number, every digit that

appears on the diagonal
sequentially, go through the diagonal.

And I'm going to take the opposite.

I'm going to say not.

Not that.

And if it's a zero, my digit...

Of course, if it's a zero in
position I comma I in this

matrix, then in my real
number, position I will be a one.

And if there's a one in the diagonal of
this matrix, if there is a one in position

I j comma j, so then
the jth digit in my new

real number, you had
a one, I'll have a zero.

And that's what we say on line 43.

We will construct a quote unquote new real
number, r sub new of I, the i-th digit,

equal to not r... I gave
the name, the matrix r.

Usually you like...
Most matrices are m.

But here I figure r for real numbers.

Anyway, so not r I comma i.

So if I want to know what the i-th digit
of my r sub new, new real number is,

so then I go to position
r, the matrix r, and I go to

row I, column I, and
whatever it says there, I do not.

I flip the bit.

I don't flip it in the matrix.

I flip it in my r new one dimensional
array.

Yeah.

All right.

So I keep on doing this, and now I have my
quote unquote new real number.

Now since matrix r has all possible real
numbers, r new isn't really all that new.

It must be on this matrix.

I thought I'd be... I thought I
would do something so convoluted.

I can't believe it actually would be on
this matrix.

But it's not true.

Because if you claim that
you can count all the real

numbers, then you must
sum position in your count.

It may be position 1,372,465,989 position.

But in that row will be the real number
corresponding to what you just said.

And if I claim r new is
a real number, it has to

be occupying some row
somewhere in this matrix.

Okay.

So which row is it?

Let me advance the board.

So which row is it?

It takes a while since the...

Yeah, there we go.

It takes a...

There's a slight delay
only because the board,

the virtual classroom,
takes hold of the file.

And when I click on my
actual file, it has to release

that for a second in order
to allow me to move it.

Anyway, so that's a few seconds delay.

All right.

So now we're going to...
So this is what we just said.

All right.

Now, let's get back to the board.

I have to.

You're still there.

I have to lower this.

Okay.

All right.

So again, so which row is it?

On the notes, it's row number 45.

But that's not the real number.

I just wanted to tell you what we're up to
in the notes.

So which row is it?

So one last time.

What's going on?

So we had... We claimed...
And it's a proof by contradiction.

We claimed that the set of real numbers
are not... are countable.

All right?

And if that's the case...

Now, we're going to
concentrate on the real

numbers between 0
and 1 just for simplicity.

So that way, we don't have to worry about
the decimal point.

Okay?

And it makes it easier for us to store it
and describe it.

And certainly, if the numbers between the
set of all real numbers between 0 and 1 is

not countable, then a
bigger set that contains

that and more certainly
can't be countable.

Right?

So we line up these numbers.

So if you claim you
could count, then every

real number could be
written down row by row.

Okay?

Now we're going to organize it,
we said.

So that way, we line up your digits.

There's a position one, a position two.

And if you... If for
some reason, you...

You know, the last one that you have
stopped somewhere that just pad more zero.

Pad the remaining digits, just so that we
have a matrix without missing pieces,

pad it with zeros.

Right?

In other words, if all you have is a one
in the first position, so, you know,

0.1, although binary, but that's
irrelevant.

The point is that you want to make every
real number have the same number of

digits, then just simply pad the rest with
zeros.

That's not a big deal.

It doesn't change the value.

But we want a nice, clean matrix.

Okay?

So we had a matrix.

And now we claim... I claim
that I have a new real number.

How is it formed?

So each digit in this real
number, and I'm storing

it separately in my own
one-dimensional array.

What we're going to do is we go to the
diagonal of the matrix.

And whatever appears in
the diagonal of the above real

number matrix, I'm going to
write the opposite digit down.

So if it's a zero, I write down in my
digit one.

And if it's a one, I write down in my
digit zero.

And I keep on doing this, and now I have a
real number.

Ah!

But if I have a real number, it's not new
after all.

It may be a new crazy way
of getting a real number, and it

certainly doesn't have any
official meaning to this number.

But meaning is not relevant in
mathematics.

Mathematics, you know, philosophy has
meaning.

Philosophers think that mathematics is
philosophical.

But the fact is that mathematics is not
about meaning.

Mathematics is about consistency.

Anyway, that's another discussion.

It'll pop up at some point.

So we have a real number that I created.

And in fact, it's not a new real number.

So where is it?

Where on the matrix is this real number?

Okay.

It has to be there.

And if you claim that it's countable,
then every real number has to be able to

hash, to be hashed, to be
mapped to a natural number,

which is the row that we
have in this count in the matrix.

All right.

So let's say, in fact, that we found it on
the kth row of this matrix.

So then in our notes, line 47,
then for all j, r new of j, my newly

convoluted, crazy, constructed real
number, right, that I have, the jth digit

is going to equal to, so we claim that
it's on the kth row of this matrix.

So therefore, it's got to be equivalent
digit by digit.

So it's got to be equal to r, the matrix
above, k, the row we claim, the real

number, this new, which isn't really new,
number appears.

And it must agree with it j by j,
digit by digit, bit by bit.

Okay.

Now, let's specifically ask, and it's true
on line 47 in the notes I write,

for all j.

I'm only going to ask, I'm going to pick
one j and create a contradiction.

Now, we know it's row k, so k is a number.

I'm going to ask you, what's the bit value
at r new of k?

This is going to cause a contradiction on
this one specific bit of this real number.

Now, since r new is found at row k of the
matrix, then r new of j is going to equal

to r k of j for j equal to k,
specifically.

That is, that r new of k equals r of k,
comma k.

Right?

The kth row, kth column.

It's the kth row, because we say that new
isn't new afterwards.

New is k, row k.

And then it's r k of comma k, the second
k, because it must agree digit by digit,

bit by bit.

But that is not possible, exclamation
point, since, according to the original

definition of r new on line
43 in the notes, that r new

of k will be equal to not r
in the matrix k, comma k.

Yeah.

All right?

Right?

That's how we defined it.

So, by claiming that r new isn't new,
but it's in fact old, and it's found at

the kth row, so then the kth
digit of r new has to equal r of

k, the kth row will be found
in r new, and the kth digit k.

Someone's speaker's on, microphone's on,
if you can shut it off, please.

I hear some noise in the background.

So, r new is at row k, and it must agree
digit by digit, column by column.

All right?

But, the way it was defined was that r new
of k is not r of r k, comma k.

So, this contradicts the statement above
that r new of k is equal to r k of k.

This contradiction implies that our
original assumption that the set of real

numbers is countable,
which allowed us to set up the

rows of this matrix in an
ordered sequential fashion.

So, that is, in fact, false.

Thus, the set of real numbers is not
countable.

Again, it technically shows that the real
numbers between 0 and 1 are not countable,

but if that smaller subset of real numbers
is not countable, then, in fact,

the fuller set of real numbers is also not
countable.

Now, what's interesting about this
proof... Let me just drink a little more.

Now, what's interesting about this proof,
which I didn't... let me add right now...

Let me get you back to the matrix.

Let's get back to the matrix for a second.

Since we have it here,
there's something very

interesting, which I
would like to point out.

Let me get you the matrix.

Again, there's a few seconds delay until
the machine releases my file.

That's why I had to pause.

All right.

Now, although we used this matrix to prove
that the set of real numbers is not

countable, as I pointed
out to you a second ago,

that's actually only an
interpretation of the matrix.

Right?

The fact is that we have a matrix containing
0s and 1s, which is stored in memory.

Remember, Turing doesn't
care why you got it, how you

got it, how you interpret it,
what value you consider it.

That's not relevant.

What's relevant is you now stored this in
memory.

Right?

You stored this in memory.

So now we leave it up to you.

It's sort of like a piece of art.

We now leave it up to you for your
interpretation.

But that's not part of the theory.

The theory just needs to store it in
memory and map it to the resulting memory.

It's the resulting memory configuration
all in the same spots of memory.

And the algorithm is what does that
manipulation, what does that metamorphosis.

But how you interpret it, that's up to
you.

Why am I saying that?

Because this identical
proof shows a number of

other proofs by reinterpreting
what this matrix is.

It's not the fact that these are real
numbers that cause the contradiction.

Well, at the bottom line, we need to say,
and therefore the real numbers

contradiction, therefore the real numbers
are not countable.

But put, instead of, everywhere in the
proof, instead of real number,

put, you know, blank.

Call it thingamajig.

Thingamajig.

So we proved that the set of thingamajigs
is not countable.

The reason I'm saying that
is because this same matrix

could be interpreted a
number of different ways.

And this identical proof,
except just change the word

real number to whatever
thingamajig I'm about to say.

Then we will have now
shown that the same technique

proves a number of other
items are not countable.

Such as what?

Okay.

So let me see.

I'm hoping this will work.

Let me just check.

I'm hoping that the
software is good enough

that if I add a sheet,
you could check that.

I need to verify that.

Oh, good.

Okay, good.

All right.

So, cause it'll be later.

I'll later when I send you the notes in
the afternoon, I'll decide whether to

integrate that directly in here or keep it
separate.

There is a pedagogical advantage to maybe
keeping it a little separate.

All right.

Take, for example,

a Boolean predicates.

Okay.

What's a Boolean predicate?

A Boolean predicate is a total function
that maps the natural numbers to binary.

True, false.

That maps the natural numbers to 0,
1.

Conventionally, 0 represents false.

And 1 represents true.

Okay.

That's a Boolean predicate.

Now, truth be told, and we're going to see
this a little bit later.

Truth be told, that what?

Later in the semester, Richard Karp,
a paper that we're going to... at the end

of the notes, I'm going to tell you how to
search for the paper and to download it,

because we're going to spend a number of
weeks on that paper.

It's such a significant paper.

We're going to spend a number of weeks on
this paper.

Actually, it's predicated on a different
paper by a friend of his, Stephen Cook.

And we're going to spend one day on that
paper.

But we're going to spend a number of weeks
on Richard Karp's paper.

And just so you should know, although you
may, when you hear that, I can imagine

you're cringing in
that, oh, no, we're going

to spend so much time
in such detailed theory.

The fact is that Richard Karp's paper,
while it is a theory paper, has

incredible, incredible practical
applications.

And I'm going to try to, although there is
a little bit of theory we'll have to do,

I'm going to try to concentrate on the
practical applications of that paper.

But it's at least two to three weeks to
discuss that one paper.

That's how significant it is.

What's so interesting to me is that Cook's
paper is 1971.

Richard Karp's paper is 1972.

So we're dealing with a paper that was
published 54 years ago.

And it's as relevant then as it is now.

And now as it is then.

Anyway, it's very, even
though it's pure theory,

technically, it's going to be
very practical, as we will see.

Amazing.

Amazing paper.

Later in the semester, Richard Karp will
narrow this definition.

I swung for completion's
sake, because you'll ask

me this later, so I might
as well tell you now.

We'll narrow this definition
of Boolean predicate to

require that the input
variables are also Boolean.

Okay, we don't have to worry about that
now.

I'll explain that later.

All right, but in discrete mathematics,
traditionally, we have what I wrote in

line two, which is that a
Boolean predicate is a total

function that maps the
natural numbers to zero or one.

Okay?

Okay?

All right, so now, let's take the natural
numbers.

Okay?

Dot, dot, dot.

Okay?

Meaning, et cetera.

All right?

See, these are our natural numbers.

All right?

And now, we're going to have...

Let me get you some boxes here.

This will be easier to relate to.

All right?

And then, well, dot, dot, dot.

Right?

So continuing on.

All right?

So let's say there... So now, we're
going to have the Boolean predicate.

BP.

Boolean predicate.

All right?

So let's say there's a one here,
and a zero here, and a one, and a zero,

and a one, and a one.

And zero, zero, dot, dot, dot.

Right?

Dot, dot, dot.

Right?

In other words, it's not really relevant
what they are.

That's all I mean.

All right?

And let's clean this up a bit.

Let's center this.

All right?

That's a Boolean predicate.

What's a Boolean predicate?

I tell you for every input what the output
is.

Now, ignore for a second, as I said to you
before, we could have done it.

It's just in my matrix, I started with
input one.

We could have started with input zero.

It would have worked actually after the
fact.

It actually reads easier with zero than
one.

But it's not relevant, because we just
called it K, I, and J.

We didn't really dwell on zero versus one.

But in Boolean predicates, we're doing it
completely.

Basically, you have a
column of natural numbers, and

then you fill in those natural
numbers to make a row.

Now, what does this look like?

Exactly like matrix A row in matrix R of
the previous proof.

Right?

It looks exactly.

What is it?

You know, if I didn't write...

If somebody would walk
into class this moment, look

at the board, and let's
say I didn't write anything.

All I did was zeros, ones, zero,
ones.

I didn't write BP.

I didn't write this.

I didn't write rows one and three.

And they see this row of zeros and ones.

They would have thought...

And let's say they go back to the page one
of the notes, and they see, ah,

so I must be talking about real numbers
again.

But I'm not.

I'm talking about Boolean predicates.

The fact is that the encoding of having
zeros and ones in all these positions is

exactly the same encoding that a real
number is.

I read... I read... You
read this as a real number.

I read this as a Boolean predicate.

Who's right?

Who's wrong?

Both of us are right and both of us are
wrong.

It's not relevant, says Turing.

But that works for us.

The proof is about the configurations of
each row, being zeros and ones.

The fact is that...
The fact is that we...

That the Boolean predicates could be
represented in the same manner.

Therefore, the identical proof that showed
that the real numbers are not countable

will now show that the set of Boolean
predicates over the natural numbers...

Mapping the natural numbers as

inputs is not countable.

Same exact proof.

Okay?

Fascinating.

What else?

All right.

In other words, let's be creative.

In other words, what else...

Since we're talking, I'm going to answer
the question in a second.

What else can we show is also represented
in this manner?

So one of them we get as a freebie.

Take, for example, bit strings.

Which are simply a concatenation.

The gluing together.

So it's one after the other into a...

Concatenation means connecting individual
letters into a single word.

Into a single word or string.

Which is simply a concatenation of zeros
and ones.

Binary digits.

Zero comma one.

Okay?

That's a bit string.

So...

Let's write a bit string.

Ta-da!

We'll call BS for bit string instead of BP
for Boolean predicate.

Ta-da!

Here's a bit string.

So what does this look like?

Well, it looks like the one above.

But again, it looks like a row and matrix
of the previous proof.

Therefore, the identical proof shows... That
show the real numbers are not countable.

It will now show that the set of all bit
strings is not countable.

Right?

Because it's just the representation.

You read it as a real number.

I read it as a Boolean predicate.

You read it as a Boolean predicate.

I read it as a bit string.

Right?

It's the configuration that caused the
contradiction.

It's not the interpretation.

The interpretation is what led us to the
configuration.

But the proof is about the configuration.

The proof isn't about a real number.

The proof is about the matrix and how
things were stored in that matrix.

Okay, let's take one more.

Sets.

A set is a collection of elements.

Sets are collections of elements.

Technically, by default, sets are
unordered.

Okay?

But if you were to store a set in a
computer,

the underlying memory addresses have now
ordered the elements of your sets.

Right?

They don't move around in the memory.

But they do move around.

They don't move around in memory.

They move around in the abstract
mathematical notion of a set.

But they can't move around once you put
them into memory.

Okay.

Now, mathematicians also allow such a
concept.

Mathematicians do allow
imposing order on sets

by declaring the set
to be an ordered set.

So if you declare
that initially, then you

are assuming that
there is an implicit order.

Okay.

Good.

Now, give me one second.

Second.

Yes.

All right.

Consider... We're
still within sets.

Consider the natural numbers.

Okay?

N.

We're gonna... R will
be the real numbers.

N will be the natural numbers.

Okay?

And let's start with zero to be complete.

Zero, one, two, three, four, five,
et cetera.

Right?

Those are the natural numbers.

Okay.

Now, an arbitrary subset, S, will contain
some, possibly all, but generally not,

of these numbers.

How can we represent S in memory?

In the computer memory.

That's right, computer.

How can we store?

Okay.

In computer memory.

Tech... The word represent is
more accurate, but it may... It's more...

It's easier to relate to if we say store.

How do we store S...

I'm sorry, give me one second.

How do we store S in computer memory?

Good.

All right.

Ready?

Subset of natural numbers.

Oh, well, this time I'll call it S.

Because we called it S.

Subset.

Here we are.

So what subset is this?

All right.

So wherever there is a one in a given
position, I,

then natural number I is in the subset S.

In the given subset.

In the given subset S.

So here, S will be equal to...
So there's a one in position zero.

There's a zero and one, so one is not in
it.

There's a two.

In position two there's a one.

In position four there's a one.

In position five there's a one.

And dot dot dot.

We don't know what else is there.

All right.

So S is the following subset.

Represented by the matrix, the row rather,
the array in column 2728.

So what does this look like?

Exactly like a row in the matrix are the
previous proof.

Therefore, the identical proof that showed
that the real numbers are now countable

will now show that the set of all subsets,
also known as, aka, also known as power

set, of the natural numbers is not
countable.

So the same exact proof, it shows Boolean
predicates are not countable.

Again, we showed the proof that the real
numbers are not countable.

The set of bit strings is not countable,
all bit strings, if it's allowed to have

any number of digits, not a finite amount
of digits.

The key here is, in all these cases, is
that the length is over the natural numbers.

And then it shows that the subsets are the
natural numbers.

And now we showed that
the power set of n, the set of

all subsets of the natural
numbers, is not countable.

Okay?

Excellent.

Very, very interesting.

All right, let's get back to our original
sheet.

All right.

Now, okay, well, first of all,
let me just double check in case...

Usually it will beep, but let me double
check in case there were any...

Sorry, let me have to close this.

I'm lowering this, rather.

All right, does anybody have any particular
questions that you would like to ask?

Or, it's pretty straightforward,
I hope.

But if anyone has any specific questions
you'd like to ask, please do so.

Okay.

All right, so I find that fascinating.

Hopefully you did as well.

By the way, if you come up with other
interpretations of our matrix,

which, in other words, if
the same proof could show

other functions are not
countable, please do so.

Okay, so, you know, actually I wanted to
do something.

There was something
I thought of, which, if

you get lost, then I
wouldn't mind doing it.

We'll continue with the notes in a second.

I'd rather just quickly do it now,
because it's a very interesting point.

Cantor actually, he doesn't
mention this exact example, but

he mentions this point in his
work, in his notes, his paper.

Well, it was handwritten.

I think I told you the history.

But anyway, but eventually what was
published.

But here's something very interesting.

I hope you'll find it interesting.

Okay, let me put it separate.

So this is uncountable.

Okay, these are our notes.

General notes, uncountable.

Now just something about counting.

I just want to make an interesting point.

A very cute example about counting.

Cantor realized that even
when we say that a set is

countable, it has to be
what Turing eventually calls

an effective computation.

Or in his case, an effective counting.

Turing doesn't call the word counting.

But the key word here is effective.

Okay, what do I mean?

I'll give an example and you'll understand
this.

So in other words, even if a set is
countable, you can, by accident or not,

count it wrongly, incorrectly.

You can count it using an ineffective
procedure, which will actually prevent you

from counting the entire set.

And that is what Cantor realized.

It's not just simply, well, uncountable.

Okay, he brings a proof.

We understand.

Uncountable, you can't figure out how to
count them.

Ah, but countable?

Well, sit down and just start counting.

It's not true.

You cannot just simply sit down and start
counting.

You have to be careful how to, you
have to be a little careful how to do it.

Okay, so let me give you a simple example.

Consider the natural numbers.

Now, the natural numbers are the counting
numbers.

Right?

Everybody has to be mapped to the natural
numbers in order to count.

So then you can say, one, you're the first
apple.

Two, your banana.

Three, your cherry.

Four, your dates.

Five, your eggplants.

Six, your figs.

Right?

Et cetera.

Correct?

So you count.

What does that mean?

You can map them, as we said.

It means, by definition, it means to map
to the natural numbers.

Good.

So that's what it means to count.

Okay?

So let's start counting.

Zero, one, two, three, four.

Right?

Dot, dot, dot.

I'm doing the successors.

Okay?

So counting by successors is effective.

Right?

Zero plus one is one, plus one is two,
plus one is three.

Right?

The successors.

Successors means plus one.

Well, effectively plus one means next.

Right?

Here, next means plus one.

Okay.

Now.

Good.

Okay.

How can we count this wrong?

Okay?

So how can we count the set in an
ineffective manner that will prevent us

from counting all the elements of the set,
even though it is countable?

So again, Cantor was very sharp.

He realized this point.

So he had to sometimes come up with
innovative ways to count things,

because sometimes the simple approach is
ineffective.

It just won't do it.

You think it will, but it won't.

So let me explain why.

So the natural numbers

can also be thought as the union of the
even numbers and the odd numbers.

Okay?

So for example, even.

Even will be equal to zero, two,
four, six, eight.

Who do we appreciate?

I don't know if you did that as kids.

We used to.

Anyway, zero, one, odd numbers are one,
three, five, seven, nine, et cetera.

Okay?

Those are the even numbers.

Those are the odd numbers.

How do we count the even numbers?

Well, what we'll do is we will take a
natural number and map it.

Natural number I, some i.

Okay, let's call it j.

Only because I is a little hard to read on
the screen.

So natural number j.

And what we're going to do is simply map
it to two times j.

So who's our... So
write this very simply.

Let's write it down.

Zero.

You know, let me borrow from the previous
line.

Even.

So two... Sorry, not two.

Zero, two, four, six, eight, 10,
12, 14, et cetera.

Right?

Those are the even numbers.

Okay?

How do we count the odd numbers?

How do we count the odd numbers?

So then we take the natural number j and
we do two times j plus one.

I'm sorry.

The arrow means mapping into.

Who do you go into?

So odd will be two times j plus one.

One, three, five, seven, nine,
11, 13, 15, et cetera.

Right?

So this is a very...
Individually, these are effective...

Individually.

These are effective manners to count the
even and odd sets respectively.

Right?

The way we just did
it, you'll be able to count

every single even
number and every single...

Respectively.

Sorry.

Every single even number and every single
odd number.

Yet, if we were to count all natural
numbers

using these procedures,
we will not... Effectively.

We will not...

Effectively.

We will not be able to effectively count
n.

Meaning, count... Here's
what we were doing.

Count all the even numbers.

Then, count all the odd numbers.

Okay.

So, we just said we have an effective
procedure.

You can do it.

It will work.

To count all the even numbers.

We also said that you have an effective
procedure to count all the odd numbers.

And, natural numbers is the union of all
even and all odd numbers.

So, it should stand to reason,
but wrong.

But, you would think it stands to reason
that you can now count by counting all the

even numbers and then count all the odd
numbers.

But, that's not true.

Why?

Because, you will be stuck in an infinite
loop with the even numbers.

And, you will never have the chance to
count any of the odd numbers.

So, that's a very interesting point that
Cantor realized.

And, he's very careful.

And, he does a lot of tricks in his
counting arguments when he was doing his

theory to make sure he doesn't fall into
this trap.

Just because something is
countable doesn't mean you

could just simply start counting
any manner that you want.

It's true that if, in theory, you could
count all the even numbers and then count

all the odd numbers, you should be... you
will be counting all the natural numbers.

But, Cantor realized that you need an
effective procedure.

And, it won't work.

Because, there are an infinite number of
evens, you'll never get done counting all

the evens before you
will... in order to have

a chance to even count
a single odd number.

That's a very interesting point.

I don't know if Cantor... it's possible
Cantor used this example.

But, I do know that... I remember his
notes and his handwriting.

I've seen it.

I've seen his manuscripts.

Copies, not the originals.

And, he does other tricks that he needs to
do.

In other situations, he makes sure that
you do this... you know, this thing.

I'll tell you an example quickly,
an example where he does this.

This... he definitely wrote... and I
remember when I took the course with

Martin Davis, the author of the book,
Martin Davis was the chair of NYU's Crown.

Institute's Computer Science Department at
the time.

Now, he's a distinguished professor at
Berkeley.

Anyway... anyway, founder of the field.

So, he presented the following,
which Cantor does write in his notes.

So, I don't know if Cantor did this one.

But, he did the following.

How do I present it to you?

How does one effectively...

Now, I'm not going to... I'm not going to
bother to finish this conversation.

In other words, he chose how to do it.

I'm going to leave it up to you,
though, to research it.

Because, how he does it doesn't really
help us much.

But, this notion, I think, the question
about how to innocently count,

and how you have to count sometimes with
some wisdom, even if the set is countable.

So, that you have to be careful.

How does one effectively count the lattice
points, i.e.

integral points, in the positive number
plane?

Meaning, x, y, where x and y are greater
or equal to 0.

Okay?

Non-negative.

Right?

So, you have four quadrants, x,
y.

Right?

And the upper right corner is the upper
right quadrant of the number plane.

Upper right quadrant of the number plane.

Of the number plane.

Okay?

And Cantor realized
intuitively that it should

be countable, but he
wants to start doing it.

So, here's the wrong way.

If you...

Now...

Okay.

One more point beforehand, and related so
we can set it up similar to the above.

Any given column or row independently is
countable.

Independently is countable since the
coordinate...

Since it is only one dimension.

And the coordinates will be the natural
numbers.

In other words, you'll
have position 0, position

1, position 2, and
whatever numbers they are.

So, you can count the points in that
plane.

Right?

If you take just a row, just a column,
just...

It's basically exactly in the matrix
structure you see on line 27.

Right?

It's just one row, one column,
etc.

Good.

Now... If we were to suggest

that... the manner to count

the entire quadrant as a whole,
which is now two dimensions

is by counting row by row,

or counting column by column

let's count every

count the number of elements in the first
row, the second row, or count all the

elements in the first column, and the
second column.

So, eventually, you'll get to do all the
entire quadrant.

That's true.

But it would not be effective.

Since... there are
an infinite number

of rows... and columns...
in the number plane.

Right?

It keeps on going.

So... if you were to count
by... if you were to count

if you, the human, were
to count... row by row

then... you would
never finish

i.e.

Infinite loop

counting... the
points in the first row,

and same

similar argument for...
for the first column.

So... Cantor had to come up

had to devise

a... a... a

a... well

ingenious... but a... an
intelligent manner... of counting

to effectively count... this
quadrant... the points in the quadrant.

So... I'll... I'll show
you how we did it.

It's... it's basically
this... uh... let's

do... five... four...
three... two... one

zero

zero... one... two...
three... four... five...

I'm only doing a small
portion of it... okay

because... I don't want it to take up
too much room... but you'll get the idea.

All right

uh... one second

all right... here you go... so
we want to start counting,

so this will be our first element... our
second element... this... you know it's

well... I'm not doing it exactly... my
point is... I'm trying to show you the wave

that he used to count

in other words... he... he would have
done... one... two... three... four... five

six... seven... eight... nine...
ten... but I just want to show you

how he realized you have
to do this... the point is

each wave has only a finite
amount of... in other words

going row and column doesn't work...
but going... the backward diagonal

does work... because the diagonal only...
first of all... it increases only by one

in other words... there's one
element in the first... such diagonal

there's one element in the
second... such diagonal

right... dot dot dot dot dot dot... okay...
so that's how he did it... and he,

and he... he gives you a
numerical... algebraic formula

to get the values for each of these...

You know, it's to index these values.

Very interesting.

So that's how we did it.

Because going by row or column won't work.

You'll have an infinite loop.

Beautiful.

Okay, now.

Just a few more minutes to finish the
notes.

So it comes out that, as Martin Davis
proves in his book, that you could use any

base arithmetic you want in order to have
a machine.

And as I said, in Eastern European
countries, they use a base-3 arithmetic.

On line 71 in the notes,
base-6 arithmetic has been

developed for certain
image processing systems.

Believe it or not, base-6.

I actually wrote a paper with someone
Natalie Hammerman, blessed memory,

a former student of mine.

Anyway, so she... the paper we published
showed... it wasn't our original idea.

We added to it.

But the point is, base-6, believe it or
not, has a special property.

You would think, why base-6?

It turns out it does, as a base-6 has a
special property for encodings.

Anyway, base-8, base-16
from assembly languages,

and base-10 we use
and the abacus used.

So you can use any base you want.

So the question is, what would base-1
arithmetic look like?

Because we said all positive integers,
which includes base-1.

So base-1 is the ship person's tally.

Tally is a count.

Four would be four ones.

Five would be five ones.

How do you do addition?

Concatenation.

Concatenation.

You know, I use dot in cell C83.

I temporarily use the dot as
concatenation.

But the point is, it's plus.

It's just that we're strings.

So then you concatenate it, and now you
have nine ones.

Anyway, he proves... Amon Davis spends two
chapters to show that you can do all

arithmetic and simulate a Turing machine
that only has base-1 arithmetic.

You can actually do it.

I know it's surprising, but you can
actually do it.

You can do anything arithmetic,
and any Turing computation can be done,

not just over base-2, but also base-1.

Now, here's the kicker.

This is really important.

Now, I call this a homework because it's
something you're going to think on your own.

It's not something I'm going to ask you to
submit.

But this is key.

Despite the fact that the above analysis
could show that any positive integer base

could enable a Turing machine equivalent
computing device, base-1 will cause

problems to analysis of algorithm tenets,
rules.

And not for submitting, but think about
it.

The answer will be available at the end of
the semester.

We're going to give
hints throughout the

semester to explain the
answer to this question.

It's not that base-1 arithmetic can't be
done.

It can be done.

But practically nobody wants it because
base-1 violates analysis of algorithms.

Violating analysis of algorithms does not
violate theory.

Remember, we made day one the distinction
between complexity and solvability, right?

So this may violate
the ability to assess

complexity, but that has
nothing to do with Turing.

Turing was only interested in solvability,
and base-1 works.

So the question is why is base-1... why
does base-1 violate complexity?

Martin Davis showed it does not violate
solvability.

One last point is that I... and here I
mentioned it.

I addressed a little bit later from
analysis of algorithms.

You could read it, which is what the basic
tenets of analysis of algorithms are.

Just so that I could bolster my claim.

But just to give you a hint, I'm
summarizing the base-1 tenets,

the analysis of algorithm tenets.

The question is what went wrong with
base-1?

The other point is that although you can
use any base, there are papers that show

the higher the base is, the faster in
practice the computing will be.

It may do the same results, but in fact,
higher bases do get you there faster.

So if an abacus was a Turing machine,
it would be the fastest machine.

If hexadecimal, it would be even faster.

Anyway, these are some points I mentioned
last time.

Lastly, which we're going to deal with in
a different class, but please keep in

mind, these theory papers deal with
complexity instead of solvability.

But quite important.

So the question is when you say complex,
easy versus hard.

So we're going to eventually deal with
that in upcoming papers.

Please search for these papers online,
download them, print them.

We're going to need them for class.

All right, it's the end of class.

If you could kindly, if
you haven't had a chance,

if you did, you don't
have to do it again.

But if you haven't had
a chance, kindly text the

word present, and we will
continue on Wednesday.

And later today, I will email you these
notes.

I want to look it over, make sure no
typos, things like that.

All right?

So kindly... Hi, Professor.

Can you hear me?

Yes, sure.

Yes, I just have a quick question.

Over the weekend, he was looking over some
of the assignments, and I saw that the

date... One thing, one thing,
let me help you out here.

Yeah.

I sort of mentioned this in the last
class.

It's okay if nobody remembers it.

I had it when I set up the... I
didn't yet set up the Brightspace.

I had to instantiate the course by cloning
a previous semester.

So nothing has been officially been posted
for us.

I am doing it, and hope to do it,
over the next day or so.

And in my email, I mentioned that.

But... So if you ask me about things coming
up, or assignments, ignore them for now.

I mean, do the assignments,
if you talk about the daily

assignments, but the due
dates aren't anywhere near now.

And I'd rather have us discuss it when the
true materials are posted.

But if you have a specific... Okay, ask
which assignment you want to ask about.

And let me see if it's still the case.

Okay, I think you had answered it.

It was regarding the dates for the keyword
assignments.

Yeah, yeah, yeah.

That's exactly right.

So ignore all that.

Ignore that.

I will email you.

And if because of my delay, setting up
Brightspace for the student is easier.

For the professor, it's not so easy.

It's worth it.

But it takes a lot of time, and that's
what's been happening.

So if because of that we need to adjust
the dates, I'll do so.

But let's not try to do the assignments.

Just don't worry about the dates right
now.

Okay?

You'll have enough time to do it,
and I'll make sure.

All right.

Thank you so much.

Sure.

Okay.

Thank you for asking.

Okay.

If you didn't have a chance, please thank
you all.

If you didn't have a chance, kindly text
the word present.

Otherwise, we all probably have to head
out to another class.