cantor_diagonal.rs

cantor_diagonal.rs

use std::fmt::{self, Display};

// Define a type alias for a binary sequence (a vector of 0s and 1s)
type BinarySequence = Vec<u8>;

/// Attempts to demonstrate Cantor's Diagonal Argument.
///
/// It generates a list of sample binary sequences and constructs a new
/// diagonal sequence that is guaranteed to not be in the list.
fn main() {
    // 1. Define a list of sequences (our 'countable' list S1, S2, S3, ...)
    // In a real proof, this list would be infinite and contain ALL sequences
    let sequences: Vec<BinarySequence> = vec![
        // S1
        vec![1, 0, 0, 0, 1, 1, 0, 0, 1, 0],
        // S2
        vec![0, 1, 0, 1, 0, 1, 1, 0, 1, 0],
        // S3
        vec![1, 1, 1, 0, 0, 1, 0, 1, 0, 1],
        // S4
        vec![0, 1, 0, 0, 0, 1, 1, 0, 1, 0],
        // S5
        vec![1, 0, 0, 1, 1, 0, 0, 0, 1, 1],
        // The list must contain sequences of at least length N to check the Nth element
        vec![0, 0, 1, 1, 0, 1, 0, 1, 1, 0],
        vec![1, 1, 0, 0, 1, 0, 1, 1, 0, 0],
        vec![0, 1, 1, 1, 0, 0, 0, 1, 1, 1],
        vec![1, 0, 1, 0, 1, 1, 0, 0, 0, 1],
        vec![0, 0, 0, 1, 1, 1, 1, 1, 1, 0],
    ];

    // The length of the sequences determines how many diagonal elements we can construct.
    let n = sequences.len();

    println!("🔢 Initial List (S):");
    print_sequences(&sequences);

    // 2. Construct the Diagonal Sequence (S_diag)
    let mut s_diag: BinarySequence = Vec::new();

    // Iterate up to the length of our list, n (0 to n-1)
    // i represents the index of the sequence (row) and the index within the sequence (column).
    for i in 0..n {
        // Get the i-th sequence (Si)
        let s_i = &sequences[i];

        // Get the i-th element of the i-th sequence (the diagonal element: S_i[i])
        // We assume all sequences are long enough (length >= n) for this demonstration.
        let diagonal_element = s_i[i];

        // 3. The diagonalization step: create a new element that is the opposite of the diagonal one.
        // If S_i[i] is 0, the new element is 1. If S_i[i] is 1, the new element is 0.
        let new_element = 1 - diagonal_element;
        s_diag.push(new_element);
    }

    println!("---");
    println!("✨ Diagonal Sequence (S_diag):");
    println!("{}", SequenceFormatter(&s_diag));
    println!("---");
    
    // 4. Verification
    println!("🔎 Verification: S_diag must not be in the list.");
    
    for (i, s) in sequences.iter().enumerate() {
        // The key insight is S_diag must differ from S_i at the i-th position.
        let diag_val = s_diag[i];
        let s_val = s[i];
        
        let match_status = if diag_val == s_val {
            "MATCH (This should not happen if sequences are long enough!)"
        } else {
            "NO MATCH"
        };
        
        println!(
            "S_diag[{i}] is {} and S{}[{i}] is {}. -> {}",
            diag_val,
            i + 1, // i is 0-indexed, S_i is 1-indexed in the image
            s_val,
            match_status
        );
    }
    
    println!("\nConclusion: The sequence S_diag was constructed to differ from the 1st sequence at the 1st position, the 2nd sequence at the 2nd position, and so on. Therefore, S_diag cannot be any sequence in the list.");

    // The theorem states that *any* hypothetical enumeration (infinite list) 
    // must fail to contain at least one sequence (S_diag), proving that
    // the set of all sequences is uncountable.
}

/// A helper struct to pretty-print the sequence
struct SequenceFormatter<'a>(&'a BinarySequence);

impl Display for SequenceFormatter<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for &bit in self.0.iter() {
            write!(f, "{}", bit)?;
        }
        Ok(())
    }
}

fn print_sequences(sequences: &[BinarySequence]) {
    for (i, s) in sequences.iter().enumerate() {
        println!("S{: <2}: {}", i + 1, SequenceFormatter(s));
    }
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=083c32cc39a2e4eef4ec2eba711200ce