Few basic points:
1. All finite languages are recursive
2. If L is recursive then L complement is also recursive
3. If L and L complement are r.e (recursively enumerable) then both are recursive
4. If S1 and S2 are finite and S1 is proper subset of S2 then S1 and S2 have different cardinality.
However, if both S1 and S1 are infinite, both sets MIGHT have the same cardinality.
Ex: S1 {set of even integers}
S2 { set of all integers }
f(2i) = i, hence the cardinality is equal for both sets in this case.
Please feel free to add more when you guys come across any properties/relations/theories.
Usha



LinkBack URL
About LinkBacks







Reply With Quote




Bookmarks