#Haskell, 94 87 82 bytes

f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]

this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.

this solution assumes the input is sorted.

proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i.

take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice.

this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.

Edit: five bytes off thanks to Ørjan Johansen!

Haskell, 94 87 82 bytes

f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]

this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.

this solution assumes the input is sorted.

proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i.

take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice.

this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.

Edit: five bytes off thanks to Ørjan Johansen!

#Haskell, 94 87 bytes

f s=and[j i-2<j(i-x)|i<-[1..2*last s],x<-s,x<i]where j 1=0;j i=1+j(i-last(filter(<i)s))

this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.

this solution assumes the input is sorted.

proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i.

take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice.

this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.

#Haskell, 94 87 82 bytes

f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]

this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.

this solution assumes the input is sorted.

proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i.

take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice.

this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.

Edit: five bytes off thanks to Ørjan Johansen!

#Haskell, 94 bytes

f s=and[all(j i-2<)[j$i-x|x<-s,x<i]|i<-[1..2*last s]]where j 0=0;j i=1+j(i-last(filter(<=i)s))

this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.

this solution assumes the input is sorted.

proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i.

take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice.

this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.

#Haskell, 94 87 bytes

f s=and[j i-2<j(i-x)|i<-[1..2*last s],x<-s,x<i]where j 1=0;j i=1+j(i-last(filter(<i)s))

this solution works by defining a function j which perform's the cashier's algorithm and tells us how many coins the cashier used. we then check up to twice the biggest number in the list, assuming that the system has been canonical for all previous numbers, that taking the biggest possible coin is the right choice.

this solution assumes the input is sorted.

proof checking up to twice the biggest number is enough: assume that the system is not canonical for some number i, and let k be the biggest number in the list not bigger than i. assume that i >= 2k and the system is canonical for all numbers less than i.

take some optimal way to make i out of coins, and assume it doesn't contain the coin k. if we throw away one of the coins, the new sum of coins must be bigger than k and smaller than i - but the cashier's algorithm on this number would use the k coin - and therefore, this set of coins can be replaced with an equal set of coins containing the coin k, and therefore there is a set of coins containing the coin k for the number i, and by induction the cashier's algorithm returns the optimal choice.

this argument really shows that we only need to check until the sum of the two biggest elements - but it is lengthier to do so.