Skolem dostrzegł również paradoksalne konsekwencje twierdzenia Löwenheima-Skolema formułowane w postaci tak zwanego paradoksu Skolema-Löwenheima: jeśli aksjomatyka Zermela jest niesprzeczna, to teoria mnogości musi mieć model przeliczalny, choć dowodzi się w niej istnienia zbiorów nieprzeliczalnych.
Prostym wnioskiem z rezultatów uzyskanych przez Skolema jeszcze w latach 20. XX wieku jest twierdzenie o pełności klasycznego rachunku logicznego. Sam Skolem nie podniósł jednak tego faktu, być może dlatego, że matematycy zaczęli przywiazywać wagę do problemu pełności teorii dopiero od momentu ukazania się pracy Hilberta i Ackermanna. Jako pierwszy dowód pełności klasycznego rachunku logicznego podał Kurt Gödel w dysertacji doktorskiej w roku 1929.
W roku 1923 Skolem opracował teorię arytmetykę pierwotnie rekurencyjną, która była jednym z przyczynków do stworzonej później teorii funkcji rekurencyjnych. Myślą przewodnią jego badań była próba sformułowania teorii wolnej od paradoksów płynących z pojęcia nieskończoności. Skolem rozwinął arytmetykę liczb naturalnych definiując jej obiekty za pomocą rekurencji pierwotnej, a następnie konstruując system wyższego rzędu dla dowodu własności systemu wyjściowego.