Existence Proofs

Source: https://xkcd.com/1856/

How To Use Facebook Emoji to Respond to a Mathematical Proof

Source: https://www.facebook.com/MathWithBadDrawings/photos/a.822582787758549/2865881973428610/?type=3&theater

Adding by a Form of 0 (Part 3)

As part of my discrete mathematics class, I introduce my freshmen/sophomore students to various proof techniques, including proofs about sets. Here is one of the examples that I use that involves adding and subtracting a number twice in the same proof.

Theorem. Let A be the set of even integers, and define

B = \{ n: n = m+1 for some odd integer m\}

Then A = B.

Proof (with annotations). Before starting the proof, I should say that I expect my students to use the formal definitions of even and odd:

  • An integer n is even if n = 2k for some integer k.
  • An integer n is odd if n = 2k+1 for some integer k.

To prove that A = B, we must show that A \subseteq B and B \subseteq A. The first of these tends to trickiest for students.

Part 1. Let n \in A. By definition of even, that means that there is an integer k so that n = 2k.

To show that n \in B, we must show that n = m + 1 for some odd integer m. To this end, notice that n = (n-1) + 1. Thus, we must show that n - 1 is an odd integer, or that n -1 can be written in the form 2k+1. To do this, we add and subtract 1 a second time:

n = 2k

= (2k - 1) + 1

= ([2k - 1 - 1] + 1) + 1

= ([2k-2] + 1) + 1

= (2[k-1] + 1) + 1.

By the closure axioms, k-1 is an integer. Therefore, 2[k-1] + 1 is an odd number by definition of odd, and hence $n \in B$.

The above part of the proof can be a bit much to swallow for students first learning about proofs. For completeness, let me also include Part 2 (which, in my experience, most students can produce without difficulty).

Part 2. Let n \in B, so that n = m + 1 for some odd integer m. By definition of odd, there is an integer k so that $m = 2k+1$. Therefore, n = (2k+1) + 1 = 2k+2 = 2(k+1). By the closure axioms, k +1 is an integer. Therefore, n is even by definition of even, and so we conclude that n \in A.

\square

For what it’s worth, this is the review problems for which I recorded myself talking through the solution for the benefit of my students.

In my opinion, the biggest conceptual barriers in this proof are these steps from Part 1:

2k = (2k - 1) + 1 = ([2k - 1 - 1] + 1) + 1.

These steps are undeniably awkward. Back in high school algebra, students would get points taken off for making the expression more complicated instead of simplifying the answer. But this is the kind of jump that I need to train my students to do so that they can master this technique and be successful in their future math classes.

Predicate Logic and Popular Culture (Part 206): Jack Johnson

Let H be the set of all things, let T be the set of all times, let G(x) be the proposition “x is good,” and let R(x,t) be the proposition “x remains at time t.” Translate the logical statement

\forall x \in H(G(x) Longrightarrow \forall t \in T(R(x,t))).

This matches a line from “Mudfootball” by Jack Johnson.

Context: Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.

Predicate Logic and Popular Culture (Part 205): Bob Marley

Let T be the set of all things, let L(x) be the proposition “x is a little thing,” and let A(x) be the proposition “x is going to be all right.” Translate the logical statement

\forall x \in T(L(x) \Longrightarrow A(x)).

This matches a line from “Three Little Birds” by Bob Marley.

Context: Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.

Predicate Logic and Popular Culture (Part 204): Billy Joel

Let T be the set of all times, and let W(t) be the proposition “She is a woman to me at time t.” Translate the logical statement

\forall t \in T( W(t)).

This matches a line from “She’s Always a Woman” by Billy Joel.

Context: Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.

Predicate Logic and Popular Culture (Part 203): Bill Withers

Let P be the set of all people, let T be the set of all times, let P(x,t) be the proposition “x has pain at time t,” and let S(x,t) be the proposition “x has sorrow at time t.” Translate the logical statement

\forall x \in P( \exists t_1 \in T(P(x,t)) \land \exists t_2 \in T(S(x,t)).

This matches a line from “Lean on Me.” Note: while I think the translation above matches the intent of the song, a case could be made that, literally rendered, the “there exists” symbols should come first — that there’s a single time that everyone has pain at that one time.

Context: Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.

Predicate Logic and Popular Culture (Part 202): The LEGO Movie

Let T be the set of all things, let p be the proposition “You’re part of a team,” let A(x) be the proposition “x is awesome,” and let C(x) be the proposition “x is cool.” Translate the logical statement

p \Longrightarrow \forall x in T(A(x) \land C(x)).

This matches the opening line of “Everything is Awesome!!!” from The LEGO Movie.

Context: Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.

Predicate Logic and Popular Culture (Part 201): Hamilton

Let T be the set of all times, let time 0 be now, and let L(t) be the proposition “I like the quiet at time t.” Translate the logical statement

\forall t \in T(t < 0 \longrightarrow \lnot L(t)).

This matches a line from “It’s Quiet Uptown” from the hit musical Hamilton.

Context: Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.

Predicate Logic and Popular Culture (Part 200): Spider-Man

Let T be the set of all times, and let R(t) be the proposition “I will rest at time t,” and let M(t) be the proposition “You are unmasked and eliminated at time t.” Translate the logical statement

\forall t \in T(\lnot M(t) \Longrightarrow \lnot R(t)).

This matches a line by J. Jonas Jameson in the 1990s Spider-Man cartoons.

Context: Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.