Cardinality

; Two finite sets with the same cardinality
(define A (list 1 2 3 4 5))
(define B (list 10 20 30 40 50))

; A bijection: f(x) = 10*x
(define (f x) (* 10 x))

(display "Bijection from A to B:") (newline)
(for-each (lambda (x)
  (display x) (display " -> ") (display (f x)) (newline))
  A)

(display "|A| = ") (display (length A)) (newline)
(display "|B| = ") (display (length B))

; The even numbers are countably infinite.
; Bijection: n -> 2n (from N to evens)

(define (nat-to-even n) (* 2 n))
(define (even-to-nat e) (/ e 2))

(display "N -> Evens:") (newline)
(define (show-pairs n limit)
  (if (> n limit) (display "...")
      (begin
        (display n) (display " -> ") (display (nat-to-even n))
        (display "  ")
        (show-pairs (+ n 1) limit))))
(show-pairs 0 8) (newline)

; The integers are countably infinite.
; Listing: 0, 1, -1, 2, -2, 3, -3, ...
(define (nat-to-int n)
  (if (= 0 (modulo n 2))
      (/ n 2)
      (- (/ (+ n 1) 2))))

(display "N -> Z:") (newline)
(define (show-ints n limit)
  (if (> n limit) (display "...")
      (begin
        (display n) (display "->") (display (nat-to-int n))
        (display "  ")
        (show-ints (+ n 1) limit))))
(show-ints 0 8)

; Cantor's diagonal argument (simulated with finite strings).
; Given a "list" of decimal expansions, construct a number not on the list.

(define r1 (list 5 1 7 0 3))
(define r2 (list 3 9 2 8 4))
(define r3 (list 7 4 1 5 6))
(define r4 (list 0 0 6 2 9))
(define r5 (list 8 3 0 7 7))

(define rows (list r1 r2 r3 r4 r5))

; Extract the diagonal: position n from row n
(define (diagonal rows)
  (define (go rs i)
    (if (null? rs) (list)
        (cons (list-ref (car rs) i)
              (go (cdr rs) (+ i 1)))))
  (go rows 0))

; Flip each digit (add 1 mod 10, avoiding 0 and 9 for cleanliness)
(define (flip d) (modulo (+ d 1) 10))

(define diag (diagonal rows))
(define anti-diag (map flip diag))

(display "Diagonal:      ") (display diag) (newline)
(display "Anti-diagonal: ") (display anti-diag) (newline)
(display "This number differs from every row at the diagonal position.")

; The cardinality hierarchy:
; |N| = aleph_0 (countably infinite)
; |R| = 2^(aleph_0) (uncountably infinite)
; |P(R)| = 2^(2^(aleph_0)) (even larger)
;
; Cantor's theorem: |S| < |P(S)| for any set S.
; No set can biject with its power set.

; Demonstrate with finite sets:
(define (power-set s)
  (if (null? s) (list (list))
      (let ((rest (power-set (cdr s))))
        (append rest
                (map (lambda (sub) (cons (car s) sub)) rest)))))

(define (check n)
  (define s (list))
  (define (make-set i) (if (> i n) (list) (cons i (make-set (+ i 1)))))
  (let ((s (make-set 1)))
    (display "|S|=") (display (length s))
    (display "  |P(S)|=") (display (length (power-set s)))
    (display "  |S| < |P(S)|? ") (display (< (length s) (length (power-set s))))
    (newline)))

(check 1)
(check 2)
(check 3)
(check 4)
(check 5)
; Always |S| < |P(S)|. Cantor proved this for all sets, finite or infinite.