Ausschaffungshaft (Art. 13b ANAG), hat sich ergeben:
A.- Der nach seinen letzten Angaben aus Litauen stammende A._ (geb. 1977; alias B._, geb. **.
** 1984, alias C._) 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 sei in der Ukraine vergewaltigt worden und habe eine grosse Summe Geld "geborgt", weshalb er das Land habe verlassen müssen, was er erst jetzt darlege. Er bitte, seinen Fall neu zu beurteilen.
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 war 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 man sich dort frei bewegen und auf die Strasse gehen könne; er wolle im Asylzentrum "leben, Sprachen lernen und zur Schule gehen". Probleme mit der Polizei oder dem Militär habe er nicht gehabt. Dem Beschwerdeführer ging es darum, hier "normal" leben und arbeiten zu können. 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 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 auf seine entsprechenden Angaben wiederholt zurückgekommen. Die Art und der Zweck seiner Einreise - in einem Lastwagen versteckt, um hier arbeiten bzw. zur Schule gehen 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. War dieser auch eher unbedeutend ("Vergessen" des Bezahlens einer Nagelschere), ergibt sich daraus doch, dass er sich um die hiesige Rechtsordnung nicht weiter kümmert, und bereit ist, sich hier mit allen Mitteln durchzuschlagen. Noch vor dem Haftrichter widersetze er sich einer Rückkehr in sein Heimatland: er besteige ein entsprechendes Flugzeug "nur mit Handschellen". Dass er auf diese Erklärung inzwischen zurückgekommen ist, lässt den Haftgrund nicht entfallen, sondern belegt, dass er die Behörden mit seinen 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. 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: