(1) 27 embeddings:
{1,2,3}→
{(1,1,1),(1,1,2),(1,1,3),(2,1,1),(2,1,2),(2,1,3),(3,1,1),(3,1,2),(3,1,3),
((1,2,1),(1,2,2),(1,2,3),(2,2,1),(2,2,2),(2,2,3),(3,2,1),(3,2,2),(3,2,3),
(1,3,1),(1,3,2),(1,3,3),(2,3,1),(2,3,2),(2,3,3),(3,3,1),(3,3,2),(3,3,3)}
(2) Number of embeddings=nⁿ where n is the set size=2020.
Each element of the set can map to itself and to each of the other elements (n mappings for each element) and the mapping of each of the n elements is independent of the others, giving nⁿ combinations in total.
(3) Compressions (f(a)≤a):
f(1)=1⇒f(a)=a, f(2)=1⇒f(a)<a, f(3)=1⇒f(a)<a
f(1)=2⇒f(a)>a, f(2)=2⇒f(a)=a, f(3)=2⇒f(a)<a
f(1)=3⇒f(a)>a, f(2)=3⇒f(a)>a, f(3)=3⇒f(a)=a
If we exclude all cases where f(a)>a we are left with:
f(1)=1, f(2)=1, f(3)=1, f(2)=2, f(3)=2, f(3)=3 (6 functions)
(4) For {1,2,...,2020}, f(1)=1, f(1)<2,...2020 (2020 for f(1)); f(2)=2, f(2)<3,... (2019 for f(2)); ...; f(2020)=2020 (1 for f(2020)). The sum of natural numbers between 1 and 2020 is 2020×2021/2=2041210 compressions.
(5) Consider the cases where x<y:
Case A: (x,y)=(1,2)
Case B: (x,y)=(1,3)
Case C: (x,y)=(2,3)
Implications of f(x)≥f(y):
Case A: f(1)=1⇒f(2)=1; f(1)=2⇒f(2)=1 or 2; f(1)=3⇒f(2)=1, 2 or 3
Case B: f(1)=1⇒f(3)=1; f(1)=2⇒f(3)=1 or 2; f(1)=3⇒f(3)=1, 2 or 3
Case C: f(2)=1⇒f(3)=1; f(2)=2⇒f(3)=1 or 2; f(2)=3⇒f(3)=1, 2 or 3
We now need to combine these cases:
f(1)=1⇒f(2)=1⇒f(3)=1 (1 function)
f(1)=2⇒[f(2)=1⇒f(3)=1] or [f(2)=2⇒f(3)=1 or 2] (3 functions)
f(1)=3⇒[f(2)=1⇒f(3)=1] or [f(2)=2⇒f(3)=1 or 2] or [f(2)=3⇒f(3)=1, 2 or 3] (6 functions). This gives us 10 decreasing functions in all.
(6) Where we have one of the 6 functions in (3) not included in the functions in (5), we have a counterexample: f(1)=1 and f(3)=3 (because, if x=1 and y=3, x<y but f(x)<f(y)—not decreasing).
(7) Where we have one of the 10 functions in (5) not included in (3), we have a counterexample: f(1)=f(2)=f(3)=3 (because f(a)=a only when a=3, but f(a)>a otherwise—so not compression).