On a computer with a single cpu core, must a multithreading program be implemented based on an OS?

No. A program can implement its own threading and scheduler. At this point, however, the program is taking on the role of an operating system, in that in the absence of a proper operating system kernel, the program must implement all of the hardware communications code normally found in drivers.

Can it be implemented in the instruction set and run without an OS?

Yes and no. The instruction set of many modern CPUs includes the functionality required for hardware-level threads, and this functionality must be implemented in the form of a thread scheduler. That may indeed be part of the program, but again, in the absence of an operating system, the program must implement those features that communicate with hardware.

Can multiple programs run in multitasking way without an OS? Can multitasking between programs be implemented without an OS (e.g. implemented only in the instruction set)?

This suggests a confusion about the role of the operating system.

In order for distinct, disconnected, independent programs to execute in a multithreading environment, a process monitor is necessary to manage the scheduling, execution, and termination of these threads. At an extremely high level, the operating system kernel is, at its heart, a process monitor.

On a computer with multiple cpus/cores, must a multithreading program be implemented based on an OS? Can it be implemented in the instruction set and run with parallel threads without an OS?

There must be some piece of code that schedules code execution on multiple cores, as well as to manage the initialization of those cores. This is normally the role of the process monitor. A single, self-contained program could in principle implement these features, but, as above, it must take on all of the roles of the kernel in order to do so.

Can multiple processes run in multiproccessing parallel way without an OS? Can this multiproccessing parallelism be implemented without an OS (e.g. but in the instruction set)?

Again, this is the role of the program monitor. On typical modern general-purpose CPU architectures, such a monitor must exist in order for processes to be scheduled on cores other than the primary core. In principle, a CPU core could be designed to deal with these matters, and I believe some GPUs and certain other small cores (GreenArrays comes to mind) are in fact built this way, or, at the very least, rely on an ancillary general-purpose CPU to run the process monitor.

Are multithreading, multiprocessing,and multitasking, respectively, intrinsic to computer architecture or to operating system?

No.

Are thread and process level parallelisms intrinsic to computer architecture, or to OS? Is multitasking ( as a kind of concurrent computing) intrinsic to computer architecture or OS?

No, and no.

Again, I detect a misunderstanding of the role of operating systems.

There are aspects of parallelism that are implemented in either the computer hardware or the operating system, but they are intrinsic to neither. Historically, this was entirely the domain of the process monitor, especially in early time-sharing systems. That role was placed in the domain of the system libraries in cooperative multitasking systems, where some system calls temporarily hand over execution to the operating system to handle task scheduling, among other things. Modern multiprocessing operating systems are little more than process monitors that manage, among other tasks, processes dedicated to hardware management.

The notion of whether or not software can do something without an OS is not really meaningful.

An OS is software, and really the only thing that distinguishes an OS from other software running on a computer is that (at least in most modern multitasking systems) the OS reserves certain kinds of operation to itself and prevents other software from performing them. Without an OS, there is nothing to stop any other software doing anything that an OS would usually do, including running using multiple threads and/or processors. This would typically involve interacting with the hardware at a level that would be prevented were an OS present, but without one such restrictions would not apply.

Now it is arguable that by implementing such features, your software (or at least some module of it) would itself become an OS, but that is an issue of semantics and not really productive.

Trying to get to a layer beneath your questions, I think what you’re really trying to ask is something closer to “is it possible for a processor architecture to provide full multitasking capabilities at a level beneath the operating system”. The answer to this is difficult: it would be possible for the processor to go further than current designs do in this direction, but in the end, operating system cooperation would be necessary because a new thread requires scheduling, and that is an OS responsibility.