Author: Anita Holm

  • Gödel’s Incompleteness Theorem: An Introduction

    This essay is based on Chapter 1 of A.W. Moore’s book on Gödel’s theorem [1].

    1 The Announcement and Impact of Gödel’s Theorem

    On September 7, 1930, at a conference in Königsberg on the “Epistemology of the Exact Sciences,” a 24-year-old Kurt Gödel presented the findings that would become his famous theorem. The result was formally published the following year under the title “On Formally Undecidable Propositions of Principia Mathematica and Related Systems I.”

    Gödel had intended to publish a sequel. In the first paper, he proved his first theorem in detail and sketched a proof of the second. The sequel was meant to generalise the first theorem and provide a detailed proof of the second. As it turned out, the sequel was never needed; his results were accepted so quickly and understood so well that a follow-up publication was unnecessary. The mathematician Roger Penrose called it “the most important theorem in mathematical logic of all time.”

    The theorem showed that any effort to create a definitive and complete set of rules for arithmetic is, in essence, impossible. It challenged prevailing beliefs about the nature of mathematics at a fundamental level and sparked philosophical debates.

    2 Core Statement of the Theorem

    The following informal statements capture the essence of the theorem:

    • “No axiomatization can determine the whole truth and nothing but the truth concerning arithmetic.”
    • “Any axiomatization of arithmetic must either be incomplete, that is, fail to capture some arithmetical truths, or be unsound, that is, capture some arithmetical falsehoods.”
    • “No finite stock of basic principles and rules enables us to prove every arithmetical truth unless it also enables us to prove some arithmetical falsehoods.”

    The term “finite” is crucial. If omitted, one could define each of the infinite arithmetic truths as a distinct basic principle, which would allow each truth to be proven in a single step. Equally vital is the “unless” provision, because an absurd rule permitting the derivation of any statement would prove all truths, but at the unacceptable cost of simultaneously proving all falsehoods.

    3 Deconstructing the Theorem: Key Concepts

    To fully grasp the theorem, one must first understand its core components: arithmetic, axiomatization and proof.

    Arithmetic

    • Definition: The study of the natural numbers (0, 1, 2, 3,…) and the algorithmic operations that apply to them, such as addition and multiplication.
    • Algorithmic Operations: These are purely mechanical procedures that can be followed step-by-step by a computer, do not rely on randomness, and are guaranteed to produce a result in a finite number of steps.

    Gödel’s theorem holds even when the scope of arithmetic is restricted to the study of natural numbers using only addition and multiplication. All other algorithmic operations can be expressed using these two operations, yet this process is more complex than it first appears. For example, while one might assume exponentiation (n^m) is simply n multiplied by itself m times, the concept of “occurring m times” requires a rigorous definition that is surprisingly difficult to achieve. This difficulty is doubly remarkable: it highlights both the power of such limited mathematical resources and the minimal requirements needed for Gödel’s theorem to apply.

    Axiomatization

    • Definition: A finite collection of basic principles and rules that form the foundation of a formal system.
    • “Basic” Principles: A principle or rule is considered “basic” if it is accepted without being derived from anything else within the system. Its status as “basic” is not compromised, even if it is questioned or shown to be incorrect.

    For example, a basic principle for multiplication could be stated as: given any natural number n, n multiplied by 0 is 0. An axiomatization also includes rules that are not specific to any one subject but apply universally. These are often said to belong to logic. For instance, a rule of logic allows us to derive a specific instance (like “7 multiplied by 0 is 0”) from a general principle (like the one above).

    More generally, in any axiomatization, two distinct categories of principles are recognised:

    1. Subject-Specific Principles: These are the rules unique to a particular area of study, such as the axioms that define arithmetic.
    2. Logical Principles: These are the rules that govern valid reasoning itself and apply universally.

    The game of chess provides a helpful analogy. The rules specifying how each piece moves are specific stipulations of the game, comparable to the axioms of arithmetic. In contrast, the reasoning used to determine, for example, that a king and a knight cannot checkmate a lone king is not a rule of chess. It is a principle of general logic applied to the game’s specific rules. This characterisation of logic as universally applicable is informal, and the exact demarcation line, as well as the placement of certain principles, remain subjects of ongoing debate.

    Proof

    • Definition: A proof of a statement, relative to a given axiomatization, is a derivation of that statement from the system’s basic principles using its basic rules.

    A robust axiomatization of arithmetic, for instance, should provide the tools to prove both simple calculations (e.g., that 827 × 240 = 198,480) and more complex statements (e.g., that there are infinitely many prime numbers).Proof is relative to the specific set of axioms and rules chosen for a formal system (axiomatization). A statement’s provability or unprovability is never absolute. A statement provable under one axiomatization might be unprovable under another. For example, the Euclidean proof that there are an infinite number of primes is perfectly acceptable. However, a truly formal presentation would require explicitly stating the underlying logical rules and axioms. This essential relativity of proof is the key factor that introduces the central problem of the theorem, focusing on the discrepancy between formal provability and the abstract concept of truth.

    4 The Core Dilemma: Truth vs. Formal Proof

    Gödel’s theorem creates a schism between the concepts of truth within arithmetic and provability within any given formal axiomatic system. The theorem can be written informally: “Any axiomatization of arithmetic must either be incomplete, that is, fail to capture some arithmetical truths, or be unsound, that is, capture some arithmetical falsehoods.”

    This statement implies that no single, finite system of axioms and rules can ever capture the entirety of arithmetical truth unless it also generates contradictions and falsehoods. Any consistent system we can construct will necessarily be incomplete, that is, unable to prove some true statements about numbers. This incompleteness creates a conceptual rift between what is true and what is formally demonstrable.

    The following statements clarify the concepts of truth, falsehood, and conjecture.

    Truths

    • A familiar, simple statement: 827 x 240 = 198,480
    • A more complex provable statement: “There are infinitely many primes.”

    Falsehoods

    • A statement that can be proven wrong by a counterexample, such as “Every natural number is the sum of three squares.” This statement is false because certain numbers, like 7, do not fit this rule.

    Conjectures

    • A statement whose status remains undetermined because neither a proof nor a counterexample has been found. Goldbach’s Conjecture serves as an illustration: “Every even number greater than 2 is the sum of two primes.”

    For the sake of this initial analysis, we proceed with the philosophical assumption that every clear arithmetical statement is unproblematically either true or false. It is worth noting, however, that this assumption itself can be scrutinised. More importantly, the theorem can be stated and proven in a way that bypasses the concept of “truth” altogether. The core dilemma remains: any consistent, finite formal system is limited. This forces us to re-evaluate what it means for a mathematical statement to be true if we cannot demonstrate its truth within its own system. Unfortunately, this dilemma has given rise to numerous misunderstandings.

    5 Common Misconceptions

    Several prevalent misconceptions obscure the theorem’s precise meaning.

    Misconception: Some truths are absolutely unprovable.

    Gödel’s theorem does not imply this. A truth that is unprovable in one sound axiomatization may be provable in another (for instance, by being added as a new axiom). The fact that any single system is incomplete does not mean that some truths are beyond the reach of all possible systems. This is like a CCTV system where no single camera covers the entire site, but the combined cameras still do.

    Misconception: The theorem applies to all subjects, including all of mathematics.

    The theorem concerns explicitly arithmetic. There are other branches of mathematics, notably analysis (the study of real numbers), for which a complete and sound axiomatization exists. This is possible because the language of analysis can refer to specific natural numbers (e.g., 2+2=4), but it lacks the means to refer to the set of natural numbers as a whole. The analogy used is a language with names for individual places (“Mercury”, “Venus”) but no word for “planet.”

    Misconception: Arithmetical statements can assert their own unprovability.

    While this idea is often associated with the theorem, the text describes it as a misconception until the concept is rigorously and carefully defined. Without the necessary groundwork, one should adhere to the view that arithmetical statements assert things about numbers, not about their own provability.

    Misconception: The theorem supports broad philosophical or metaphysical claims.

    The theorem is frequently co-opted to support grand claims, such as justifying a belief in God or that “Man will never know the final secret of the universe” (Rudy Rucker). David Foster Wallace connected it to “the great postmodern uncertainty.” The text dismisses these, stating there is “simply no interesting connection between Gödel’s theorem and the ideas being canvassed in these claims.”

    6 Conclusion

    Gödel’s Incompleteness Theorem is probably the most significant achievement in mathematical logic of the 20th century. It irrevocably changed our understanding of both mathematics and philosophy. The core finding is that any formal axiomatic system about arithmetic must be either incomplete or unsound. This demonstrates a conceptual gap between truth and formal provability.

    Gödel’s theorem defines the boundaries of formalisation, but it does not assert the existence of universally unprovable truths or apply to every area of mathematics. His work did not conclude a mathematical investigation. On the contrary, it compelled a deeper examination of arithmetic, axioms and proofs and offered a new path for understanding the nature of certainty and the complexity of natural numbers. The quest for truth persists. However, the idea that one finite set of rules could entirely encapsulate the truth of arithmetic is now recognised as impossible.

    References

    [1] Moore, A. W. 2022. Gödel’s Theorem: A Very Short Introduction. Oxford: Oxford University Press.

  • Power Up Your Python Scripts: Handling Command-Line Arguments (ResizerMate Part 2 Walkthrough)


    Welcome back to the ResizerMate project! In Part 1, we laid the groundwork for our image resizing tool. Now, in Part 2, as shown in the “Code With Me” video, it’s time to make our Python script significantly more flexible and user-friendly by learning how to process command-line arguments.

    Being able to pass arguments to your script directly from the terminal (or command line) means you don’t have to hardcode values like file paths. This makes your scripts reusable and automatable. This post will guide you step-by-step through the Python code developed in the video, explaining how to use the sys and os modules for this purpose, and how to keep your project tidy with Git and GitHub.

    Let’s dive into the code!

    The Enhanced Python Script

    Here’s an enhanced Python script that’s developed in the video to handle command-line inputs for an input image and an output folder:

    import sysimport os
    
    if __name__ == "__main__":
        # Check if the correct number of arguments is provided    
        if len(sys.argv) != 3:
            print("Usage: python script.py <input_image_path> <output_folder>")
            sys.exit(1)  # Exit if arguments are incorrect
    
        # Assign command-line arguments to variables
        input_image_path = sys.argv[1]
        output_folder_path = sys.argv[2] # Renamed for clarity from video's 'output_path'
    
        # Define the main function to encapsulate the script's logic
        def main(image_path, out_folder):
            # Ensure the output directory exists, create if not
            if not os.path.exists(out_folder):
                os.makedirs(out_folder)
                print(f"Created output folder: {out_folder}")
    
            # Extract the base name of the input image (e.g., "image" from "image.jpg")
            base_name = os.path.splitext(os.path.basename(image_path))[0]
    
            # In the video, the output file name isn't constructed, but 
            # let's assume it's something like this:
            # output_file_name = f"{base_name}_resized.jpg" # Example format
            # full_output_path = os.path.join(out_folder, output_file_name)
    
            print(f"Processing image: {image_path}")
            print(f"Output will be in: {out_folder}")
            print(f"Base name of image: {base_name}")
            # print(f"Full output path would be: {full_output_path}") # If you build full path
    
        # Call the main function with the provided arguments
        main(input_image_path, output_folder_path)

    Step-by-Step Breakdown

    Let’s break down what each part of this script does, as shown in the video.

    1. Importing Necessary Modules [Video Timestamp approx. 00:11]

    import sys
    import os
    • sys: This module provides access to system-specific parameters and functions. Crucially for us, it includes sys.argv, which is a list containing the command-line arguments passed to the script.
    • os: This module provides a way of using operating system dependent functionality like reading or writing to the file system. We’ll use it to check for directory existence and create directories.

    2. Checking for Correct Command-Line Arguments [Video Timestamp approx. 00:29]

    if __name__ == "__main__":
        if len(sys.argv) != 3:
            print("Usage: python script.py <input_image_path> <output_folder>")
            sys.exit(1)
    • if __name__ == "__main__":: This is a standard Python construct that ensures the code inside this block only runs when the script is executed directly (not when imported as a module into another script).
    • sys.argv: This is a list where sys.argv[0] is the name of the script itself (e.g., script.py), sys.argv[1] is the first argument, sys.argv[2] is the second, and so on.
    • len(sys.argv) != 3: We expect two user-provided arguments (input image path and output folder path) plus the script name, making a total of 3 items in sys.argv. If the count isn’t 3, the script prints a helpful usage message.
    • sys.exit(1): If the arguments are incorrect, the script exits. The 1 typically indicates that an error occurred.

    3. Assigning Arguments to Variables [Video Timestamp approx. 03:51]

        input_image_path = sys.argv[1]
        output_folder_path = sys.argv[2]

    Here, we assign the first user-supplied argument (sys.argv[1]) to input_image_path and the second (sys.argv[2]) to output_folder_path.

    4. Defining the main Function [Video Timestamp approx. 04:14]

        def main(image_path, out_folder):
            # ... logic inside main ...

    Encapsulating the core logic of the script within a main function is good practice. It makes the code more organized and readable.

    5. Handling File System Operations with os [Video Timestamps approx. 04:44 & 05:21]

    Inside the main function:

        if not os.path.exists(out_folder):
            os.makedirs(out_folder)
            print(f"Created output folder: {out_folder}")
    • os.path.exists(out_folder): Checks if the path specified by out_folder already exists in the file system.
    • os.makedirs(out_folder): If the path doesn’t exist, this function creates the directory. makedirs is useful because it will create any necessary parent directories as well.
        base_name = os.path.splitext(os.path.basename(image_path))[0]        
        print(f"Base name of image: {base_name}")
    • os.path.basename(image_path): Extracts the filename from a full path (e.g., “image.jpg” from “/path/to/image.jpg”).
    • os.path.splitext(...): Splits the filename into a pair: (root, extension). For example, (“image”, “.jpg”).
    • [0]: We take the first element of this pair, which is the base name without the extension.
    • While the provided script only prints the base name, in a real scenario, you’d likely use os.path.join() to combine out_folder, base_name, and a new extension/suffix to create the full path for the output file. For example: full_output_path = os.path.join(out_folder, f{base_name}_resized.jpg").

    6. Calling the main Function

        main(input_image_path, output_folder_path)

    Finally, the main function is called with the arguments captured from the command line.

    Running and Testing [Video Timestamp approx. 06:32]

    The video demonstrates running the script from the command line, providing different input image paths and output folder locations. This is how you’d typically use such a script:

    python your_script_name.py /path/to/your/image.jpg /path/to/your/output_directory

    The video also touches upon encountering and fixing errors [Video Timestamps 03:24, 07:12], such as a TypeError or indentation errors. This is a natural part of coding! Using an editor like VS Code with Python support can help catch some of these early.

    Version Control with Git and GitHub [Video Timestamp approx. 07:37]

    Throughout the development process, especially when adding new features like this, it’s crucial to use version control. The video shows using Git to:

    1. Stage changes: git add <filename> or git add .
    2. Commit changes: git commit -m "Added command-line argument parsing"
    3. Push changes to GitHub: git push

    This workflow ensures your changes are tracked, you can revert if something goes wrong, and your code is backed up on GitHub.

    Conclusion

    By following along with the video and this guide, you’ve learned how to make your Python scripts significantly more versatile by accepting command-line arguments. You’ve seen how to use the sys module to read these arguments and the os module to interact with the file system, all while keeping your code organized and version-controlled. These are foundational skills for any Python developer building command-line tools or automating tasks!

  • From Zero to Python: A Step-by-Step Guide to Your First Project Setup


    So, you’re ready to dive into a new Python project, but where do you start? This guide breaks down the initial setup process, mirroring the steps often taken by developers to get a project like “ResizerMate” off the ground. We’ll cover creating a home for your code on GitHub, getting it onto your local machine, writing your first lines of Python in VS Code, and saving your progress with Git.

    Let’s get started!

    Step 1: Create Your Project’s Home on GitHub [Video Timestamp: 00:04]

    Every good project needs a central hub. GitHub is a popular platform for hosting and collaborating on code. The first step in the video is to create a new “repository” (often called a “repo”) on GitHub.

    • What’s happening? A new repository named “ResizerMate” is created. It’s set to “private,” meaning only the creator (or those they grant access to) can see it.
    • Why is this important? This gives your project a remote backup and a place for version history. If you plan to collaborate, it’s essential.
    • Learn More:

    Step 2: Bring Your Project to Your Computer (Cloning) [Video Timestamp: 00:46]

    Once the repository exists on GitHub (the “remote” location), you need a copy on your own computer (the “local” location) to actually work on the code. This is done by “cloning” the repository.

    • What’s happening? The video shows using Windows PowerShell (a command-line tool) with the git clone command to download the “ResizerMate” repository from GitHub to the local machine.
    • Why is this important? This creates a local working copy of your project that’s linked to the remote GitHub repository, allowing you to synchronize changes.
    • Learn More:

    Step 3: Open in VS Code & Create Your First Python File [Video Timestamp: 01:51]

    With the project on your local machine, it’s time to open it in a code editor. Visual Studio Code (VS Code) is a popular choice for Python development.

    • What’s happening? The “ResizerMate” project folder is opened in VS Code. Then, a new file named script.py is created. The .py extension tells VS Code (and Python) that this is a Python file.
    • Why is this important? VS Code provides tools like syntax highlighting, debugging, and terminal integration that make coding easier. Creating a .py file is where your Python code will live.
    • Learn More:

    Step 4: Write Your First Python Script (“Hello, World!”) [Video Timestamp: 02:13]

    It’s a tradition in programming to start with a simple “Hello, World!” program to ensure everything is set up correctly.

    • What’s happening? The video shows the following Python code being typed into script.py:
    if __name__ == "__main__": 
        print("hello world")
    • Why is this important? This basic script, when run, will print “hello world” to the screen. The if __name__ == "__main__": part is a common Python idiom that ensures the print statement runs when the script is executed directly.
    • Learn More about Python basics: If you’re new to Python, the official Python tutorial is a great place to start: The Python Tutorial

    Step 5: Run Your Python Script [Video Timestamp: 02:43]

    After writing the code, the next step is to run it and see the output.

    • What’s happening? The script is run in the terminal (the integrated terminal within VS Code).
    • Why is this important? This confirms that your Python installation is working and your script does what you expect.
    • Learn More (running Python in VS Code is covered in the VS Code Python tutorial linked in Step 3).

    Step 6: Save Your Work with Git & Push to GitHub [Video Timestamps: 02:49 – 03:35]

    Now that you’ve made changes (created a new file and added code), you need to save this progress to your version control system (Git) and then send these changes back to your GitHub repository. This is a multi-step process:

    1. Add files to staging (git add): You tell Git which changes you want to include in your next save point (commit).
    2. Commit changes (git commit): You create a snapshot of your changes with a descriptive message. This snapshot is saved in your local Git repository.
    3. Push changes (git push): You upload your local commits to the remote repository on GitHub.
    • What’s happening? The video shows the script.py file being added to Git, then a “commit” is made with a message describing the changes. Finally, these committed changes are “pushed” to the GitHub repository. The video concludes by verifying on GitHub.com that the file and its content have appeared in the remote “ResizerMate” repository.
    • Why is this important?
      • git add prepares your changes.
      • git commit creates a record of your work locally, allowing you to revert to this point if needed.
      • git push updates the remote repository on GitHub, backing up your work and making it available to collaborators (if any).
    • Learn More:

    And that’s it! You’ve successfully initiated a Python project, from creating its online presence on GitHub to writing and saving your first lines of code. These fundamental steps are the bedrock of most software development workflows. Happy coding!