[FOM] Computability question

[Ben Sherman]

You're right: undecidable languages aren't closed under either binary union or binary intersection. Here is a simple class of counterexamples:

Given an undecidable language L, its complement Lc is also undecidable. Then the union of L and Lc is the trivially true subset, which is decidable, and the intersection of L and Lc is the trivially false subset, which is decidable.

> On Feb 11, 2017, at 12:06 PM, fom-request at cs.nyu.edu wrote:
> 
> From: Daniel Schwartz <schwartz at cs.fsu.edu <mailto:schwartz at cs.fsu.edu>>
> Subject: [FOM] Computability question
> Date: February 10, 2017 at 9:25:51 PM EST
> To: fom at cs.nyu.edu <mailto:fom at cs.nyu.edu>
> Reply-To: Foundations of Mathematics <fom at cs.nyu.edu <mailto:fom at cs.nyu.edu>>
> 
> 
> Dear FOM list,
> 
> Would anyone know the answer to the following?
> 
> It is well known that the decidable languages are closed with respect to
> union and intersection.  What about the undecidable languages?
> 
> I'm guessing that these are not closed with respect to either union or
> intersection, since I have been unable to find proofs, but I don't know of
> any counterexamples.
> 
> Any light that anyone can shed on this would be appreciated.
> 
> Dan Schwartz
> 
> ************************************************************************
> Dr. Daniel G. Schwartz                            Office    850-644-5875
> Dept. of Computer Science, MC 4530                CS Dept   850-644-4029
> Florida State University                          Fax       850-644-0058
> Tallahassee, FL 32306-4530                        schwartz at cs.fsu.edu <mailto:schwartz at cs.fsu.edu>
> U.S.A.                                   http://www.cs.fsu.edu/~schwartz <http://www.cs.fsu.edu/~schwartz>
> ************************************************************************

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170211/759d7f9b/attachment.html>