Ausschaffungshaft (Art. 13b ANAG), hat sich ergeben:
A.- Der nach seinen letzten Angaben aus Litauen stammende A._ (geb. **. **. 1978; alias B._, geb. **.** 1984) reiste in einem Lastwagen versteckt illegal in die Schweiz ein und wurde hier am 3. September 2001 bei einem Ladendiebstahl angehalten. In der Folge wiesen ihn die Einwohnerdienste des Kantons Basel-Stadt formlos weg und nahmen ihn in Ausschaffungshaft. Der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Verwaltungsgericht des Kantons Basel-Stadt prüfte diese am 5. September 2001 und genehmigte sie bis zum 2. Dezember 2001.
B.- A._ gelangte hiergegen mit einer in Russisch abgefassten Eingabe, welche von Amtes wegen übersetzt wurde, an das Bundesgericht (Beschwerdeeingang: 12. September 2001); er ersucht darin sinngemäss um Haftentlassung. Er wolle, dass "alles noch einmal angeschaut" werde. Er könne nicht in die Ukraine zurückkehren, da sein Kollege und er dort eine grosse Summe Geld "geborgt" hätten. Er wolle mehr "Ausgang und mehr Luft".
Der Einzelrichter für Zwangsmassnahmen im Ausländerrecht und die Einwohnerdienste des Kantons Basel-Stadt beantragen, die Beschwerde abzuweisen. Das Bundesamt für Ausländerfragen liess sich nicht vernehmen. A._ machte von der Möglichkeit keinen Gebrauch, sich noch einmal zu äussern.
C.- Mit Schreiben vom 24. September 2001 wurde vom Bundesamt für Flüchtlinge ein Amtsbericht zur Frage eingeholt, ob ein gültiges Asylgesuch vorliege, was dieses mit Antwort vom 1. Oktober 2001 verneinte. Der entsprechende Bericht ist A._ am 3. Oktober 2001 über die Einwohnerdienste des Kantons Basel-Stadt zur Kenntnis gebracht worden.

Das Bundesgericht zieht in Erwägung:
1.- Die Verwaltungsgerichtsbeschwerde hat die Begehren, deren Begründung mit Angabe der Beweismittel und die Unterschrift des Beschwerdeführers oder seines Vertreters zu enthalten (Art. 108 Abs. 2 OG). Sie muss sich sachbezogen mit dem angefochtenen Entscheid auseinander setzen (<ref-ruling> ff.). Bei Laienbeschwerden gegen die Genehmigung der Ausschaffungshaft stellt das Bundesgericht indessen keine hohen Anforderungen an die Beschwerdebegründung (vgl. <ref-ruling> E. 3b S. 277). Ist daraus - wie hier - ersichtlich, dass sich der Betroffene (zumindest auch) gegen seine Haft wendet, nimmt es entsprechende Eingaben als Verwaltungsgerichtsbeschwerden entgegen. Gegenstand des Verfahrens bildet dabei jedoch ausschliesslich die Rechtmässigkeit der ausländerrechtlichen Administrativhaft, nicht auch die Asyl- bzw. Wegweisungsfrage (vgl. Art. 100 Abs. 1 lit. b Ziff. 4 OG). Die Zulässigkeit des Wegweisungsentscheids wird vorfrageweise nur berücksichtigt, wenn dieser als offensichtlich rechtswidrig zu gelten hat (vgl. <ref-ruling> E. 2c S. 61).
2.- Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, soweit die Voraussetzungen von Art. 13b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2a S. 61; <ref-ruling> E. 1 S. 150 f.), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist. Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 1 S. 3), die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. dazu BGE <ref-ruling> E. 3 S. 152 ff.) und die Papierbeschaffung mit dem nötigen Nachdruck verfolgt werden (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.).
3.- a) Der Beschwerdeführer ist am 4. September 2001 formlos weggewiesen worden; dieser Entscheid ist nicht offensichtlich rechtswidrig, obwohl der Beschwerdeführer während seines Aufenthalts in der Schweiz wiederholt den Ausdruck "Asyl" gebraucht hat: Nach Art. 18 und 19 des Asylgesetzes vom 26. Juni 1998 (SR 142. 31) gilt als Asylgesuch jede Äusserung, mit der eine Person bei einer schweizerischen Vertretung, an einem geöffneten Grenzübergang oder an einer Empfangsstelle zu erkennen gibt, dass sie die Schweiz um Schutz vor Verfolgung ersucht (vgl. Mario Gattiker, Das Asyl- und Wegweisungsverfahren, Bern 1999, S. 22). Ist auch grundsätzlich davon auszugehen, dass an die entsprechende Erklärung keine allzu hohen Anforderungen zu stellen sind, durften die kantonalen Behörden hier doch annehmen, dass bis zur formlosen Wegweisung kein solches Gesuch vorlag. Der Beschwerdeführer hatte zwar offenbar gegenüber der Verkäuferin im Coop, wo er angehalten wurde, geäussert, er wolle "Asyl"; diese war für die Entgegennahme des entsprechenden Gesuchs aber offensichtlich unzuständig. Den Behörden gegenüber erklärte er in der Folge, der Schlepper bzw. Chauffeur habe seinem Begleiter und ihm geraten, sie sollten der Polizei gegenüber "Asyl, Asyl" sagen; aus den weiteren Einvernahmen ergab sich aber, dass er überhaupt nicht wusste, was das eigentlich heissen sollte. Darauf angesprochen, warum er ins Asylzentrum wolle, erklärte er, dass es ihm in seinem Heimatland schlecht gegangen sei und er hier ein normales Leben führen möchte. Er wolle die Schweiz nicht verlassen, weil er annehme, es werde ihm hier besser gehen als in der Heimat.
Sein ihm vom Schlepper empfohlener, inhaltsloser Gebrauch des Ausdrucks "Asyl" sollte dies ermöglichen und eine sofortige Wegweisung verhindern, ohne dass der Beschwerdeführer auch nur ansatzweise um Schutz vor einer Verfolgung nachsuchen wollte, was letztlich die Tatsache belegt, dass er erst um "Asyl" bat, als er angehalten wurde. Unter diesen Umständen war es nicht offensichtlich unhaltbar, ihn formlos wegzuweisen (Art. 12 ANAG in Verbindung mit Art. 17 der entsprechenden Vollziehungsverordnung vom 1. März 1949, ANAV; SR 142. 201) und den Vollzug dieses Entscheids mit einer Ausschaffungshaft zu sichern. Dies wird durch den im bundesgerichtlichen Verfahren eingeholten Amtsbericht des Bundesamts für Flüchtlinge bestätigt, wonach gestützt auf die Erklärungen des Beschwerdeführers, denen jegliche Ernsthaftigkeit abgehe, kein Asylverfahren eröffnet werde. Der Beschwerdeführer hat seinerseits inzwischen erklärt, nicht wie ursprünglich behauptet B._ zu heissen und aus der Ukraine zu stammen; er sei entgegen seinen früheren Angaben auch nicht minderjährig. Er komme aus Litauen, wohin er nunmehr zurückkehren wolle. Ein allfälliges Asylgesuch wäre damit gegenstandslos.
b) Die anderen Haftvoraussetzungen sind ohne weiteres gegeben, insbesondere besteht beim Beschwerdeführer Untertauchensgefahr im Sinne von Art. 13b Abs. 1 lit. c ANAG (vgl. <ref-ruling> E. 3b/aa S. 375; <ref-ruling> E. 2a S. 50 f.; <ref-ruling> E. 2b S. 198): Seine Identität steht nicht fest. Er ist inzwischen auf seine entsprechenden Angaben denn auch zurückgekommen. Die Art und der Zweck seiner Einreise - in einem Lastwagen versteckt, um hier im Vergleich zu seiner Heimat "normal" leben und arbeiten zu können - legen nahe, dass er sich ohne Haft den Behörden zum Vollzug der Wegweisung nicht zur Verfügung halten wird. Er ist mittellos und wurde bei einem versuchten Ladendiebstahl angehalten.
Zwar war dieser eher unbedeutend ("Vergessen" des Bezahlens einer Nagelschere), doch ergibt sich daraus dennoch, dass er sich um die hiesige Rechtsordnung nicht weiter kümmert, und bereit ist, sich hier mit allen möglichen Mitteln durchzuschlagen. Noch vor dem Haftrichter widersetze er sich einer Rückkehr in sein Heimatland. Dass er diese Erklärung inzwischen widerrufen hat, lässt den Haftgrund nicht entfallen, sondern belegt, dass er die Behörden mit seinen falschen Angaben bewusst und planmässig zu täuschen versuchte, um ihre Vollzugsbemühungen zu erschweren. Damit lassen hinreichend konkrete Indizien befürchten, dass er sich ohne die angeordnete Administrativmassnahme der Ausschaffung entziehen wird. Die kantonalen Behörden haben die Identitätsabklärung und Papierbeschaffung sofort in die Wege geleitet; die Ausschaffung des Beschwerdeführers ist zudem zurzeit weder in die Ukraine noch nach Litauen rechtlich oder tatsächlich unmöglich. Die vom Beschwerdeführer beanstandeten Haftbedingungen entsprechen schliesslich den gesetzlichen Anforderungen; im Übrigen handelt es sich bei den entsprechenden unsubstantiierten Vorbringen um vor Bundesgericht unzulässige Noven, nachdem er die Haftbedingungen vor dem Haftrichter nicht beanstandet hatte (vgl. <ref-ruling> E. 3a, mit Hinweisen).
Der angefochtene Entscheid ist deshalb rechtmässig.
4.- a) Die Beschwerde ist demnach abzuweisen, soweit darauf eingetreten wird.
b) Dem Verfahrensausgang entsprechend würde der Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 OG). In Fällen der vorliegenden Art rechtfertigt es sich jedoch, von der Erhebung einer Gerichtsgebühr abzusehen (vgl. Art. 154 OG).
c) Die Einwohnerdienste des Kantons Basel-Stadt werden ersucht, dafür besorgt zu sein, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und verständlich gemacht wird.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, den Einwohnerdiensten, Abteilung Internationale Kundschaft, und dem Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Verwaltungsgericht des Kantons Basel-Stadt sowie dem Bundesamt für Ausländerfragen und dem Bundesamt für Flüchtlinge schriftlich mitgeteilt.
_
Lausanne, 9. Oktober 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Der Gerichtsschreiber: