[Automata] Automata Prove: Infinite Countable

Automata Prove: Infinite Countable

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Infinite Countable

Infinite number임에도 규칙이 있으며 bijective가 된다면 countable에 해당한다.

이를 Infinite countable이라고 하며 Backward 방식을 통해 증명이 가능하다.

1. f: N -> A such  that f(n) = 2n-1
2. for every(all) y ∈ B
3. x ∈ A: let x = (y+1)/2
4. f(x) = 2x-1 = 2((y+1)/2) - 1 = y
5. Exists x ∈ A such that f(x) = y
6. f is onto if for every y ∈ B, there exists x ∈ A such that f(x) = y [Definiton of onto function]
7. for every x1 and x2
8. assume(if) f(x1) = f(x2)
9. 2(x1)-1 = 2(x2)-1 by f(x1) = f(x2) and definition of f
10. x1 = x2
11. f(x1) = f(x2) implies x1 = x2
12. for every x1 and x2, f(x1) = f(x2) implies x1 = x2
13. f is one-one if for every x1 and x2, f(x1) = f(x2) implies x1 = x2 [Definition of one-one function]
14. There is bijective function from N to A [Definition of bijective function]
15. A is countably infinite if there is a bijective function from N to A [Definition of countably infinite]
16. A is countable infinite
17. A is countable if it is finite or countably infinite [Definition of countable with a set]
18. A = {1, 3, 5, 7, 9, 11,...} is countably infinite
19. QED

 

---