Mrthfx

In the question What is “dist-upgrade” and why does it upgrade more than “upgrade”? the accepted answer explains that linux-headers-3.0.0-13 is a new package replacing linux-headers-3.0.0-12.

How is it a new package and not simply a new version, and how to know (recognize) the difference?

Further, why is linux-headers-3.0.0-13 listed in the output of the command sudo apt-get upgrade if it is a new package and not a new version of an already installed package?

The answer hints at the argument that it is because linux-headers-3.0.0-12 and linux-headers-3.0.0-13 are connected to the same virtual package ("linux-headers is a virtual package that is provided by both linux-headers-3.0.0-12 and linux-headers-3.0.0-13"). Is it for this reason that linux-headers-3.0.0-13 is listed? And if so, why don't we see other packages provided by other virtual packages suggested as upgrades?

EDIT:

Although the example above concerns kernel packages, my question is not kernel-oriented but more general; or is it of kernel-only relevance?

The reason of having kernel meta-packages like linux-image-generic and linux-headers-generic pointing to real kernel packages is to allow having more than one instance of a kernel.

You can have linux-headers-3.0.0-13-generic and linux-headers-3.0.0-12-generic installed at the same time.

When you upgrade meta linux-headers-generic, it pulls the latest real package as a dependency. If we had these kernel packages as one with different versions, it would be always replaced.

apt-get upgrade doesn't install new packages

 upgrade

           upgrade is used to install the newest versions of all packages

           currently installed on the system from the sources enumerated in

           /etc/apt/sources.list. Packages currently installed with new

           versions available are retrieved and upgraded; under no

           circumstances are currently installed packages removed, or packages

           not already installed retrieved and installed. New versions of

           currently installed packages that cannot be upgraded without

           changing the install status of another package will be left at

           their current version. An update must be performed first so that

           apt-get knows that new versions of packages are available.

That's why it doesn't upgrade meta packages that are dependent on new packages.

It is not kernel related. There are some other examples.

How is it a new package and not simply a new version, and how to know (recognize) the difference?

Different packages have different names. Different versions of the same package have the same package name and different version numbers. You can see your installed packages and their version numbers with, e.g., apt list --installed:

firas@itsuki ~ % apt list --installed | grep linux-image

linux-image-4.18.0-14-generic/cosmic-updates,cosmic-security,now 4.18.0-14.15 amd64 [installed,automatic]

linux-image-4.18.0-15-generic/cosmic-updates,cosmic-security,now 4.18.0-15.16 amd64 [installed,automatic]

linux-image-generic/cosmic-updates,cosmic-security,now 4.18.0.15.16 amd64 [installed,automatic]

Here I have three installed packages whose names contain linux-image: linux-image-4.18.0-14-generic version 4.18.0-14.15, linux-image-4.18.0-15-generic version 4.18.0-15.16, and linux-image-generic version 4.18.0.15.16. In particular, linux-image-4.18.0-14-generic and linux-image-4.18.0-15-generic are different names, so they are different packages. Don't be fooled by how similar the names are, the point is that they are not the same. They might as well be named foo and bar.

Also, in the file names of .deb packages, the package name and version number are typically separated by underscores:

firas@itsuki ~ % ls /home/apt/archives/linux-image-*

/home/apt/archives/linux-image-4.18.0-14-generic_4.18.0-14.15_amd64.deb

/home/apt/archives/linux-image-4.18.0-15-generic_4.18.0-15.16_amd64.deb

/home/apt/archives/linux-image-generic_4.18.0.15.16_amd64.deb