Please Login to access more options.


Today

« January 2019 »

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

From Ben: Remember to complete the Prep Report in I-Learn. I'll list, below, the people who are presenting each problem.
  • 4 - Dayton
  • 7 - George
  • 8 - Brook 8b
  • 9 - Julie
  • 10 - Sheldon

Definition (Limit Point Of A Set Of Real Numbers)

Let $S$ be a set of real numbers. We say that a point $p$ is a limit point of $S$ if every open interval $I=(a,b)$ that contains $p$ also contains a point $x$ in $S$ with $x\neq p$.

Problem 6: (A Limit Point Of An Open Interval)

Let $S=(0,1)$ which is the open interval from 0 to 1 that does not include the end points. Prove that $p=1$ is a limit point of $S$. Then state another limit point of $S$.

Problem 7: (A Set With One Limit Point)

Let $\ds S=\left\{\frac{1}{n}\mid n\in \mathbb{N}\right\}$, the collection of fractions of the form $\frac{1}{n}$ where $n$ is a natural number. Prove that $p=0$ is a limit point of $S$.

Prediction:

How does this class differ from your lower level math courses? What's the best way to succeed in this class?

Click to see a possible answer.

In your lower level courses, the focus is often primarily on learning how to mimic an algorithm to obtain a numerically correct answer at the end. In your upper division courses, the focus shifts to the process of how we obtain answers, and the logic behind why the process works. This course prepares you for this shift in focus.

You'll want to spend 2-3 hours between each class period working on the problem set on this course website. The best way to succeed in this course is consistent daily effort. Study groups can be a life saver as well, provided you think of group meetings as working meetings (where everyone works on new material rather than sharing what you already figured out).

Nothing can substitute for diligent consistent effort. As you work, you will hit dead ends. That's a normal part of doing mathematics. Failure is an important part of the learning process. Don't worry if you don't get the solution to every problem before class. Just do your best, and give yourself enough time before class to be able to ask questions of others.

In the work above, we saw several sets of real numbers. We've used sets our whole life to group together objects that have some common property. That is precisely what a set it, a group of things that share something in common.

Definition (Set, Subset, Equality Of Sets)

A set $S$ is a collection of elements that have been grouped together.

  • We use brackets $\{$ and $\}$ to enclose elements of sets.
  • We'll write $x\in S$ to say that $x$ is an element of $S$ or $x$ is in $S$. Similarly, we'll write $x\notin S$ to say that $x$ is not in $S$.
  • We say that a set $B$ is a subset of the set $S$, and we write $B\subseteq S$, if every element in $B$ is also an element of $S$. We also read $A\subseteq B$ as "$A$ is contained in $B$." We'll often write $B\supseteq A$ instead of $A\subseteq B$, and read $B\supseteq A$ as either "$B$ is a super set of $A$" or "$B$ contains $A$."
  • We say that $B$ is a proper subset of $S$ if $B\subseteq S$ but there is an element of $S$ that is not in $B$.
  • We say that two sets $A$ and $B$ are equal if $A\subseteq B$ and $B\subseteq A$.

There are two general ways to express elements of a set. We can use the roster method where we list the elements of a set, as in $\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\ldots\}$. The roster method requires the reader to guess the remaining elements of the set, and hence can sometimes lead to unclear proofs. To avoid this potential confusion, we use set builder notation. With set builder notation, we express how to obtain the elements, as in $\{\frac{1}{n}\mid \in\mathbb{N}\}$. Any time you see $\{x\mid P(x)\}$ you can read this as the set of $x$ such that $P(x)$ holds.

There are many different ways we can use set builder notation to describe the exact same set, and we need to be able to show when two different ways are equal. For an example, consider the interval $I=(5,9] $. Let $S$ be the collection of upper bounds of $I$, which we can write in set builder notation as $$S=\{x\mid x \text{ is an upper bound of } I\}.$$ I claim that $S=\{x\mid x\geq 9\} $. Halt. This is a claim that two sets, namely $S$ and the set $A=\{x\mid x\geq 9\} $ are equal. From the definition above about equality of sets, to prove this claim is true we must prove that $S\subseteq A$ and that $A\subseteq S$. That's precisely what the next problem has you prove.

Problem 8: (First Proof That Two Sets Are Equal)

Let $I=(5,9] $. Consider the sets $S=\{x\mid x \text{ is an upper bound of } I\}$ and $A=\{x\mid x\geq 9\} $. Prove that $S=A$.

  • Start by proving that $S\subseteq A$. So show that every element of $S$ is an element of $A$.
  • Then prove that $A\subseteq S$.

Problem 9: (Second Proof That Two Sets Are Equal)

Let $I=(5,9] $. Consider the sets $T=\{x\mid x \text{ is a lower bound of } I\}$ and $B=\{x\mid x\leq 5\} $. Prove that $T=B$.

An important set that will show up often throughout the semester is the set with nothing in it, which we call the empty set.

Definition (Empty Set)

The empty set is the set $\emptyset = \{\}$ that contains no elements. If we think of a set as a box with elements in it, then the empty set is a box with nothing in it.

Here is another axiom that you have probably used many times in your life without ever realizing it.

Axiom (Well Ordering Principle)

Every nonempty subset $S$ of the natural numbers has a least element. By least element, we mean that there is a natural number $m$ which is an element of $S$ such that $m\leq x$ for every $x$ in $S$.

Problem 10: (Which Dominoes Remain Standing)

Suppose that Jon has set up an infinite number of dominoes, with the dominoes numbered $1,2,3, \ldots$. The dominoes are set up so that if the $k$th domino falls, then the $(k+1)$st domino will also fall. So if the 7th domino falls, then the 8th must fall as well. Jon knocks down the first domino, which starts causing other dominos to fall. Which dominos fall? Which dominoes remain standing? Make sure you prove your result. The well ordering principle will come in handy.

Suggestion: Use set builder notation to help you, so let $F=\{n\in \mathbb{N}\mid \text{domino $n$ fell}\}$ and $S=\{n\in \mathbb{N}\mid \text{domino $n$ remains standing}\}$. Then make some claims and prove they are correct.

Definition (Statement And Open Sentence)
  • A statement is a sentence that can be classified as either true or false (but not both). The truth value of a statement is either "True" or "False." For a sentence to be a statement, it is not necessary that we know the truth value, but it must be clear that the value is either "True" or "False."
  • Some sentences involve a variable, and the truth value of the sentence cannot be determined until the value of the variable is specified. An open sentence is a sentence involving a variable whose truth value cannot be determined until the variables in the sentence are specified, at which point the open sentence becomes a statement.
Exercise (Recognizing Statements And Open Sentences)

Classify each sentence below as a statement, an open sentence, or neither. Make sure you justify each answer.

  1. Every integer is either even or odd.
  2. Today is Thursday.
  3. $x^2-9=0.$
  4. The second coming will occur in 2050.
  5. Sunsets are beautiful.
  6. Have you read the first book in the Harry Potter series?
  7. $\cos^2(x)+\sin^2(x)=1$.

Click to see a solution.

  1. The sentence "Every integer is either even or odd" is a statement, as it has the truth value of "True."
  2. The sentence "Today is Thursday" is an open sentence. The truth value depends on what the variable "today" is.
  3. The sentence "$x^2-9=0$" is an open sentence. The variable is $x$, and the value $x$ determines whether or not $x^2-9$ equals zero or not.
  4. The sentence "The second coming will occur in 2050" is a statement. It is either true or false, however we do not have the ability to determine the truth value (as we cannot see the future). The sentence is definitely either true or false, and not both, so it is a statement.
  5. The sentence "Sunsets are beautiful" is an opinion, and hence is neither a statement nor an open sentence.
  6. While "$\cos^2(x)+\sin^2(x)=1$" has a variable $x$ in it, we could argue that this is a statement and not an open sentence as the sentence is true for any value $x$ that makes sense in this sentence. However, since the variable $x$ was not specified, you could also argue that this is an open sentence. The context in which sentence occurs may alter whether a sentence is an open sentence or statement. If the sentence had instead read "For any real number $x$ we have $\cos^2(x)+\sin^2(x)=1$," then the sentence is definitely a true statement without any possible argument.
Definition (Negation, Conjunction, Disjunction Of Statements)

Let $P$ and $Q$ be statements or open sentences.

  • The negation of $P$, written $\sim P$, is the statement or open sentence which is true precisely when $P$ is false. We often read $\sim P$ as "It is not the case that $P$."
  • The conjunction of $P$ and $Q$, written $P\wedge Q$, is the statement or open sentence "$P$ and $Q$." A conjunction is true only when both $P$ and $Q$ are true. So a conjunction is false unless both $P$ and $Q$ are true.
  • The disjunction of $P$ and $Q$, written $P\vee Q$, is the statement or open sentence "$P$ or $Q$." A disjunction is true when $P$ is true, or $Q$ is true, or both are true. So a disjunction is true unless both $P$ and $Q$ are false.
Definition (Truth Table)

Let $P_1, P_2, \ldots, P_n$ be $n$ statements or open sentences that are used to make the compound sentence $P$. A truth table for this compound sentence is a table that keeps track of all possible truth values for the compound sentence based upon the possible truth values for each of $P_1, P_2, \ldots, P_n$.

Exercise (A Truth Table For A Conjunction Its Negation)

Construct a truth table for $P\wedge Q$ and $\sim(P\wedge Q)$.

Click to see a solution.

We know that $P\wedge Q$ is false unless both $P$ and $Q$ are both true. There are four cases to consider when looking at the truth values of $P$ and $Q$, hence our truth table has 4 rows. This gives us the third column in the truth table below for $P\wedge Q$. The fourth column below contains the truth values for $\sim(P\wedge Q)$ by just interchanging the $T$ and $F$ values from the third column. $$ \begin{array}{c|c|c} P&Q&P\wedge Q&\sim(P\wedge Q) \\\hline T&T&T&F\\ T&F&F&T\\ F&T&F&T\\ F&F&F&T \end{array} $$

Definition (Logically Equivalent)

We say two statements or open sentences are logically equivalent if they have the same truth value for all possible values of their component statements.

Problem 11: (De Morgan's Laws With Truth Tables)

Let $P$ and $Q$ be statements or open sentences. Start by completing the truth table below to give the truth values for $P\vee Q$, $\sim (P\vee Q)$, $(\sim P)\vee (\sim Q)$, and $(\sim P)\wedge (\sim Q).$ $$ \begin{array}{c|c|c|c|c|c|c|c} P&Q&P\vee Q&\sim(P\vee Q) &\sim P&\sim Q &(\sim P)\vee (\sim Q) & (\sim P)\wedge (\sim Q)\\\hline T&T&&&&&&\\ T&F&&&&&&\\ F&T&&&&&&\\ F&F&&&&&& \end{array} $$

  1. Use your truth table to prove that $\sim (P\vee Q)$ and $(\sim P)\wedge (\sim Q)$ are logically equivalent.
  2. Construct a similar truth table to prove that $\sim (P\wedge Q)$ and $(\sim P)\vee (\sim Q)$ are logically equivalent .

In other words, when you have finished this problem you will have shown that

the negation of a disjunction is the conjunction of the negations, and
the negation of a conjunction is the disjunction of the negations.

Problem 12: (Associativity Laws With Truth Tables)

Let $P$, $Q$, and $R$ be statements or open sentences. Use truth tables to prove each of the following.

  1. Prove that $(P\wedge Q)\wedge R$ is equivalent to $P\wedge (Q\wedge R)$.
  2. Prove that $(P\vee Q)\vee R$ is equivalent to $P\vee (Q\vee R)$.
  3. Is $(P\vee Q)\wedge R$ equivalent to $P\vee (Q\wedge R)$.

Problem 13: (Distributive Laws With Truth Tables)

Let $P$, $Q$, and $R$ be statements or open sentences. Use truth tables to prove each of the following.

  1. Prove that $(P\wedge Q)\vee R$ is equivalent to $(P\vee R)\wedge (Q\vee R)$.
  2. Prove that $(P\vee Q)\wedge R$ is equivalent to $(P\wedge R)\vee (Q\wedge R)$.

Problem 14: (Creating A Truth Table For An Implication)

Suppose your teacher tells you the following "If you pass the final, then you pass the class." This sentence contains a construction of the form "If $P$, then $Q$."

  1. There are four different scenarios that might occur as you may or may not pass the final, and you may or may not pass the class. List the four scenarios and decide in each scenario if the teacher lied.
  2. Suppose that $P$ and $Q$ are statements. Use your answer to the previous part to construct a truth table for the statement "If $P$ then $Q$."

Definition (Implication)

If $P$ and $Q$ are statements or open sentences, then an implication, written symbolically as $P\implies Q$, is the sentence "If $P$, then $Q$" or equivalently "$P$ implies $Q$". There are several equivalent ways to express this sentence such as "$Q$ if $P$" or "$P$ only if $Q$." The implication $P\implies Q$ is true unless $P$ is true and $Q$ is false.

Definition (Converse, Inverse, And Contrapositive)

Consider the implication $P\implies Q$. From this implication we can define 3 other implications.

  • The converse of $P\implies Q$ is the implication $Q\implies P$.
  • The inverse of $P\implies Q$ is the implication $(\sim P)\implies (\sim Q)$.
  • The contrapositive of $P\implies Q$ is the implication $(\sim Q)\implies (\sim P)$.

Problem 15: (Practice With Converse Inverse And Contrapositive)

Let $A=[3,7)$. Consider the implication "If $x\geq 8$ then $x$ is an upper bound of $A$."

  1. Is this implication true or false?
  2. Write the converse of this implication and determine the truth value of the converse.
  3. Write the inverse of this implication and determine the truth value of the inverse.
  4. Write the contrapositive of this implication and determine the truth value of the contrapositive.

Remember to always justify any claims you make.

Problem 16: (What Is Logically Equivalent To An Implication)

Consider the implication $P\implies Q$.

  1. Construct a truth table that contains the possible values for this implication, the converse, the inverse, and the contrapositive. Feel free to use the table at the end of this problem to complete your work.
  2. Which of these sentences are logically equivalent?

$$ \begin{array}{c|c|c|c|c|c|c|c} P&Q&P\implies Q&Q\implies P &\sim P&\sim Q &(\sim P)\implies (\sim Q) & (\sim Q)\implies (\sim P)\\\hline T&T&&&&&&\\ T&F&&&&&&\\ F&T&&&&&&\\ F&F&&&&&& \end{array} $$

Problem 17: (Creating Examples Of Implications)

Give an example of each of the following, or explain why it cannot be done. Make sure you justify your claims (as always).

  1. An implication that is true, and the converse is true.
  2. An implication that is false, but the converse is true.
  3. An implication that is true, but the contrapositive is false.

Problem 18: (The Negation Of An Implication Is A Conjunction)

In this problem we want to find the negation of $P\implies Q$.

  1. In a truth table for an implication $P\implies Q$, how many of the 4 rows contain the truth value $T$?
  2. In a truth table for a conjuction $P\wedge Q$, how many of the 4 rows contain the truth value $T$?
  3. In a truth table for a disjunction $P\vee Q$, how many of the 4 rows contain the truth value $T$?
  4. In a truth table for the negation of the implication $P\implies Q$, how many of the 4 rows contain the truth value $T$? Based off this answer alone, explain why you expect the negation of an implication to be a conjunction.
  5. Complete the truth table below, and use your answer to determine which statement is logically equivalent to $\sim(P\implies Q)$.

$$ \begin{array}{c|c|c|c|c|c|c|c} P&Q&P\implies Q&\sim(P\implies Q) &P \wedge Q &P \wedge (\sim Q) & (\sim P) \wedge Q& (\sim P) \wedge (\sim Q) \\\hline T&T&&&&&&\\ T&F&&&&&&\\ F&T&&&&&&\\ F&F&&&&&& \end{array} $$

For more problems, see AllProblems