How to add a column with a foreign key constraint to a table that already exists?
You just have to add another step - in fact PostgreSQL is already telling you that: column &quot;sender&quot; referenced in foreign key constraint does not exist.
The FOREIGN KEY (aka parent) column has to already exist in order to make it an FK.
I did the following (from here and the documentation). Note that the parent column has to have a UNIQUE constraint (or be the PRIMARY KEY) but it doesn't have to be NOT NULL. This is because NULLs are not equal to each other, nor are they equal to anything else - each NULL is considered UNIQUE in its own right!
CREATE TABLE x(a INT UNIQUE NOT NULL);

CREATE TABLE y(b INT);

ALTER TABLE y ADD COLUMN c INT NOT NULL
CONSTRAINT y_x_fk_c REFERENCES x (a)   -- if x (a) doens't exist, this will fail!
ON UPDATE CASCADE ON DELETE CASCADE;  -- or other Referential Integrity Action

A couple of points to note (see the fiddle here) - an attempt to insert a value into y (c) which is not in x (a) fails and the constraint name is given in the error message.
The fiddle has NOT NULL constraints on x (a) and on y (c). Unless I have a really compelling reason, I always declare my columns as NOT NULL - it helps the optimiser and reduces the potential for confusion/error. You can experiment yourself with the fiddle to see what happens when you leave out the NOT NULL on either (and both) field(s) - the behaviour isn't always intuitively obvious!
ALWAYS give your foreign keys meaningful names. Being told that key &quot;SYS_C00308108&quot; is being violated is not very helpful. See the fiddle here for Oracle's behaviour under these circumstances the key name will vary from fiddle to fiddle, but is some arbitrary string beginning with SYS_... (comes after the long dbfiddle generated tablename).
Evan Carroll in his answer here believes that auto-generated names are OK - I've shown why that is not a good idea for Oracle (at least up to 18c), but I also feel that it's not a good idea for PostgreSQL either - potential problems for portability if nothing else.
I would like to credit Evan Carroll for pointing out that the addition of the new field and the FOREIGN KEY creation and the CONSTRAINT (with specified name) can be added in one step and not two steps as I originally said) - so please give him credit for that if you feel like upvoting me - I do go into more detail however.
Considering the statement in your question:
ALTER TABLE message ADD FOREIGN KEY (sender) REFERENCES users;

It would be a &quot;nice-to-have&quot; if the RDBMS could automatically create the field you want with the data type matching the referenced field.
All I would say is that changing DDL is (or at least should be) a rarely used operation and not something that you'd want to be doing regularly. It also risks adding to an already fairly substantial documentation.
At least PostgreSQL tries to do something reasonable - it concatenates the table name, the FOREIGN KEY field name and fkey. Furthermore, when you do name the constraint yourself,  the error message will add DETAIL: Key (c)=(7) is not present in table &quot;x&quot;. to give something that might make sense to a human being (unlike Oracle - see the end of the PostgreSQL fiddle).