Countable and Reducable

Question

Consider the following statements:

$S_{1}$ : For any two sets A and B, if A is uncountably infinite and B is countably infinite, then $A\cap B$ is countably infinite.

$S_{2}$ : For any two language A and B, if $A\subseteq B$, then $A$ is reducable to $B$.

The number of incorrect statement are _________________________

Comments

I think 1 ? First one only

---

No...

---

Sorry first one is correct. Second one is incorrect

Answer 1

First one is right and second one is wrong.

IF we take intersection at most we will get the smaller set which will be countable.

https://www.math.ucla.edu/~tao/java/MultipleChoice/countable.txt

second - problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently."

https://en.wikipedia.org/wiki/Reduction_(complexity)

So A is a subset of B and B can't be used to solve A so we can't say A is reducable to B

Comments

@Tendua. If A is subset of B, and if we have algorithm to solve B then why not for problem that is subset of B?

I think, if I cant solve smaller problem(here A), then how can I solve bigger problem(here B)?

---

Reducibility definition says that we should be able to solve A using B. Or I will say solving A cannot be harder than solving B, But here in every case it will not be true. Finding shortest path to one village may be a subset of finding the shortest path to n villages.

---

@ Tendua @ Sushant Gokhale @ srestha 

i think first is wrong...

if A∩B =Empty set then it's finite?