1. The Cantor diagonal argument

Definition 1.1. A set S is finite if there is a bijection between S and {1, 2, . . . , n} for some positive integer n, andinfinite otherwise. (I.e., if it makes sense to count its elements.)

Definition 1.2. Two sets have the same cardinality iff there is a bijection between them. (“Bijection”, remember, means “function that is one-to-one and onto”.)

A set S is called countably infinite if there is a bijection between S and N. That is, you can label the elements of S 1, 2, . . . so that each positive integer is used exactly once as a label.

Why “countably infinite”? Such a set is countable because you can count it (via the labeling just mentioned). Unlike a finite set, you never stop counting. But at least the elements can be put in correspondence with N. On the other hand, not all infinite sets are countably infinite. In fact, there are infinitely many sizes of infinite sets.

Definition 1.3. The Cantor diagonal argument, also called the Cantor diagonal method or Cantor’s diagonal slash, is a clever technique used by Georg Cantor to show that the integers and reals cannot be put into a one-to-one correspondence (i.e., the uncountably infinite set of real numbers is “larger” than the countably infinite set of integers).

Georg Cantor proved this astonishing fact in 1895 by showing that the the set of real numbers is not countable. That is, it is impossible to construct a bijection between N and R. In fact, it’s impossible to construct a bijection between N and the interval [0, 1] (whose cardinality is the same as that of R).

Here’s Cantor’s proof:

Suppose that f : N → [0, 1] is any function. Make a table of values of f, where the 1st row contains the decimal expansion of f(1), the 2nd row contains the decimal expansion of f(2), . . . the nth row contains the decimal expansion of f(n), . . . Perhaps f(1) = (π/10) , f(2) = (37/99), f(3) = (1/7), f(4) =((Sqrt[2])/2), f(5) = (3/8), so that the table starts out like this.

Grid[{
{Item["n",Background->White],"f(n)"},
{1,"0 . 3 1 4 1 5 9 2 6 5 3 ⋯"},
{2,"0 . 3 7 3 7 3 7 3 7 3 7 ⋯"},
{3,"0 . 1 4 2 8 5 7 1 4 2 8 ⋯"},
{4, "0 . 7 0 7 1 0 6 7 8 1 1 ⋯"},
{5, "0 . 3 7 5 0 0 0 0 0 0 0 ⋯"},
{⋮,⋮}
}
,Dividers->{{False,True},{False,True}}]

Of course, only part of the table can be shown on a piece of paper — it goes on forever down and to the right.

Can f possibly be onto? That is, can every number in [0, 1] appear somewhere in the table? 

In fact, the answer is no — there are lots and lots of numbers that can’t possibly appear! For example, let’s underline the digits in the main diagonal of the table.

Grid[{
{Item["n",Background->White],"f(n)"},
{1,"0 . \!\(\*
StyleBox[\"3\",\nFontVariations->{\"Underline\"->True}]\)\!\(\*
StyleBox[\" \",\nFontWeight->\"Plain\"]\)1 4 1 5 9 2 6 5 3 ⋯"},
{2,"0 . 3 \!\(\*
StyleBox[\"7\",\nFontVariations->{\"Underline\"->True}]\) 3 7 3 7 3 7 3 7 ⋯"},
{3,"0 . 1 4 \!\(\*
StyleBox[\"2\",\nFontVariations->{\"Underline\"->True}]\) 8 5 7 1 4 2 8 ⋯"},
{4, "0 . 7 0 7 \!\(\*
StyleBox[\"1\",\nFontVariations->{\"Underline\"->True}]\) 0 6 7 8 1 1 ⋯"},
{5, "0 . 3 7 5 0 \!\(\*
StyleBox[\"0\",\nFontVariations->{\"Underline\"->True}]\) 0 0 0 0 0 ⋯"},
{⋮,⋮}
}
,Dividers->{{False,True},{False,True}}]

The underlined digits are 0.37210 . . . . Suppose that we add 1 to each of these digits, to get the number: 0.48321 . . . .

Now, this number can’t be in the table. Why not? Because:

• it differs from f(1) in its first digit;
• it differs from f(2) in its second digit;
• ⋯
• it differs from f(n) in its nth digit;
• ⋯

So it can’t equal f(n) for any n — that is, it can’t appear in the table

Precisely that the function f can’t possibly be onto — there will always be (infinitely many!) missing values. Therefore, there does not exist a bijection between N and [0,1].

□

Binary digits as uncountable set

If (Subscript[s, 1]), (Subscript[s, 2]), … , (Subscript[s, n]), … is any enumeration of elements from T - set of all infinite sequences of binary digits (i.e. consisting only of zeroes and ones), then there is always an element s of T which corresponds to no (Subscript[s, n]) in the enumeration.

To prove this, given an enumeration of arbitrary members from T, like e.g.

(Subscript[s, 1]) = (0, 0, 0, 0, 0, 0, 0, ...)
(Subscript[s, 2]) = (1, 1, 1, 1, 1, 1, 1, ...)	
(Subscript[s, 3]) = (0, 1, 0, 1, 0, 1, 0, ...)	
(Subscript[s, 4]) = (1, 0, 1, 0, 1, 0, 1, ...)
(Subscript[s, 5]) = (1, 1, 0, 1, 0, 1, 1, ...)
(Subscript[s, 6]) = (0, 0, 1, 1, 0, 1, 1, ...)
(Subscript[s, 7]) = (1, 0, 0, 0, 1, 0, 0, ...)
...

he constructs the sequence s by choosing its nth digit as complementary to the nth digit of (Subscript[s, n]), for every n. In the example, this yields:

(Subscript[s, 1]) = (0, 0, 0, 0, 0, 0, 0, ...)
(Subscript[s, 2]) = (1, 1, 1, 1, 1, 1, 1, ...)	
(Subscript[s, 3]) = (0, 1, 0, 1, 0, 1, 0, ...)	
(Subscript[s, 4]) = (1, 0, 1, 0, 1, 0, 1, ...)
(Subscript[s, 5]) = (1, 1, 0, 1, 0, 1, 1, ...)
(Subscript[s, 6]) = (0, 0, 1, 1, 0, 1, 1, ...)
(Subscript[s, 7]) = (1, 0, 0, 0, 1, 0, 0, ...)
...

s =  (1, 0, 1, 1, 1, 0, 1, ...)

By construction, s differs from each (Subscript[s, n]), since their nth digits differ (highlighted in the example). Hence, s cannot occur in the enumeration.

Based on this theorem, Cantor then uses an indirect argument to show that:

The set T is uncountable.

He assumes for contradiction that T was countable. Then (all) its elements could be written as an enumeration (Subscript[s, 1]), (Subscript[s, 2]), … , (Subscript[s, n]), … . Applying the previous theorem to this enumeration would produce a sequence s not belonging to the enumeration. However, s was an element of T and should therefore be in the enumeration. This contradicts the original assumption, so T must be uncountable.

□

Dynamic[Ceiling[pt/6.0]]

This is Cantor Diagonalization argument  demonstration, just run the code below in case opens with error. 

The Cyan square is your mouse in the plot below, it picks up each rows of 1s and 0s and compares it to the diagonalization which is diagonal flipped i.e. 1->0 and 0->1. You see no matter which row you choose there is no match between the row and the diagonalization since exactly at [i,i] the two are different (green or red 1 or 0).

m1[]:=DynamicModule[{},

Panel@Column[{
Button["Again",
{i,j}={50,50};
table=RandomInteger[{0,1}, {1000,1000}]+Table[If[ii==jj,2,0],{ii,1,1000},{jj,1,1000}];
mat=table[[1;;110,1;;110]];
diag=Diagonal[mat]-2;
pt={i,j};],

LocatorPane[Dynamic[pt],Dynamic@Column[{"Diagonalization: Red=0, Green=1",
(*"Row",
(*swap i j *)
{j,i}=Ceiling[pt/6.0];Dynamic[Row[mat[[If[i==0,111-1,111-i]]]/.{2->Text[Style[1,Green]],3->Text[Style[0,Red]]}]],
"Diagonalization",
Row[diag],*)
Tooltip[ArrayPlot[mat, ColorFunction->(Which[ #==0,Black, #==1,White,  #==2,Red, #==3,Green ]&),ColorFunctionScaling->False,Mesh->True,ImageSize->700,PixelConstrained->True],Column[{"Row",{j,i}=Ceiling[pt/6.0];Dynamic[Row[mat[[If[i==0,111-1,111-i]]]/.{2->Text[Style[1,Green]],3->Text[Style[0,Red]]}]], "Diagonalization",Row[diag]}]]}],Appearance->Graphics[Style[Rectangle[],Cyan],
ImageSize->{7}],AutoAction->True]}],

Initialization:>({i,j}={50,50};table=RandomInteger[{0,1}, {1000,1000}]+Table[If[ii==jj,2,0],{ii,1,1000},{jj,1,1000}];
mat=table[[1;;110,1;;110]];
diag=Diagonal[mat]-2;
pt={i,j};)
]

m1[]

2. Enumerating the rationals

One of the methods to enumerating the positive rationals is:

1) generate a two-dimensional matrix (an infinite list of infinite lists);
2) traverse its finite diagonals (an infinite list of finite lists)

Each row of the matrix has the positive rationals with a given denominator, and each column those with a given numerator:

Grid[{{Style["(1/1)",Large],Style["(2/1)",Large],Style["(3/1)",Large],Style["...",Large],Style["(m/1)",Large],Style["...",Large]},
{Style["(1/2)",Large],Style["(2/2)",Large],Style["(3/2)",Large],Style["...",Large],Style["(m/2)",Large],Style["...",Large]},
{Style["⋮",Large]},
{Style["(1/n)",Large],Style["(2/n)",Large],Style["(3/n)",Large],Style["...",Large],Style["(m/n)",Large],Style["...",Large]},
{Style["⋮",Large]}
},Spacings->{2,2},ItemStyle->Bold]

Below we can consider example for m = n = 11 (or 12 depends on static size).

m2[]:=DynamicModule[{k},

Manipulate[
Module[{
fullFractions=Table[{n,d},{n,1,12},{d,1,12}],
fractions,(*list of all the fractions*)
i=1,j=1,
fullVertexList={},
vertexList={},edgeList={},coordinateList={},labelList={},
graph,
stage=1,
size,
f(*used as a symbolic head*)
},
k=Min[k,If[repeatFractions,78,57]];
While[0<i≤12&&0<j≤12,
If[GCD[j,i]==1 ||repeatFractions,AppendTo[fullVertexList,f[j,i]]];
Catch[
If[stage==1,j++;stage=2;Throw[Null]];
If[stage==2,i++;j--;If[j==1,stage=3];Throw[Null]];
If[stage==3, i++;stage=4;Throw[Null]];
If[stage==4,i--;j++;If[i==1,stage=1];Throw[Null]];
]
];
size=If[staticSize,12,Max[Apply[Max,fullVertexList[[;;k]],{0,1}],6]];
fractions=Flatten[Map[#[[;;size]]&,fullFractions,{0,1}],1];
vertexList=fullVertexList[[;;Position[fullVertexList,a_f/;Sort[List@@a]=={1,size}][[-1,1]]]];
edgeList=Table[Null,{Length[vertexList]-1}];
For[i=1,i<Length[vertexList],i++,
edgeList[[i]]=vertexList[[i]]\[DirectedEdge] vertexList[[i+1]]];
coordinateList={#[[1]],size-#[[2]]+1}&/@fractions;
labelList=Map[#->Placed[
If[reduceFractions,
ToString[Divide@@#,InputForm],
StringJoin@@Insert[ToString/@#,"/",2]
],Above]&,f@@@fractions];
graph=Graph[
f@@@fractions,(*list of verticies*)
edgeList,(*list of edges (arrows between fractions)*)
VertexCoordinates->coordinateList,(*placement of verticies*)
VertexLabels->labelList,(*labeling the verticies*)
ImageSize->{400,400},PlotRange->Table[{1-size/10,11size/10},{2}]];
k=Min[k,If[repeatFractions,78,57]];
Text@Column[{
Style["\tindex value: "<>ToString[k]<>"\trational: "<>
(If[reduceFractions,ToString[Divide@@#,InputForm],StringJoin@@Insert[ToString/@#,"/",2]]&@vertexList[[k]]),FontSize->12],
HighlightGraph[graph,{Style[Join[vertexList[[;;k-1]],edgeList[[;;k-1]]],Green],Style[vertexList[[k]],Yellow]}]
},Alignment-> Center]
],
Control[{{k,1,"rational numbers enumerated"},1,Dynamic[If[repeatFractions,78,57],Initialization->5],
1,ImageSize->Medium,Appearance->"Labeled",ControlPlacement->Top}],
"repeat fractions",
{{repeatFractions,False,""},{True,False}},
"reduce fractions",
{{reduceFractions,False,""},{True,False}},
"static size",
{{staticSize,False,""},{True,False}},
ControlPlacement->Left
]


]

m2[]

All very well, but the resulting enumeration of the positive rationals contains duplicates. Iin fact, infinitely many duplicates of every rational.

Theorem 2.1 The set of natural numbers and the set of positive rationals have the same cardinality.

Proof:
The positive rationals can only have the same cardinality as the natural numbers if they can be put into a one-to-one correspondence with the natural numbers (i.e., if a bijection between the sets can be found). Putting the positive rationals into a one-to-one correspondence with the natural numbers is equivalent to “listing” all of the positive rationals with no duplications. In this way, 1 is paired with the first element of the list, 2 is paired with the second element of the list, 3 is paired with the third, and so on... If all of the rationals show up in the list, we are guaranteed the implied function is surjective (i.e., “onto”). If there are no duplicates in the list, we are guaranteed the implied function is injective.

Consider the following infinite table, which clearly contains all of the postive rationals (with some duplicates upon considering reducing things to lowest form). Suppose we list the positive rationals in the following way. Starting with the upper left corner, snake back and forth along the diagonals as shown below. Exactly the same as we have on plot above.
Writing down the fractions as they appear on this path, being careful to skip any (reducible) fractions that would have previously appeared in the list. 

So we can see the first few elements of this list (and hence, the first few elements of the one-to-one correspondence with the natural numbers) would be...

Grid[{{"ℕ","(SuperPlus[ℚ])"},
{1,"1/1"},
{2,"2/1"},
{3,"1/2"},
{4,"1/3"},
{5,"3/1"},
{6,"4/1"},
{7,"3/2"},
{8,"2/3"},
{9,"1/4"},
{10,"1/5"},
{"⋮","⋮"}
},Dividers->Center]

Every positive rational number eventually shows up in the list on the right, and (by design) there are no duplicates.

Thus, there is a bijection between the positive rationals and the natural numbers. Consequently, these two sets to have the same cardinality.

□

Except above method there are also three well-known sequences used to enumerate the rationals: the Stern-Brocot sequences (Subscript[SB, n]), the Calkin-Wilf sequences (Subscript[CW, n]), and the Farey sequences (Subscript[F, n]).

2.1. Stern–Brocot tree

(0/1) is a fraction while (1/0) is not. However, using it as such helps describe a way to get all possible positive fractions arranged in a very nice manner. So disguising (1/0) as a fraction has a very good excuse.

Definition 3.1. The mediant of two fractions ((Subscript[m, 1])/(Subscript[n, 1])) and ((Subscript[m, 2])/(Subscript[n, 2])) is, by definition, the fraction (((Subscript[m, 1]) + (Subscript[m, 2]))/((Subscript[n, 1])+ (Subscript[n, 2]))). 

So, for example, from (0/1) and (1/0) we get (1/1) = 1. Which is the topic point on the plot below.

 The mediant of  (0/1) and (1/1) is (1/2) (that gives the second value on the left, ftom the top) while the mediant of (1/1) and (1/0)  is (2/1) = 2. 
 
 On the next stage of the construction, we form four new fractions: (1/3)  from (0/1)  and (1/2) , whereas (2/3)  from (1/2)  and (1/1) , (3/2)  from (1/1)  and (2/1) , and, finally, the mediant of (2/1)  and (1/0)  which is (3/1) . 
 
 Continuing this way we get an infinite tree known as the Stern-Brocot tree because it was discovered independently by the German mathematician Moriz Stern (1858) and by the French clock maker Achille Brocot (1860).

m3[]:=DynamicModule[{},

Manipulate[SternBrocotGraphics[j,6],
{{j,1,"enumeration index"},1,-1+2^6,1},SaveDefinitions->True,AutorunSequencing->{{1,15}}],

Initialization:>(SternBrocotGraphics[j_,mm_:6]:=Graphics[{Gray,Union[Flatten[Table[{Line[#]&/@Transpose[{Most[#],Rest[#]}]}&[theSternBrocotLine[jj,mm]],{jj,2,-1+2^mm}]]],RGBColor[1,.47,0],Thickness[.007],Line[theSternBrocotLine[j,mm]],Black,theSternBrocotTree[mm,j]},
ImageSize->{500,431},AspectRatio->1/GoldenRatio,PlotRange->All];
theSternBrocotTree[mm_,j_:0]:=Text[FromSternBrocot[#],theSternBrocotCoordinate[#,mm],{0,0},Background->If[#==j,RGBColor[1,.71,0],White]]&/@Range[-1+2^mm];
theSternBrocotCoordinate[u_,r_]:=With[{ii=Length[IntegerDigits[u,2]]},{-3+2^(1-ii)*(1+2*u),(1-ii)/(1+r)}];
theSternBrocotLine[n_,t_]:=Prepend[With[{sb=ToSternBrocot[n]},MapIndexed[theSternBrocotCoordinate[FromDigits[Flatten[{1,Take[sb,#2[[1]]]}],2],t]&,sb]],{0,0}];
FromSternBrocot[sb_List]:=Rational@@({1,1}.(Dot@@((Reverse@sb)/.{0->{{1,1},{0,1}},1->{{1,0},{1,1}}})));
FromSternBrocot[n_Integer]:=FromSternBrocot[ToSternBrocot[n]];
ToSternBrocot[Times[rn_,Power[rd_,-1]],maxt_:64]:=ToSternBrocot[List[rn,rd],maxt];
ToSternBrocot[(List|Rational)[rn_,rd_],maxt_:64]:=Module[{st=1,m=Abs[rn],n=Abs[rd]},
Reap[While[And[Unequal[m,n],st<maxt],st=1+st;If[m <n,Sow[0];n=n-m,Sow[1];m=m-n]]]][[2,1]];
ToSternBrocot[n_Integer]:=Rest[IntegerDigits[n,2]];
ToSternBrocotIndex[n_Integer]:=FromDigits[Flatten[{1,ToSternBrocot[{n,1}]}],2];
ToSternBrocotIndex[sb_List]:=FromDigits[Flatten[{1,sb}],2];)

]

m3[]

3. The Infinite Hotel Paradox

Hilbert’s paradox of the Grand Hotel is a veridical paradox (a valid argument with a seemingly absurd conclusion, as opposed to a falsidical paradox, which is a seemingly valid demonstration of an actual contradiction) about infinite sets meant to illustrate certain counterintuitive properties of infinite sets. The idea was introduced by David Hilbert in a lecture he gave in 1924 and was popularized through George Gamow’s 1947 book “One Two Three... Infinity”.

Let us imagine a hotel with a finite number of rooms, and assume that all the rooms are occupied. A new guest arrives and asks for a room. “Sorry,” says the proprietor, “but all the rooms are occupied.” Now let us imagine a hotel with an infinite number of rooms, and all the rooms are occupied. To this hotel, too, comes a new guest and asks for a room.

“But of course!” exclaims the proprietor, and he moves the person previously occupying room N1 into room N2, the person from room N2 into room N3, the person from room N3 into room N4, and so on....Therefore every gest moved from room n to room n+1.

n ⟶ n+1

Since there are infinite number of rooms there is a new room for each existing guest. That and the new customer receives room N1, which became free as the result of these transpositions.

Similar situation we will get if to this hotel will came a finite number of frends c, let us assume that c = 10. In this case the person previously occupying room N1 goes into room N11, the person from room N2 moves into room N12. And so on.... and those group of friends have 10th first rooms free.

n ⟶ n+c

(For visualization above two cases see "finite" in panel below.)

Let us imagine now a hotel with an infinite number of rooms, all taken up, and an infinite number of new guests who come in one infinite long bus and ask for rooms.

"Certainly, gentlemen," says the proprietor, "just wait a minute."

He moves the occupant of N1 into N2, the occupant of N2 into N4, and occupant of N3 into N6, and so on, and so on... Each current quest moves from room number n to room number 2n, filling all even number of rooms. Now all odd-numbered rooms became free and the infinite of new guests can easily be accommodated in them.

n ⟶ 2n

However if we get finite group of buses b with infinite numbers of people inside, let assume that b = 3. Then to solve a proprietor problem we need to move people from room number n to room number (3+1)n. For example person from room N1 moves to room N4, the person from room N2 goes  to room N8. And so on.... Therfore we have rooms N1, N2, N3 for all 1st guests from each buses(bus 1, bus 2 and bus 3, because we condiser b=3) and rooms N5, N6, N7 for all 2nd guests from each buses.....and so forth.

n ⟶ (b+1)n

(For visualization above two cases see “finite x infinity” in panel below.)

However let us consider now that infinite line of infinitely large buses each with an countable infinite numbers of pasangers who want to visit this hotel with an infinite number of rooms, all taken up.

Again, the proprieter says "Please, step inside!"

How is it possible? To do this we can use many methods, however here we consider Triangular number method. We start from people which are already in the hotel. Those people will be moved to the nth trianglular number grater then 0. For example person from room N1 stays in same room because 1 is the 1st triangular number from our set of triangular numbers. Subsequently person from room N2 moves to room N3, the person from N3 moves to room N6, the person from N4 moves to room N10, etc.

Afterwards we need to located in the hotel guests from buses. Let us assume that b is a number of bus and p number of place in each bus. To give apropriate room for a people from buses, at first we need to add a number (b + p - 1) to the room number which are occupied rooms now(after using triangular method). For example, occupied rooms are N1, N3, N6, N10,...
To locate 1st guest p=1 from first bus b=1, to number 1 (N1) we have to add (b+p-1) = (1 + 1 - 1) = 1, that gives 1 + 1 = 2. Therfore he moves to room N2.
To locate 2nd guest p=2 from first bus b=1, to number 3 (N3) we have to add (b+p-1) = (1 + 2 - 1) = 2, that gives 3 + 2 = 5. Therfore he moves to room N5.
To locate 3rd guest p=3 from first bus b=1, to number 6 (N6) we have to add (b+p-1) = (1 + 3 - 1) = 3, that gives 6 + 3 = 9. Therfore he moves to room N9.
etc.

Now guests from 1st bus occupied rooms N2, N5, N9,... To locate people from 2nd bus we have to add (b + p - 1) to the numbers of rooms which are occupied by guests from 1st bus.
To locate 1st guest p=1 from 2nd bus b=2, to number 2 (N2) we have to add (b+p-1) = (2 + 1 - 1) = 2, that gives 2 + 2 = 4. Therfore he moves to room N4.
To locate 2nd guest p=2 from 2nd bus b=2, to number 5 (N5) we have to add (b+p-1) = (2 + 2 - 1) = 3, that gives 5 + 3 = 8. Therfore he moves to room N8.
To locate 3rd guest p=3 from 2nd bus b=2, to number 9 (N9) we have to add (b+p-1) = (2 + 3 - 1) = 4, that gives 9 + 4 = 13. Therfore he moves to room N13.
etc.

Afterwards in each subsequent bus we need to add number (b + p - 1) to the numbers of rooms which are occupied by guests from previous bus. For example for finding numbers of rooms for guests from bus number 3 (b=3) we have to take numbers of occuiped rooms for guests from bus number 2 and to those numbers add (3 + p -1), for finding numbers of rooms for guests from bus number 4 (b=4) we have to take numbers of occuiped rooms for guests from bus number 3 and to those numbers add (4 + p -1),.... and so on.
(For visualization above case see “infinity x infinity” in panel below.)

How we can be sure that this method is well define? See for example in panel below case “infinity x infinity”. Notice how numbers in table behave. If we consider snake’s moves start from 1, go one step down to 2 and move diagonally upwards to 3. Then again back to 4 and again move diagonally upwards to 6,... and so one, We realise that above algorith cover all natural numbers, with no possibility of repeat any number. Therfore it is well define.


This paradax only deals with the lovest level of infinity. Namely the countable infinity of the natural numbers, like 1, 2, 3, 4 ... . Cantor called this level of infinity (Subscript[𝒩, 0]). If we use the real numbers as a possible labels for numbers of rooms or seats in the bus this situation will no longer be possible.

(*FIXME: the local vars *)
m4[]:=DynamicModule[{},

Manipulate[
Pane[
Style[TraditionalForm@Text@Switch[choose,
finite,
Column[{
"full hotel",Grid[Transpose@Append[Prepend[Table[{i,Subscript[g,i]},{i,1,n}],{"room","guest"}],{"⋯","⋯"}]],
"new guests",
Row[Riffle[Table[Subscript[T,j],{j,1,k}],", "]],
"new guests in full hotel",
Grid[Transpose@Append[Prepend[Table[{m,If[m<=k,Subscript[T,m],Subscript[g,m-k]]},{m,1,k+n}],{"room","guest"}],{"⋯","⋯"}]]
},Center,Background->{{LightBlue,None}},Dividers->{{True,True},{True,False,True,False,True,False,True}}
],
inf1,
table2=Table[Subscript[F,j1,j2],{j1,1,k},{j2,1,n}];
Column[{
"full hotel",Grid[Transpose@Append[Prepend[Table[{i,Subscript[g,i]},{i,1,n}],{"room","guest"}],{"⋯","⋯"}]],
"new guests",
Grid[Append[#,"⋯"]&/@table2],
"new guests in full hotel",
Grid[Transpose@Insert[Take[Prepend[
Transpose[
{
Table[i,{i,1,(k+1)n}],

Flatten@Transpose@Join[table2,{Table[Subscript[g,i],{i,1,n}]}]
}
],
{"room","guest"}],n+1],{"⋯","⋯"},-1]]
},Center,Background->{{LightBlue,None}},Dividers->{{True,True},{True,False,True,False,True,False,True}}
],
inf2,
table2=Table[Subscript[S,j1,j2],{j1,1,k},{j2,1,n}];
Column[{
"full hotel",Grid[Transpose@Append[Prepend[Table[{i,Subscript[g,i]},{i,1,n}],{"room","guest"}],{"⋯","⋯"}]],
"old and new guests aboard ship",
Grid[Append[Append[#,"⋯"]&/@Prepend[table2,Table[Subscript[g,i],{i,1,n}]],
Table[⋮,{j2,1,n}]]],
"room numbers for old and new guests",
Grid[Append[Append[#,"⋯"]&/@Transpose[Reverse@Table[PairingFunction1[j1,j2],{j1,n,1,-1},{j2,k+1}]],
Table[⋮,{j2,1,n}]]]
},Center,Background->{{LightBlue,None}},Dividers->{{True,True},{True,False,True,False,True,False,True,False,True}}
]
],
FontSize->16],
ImageSize->{450,400}
],{{choose,finite,"number of new guests"},{finite->"finite",inf1->" finite × infinite ",inf2->" infinite × infinite "}},
{{k,3,"new guests"},1,5,1,Appearance->"Labeled"},
{{n,4,"width"},1,8,1,Appearance->"Labeled"},
SaveDefinitions->True, TrackedSymbols->{k,n,choose}
],

Initialization:>(PairingFunction1[i_,j_]:=(i+j-2)(i+j-1)/2+i;)

]

m4[]