Redirecting Errors For Old URLS and Attachments

I am having troubles trying to redirect to a 404 pages for attachment files and old URL’s. I have over 19,000 posts and recently I have change the URLs. For example…

OLD URL:
http://www.example.com/market/post-example/

NEW URL:
http://www.example.com/product/post-example/

I am needing all the old URL’s to show a true 404 error page so they are no longer getting indexed in search engines or are removed from search engines.

For this Firefox browsers shows the following:

http://prntscr.com/c495wb

For this Google Chrome browser shows the following:

http://prntscr.com/c495ly

Also with attachment URL’s such as the following…

REAL URL:
http://www.example.com/product/example-post/

ATTACHMENT URL:
http://www.example.com/example-post/

I am needing all the attachment URL’s to show a 404 error page or when they are needing to be redirected to the real URL, because currently they do nothing, meaning the browser just keeps trying to load but is unsuccessful.

This is what FireFox browser shows me:

http://prntscr.com/c494vr

This is what Google Chrome browser shows me:

http://prntscr.com/c495ly

Any help will be great. Thanks