I have a lot of concrete experience and have been a QC inspector, with many training courses. If the slab froze in spite of the calcium (which nobody but amateurs use anymore) you have potential for structural failure. The plant would not have provided air-entertainment w/o it being in the order. Besides air only protects downstream after the hydration is complete. Your remedy is of a cost beyond the award capability of a small claims court.
It cost twice as much or more to remove the existing which you have a good case for demanding; so, you have that as a lever on the contractor. Yes, the blame is on the contractor. I assume he is a small business guy without any extra resources, under insured, or not insured for errors and omissions. Naturally you did not require a performance bond. You are in a good negotiating position for total replacement. If I was your QC faced with this conundrum; I would advise you: Sandblast the entire surface and remove all dust and loose particles, add a new form on top for a complete new slab same thickness as previous, install reinforcing, and construction joints making sure it is on chairs not being lifted through the concrete, you order the concrete not your finisher (more on that later), do not add water on site that is in excess of the plant mix design, finish, cut control joints (1/3 deep as slab is thick) approx every 12' each way as right then not the next day. Cold weather (below 40 degrees) cover with insulating blankets after spraying curing compound. If you finisher poo poos all this find a new one or convince him to learn your way. Quality concrete work is not el cheapo work especially in cold or hot weather.
Concrete Mix. Discuss with the batch plant mix engineer your situation and get their advice on additives to help prevent freezing, water reducing to help finishing low slump concrete (that is why back water finishers add extra water). If the building will be open for an extended period of future freezing weather the add 4-5% air. 4000 PSI strength is plenty for a slab on grade support by a solid sub-grade (your deficient slab). Strongly consider using synthetic fiber instead of steel reinforcing. Do not waste money on wire mesh unless it is solidly installed on chairs and is not walked on. Contrary to popular opinion you cannot stand there and lift it with a hook and have in the right place. Any reinforcing needs to be 2" from the bottom of the slab.
Calcium: That is old school, the concrete will weep salt crystal to the surface for a long time every time it gets wet, lowers concrete strength, and corrodes reinforcing and surface mounted metals. I am surprised the batch plant even did it as it is a no no today.
Plus: It will cost the contractor 1/2 or less to top a new slab than tear-out of the previous. If he wants to got to court be sure and get your credentialed concrete expert witness and ope your wallet for your lawyer.
Concrete is now a science that is mature but improvements occur every year, experimentation and testing are a continuous process. Become the resident expert: go to Amazon books and buy "The Contractors Guide to Quality Concrete Construction" It is only $83, cheap education. I have given many away to friends planning concrete work.
Ron