0_1_3A_What_is_Discrete_Mathematics
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/0%3A_Introduction_and_Preliminaries/0.1%3A_What_is_Discrete_Mathematics
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
dis·crete / dis'krët.
*Adjective*: Individually separate and distinct.
*Synonyms*: separate - detached - distinct - abstract.
Defining *discrete mathematics* is hard because defining *mathematics* is hard. What is mathematics? The study of numbers? In part, but you also study functions and lines and triangles and parallelepipeds and vectors and …. Or perhaps you want to say that mathematics is a collection of tools that allow you to solve problems. What sort of problems? Okay, those that involve numbers, functions, lines, triangles, …. Whatever your conception of what mathematics is, try applying the concept of “discrete” to it, as defined above. Some math fundamentally deals with *stuff* that is individually separate and distinct.
In an algebra or calculus class, you might have found a particular set of numbers (maybe the set of numbers in the range of a function). You would represent this set as an interval: \\$$0,\infty)\\ is the range of \\f(x) = x^2\\ since the set of outputs of the function are all real numbers 0 and greater. This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them which are also in the set. Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function which gives the number of children of each person reading this. What is the range? I'm guessing it is something like \\\\0, 1, 2, 3\\\text{.}\\ Maybe 4 is in there too. But certainly there is nobody reading this that has 1.32419 children. This set *is* discrete because the elements are separate. Also notice that the inputs to the function are a discrete set as each input is an individual person. You would not consider fractional inputs (we don't care about anything \\2/3\\ between a pair of readers).
One way to get a feel for the subject is to consider the types of problems you solve in discrete math. Here are a few simple examples:
Investigate!
*Note: Throughout the text you will see *Investigate!* activities like this one. Answer the questions in these as best you can to give yourself a feel for what is coming next.*
1. The most popular mathematician in the world is throwing a party for all of his friends. As a way to kick things off, they decide that everyone should shake hands. Assuming all 10 people at the party each shake hands with every other person (but not themselves, obviously) exactly once, how many handshakes take place?
2. At the warm-up event for Oscar's All Star Hot Dog Eating Contest, Al ate one hot dog. Bob then showed him up by eating three hot dogs. Not to be outdone, Carl ate five. This continued with each contestant eating two more hot dogs than the previous contestant. How many hot dogs did Zeno (the 26th and final contestant) eat? How many hot dogs were eaten all together?
3. After excavating for weeks, you finally arrive at the burial chamber. The room is empty except for two large chests. On each is carved a message (strangely in English): \![$$(https://math.libretexts.org/images/two-chests.svg)
\![two-chests.svg$$(https://math.libretexts.org/@api/deki/files/12720/two-chests.svg?revision=1)
You know exactly one of these messages is true. What should you do?
1. Back in the days of yore, five small towns decided they wanted to build roads directly connecting each pair of towns. While the towns had plenty of money to build roads as long and as winding as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed. Is it possible for each of these towns to build a road to each of the four other towns without creating any intersections?
One reason it is difficult to define discrete math is that it is a very broad description which encapsulates a large number of subjects. In this course we will study four main topics: combinatorics (the theory of ways things *combine*; in particular, how to count these ways), sequences , symbolic logic , and graph theory . However, there are other topics that belong under the discrete umbrella, including computer science, abstract algebra, number theory, game theory, probability, and geometry (some of these, particularly the last two, have both discrete and non-discrete variants).
Ultimately the best way to learn what discrete math is about is to *do* it. Let's get started! Before we can begin answering more complicated (and fun) problems, we must lay down some foundation. We start by reviewing mathematical statements, sets, and functions in the framework of discrete mathematics.
---
0_2_3A_Mathematical_Statements
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/0%3A_Introduction_and_Preliminaries/0.2%3A_Mathematical_Statements
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a *knight*, who always tells the truth, or a *knave*, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave. Each troll makes a single statement:
- Troll 1: If I am a knave, then there are exactly two knights here.
- Troll 2: Troll 1 is lying.
- Troll 3: Either we are all knaves or at least one of us is a knight.
Which troll is which?
In order to *do* mathematics, we must be able to *talk* and *write* about mathematics. Perhaps your experience with mathematics so far has mostly involved finding answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.
Communication in mathematics requires more precision than many other subjects, and thus we should take a few pages here to consider the basic building blocks: *mathematical statements*.
Atomic and Molecular Statements
A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular .
Example \\\PageIndex{1}\\
These are statements (in fact, *atomic* statements):
- Telephone numbers in the USA have 10 digits.
- The moon is made of cheese.
- 42 is a perfect square.
- Every even number greater than 2 can be expressed as the sum of two primes.
- \\3+7 = 12\\
And these are not statements:
- Would you like some cake?
- The sum of two squares.
- \\1+3+5+7+\cdots+2n+1\text{.}\\
- Go to your room!
- \\3+x = 12\\
The reason the last sentence is not a statement is because it contains a variable. Depending on what \\x\\ is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done in a number of ways. For example, “\\3+x = 12\\ where \\x = 9\\” is a true statement, as is “\\3+x = 12\\ for some value of \\x\\”. This is an example of *quantifying* over a variable, which we will discuss more in a bit.
You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives . For example, this is a molecular statement:
Telephone numbers in the USA have 10 digits and 42 is a perfect square.
Note that we can break this down into two smaller statements. The two shorter statements are *connected* by an “and.” We will consider 5 connectives: “and” (Sam is a man and Chris is a woman), “or” (Sam is a man or Chris is a woman), “if…, then…” (if Sam is a man, then Chris is a woman), “if and only if” (Sam is a man if and only if Chris is a woman), and “not” (Sam is not a man). The first four are called binary connectives (because they connect two statements) while “not” is an example of a unary connective (since it applies to a single statement).
Which connective we use to modify statement(s) will determine the truth value of the molecular statement (that is, whether the statement is true or false), based on the truth values of the statements being modified. It is important to realize that we do not need to know what the parts actually say, only whether those parts are true or false. So to analyze logical connectives, it is enough to consider propositional variables (sometimes called *sentential* variables), usually capital letters in the middle of the alphabet: \\P, Q, R, S, \ldots\text{.}\\ These are variables that can take on one of two values: T or F. We also have symbols for the logical connectives: \\\wedge\text{,}\\ \\\vee\text{,}\\ \\\imp\text{,}\\ \\\iff\text{,}\\ \\\neg\text{.}\\
Logical Connectives
- \\P \wedge Q\\ means \\P\\ and \\Q\text{,}\\ called a conjunction .
- \\P \vee Q\\ means \\P\\ or \\Q\text{,}\\ called a disjunction .
- \\P \imp Q\\ means if \\P\\ then \\Q\text{,}\\ called an implication or conditional .
- \\P \iff Q\\ means \\P\\ if and only if \\Q\text{,}\\ called a biconditional .
- \\\neg P\\ means not \\P\text{,}\\ called a negation .
The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connectives:
Truth Conditions for Connectives
- \\P \wedge Q\\ is true when both \\P\\ and \\Q\\ are true
- \\P \vee Q\\ is true when \\P\\ or \\Q\\ or both are true.
- \\P \imp Q\\ is true when \\P\\ is false or \\Q\\ is true or both.
- \\P \iff Q\\ is true when \\P\\ and \\Q\\ are both true, or both false.
- \\\neg P\\ is true when \\P\\ is false.
Note that for us, *or* is the inclusive or (and not the sometimes used *exclusive or*) meaning that \\P \vee Q\\ is in fact true when both \\P\\ and \\Q\\ are true. As for the other connectives, “and” behaves as you would expect, as does negation. The biconditional (if and only if) might seem a little strange, but you should think of this as saying the two parts of the statements are *equivalent*. This leaves only the conditional \\P \imp Q\\ which has a slightly different meaning in mathematics than it does in ordinary usage. However, implications are so common and useful in mathematics, that we must develop fluency with their use, and as such, they deserve their own subsection.
Implications
Implications
An implication or conditional is a molecular statement of the form
\begin{equation\*} P \imp Q \end{equation\*}
where \\P\\ and \\Q\\ are statements. We say that
- \\P\\ is the hypothesis (or antecedent ).
- \\Q\\ is the conclusion (or consequent ).
An implication is *true* provided \\P\\ is false or \\Q\\ is true (or both), and *false* otherwise. In particualr, the only way for \\P \imp Q\\ to be false is for \\P\\ to be true *and* \\Q\\ to be false.
Easily the most common type of statement in mathematics is the conditional, or implication. Even statements that do not at first look like they have this form conceal an implication at their heart. Consider the *Pythagorean Theorem*. Many a college freshman would quote this theorem as “\\a^2 + b^2 = c^2\text{.}\\” This is absolutely not correct. For one thing, that is not a statement since it has three variables in it. Perhaps they imply that this should be true for any values of the variables? So \\1^2 + 5^2 = 2^2\text{???}\\ How can we fix this? Well, the equation is true as long as \\a\\ and \\b\\ are the legs or a right triangle and \\c\\ is the hypotenuse. In other words:
*If* \\a\\ and \\b\\ are the legs of a right triangle with hypotenuse \\c\text{,}\\ *then* \\a^2 + b^2 = c^2\text{.}\\
This is a reasonable way to think about implications: our claim is that the conclusion (“then” part) is true, but on the assumption that the hypothesis (“if” part) is true. We make no claim about the conclusion in situations when the hypothesis is false.
Still, it is important to remember that an implication is a statement, and therefore is either true or false. The truth value of the implication is determined by the truth values of its two parts. To agree with the usage above, we say that an implication is true either when the hypothesis is false, or when the conclusion is true. This leaves only one way for an implication to be false: when the hypothesis is true and the conclusion is false.
Example \\\PageIndex{2}\\
Consider the statement:
If Bob gets a 90 on the final, then Bob will pass the class.
This is definitely an implication: \\P\\ is the statement “Bob gets a 90 on the final,” and \\Q\\ is the statement “Bob will pass the class.”
Suppose I made that statement to Bob. In what circumstances would it be fair to call me a liar? What if Bob really did get a 90 on the final, and he did pass the class? Then I have not lied; my statement is true. However, if Bob did get a 90 on the final and did not pass the class, then I lied, making the statement false. The tricky case is this: what if Bob did not get a 90 on the final? Maybe he passes the class, maybe he doesn't. Did I lie in either case? I think not. In these last two cases, \\P\\ was false, and the statement \\P \imp Q\\ was true. In the first case, \\Q\\ was true, and so was \\P \imp Q\text{.}\\ So \\P \imp Q\\ is true when either \\P\\ is false or \\Q\\ is true.
Just to be clear, although we sometimes read \\P \imp Q\\ as “\\P\\ *implies* \\Q\\”, we are not insisting that there is some causal relationship between the statements \\P\\ and \\Q\text{.}\\ In particular, if you claim that \\P \imp Q\\ is *false*, you are not saying that \\P\\ does not imply \\Q\text{,}\\ but rather that \\P\\ is true and \\Q\\ is false.
Example \\\PageIndex{3}\\
Decide which of the following statements are true and which are false. Briefly explain.
1. \\0=1 \~~ \imp \~~ 1=1\\
2. \\1=1 \~~ \imp \~~\\ most horses have 4 legs
3. If 8 is a prime number, then the 7624th digit of \\\pi\\ is an 8.
4. If the 7624th digit of \\\pi\\ is an 8, then \\2+2 = 4\\
Solution
All four of the statements are true. Remember, the only way for an implication to be false is for the *if* part to be true and the *then* part to be false.
1. Here the hypothesis is false and the conclusion is true, so the implication is true.
2. Here both the hypothesis and the conclusion is true, so the implication is true. It does not matter that there is no meaningful connection between the true mathematical fact and the fact about horses.
3. I have no idea what the 7624th digit of \\\pi\\ is, but this does not matter. Since the hypothesis is false, the implication is automatically true.
4. Similarly here, regardless of the truth value of the hypothesis, the conclusion is true, making the implication true.
It is important to understand the conditions under which an implication is true not only to decide whether a mathematical statement is true, but in order to *prove* that it is. Proofs might seem scary (especially if you have had a bad high school geometry experience) but all we are really doing is explaining (very carefully) why a statement is true. If you understand the truth conditions for an implication, you already have the outline for a proof.
Direct Proofs of Implications
To prove an implication \\P \imp Q\text{,}\\ it is enough to assume \\P\text{,}\\ and from it, deduce \\Q\text{.}\\
There are other techniques to prove statements (implications and others) that we will encounter throughout our studies, and new proof techniques are discovered all the time. Direct proof is the easiest and most elegant style of proof and has the advantage that such a proof often does a great job of explaining *why* the statement is true.
Example \\\PageIndex{4}\\
Prove: If two numbers \\a\\ and \\b\\ are even, then their sum \\a+b\\ is even.
Solution
Suppose the numbers \\a\\ and \\b\\ are even. This means that \\a = 2k\\ and \\b=2j\\ for some integers \\k\\ and \\j\text{.}\\ The sum is then \\a+b = 2k+2j = 2(k+j)\text{.}\\ Since \\k+j\\ is an integer, this means that \\a+b\\ is even.
Notice that since we get to assume the hypothesis of the implication we immediately have a place to start. The proof proceeds essentially by repeatedly asking and answering, “what does that mean?”
\\\square\\
This sort of argument shows up outside of math as well. If you ever found yourself starting an argument with “hypothetically, let's assume …,” then you have attempted a direct proof of your desired conclusion.
Since implications are so prevalent in mathematics, we have some special language to help discuss them:
Converse and Contrapositive
- The converse of an implication \\P \imp Q\\ is the implication \\Q \imp P\text{.}\\ The converse is NOT logically equivalent to the original implication. That is, whether the converse of an implication is true is independent of the truth of the implication.
- The contrapositive of an implication \\P \imp Q\\ is the statement \\\neg Q \imp \neg P\text{.}\\ An implication and its contrapositive are logically equivalent (they are either both true or both false).
Mathematics is overflowing with examples of true implications with a false converse. If a number greater than 2 is prime, then that number is odd. However, just because a number is odd does not mean it is prime. If a shape is a square, then it is a rectangle. But it is false that if a shape is a rectangle, then it is a square. While this happens often, it does not always happen. For example, the Pythagorean theorem has a true converse: if \\a^2 + b^2 = c^2\text{,}\\ then the triangle with sides \\a\text{,}\\ \\b\text{,}\\ and \\c\\ is a *right* triangle. Whenever you encounter an implication in mathematics, it is always reasonable to ask whether the converse is true.
The contrapositive, on the other hand, always has the same truth value as its original implication. This can be very helpful in deciding whether an implication is true: often it is easier to analyze the contrapositive.
Example \\\PageIndex{5}\\
True or false: If you draw any nine playing cards from a regular deck, then you will have at least three cards all of the same suit. Is the converse true?
Solution
True. The original implication is a little hard to analyze because there are so many different combinations of nine cards. But consider the contrapositive: If you *don't* have at least three cards all of the same suit, then you don't have nine cards. It is easy to see why this is true: you can at most have two cards of each of the four suits, for a total of eight cards (or fewer).
The converse: If you have at least three cards all of the same suit, then you have nine cards. This is false. You could have three spades and nothing else. Note that to demonstrate that the converse (an implication) is false, we provided an example where the hypothesis is true (you do have three cards of the same suit), but where the conclusion is false (you do not have nine cards).
Understanding converses and contrapositives can help understand implications and their truth values:
Example \\\PageIndex{6}\\
Suppose I tell Sue that if she gets a 93% on her final, then she will get an A in the class. Assuming that what I said is true, what can you conclude in the following cases:
1. Sue gets a 93% on her final.
2. Sue gets an A in the class.
3. Sue does not get a 93% on her final.
4. Sue does not get an A in the class.
Solution
Note first that whenever \\P \imp Q\\ and \\P\\ are both true statements, \\Q\\ must be true as well. For this problem, take \\P\\ to mean “Sue gets a 93% on her final” and \\Q\\ to mean “Sue will get an A in the class.”
1. We have \\P \imp Q\\ and \\P\text{,}\\ so \\Q\\ follows. Sue gets an A.
2. You cannot conclude anything. Sue could have gotten the A because she did extra credit for example. Notice that we do not know that if Sue gets an \\A\text{,}\\ then she gets a 93% on her final. That is the converse of the original implication, so it might or might not be true.
3. The contrapositive of the converse of \\P \imp Q\\ is \\\neg P \imp \neg Q\text{,}\\ which states that if Sue does not get a 93% on the final, then she will not get an A in the class. But this does not follow from the original implication. Again, we can conclude nothing. Sue could have done extra credit.
4. What would happen if Sue does not get an A but *did* get a 93% on the final? Then \\P\\ would be true and \\Q\\ would be false. This makes the implication \\P \imp Q\\ false! It must be that Sue did not get a 93% on the final. Notice now we have the implication \\\neg Q \imp \neg P\\ which is the contrapositive of \\P \imp Q\text{.}\\ Since \\P \imp Q\\ is assumed to be true, we know \\\neg Q \imp \neg P\\ is true as well.
As we said above, an implication is not logically equivalent to its converse, but it is possible that both are true. In this case, when both \\P \imp Q\\ and \\Q \imp P\\ are true, we say that \\P\\ and \\Q\\ are equivalent. This is the biconditional we mentioned earlier:
If and only if
\\P \iff Q\\ is logically equivalent to \$P \imp Q) \wedge (Q \imp P)\text{.}\\
Example: Given an integer \\n\text{,}\\ it is true that \\n\\ is even if and only if \\n^2\\ is even. That is, if \\n\\ is even, then \\n^2\\ is even, as well as the converse: if \\n^2\\ is even, then \\n\\ is even.
You can think of “if and only if” statements as having two parts: an implication and its converse. We might say one is the “if” part, and the other is the “only if” part. We also sometimes say that “if and only if” statements have two directions: a forward direction \$P \imp Q)\\ and a backwards direction (\\P \leftarrow Q\text{,}\\ which is really just sloppy notation for \\Q \imp P\$.
Let's think a little about which part is which. Is \\P \imp Q\\ the “if” part or the “only if” part? Perhaps we should look at an example:
Example \\\PageIndex{7}\\
Suppose it is true that I sing if and only if I'm in the shower. We know this means both that if I sing, then I'm in the shower, and also the converse, that if I'm in the shower, then I sing. Let \\P\\ be the statement, “I sing,” and \\Q\\ be, “I'm in the shower.” So \\P \imp Q\\ is the statement “if I sing, then I'm in the shower.” Which part of the if and only if statement is this?
What we are really asking is what is the meaning of “I sing if I'm in the shower” and “I sing only if I'm in the shower.” When is the first one (the “if” part) *false*? When I am in the shower but not singing. That is the same condition on being false as the statement “if I'm in the shower, then I sing.” So the “if” part is \\Q \imp P\text{.}\\ On the other hand, to say, “I sing only if I'm in the shower” is equivalent to saying “if I sing, then I'm in the shower,” so the “only if” part is \\P \imp Q\text{.}\\
It is not terribly important to know which part is the “if” or “only if” part, but this does get at something very, very important: *there are many ways to state an implication!* The problem is, since these are all different ways of saying the same implication, we cannot use truth tables to analyze the situation. Instead, we just need good English skills.
Example \\\PageIndex{8}\\
Rephrase the implication, “if I dream, then I am asleep” in as many different ways as possible. Then do the same for the converse.
Solution
The following are all equivalent to the original implication:
1. I am asleep if I dream.
2. I dream only if I am asleep.
3. In order to dream, I must be asleep.
4. To dream, it is necessary that I am asleep.
5. To be asleep, it is sufficient to dream.
6. I am not dreaming unless I am asleep.
The following are equivalent to the converse (if I am asleep, then I dream):
1. I dream if I am asleep.
2. I am asleep only if I dream.
3. It is necessary that I dream in order to be asleep.
4. It is sufficient that I be asleep in order to dream.
5. If I don't dream, then I'm not asleep.
Hopefully you agree with the above example. We include the “necessary and sufficient” versions because those are common when discussing mathematics. In fact, let's agree once and for all what they mean:
Necessary and Sufficient
- “\\P\\ is necessary for \\Q\\” means \\Q \imp P\text{.}\\
- “\\P\\ is sufficient for \\Q\\” means \\P \imp Q\text{.}\\
- If \\P\\ is necessary and sufficient for \\Q\text{,}\\ then \\P \iff Q\text{.}\\
To be honest, I have trouble with these if I'm not very careful. I find it helps to have an example in mind:
Example \\\PageIndex{9}\\
Recall from calculus, if a function is differentiable at a point \\c\text{,}\\ then it is continuous at \\c\text{,}\\ but that the converse of this statement is not true (for example, \\f(x) = \|x\|\\ at the point 0). Restate this fact using “necessary and sufficient” language.
Solution
It is true that in order for a function to be differentiable at a point \\c\text{,}\\ it is necessary for the function to be continuous at \\c\text{.}\\ However, it is not necessary that a function be differentiable at \\c\\ for it to be continuous at \\c\text{.}\\
It is true that to be continuous at a point \\c\text{,}\\ it is sufficient that the function be differentiable at \\c\text{.}\\ However, it is not the case that being continuous at \\c\\ is sufficient for a function to be differentiable at \\c\text{.}\\
Thinking about the necessity and sufficiency of conditions can also help when writing proofs and justifying conclusions. If you want to establish some mathematical fact, it is helpful to think what other facts would *be enough* (be sufficient) to prove your fact. If you have an assumption, think about what must also be necessary if that hypothesis is true.
Quantifiers
Investigate!
Consider the statement below. Decide whether any are equivalent to each other, or whether any imply any others.
1. You can fool some people all of the time.
2. You can fool everyone some of the time.
3. You can always fool some people.
4. Sometimes you can fool everyone.
It would be nice to use variables in our mathematical sentences. For example, suppose we wanted to claim that if \\n\\ is prime, then \\n+7\\ is not prime. This looks like an implication. I would like to write something like
\begin{equation\*} P(n) \imp \neg P(n+7) \end{equation\*}
where \\P(n)\\ means “\\n\\ is prime.” But this is not quite right. For one thing, because this sentence has a free variable (that is, a variable that we have not specified anything about), it is not a statement. Now, if we plug in a specific value for \\n\text{,}\\ we do get a statement. In fact, it turns out that no matter what value we plug in for \\n\text{,}\\ we get a true implication. What we really want to say is that *for all* values of \\n\text{,}\\ if \\n\\ is prime, then \\n+7\\ is not. We need to *quantify* the variable.
Although there are many types of *quantifiers* in English (e.g., many, few, most, etc.) in mathematics we, for the most part, stick to two: existential and universal.
Universal and Existential Quantifiers
The existential quantifier is \\\exists\\ and is read “there exists” or “there is.” For example,
\\\exists x (x \< 0) \\
asserts that there is a number less than 0.
The universal quantifier is \\\forall\\ and is read “for all” or “every.” For example,
\begin{equation\*} \forall x (x \ge 0) \end{equation\*}
asserts that every number is greater than or equal to 0.
As with all mathematical statements, we would like to decide whether quantified statements are true or false. Consider the statement
\begin{equation\*} \forall x \exists y (y \< x). \end{equation\*}
You would read this, “for every \\x\\ there is some \\y\\ such that \\y\\ is less than \\x\text{.}\\” Is this true? The answer depends on what our *domain of discourse* is: when we say “for all” \\x\text{,}\\ do we mean all positive integers or all real numbers or all elements of some other set? Usually this information is implied. In discrete mathematics, we almost always quantify over the *natural numbers*, 0, 1, 2, …, so let's take that for our domain of discourse here.
For the statement to be true, we need it to be the case that no matter what natural number we select, there is always some natural number that is strictly smaller. Perhaps we could let \\y\\ be \\x-1\text{?}\\ But here is the problem: what if \\x = 0\text{?}\\ Then \\y = -1\\ and that is *not a number!* (in our domain of discourse). Thus we see that the statement is false because there is a number which is less than or equal to all other numbers. In symbols,
\begin{equation\*} \exists x \forall y (y \ge x). \end{equation\*}
To show that the original statement is false, we proved that the *negation* was true. Notice how the negation and original statement compare. This is typical.
Quantifiers and Negation
\\\neg \forall x P(x)\\ is equivalent to \\\exists x \neg P(x)\text{.}\\
\\\neg \exists x P(x)\\ is equivalent to \\\forall x \neg P(x) \text{.}\\
Essentially, we can pass the negation symbol over a quantifier, but that causes the quantifier to switch type. This should not be surprising: if not everything has a property, then something doesn't have that property. And if there is not something with a property, then everything doesn't have that property.
---
0_3_3A_Sets
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/0%3A_Introduction_and_Preliminaries/0.3%3A_Sets
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
The most fundamental objects we will use in our studies (and really in all of math) are *sets*. Much of what follows might be review, but it is very important that you are fluent in the language of set theory. Most of the notation we use below is standard, although some might be a little different than what you have seen before.
For us, a set will simply be an unordered collection of objects. Two examples: we could consider the set of all actors who have played *The Doctor* on *Doctor Who*, or the set of natural numbers between 1 and 10 inclusive. In the first case, Tom Baker is a element (or member) of the set, while Idris Elba, among many others, is not an element of the set. Also, the two examples are of different sets. Two sets are equal exactly if they contain the exact same elements. For example, the set containing all of the vowels in the declaration of independence is precisely the same set as the set of vowels in the word “questionably” (namely, all of them); we do not care about order or repetitions, just whether the element is in the set or not.
Notation
We need some notation to make talking about sets easier. Consider,
\begin{equation\*} A = \\1, 2, 3\\. \end{equation\*}
This is read, “\\A\\ is the set containing the elements 1, 2 and 3.” We use curly braces “\\\\,\~~ \\\\” to enclose elements of a set. Some more notation:
\begin{equation\*} a \in \\a, b, c\\. \end{equation\*}
The symbol “\\\in\\” is read “is in” or “is an element of.” Thus the above means that \\a\\ is an element of the set containing the letters \\a\text{,}\\ \\b\text{,}\\ and \\c\text{.}\\ Note that this is a true statement. It would also be true to say that \\d\\ is not in that set:
\begin{equation\*} d \not\in \\a, b, c\\. \end{equation\*}
Be warned: we write “\\x \in A\\” when we wish to express that one of the elements of the set \\A\\ is \\x\text{.}\\ For example, consider the set,
\begin{equation\*} A = \\1, b, \\x, y, z\\, \emptyset\\. \end{equation\*}
This is a strange set, to be sure. It contains four elements: the number 1, the letter b, the set \\\\x,y,z\\\text{,}\\ and the empty set (\\\emptyset = \\ \\\text{,}\\ the set containing no elements). Is \\x\\ in \\A\text{?}\\ The answer is no. None of the four elements in \\A\\ are the letter \\x\text{,}\\ so we must conclude that \\x \notin A\text{.}\\ Similarly, consider the set \\B = \\1,b\\\text{.}\\ Even though the elements of \\B\\ are elements of \\A\text{,}\\ we cannot say that the *set* \\B\\ is one of the elements of \\A\text{.}\\ Therefore \\B \notin A\text{.}\\ (Soon we will see that \\B\\ is a *subset* of \\A\text{,}\\ but this is different from being an *element* of \\A\text{.}\$
We have described the sets above by listing their elements. Sometimes this is hard to do, especially when there are a lot of elements in the set (perhaps infinitely many). For instance, if we want \\A\\ to be the set of all even natural numbers, we could write,
\begin{equation\*} A = \\0, 2, 4, 6, \ldots\\, \end{equation\*}
but this is a little imprecise. A better way would be
\begin{equation\*} A = \\x \in \N \st \exists n\in \N ( x = 2 n)\\. \end{equation\*}
Breaking that down: “\\x \in \N\\” means \\x\\ is in the set \\\N\\ (the set of natural numbers, \\\\0,1,2,\ldots\\\$, “\\:\\” is read “such that” and “\\\exists n\in \N (x = 2n) \\” is read “there exists an \\n\\ in the natural numbers for which \\x\\ is two times \\n\\” (in other words, \\x\\ is even). Slightly easier might be,
\begin{equation\*} A = \\x \st x\text{ is even} \\. \end{equation\*}
Note: Sometimes people use \\\|\\ or \\\backepsilon\\ for the “such that” symbol instead of the colon.
Defining a set using this sort of notation is very useful, although it takes some practice to read them correctly. It is a way to describe the set of all things that satisfy some condition (the condition is the logical statement after the “\\\st\\” symbol). Here are some more examples:
Example \\\PageIndex{1}\\
Describe each of the following sets both in words and by listing out enough elements to see the pattern.
1. \\\\x \st x + 3 \in \N\\\text{.}\\
2. \\\\x \in \N \st x + 3 \in \N\\\text{.}\\
3. \\\\x \st x \in \N \vee -x \in \N\\\text{.}\\
4. \\\\x \st x \in \N \wedge -x \in \N\\\text{.}\\
Solution
1. This is the set of all numbers which are 3 less than a natural number (i.e., that if you add 3 to them, you get a natural number). The set could also be written a s \\\\-3, -2, -1, 0, 1, 2, \ldots\\\\ (note that 0 is a natural number, so \\-3\\ is in this set because \\-3 + 3 = 0\$.
2. This is the set of all natural numbers which are 3 less than a natural number. So here we just have \\\\0, 1, 2,3 \ldots\\\text{.}\\
3. This is the set of all integers (positive and negative whole numbers, written \\\Z\$. In other words, \\\\\ldots, -2, -1, 0, 1, 2, \ldots\\\text{.}\\
4. Here we want all numbers \\x\\ such that \\x\\ and \\-x\\ are natural numbers. There is only one: 0. So we have the set \\\\0\\\text{.}\\
We already have a lot of notation, and there is more yet. Below is a handy chart of symbols. Some of these will be discussed in greater detail as we move forward.
Special sets
- \\\emptyset\\: The empty set is the set which contains no elements.
- \\\U\\: The universe set is the set of all elements.
- \\\N\\: The set of natural numbers. That is, \\\N = \\0, 1, 2, 3\ldots\\\text{.}\\
- \\\Z\\: The set of integers. That is, \\\Z = \\\ldots, -2, -1, 0, 1, 2, 3, \ldots\\\text{.}\\
- \\\Q\\: The set of rational numbers.
- \\\R\\: The set of real numbers.
- \\\pow(A)\\: The power set of any set \\A\\ is the set of all subsets of \\A\text{.}\\
Set Theory Notation
- \\\\, \\\\: We use these braces to enclose the elements of a set. So \\\\1,2,3\\\\ is the set containing 1, 2, and 3.
- \\\st\\: \\\\x \st x \> 2\\\\ is the set of all \\x\\ such that \\x\\ is greater than 2.
- \\\in\\: \\2 \in \\1,2,3\\\\ asserts that 2 is an element of the set \\\\1,2,3\\\text{.}\\
- \\\not\in\\: \\4 \notin \\1,2,3\\\\ because 4 is not an element of the set \\\\1,2,3\\\text{.}\\
- \\\subseteq\\: \\A \subseteq B\\ asserts that \\A\\ is a subset of \\B\\: every element of \\A\\ is also an element of \\B\text{.}\\
- \\\subset\\: \\A \subset B\\ asserts that \\A\\ is a proper subset of \\B\\: every element of \\A\\ is also an element of \\B\text{,}\\ but \\A \ne B\text{.}\\
- \\\cap\\: \\A \cap B\\ is the intersection of \\A\\ and \\B\\: the set containing all elements which are elements of both \\A\\ and \\B\text{.}\\
- \\\cup\\: \\A \cup B\\ is the union of \\A\\ and \\B\\: is the set containing all elements which are elements of \\A\\ or \\B\\ or both.
- \\\times\\: \\A \times B\\ is the Cartesian product of \\A\\ and \\B\\: the set of all ordered pairs \$a,b)\\ with \\a \in A\\ and \\b \in B\text{.}\\
- \\\setminus\\: \\A \setminus B\\ is \\A\\ set-minus \\B\\: the set containing all elements of \\A\\ which are not elements of \\B\text{.}\\
- \\\bar{A}\\: The complement of \\A\\ is the set of everything which is not an element of \\A\text{.}\\
- \\\card{A}\\: The cardinality (or size) of \\A\\ is the number of elements in \\A\text{.}\\
Investigate!
1. Find the cardinality of each set below.
1. \\A = \\3,4,\ldots, 15\\\text{.}\\
2. \\B = \\n \in \N \st 2 \lt n \le 200\\\text{.}\\
3. \\C = \\n \le 100 \st n \in \N \wedge \exists m \in \N (n = 2m+1)\\\text{.}\\
2. Find two sets \\A\\ and \\B\\ for which \\\|A\| = 5\text{,}\\ \\\|B\| = 6\text{,}\\ and \\\|A\cup B\| = 9\text{.}\\ What is \\\|A \cap B\|\text{?}\\
3. Find sets \\A\\ and \\B\\ with \\\|A\| = \|B\|\\ such that \\\|A\cup B\| = 7\\ and \\\|A \cap B\| = 3\text{.}\\ What is \\\|A\|\text{?}\\
4. Let \\A = \\1,2,\ldots, 10\\\text{.}\\ Define \\\mathcal{B}\_2 = \\B \subseteq A \st \|B\| = 2\\\text{.}\\ Find \\\|\mathcal{B}\_2\|\text{.}\\
5. For any sets \\A\\ and \\B\text{,}\\ define \\AB = \\ab \st a\in A \wedge b \in B\\\text{.}\\ If \\A = \\1,2\\\\ and \\B = \\2,3,4\\\text{,}\\ what is \\\|AB\|\text{?}\\ What is \\\|A \times B\|\text{?}\\
Relationships Between Sets
We have already said what it means for two sets to be equal: they have exactly the same elements. Thus, for example,
\begin{equation\*} \\1, 2, 3\\ = \\2, 1, 3\\. \end{equation\*}
(Remember, the order the elements are written down in does not matter.) Also,
\begin{equation\*} \\1, 2, 3\\ = \\1, 1+1, 1+1+1\\ = \\I, II, III\\ \end{equation\*}
since these are all ways to write the set containing the first three positive integers (how we write them doesn't matter, just what they are).
What about the sets \\A = \\1, 2, 3\\\\ and \\B = \\1, 2, 3, 4\\\text{?}\\ Clearly \\A \ne B\text{,}\\ but notice that every element of \\A\\ is also an element of \\B\text{.}\\ Because of this we say that \\A\\ is a *subset* of \\B\text{,}\\ or in symbols \\A \subset B\\ or \\A \subseteq B\text{.}\\ Both symbols are read “is a subset of.” The difference is that sometimes we want to say that \\A\\ is either equal to or is a subset of \\B\text{,}\\ in which case we use \\\subseteq\text{.}\\ This is analogous to the difference between \\\<\\ and \\\le\text{.}\\
Example \\\PageIndex{2}\\
Let \\A = \\1, 2, 3, 4, 5, 6\\\text{,}\\ \\B = \\2, 4, 6\\\text{,}\\ \\C = \\1, 2, 3\\\\ and \\D = \\7, 8, 9\\\text{.}\\ Determine which of the following are true, false, or meaningless.
1. \\A \subset B\text{.}\\
2. \\B \subset A\text{.}\\
3. \\B \in C\text{.}\\
4. \\\emptyset \in A\text{.}\\
5. \\\emptyset \subset A\text{.}\\
6. \\A \< D\text{.}\\
7. \\3 \in C\text{.}\\
8. \\3 \subset C\text{.}\\
9. \\\\3\\ \subset C\text{.}\\
Solution
1. False. For example, \\1\in A\\ but \\1 \notin B\text{.}\\
2. True. Every element in \\B\\ is an element in \\A\text{.}\\
3. False. The elements in \\C\\ are 1, 2, and 3. The *set* \\B\\ is not equal to 1, 2, or 3.
4. False. \\A\\ has exactly 6 elements, and none of them are the empty set.
5. True. Everything in the empty set (nothing) is also an element of \\A\text{.}\\ Notice that the empty set is a subset of every set.
6. Meaningless. A set cannot be less than another set.
7. True. \\3\\ is one of the elements of the set \\C\text{.}\\
8. Meaningless. \\3\\ is not a set, so it cannot be a subset of another set.
9. True. \\3\\ is the only element of the set \\\\3\\\text{,}\\ and is an element of \\C\text{,}\\ so every element in \\\\3\\\\ is an element of \\C\text{.}\\
In the example above, \\B\\ is a subset of \\A\text{.}\\ You might wonder what other sets are subsets of \\A\text{.}\\ If you collect all these subsets of \\A\\ into a new set, we get a set of sets. We call the set of all subsets of \\A\\ the power set of \\A\text{,}\\ and write it \\\pow(A)\text{.}\\
Example \\\PageIndex{3}\\
Let \\A = \\1,2,3\\\text{.}\\ Find \\\pow(A)\text{.}\\
Solution
\\\pow(A)\\ is a set of sets, all of which are subsets of \\A\text{.}\\ So
\begin{equation\*} \pow(A) = \\ \emptyset, \\1\\, \\2\\, \\3\\, \\1,2\\, \\1, 3\\, \\2,3\\, \\1,2,3\\\\. \end{equation\*}
Notice that while \\2 \in A\text{,}\\ it is wrong to write \\2 \in \pow(A)\\ since none of the elements in \\\pow(A)\\ are numbers! On the other hand, we do have \\\\2\\ \in \pow(A)\\ because \\\\2\\ \subseteq A\text{.}\\
What does a subset of \\\pow(A)\\ look like? Notice that \\\\2\\ \not\subseteq \pow(A)\\ because not everything in \\\\2\\\\ is in \\\pow(A)\text{.}\\ But we do have \\\\ \\2\\ \\ \subseteq \pow(A)\text{.}\\ The only element of \\\\\\2\\\\\\ is the set \\\\2\\\\ which is also an element of \\\pow(A)\text{.}\\ We could take the collection of all subsets of \\\pow(A)\\ and call that \\\pow(\pow(A))\text{.}\\ Or even the power set of that set of sets of sets.
Another way to compare sets is by their *size*. Notice that in the example above, \\A\\ has 6 elements and \\B\text{,}\\ \\C\text{,}\\ and \\D\\ all have 3 elements. The size of a set is called the set's cardinality . We would write \\\|A\| = 6\text{,}\\ \\\|B\| = 3\text{,}\\ and so on. For sets that have a finite number of elements, the cardinality of the set is simply the number of elements in the set. Note that the cardinality of \\\\ 1, 2, 3, 2, 1\\\\ is 3. We do not count repeats (in fact, \\\\1, 2, 3, 2, 1\\\\ is exactly the same set as \\\\1, 2, 3\\\$. There are sets with infinite cardinality, such as \\\N\text{,}\\ the set of rational numbers (written \\\mathbb Q\$, the set of even natural numbers, and the set of real numbers (\\\mathbb R\$. It is possible to distinguish between different infinite cardinalities, but that is beyond the scope of this text. For us, a set will either be infinite, or finite; if it is finite, then we can determine its cardinality by counting elements.
Example \\\PageIndex{4}\\
1. Find the cardinality of \\A = \\23, 24, \ldots, 37, 38\\\text{.}\\
2. Find the cardinality of \\B = \\1, \\2, 3, 4\\, \emptyset\\\text{.}\\
3. If \\C = \\1,2,3\\\text{,}\\ what is the cardinality of \\\pow(C)\text{?}\\
Solution
1. Since \\38 - 23 = 15\text{,}\\ we can conclude that the cardinality of the set is \\\|A\| = 16\\ (you need to add one since 23 is included).
2. Here \\\|B\| = 3\text{.}\\ The three elements are the number 1, the set \\\\2,3,4\\\text{,}\\ and the empty set.
3. We wrote out the elements of the power set \\\pow(C)\\ above, and there are 8 elements (each of which is a set). So \\\card{\pow(C)} = 8\text{.}\\ (You might wonder if there is a relationship between \\\card{A}\\ and \\\card{\pow(A)}\\ for all sets \\A\text{.}\\ This is a good question which we will return to in Chapter 1.)
Operations On Sets
Is it possible to add two sets? Not really, however there is something similar. If we want to combine two sets to get the collection of objects that are in either set, then we can take the union of the two sets. Symbolically,
\begin{equation\*} C = A \cup B, \end{equation\*}
read, “\\C\\ is the union of \\A\\ and \\B\text{,}\\” means that the elements of \\C\\ are exactly the elements which are either an element of \\A\\ or an element of \\B\\ (or an element of both). For example, if \\A = \\1, 2, 3\\\\ and \\B = \\2, 3, 4\\\text{,}\\ then \\A \cup B = \\1, 2, 3, 4\\\text{.}\\
The other common operation on sets is intersection . We write,
\begin{equation\*} C = A \cap B \end{equation\*}
and say, “\\C\\ is the intersection of \\A\\ and \\B\text{,}\\” when the elements in \\C\\ are precisely those both in \\A\\ and in \\B\text{.}\\ So if \\A = \\1, 2, 3\\\\ and \\B = \\2, 3, 4\\\text{,}\\ then \\A \cap B = \\2, 3\\\text{.}\\
Often when dealing with sets, we will have some understanding as to what “everything” is. Perhaps we are only concerned with natural numbers. In this case we would say that our universe is \\\N\text{.}\\ Sometimes we denote this universe by \\\U\text{.}\\ Given this context, we might wish to speak of all the elements which are *not* in a particular set. We say \\B\\ is the complement of \\A\text{,}\\ and write,
\begin{equation\*} B = \bar A \end{equation\*}
when \\B\\ contains every element not contained in \\A\text{.}\\ So, if our universe is \\\\1, 2,\ldots, 9, 10\\\text{,}\\ and \\A = \\2, 3, 5, 7\\\text{,}\\ then \\\bar A = \\1, 4, 6, 8, 9,10\\\text{.}\\
Of course we can perform more than one operation at a time. For example, consider
\begin{equation\*} A \cap \bar B. \end{equation\*}
This is the set of all elements which are both elements of \\A\\ and not elements of \\B\text{.}\\ What have we done? We've started with \\A\\ and removed all of the elements which were in \\B\text{.}\\ Another way to write this is the set difference :
\begin{equation\*} A \cap \bar B = A \setminus B. \end{equation\*}
It is important to remember that these operations (union, intersection, complement, and difference) on sets produce other sets. Don't confuse these with the symbols from the previous section (element of and subset of). \\A \cap B\\ is a set, while \\A \subseteq B\\ is true or false. This is the same difference as between \\3 + 2\\ (which is a number) and \\3 \le 2\\ (which is false).
Example \\\PageIndex{5}\\
Let \\A = \\1, 2, 3, 4, 5, 6\\\text{,}\\ \\B = \\2, 4, 6\\\text{,}\\ \\C = \\1, 2, 3\\\\ and \\D = \\7, 8, 9\\\text{.}\\ If the universe is \\\U = \\1, 2, \ldots, 10\\\text{,}\\ find:
1. \\A \cup B\text{.}\\
2. \\A \cap B\text{.}\\
3. \\B \cap C\text{.}\\
4. \\A \cap D\text{.}\\
5. \\\bar{B \cup C}\text{.}\\
6. \\A \setminus B\text{.}\\
7. \$D \cap \bar C) \cup \bar{A \cap B}\text{.}\\
8. \\\emptyset \cup C\text{.}\\
9. \\\emptyset \cap C\text{.}\\
Solution
1. \\A \cup B = \\1, 2, 3, 4, 5, 6\\ = A\\ since everything in \\B\\ is already in \\A\text{.}\\
2. \\A \cap B = \\2, 4, 6\\ = B\\ since everything in \\B\\ is in \\A\text{.}\\
3. \\B \cap C = \\2\\\\ as the only element of both \\B\\ and \\C\\ is 2.
4. \\A \cap D = \emptyset\\ since \\A\\ and \\D\\ have no common elements.
5. \\\bar{B \cup C} = \\5, 7, 8, 9, 10\\\text{.}\\ First we find that \\B \cup C = \\1, 2, 3, 4, 6\\\text{,}\\ then we take everything not in that set.
6. \\A \setminus B = \\1, 3, 5\\\\ since the elements 1, 3, and 5 are in \\A\\ but not in \\B\text{.}\\ This is the same as \\A \cap \bar B\text{.}\\
7. \$D \cap \bar C) \cup \bar{A \cap B} = \\1, 3, 5, 7, 8, 9, 10\\.\\ The set contains all elements that are either in \\D\\ but not in \\C\\ (i.e., \\\\7,8,9\\\$, or not in both \\A\\ and \\B\\ (i.e., \\\\1,3,5,7,8,9,10\\\$.
8. \\\emptyset \cup C = C\\ since nothing is added by the empty set.
9. \\\emptyset \cap C = \emptyset\\ since nothing can be both in a set and in the empty set.
You might notice that the symbols for union and intersection slightly resemble the logic symbols for “or” and “and.” This is no accident. What does it mean for \\x\\ to be an element of \\A\cup B\text{?}\\ It means that \\x\\ is an element of \\A\\ *or* \\x\\ is an element of \\B\\ (or both). That is,
\begin{equation\*} x \in A \cup B \qquad \Iff \qquad x \in A \vee x \in B. \end{equation\*}
Similarly,
\begin{equation\*} x \in A \cap B \qquad \Iff \qquad x \in A \wedge x \in B. \end{equation\*}
Also,
\begin{equation\*} x \in \bar A \qquad \Iff \qquad \neg (x \in A). \end{equation\*}
which says \\x\\ is an element of the complement of \\A\\ if \\x\\ is not an element of \\A\text{.}\\
There is one more way to combine sets which will be useful for us: the Cartesian product , \\A \times B\\. This sounds fancy but is nothing you haven't seen before. When you graph a function in calculus, you graph it in the Cartesian plane. This is the set of all ordered pairs of real numbers \$x,y)\text{.}\\ We can do this for *any* pair of sets, not just the real numbers with themselves.
Put another way, \\A \times B = \$a,b) \st a \in A \wedge b \in B\\\text{.}\\ The first coordinate comes from the first set and the second coordinate comes from the second set. Sometimes we will want to take the Cartesian product of a set with itself, and this is fine: \\A \times A = \$a,b) \st a, b \in A\\\\ (we might also write \\A^2\\ for this set). Notice that in \\A \times A\text{,}\\ we still want *all* ordered pairs, not just the ones where the first and second coordinate are the same. We can also take products of 3 or more sets, getting ordered triples, or quadruples, and so on.
Example \\\PageIndex{6}\\
Let \\A = \\1,2\\\\ and \\B = \\3,4,5\\\text{.}\\ Find \\A \times B\\ and \\A \times A\text{.}\\ How many elements do you expect to be in \\B \times B\text{?}\\
Solution
\\A \times B = \$1,3), (1,4), (1,5), (2,3), (2,4), (2,5)\\\text{.}\\
\\A \times A = A^2 = \$1,1), (1,2), (2,1), (2,2)\\\text{.}\\
\\\|B\times B\| = 9\text{.}\\ There will be 3 pairs with first coordinate \\3\text{,}\\ three more with first coordinate \\4\text{,}\\ and a final three with first coordinate \\5\text{.}\\
Venn Diagrams
There is a very nice visual tool we can use to represent operations on sets. A Venn diagram displays sets as intersecting circles. We can shade the region we are talking about when we carry out an operation. We can also represent cardinality of a particular set by putting the number in the corresponding region.
\![two-set-venn-empty.svg$$(https://math.libretexts.org/@api/deki/files/12897/two-set-venn-empty.svg?revision=1&size=bestfit&width=207&height=148) \![three-set-empty.svg$$(https://math.libretexts.org/@api/deki/files/12898/three-set-empty.svg?revision=1&size=bestfit&width=194&height=147)
\![$$(https://math.libretexts.org/images/two-set-venn-empty.svg) \![$$(https://math.libretexts.org/images/three-set-empty.svg)
Each circle represents a set. The rectangle containing the circles represents the universe. To represent combinations of these sets, we shade the corresponding region. For example, we could draw \\A \cap B\\ as:
\![two-set-cap.svg$$(https://math.libretexts.org/@api/deki/files/12896/two-set-cap.svg?revision=1&size=bestfit&width=219&height=157)
\![$$(https://math.libretexts.org/images/two-set-cap.svg)
Here is a representation of \\A \cap \bar B\text{,}\\ or equivalently \\A \setminus B\text{:}\\
\![two-set-a-minus-b.svg$$(https://math.libretexts.org/@api/deki/files/12900/two-set-a-minus-b.svg?revision=1&size=bestfit&width=217&height=155)
\![$$(https://math.libretexts.org/images/two-set-a-minus-b.svg)
A more complicated example is \$B \cap C) \cup (C \cap \bar A)\text{,}\\ as seen below.
\![three-set-complicated.svg$$(https://math.libretexts.org/@api/deki/files/12899/three-set-complicated.svg?revision=1&size=bestfit&width=228&height=173)
\![$$(https://math.libretexts.org/images/three-set-complicated.svg)
Notice that the shaded regions above could also be arrived at in another way. We could have started with all of \\C\text{,}\\ then excluded the region where \\C\\ and \\A\\ overlap outside of \\B\text{.}\\ That region is \$A \cap C) \cap \bar B\text{.}\\ So the above Venn diagram also represents \\C \cap \bar{\left((A\cap C)\cap \bar B\right)}.\\ So using just the picture, we have determined that
\begin{equation\*} (B \cap C) \cup (C \cap \bar A) = C \cap \bar{\left((A\cap C)\cap \bar B\right)}. \end{equation\*}
---
0_4_3A_Functions
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/0%3A_Introduction_and_Preliminaries/0.4%3A_Functions
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
A function is a rule that assigns each input exactly one output. We call the output the image of the input. The set of all inputs for a function is called the domain . The set of all allowable outputs is called the codomain . We would write \\f:X \to Y\\ to describe a function with name \\f\text{,}\\ domain \\X\\ and codomain \\Y\text{.}\\ This does not tell us *which* function \\f\\ is though. To define the function, we must describe the rule. This is often done by giving a formula to compute the output for any input (although this is certainly not the only way to describe the rule).
For example, consider the function \\f:\N \to \N\\ defined by \\f(x) = x^2 + 3\text{.}\\ Here the domain and codomain are the same set (the natural numbers). The rule is: take your input, multiply it by itself and add 3. This works because we can apply this rule to every natural number (every element of the domain) and the result is always a natural number (an element of the codomain). Notice though that not every natural number actually is an output (there is no way to get 0, 1, 2, 5, etc.). The set of natural numbers that are *actually outputs* is called the range of the function (in this case, the range is \\\\3, 4, 7, 12, 19, 28, \ldots\\\text{,}\\ all the natural numbers that are 3 more than a perfect square).
The key thing that makes a rule actually a *function* is that there is *exactly one* output for each input. That is, it is important that the rule be a good rule. What output do we assign to the input 7? There can only be one answer for any particular function.
The description of the rule can vary greatly. We might just give a list of the images of each input. You could also describe the function with a table or a graph or in words.
Example \\\PageIndex{1}\\
The following are all examples of functions:
1. \\f:\Z \to \Z\\ defined by \\f(n) = 3n\text{.}\\ The domain and codomain are both the set of integers. However, the range is only the set of integer multiples of 3.
2. \\g: \\1,2,3\\ \to \\a,b,c\\\\ defined by \\g(1) = c\text{,}\\ \\g(2) = a\\ and \\g(3) = a\text{.}\\ The domain is the set \\\\1,2,3\\\text{,}\\ the codomain is the set \\\\a,b,c\\\\ and the range is the set \\\\a,c\\\text{.}\\ Note that \\g(2)\\ and \\g(3)\\ are the same element of the codomain. This is okay since each element in the domain still has only one output.
3. \\h:\\1,2,3\\ \to \\1,2,3\\\\ defined as follows:
\![arrow-function-example.svg$$(https://math.libretexts.org/@api/deki/files/12865/arrow-function-example.svg?revision=1&size=bestfit&width=119&height=111)
\![$$(https://math.libretexts.org/images/arrow-function-example.svg)
This means that the function \\f\\ sends 1 to 2, 2 to 1 and 3 to 3: just follow the arrows.
The arrow diagram used to define the function above can be very helpful in visualizing functions. We will often be working with functions with *finite* domains, so this kind of picture is often more useful than a traditional graph of a function. A graph of the function in example 3 above would look like this:
\![discrete-function-graph.svg$$(https://math.libretexts.org/@api/deki/files/12866/discrete-function-graph.svg?revision=1&size=bestfit&width=203&height=203)
\![$$(https://math.libretexts.org/images/discrete-function-graph.svg)
It would be absolutely WRONG to connect the dots or try to fit them to some curve. There are only three elements in the domain. A curve suggests that the domain contains an entire interval of real numbers. Remember, we are not in calculus any more!
Since we will so often use functions with small domains and codomains, let's adopt some notation that is a little easier to work with than that of examples 2 and 3 above. All we need is some clear way of denoting the image of each element in the domain. In fact, writing a table of values would work perfectly:
| | | | | | |
|----------|-----|-----|-----|-----|-----|
| \\x\\ | 0 | 1 | 2 | 3 | 4 |
| \\f(x)\\ | 3 | 3 | 2 | 4 | 1 |
We simplify this further by writing this as a matrix with each input directly over its output:
\begin{equation\*} f = \begin{pmatrix}0 & 1 & 2& 3 & 4 \\ 3 & 3 & 2 & 4 & 1\end{pmatrix} \end{equation\*}
Note this is just notation and not the same sort of matrix you would find in a linear algebra class (it does not make sense to do operations with these matrices, or row reduce them, for example).
It is important to know how to determine if a rule is or is not a function. Drawing the arrow diagrams can help.
Example \\\PageIndex{2}\\
Which of the following diagrams represent a function? Let \\X = \\1,2,3,4\\\\ and \\Y = \\a,b,c,d\\\\.
\![h-arrows.svg$$(https://math.libretexts.org/@api/deki/files/12869/h-arrows.svg?revision=1&size=bestfit&width=159&height=124) \![f-arrows.svg$$(https://math.libretexts.org/@api/deki/files/12867/f-arrows.svg?revision=1&size=bestfit&width=152&height=123) \![g-arrows.svg$$(https://math.libretexts.org/@api/deki/files/12868/g-arrows.svg?revision=1&size=bestfit&width=160&height=126)
Solution
\\f\\ is a function. So is \\g\text{.}\\ There is no problem with an element of the codomain not being the image of any input, and there is no problem with \\a\\ from the codomain being the image of both 2 and 3 from the domain. We could use our two-line notation to write these as
\begin{equation\*} f= \begin{pmatrix} 1 & 2 & 3 & 4 \\ d & a & c & b \end{pmatrix} \qquad g = \begin{pmatrix} 1 & 2 & 3 & 4 \\ d & a & a & b \end{pmatrix}. \end{equation\*}
However, \\h\\ is NOT a function. In fact, it fails for two reasons. First, the element 1 from the domain has not been mapped to any element from the codomain. Second, the element 2 from the domain has been mapped to more than one element from the codomain (\\a\\ and \\c\$. Note that either one of these problems is enough to make a rule not a function. In general, neither of the following mappings are functions:
\![not-function-a.svg$$(https://math.libretexts.org/@api/deki/files/12870/not-function-a.svg?revision=1&size=bestfit&width=126&height=93) \![not-function-b.svg$$(https://math.libretexts.org/@api/deki/files/12871/not-function-b.svg?revision=1&size=bestfit&width=180&height=91)
\![$$(https://math.libretexts.org/images/not-function-a.svg) \![$$(https://math.libretexts.org/images/not-function-b.svg)
It might also be helpful to think about how you would write the two-line notation for \\h\text{.}\\ We would have something like:
\begin{equation\*} h=\begin{pmatrix} 1 & 2 & 3 & 4 \\ & a,c? & d & b\end{pmatrix}. \end{equation\*}
There is nothing under 1 (bad) and we needed to put more than one thing under 2 (very bad). With a rule that is actually a function, the two-line notation will always “work”.
Surjections, Injections, and Bijections
We now turn to investigating special properties functions might or might not possess.
In the examples above, you may have noticed that sometimes there are elements of the codomain which are not in the range. When this sort of the thing *does not* happen, (that is, when everything in the codomain is in the range) we say the function is onto or that the function maps the domain *onto* the codomain. This terminology should make sense: the function puts the domain (entirely) on top of the codomain. The fancy math term for an onto function is a surjection , and we say that an onto function is a surjective function.
In pictures:
\![non-surjective-ex.svg$$(https://math.libretexts.org/@api/deki/files/12873/non-surjective-ex.svg?revision=1&size=bestfit&width=154&height=112) \![surjective-ex.svg$$(https://math.libretexts.org/@api/deki/files/12872/surjective-ex.svg?revision=1&size=bestfit&width=154&height=112)
\![$$(https://math.libretexts.org/images/surjective-ex.svg) \![$$(https://math.libretexts.org/images/non-surjective-ex.svg)
Example \\\PageIndex{3}\\: Surjective Functions
Which functions are surjective (i.e., onto)?
1. \\f:\Z \to \Z\\ defined by \\f(n) = 3n\text{.}\\
2. \\g: \\1,2,3\\ \to \\a,b,c\\\\ defined by \\g = \begin{pmatrix}1 & 2 & 3 \\ c & a & a \end{pmatrix}\text{.}\\
3. \\h:\\1,2,3\\ \to \\1,2,3\\\\ defined as follows:
\![ex-surj-q.svg$$(https://math.libretexts.org/@api/deki/files/12874/ex-surj-q.svg?revision=1&size=bestfit&width=149&height=129)
Solution
1. \\f\\ is not surjective. There are elements in the codomain which are not in the range. For example, no \\n \in \Z\\ gets mapped to the number 1 (the rule would say that \\\frac{1}{3}\\ would be sent to 1, but \\\frac{1}{3}\\ is not in the domain). In fact, the range of the function is \\3\Z\\ (the integer multiples of 3), which is not equal to \\\Z\text{.}\\
2. \\g\\ is not surjective. There is no \\x \in \\1,2,3\\\\ (the domain) for which \\g(x) = b\text{,}\\ so \\b\text{,}\\ which is in the codomain, is not in the range. Notice that there is an element from the codomain “missing” from the bottom row of the matrix.
3. \\h\\ is surjective. Every element of the codomain is also in the range. Nothing in the codomain is missed.
To be a function, a rule cannot assign a single element of the domain to two or more different elements of the codomain. However, we have seen that the reverse *is* permissible: a function might assign the same element of the codomain to two or more different elements of the domain. When this *does not* occur (that is, when each element of the codomain is the image of at most one element of the domain) then we say the function is one-to-one . Again, this terminology makes sense: we are sending at most one element from the domain to one element from the codomain. One input to one output. The fancy math term for a one-to-one function is an injection . We call one-to-one functions injective functions.
In pictures:
\![injective-ex.svg$$(https://math.libretexts.org/@api/deki/files/12901/injective-ex.svg?revision=1&size=bestfit&width=221&height=122) \![non-injective-ex.svg$$(https://math.libretexts.org/@api/deki/files/12902/non-injective-ex.svg?revision=1&size=bestfit&width=221&height=122)
\![$$(https://math.libretexts.org/images/injective-ex.svg) \![$$(https://math.libretexts.org/images/non-injective-ex.svg)
Example \\\PageIndex{4}\\
Which functions are injective (i.e., one-to-one)?
1. \\f:\Z \to \Z\\ defined by \\f(n) = 3n\text{.}\\
2. \\g: \\1,2,3\\ \to \\a,b,c\\\\ defined by \\g = \begin{pmatrix}1 & 2 & 3 \\ c & a & a \end{pmatrix}\text{.}\\
3. \\h:\\1,2,3\\ \to \\1,2,3\\\\ defined as follows:
\![ex-inj-q.svg$$(https://math.libretexts.org/@api/deki/files/58929/ex-inj-q.svg?revision=1&size=bestfit&width=149&height=129)
Solution
1. \\f\\ is injective. Each element in the codomain is assigned to at *most* one element from the domain. If \\x\\ is a multiple of three, then only \\x/3\\ is mapped to \\x\text{.}\\ If \\x\\ is not a multiple of 3, then there is no input corresponding to the output \\x\text{.}\\
2. \\g\\ is not injective. Both inputs \\2\\ and \\3\\ are assigned the output \\a\text{.}\\ Notice that there is an element from the codomain that appears more than once on the bottom row of the matrix.
3. \\h\\ is injective. Each output is only an output once.
From the examples above, it should be clear that there are functions which are surjective, injective, both, or neither. In the case when a function is both one-to-one and onto (an injection and surjection), we say the function is a bijection , or that the function is a bijective function.
Inverse Image
When discussing functions, we have notation for talking about an element of the domain (say \\x\$ and its corresponding element in the codomain (we write \\f(x)\text{,}\\ which *is* the image of \\x\$. It would also be nice to start with some element of the codomain (say \\y\$ and talk about which element or elements (if any) from the domain it is the image of. We could write “those \\x\\ in the domain such that \\f(x) = y\text{,}\\” but this is a lot of writing. Here is some notation to make our lives easier.
Suppose \\f:X \to Y\\ is a function. For \\y \in Y\\ (an element of the codomain), we write \\f\inv(y)\\ to represent the *set* of all elements in the domain \\X\\ which get sent to \\y\text{.}\\ That is, \\f\inv(y) = \\x \in X \st f(x) = y\\\text{.}\\ We say that \\f\inv(y)\\ is the complete inverse image of \\y\\ under \\f\text{.}\\
WARNING: \\f\inv(y)\\ is not an inverse function! Inverse functions only exist for bijections, but \\f\inv(y)\\ is defined for any function \\f\text{.}\\ The point: \\f\inv(y)\\ is a *set*, not an *element* of the domain.
Example \\\PageIndex{5}\\
Consider the function \\f:\\1,2,3,4,5,6\\ \to \\a,b,c,d\\\\ given by
\begin{equation\*} f = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ a & a & b & c & c & c\end{pmatrix}. \end{equation\*}
Find the complete inverse image of each element in the codomain.
Solution
Remember, we are looking for sets.
\begin{equation\*} f\inv(a) = \\1,2\\ \end{equation\*} \begin{equation\*} f\inv(b) = \\3\\ \end{equation\*} \begin{equation\*} f\inv(c) = \\4,5,6\\ \end{equation\*} \begin{equation\*} f\inv(d) = \emptyset. \end{equation\*}
Example \\\PageIndex{6}\\
Consider the function \\g:\Z \to \Z\\ defined by \\g(n) = n^2 + 1\text{.}\\ Find \\g\inv(1)\text{,}\\ \\g\inv(2)\text{,}\\ \\g\inv(3)\\ and \\g\inv(10)\text{.}\\
Solution
To find \\g\inv(1)\text{,}\\ we need to find all integers \\n\\ such that \\n^2 + 1 = 1\text{.}\\ Clearly only 0 works, so \\g\inv(1) = \\0\\\\ (note that even though there is only one element, we still write it as a set with one element in it).
To find \\g\inv(2)\text{,}\\ we need to find all \\n\\ such that \\n^2 + 1 = 2\text{.}\\ We see \\g\inv(2) = \\-1,1\\\text{.}\\
If \\n^2 + 1 = 3\text{,}\\ then we are looking for an \\n\\ such that \\n^2 = 2\text{.}\\ There are no such integers so \\g\inv(3) = \emptyset\text{.}\\
Finally, \\g\inv(10) = \\-3, 3\\\\ because \\g(-3) = 10\\ and \\g(3) = 10\text{.}\\
Since \\f\inv(y)\\ is a set, it makes sense to ask for \\\card{f\inv(y)}\text{,}\\ the number of elements in the domain which map to \\y\text{.}\\
Example \\\PageIndex{7}\\
Find a function \\f:\\1,2,3,4,5\\ \to \N\\ such that \\\card{f\inv(7)} = 5\text{.}\\
Solution
There is only one such function. We need five elements of the domain to map to the number \\7 \in \N\text{.}\\ Since there are only five elements in the domain, all of them must map to 7. So
\begin{equation\*} f = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 7 & 7 & 7 & 7 & 7\end{pmatrix}. \end{equation\*}
Function Definitions
- A function is a rule that assigns each element of a set, called the domain , to exactly one element of a second set, called the codomain .
- Notation: \\f:X \to Y\\ is our way of saying that the function is called \\f\text{,}\\ the domain is the set \\X\text{,}\\ and the codomain is the set \\Y\text{.}\\
- To specify the rule for a function with small domain, use two-line notation by writing a matrix with each output directly below its corresponding input, as in:
\begin{equation\*} f = \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 1 \end{pmatrix}. \end{equation\*}
- \\f(x) = y\\ means the element \\x\\ of the domain (input) is assigned to the element \\y\\ of the codomain. We say \\y\\ is an output. Alternatively, we call \\y\\ the image of \\x\\ under \\f\\ .
- The range is a subset of the codomain. It is the set of all elements which are assigned to at least one element of the domain by the function. That is, the range is the set of all outputs.
- A function is injective (an injection or one-to-one ) if every element of the codomain is the output for at most one element from the domain.
- A function is surjective (a surjection or onto ) if every element of the codomain is the output of at least one element of the domain.
- A bijection is a function which is both an injection and surjection. In other words, if every element of the codomain is the output of exactly one element of the domain.
- The image of an element \\x\\ in the domain is the element \\y\\ in the codomain that \\x\\ is mapped to. That is, the image of \\x\\ under \\f\\ is \\f(x)\text{.}\\
- The complete inverse image of an element \\y\\ in the codomain, written \\f\inv(y)\text{,}\\ is the *set* of all elements in the domain which are assigned to \\y\\ by the function.
---
0_E_3A_Introduction_and_Preliminaries__Exercises_
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/0%3A_Introduction_and_Preliminaries/0.E%3A_Introduction_and_Preliminaries_(Exercises)
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
0.2: Mathematical Statements
1
Classify each of the sentences below as an atomic statement, and molecular statement, or not a statement at all. If the statement is molecular, say what kind it is (conjuction, disjunction, conditional, biconditional, negation).
1. The sum of the first 100 odd positive integers.
2. Everybody needs somebody sometime.
3. The Broncos will win the Super Bowl or I'll eat my hat.
4. We can have donuts for dinner, but only if it rains.
5. Every natural number greater than 1 is either prime or composite.
6. This sentence is false.
Answer
1. This is not a statement; it does not make sense to say it is true or false.
2. This is an atomic statement (there are some quantifiers, but no connectives).
3. This is a molecular statement, specifically a disjunction. Although if we read into it a bit more, what the speaker is really saying is that if the Broncos do not win the super bowl, then he will eat his hat, which would be a conditional.
4. This is a molecular statement, a conditional.
5. This is an atomic statement. Even though there is an “or” in the statement, it would not make sense to consider the two halves of the disjuction. This is because we quantified *over* the disjunction. In symbols, we have \\\forall x (x \> 1 \imp (P(x) \vee C(x)))\text{.}\\ If we drop the quantifier, we are not left with a statement, since there is a free variable.
6. This is not a statement, although it certainly looks like one. Remember that statements must be true or false. If this sentence were true, that would make it false. If it were false, that would make it true. Examples like this are rare and usually arise from some sort of self-reference.
2
Suppose \\P\\ and \\Q\\ are the statements: \\P\text{:}\\ Jack passed math. \\Q\text{:}\\ Jill passed math.
1. Translate “Jack and Jill both passed math” into symbols.
2. Translate “If Jack passed math, then Jill did not” into symbols.
3. Translate “\\P \vee Q\\” into English.
4. Translate “\\\neg(P \wedge Q) \imp Q\\” into English.
5. Suppose you know that if Jack passed math, then so did Jill. What can you conclude if you know that:
1. Jill passed math?
2. Jill did not pass math?
Answer
1. \\P \wedge Q\text{.}\\
2. \\P \imp \neg Q\text{.}\\
3. Jack passed math or Jill passed math (or both).
4. If Jack and Jill did not both pass math, then Jill did.
1. Nothing else.
2. Jack did not pass math either.
3
Geoff Poshingten is out at a fancy pizza joint, and decides to order a calzone. When the waiter asks what he would like in it, he replies, “I want either pepperoni or sausage. Also, if I have sausage, then I must also include quail. Oh, and if I have pepperoni or quail then I must also have ricotta cheese.”
1. Translate Geoff's order into logical symbols.
2. The waiter knows that Geoff is either a liar or a truth-teller (so either everything he says is false, or everything is true). Which is it?
3. What, if anything, can the waiter conclude about the ingredients in Geoff's desired calzone?
4
Consider the statement “If Oscar eats Chinese food, then he drinks milk.”
1. Write the converse of the statement.
2. Write the contrapositive of the statement.
3. Is it possible for the contrapositive to be false? If it was, what would that tell you?
4. Suppose the original statement is true, and that Oscar drinks milk. Can you conclude anything (about his eating Chinese food)? Explain.
5. Suppose the original statement is true, and that Oscar does not drink milk. Can you conclude anything (about his eating Chinese food)? Explain.
5
Which of the following statements are equivalent to the implication, “if you win the lottery, then you will be rich,” and which are equivalent to the converse of the implication?
1. Either you win the lottery or else you are not rich.
2. Either you don't win the lottery or else you are rich.
3. You will win the lottery and be rich.
4. You will be rich if you win the lottery.
5. You will win the lottery if you are rich.
6. It is necessary for you to win the lottery to be rich.
7. It is sufficient to win the lottery to be rich.
8. You will be rich only if you win the lottery.
9. Unless you win the lottery, you won't be rich.
10. If you are rich, you must have won the lottery.
11. If you are not rich, then you did not win the lottery.
12. You will win the lottery if and only if you are rich.
Answer
The statements are equivalent to the…
1. converse.
2. implication.
3. neither.
4. implication.
5. converse.
6. converse.
7. implication.
8. converse.
9. converse.
10. converse (in fact, this *is* the converse).
11. implication (the statement is the contrapositive of the implication).
12. neither.
6
Consider the implication, “if you clean your room, then you can watch TV.” Rephrase the implication in as many ways as possible. Then do the same for the converse.
Hint
Of course there are many answers. It helps to assume that the statement is true and the converse is *note* true. Think about what that means in the real world and then start saying it in different ways. Some ideas: Use “necessary and sufficient” language, use “only if,” consider negations, use “or else” language.
7
Translate into symbols. Use \\E(x)\\ for “\\x\\ is even” and \\O(x)\\ for “\\x\\ is odd.”
1. No number is both even and odd.
2. One more than any even number is an odd number.
3. There is prime number that is even.
4. Between any two numbers there is a third number.
5. There is no number between a number and one more than that number.
Answer
1. \\\neg \exists x (E(x) \wedge O(x))\text{.}\\
2. \\\forall x (E(x) \imp O(x+1))\text{.}\\
3. \\\exists x(P(x) \wedge E(x))\\ (where \\P(x)\\ means “\\x\\ is prime”).
4. \\\forall x \forall y \exists z(x \lt z \lt y \vee y \lt z \lt x)\text{.}\\
5. \\\forall x \neg \exists y (x \lt y \lt x+1)\text{.}\\
8
Translate into English:
1. \\\forall x (E(x) \imp E(x +2))\text{.}\\
2. \\\forall x \exists y (\sin(x) = y)\text{.}\\
3. \\\forall y \exists x (\sin(x) = y)\text{.}\\
4. \\\forall x \forall y (x^3 = y^3 \imp x = y)\text{.}\\
Answer
1. Any even number plus 2 is an even number.
2. For any \\x\\ there is a \\y\\ such that \\\sin(x) = y\text{.}\\ In other words, every number \\x\\ is in the domain of sine.
3. For every \\y\\ there is an \\x\\ such that \\\sin(x) = y\text{.}\\ In other words, every number \\y\\ is in the range of sine (which is false).
4. For any numbers, if the cubes of two numbers are equal, then the numbers are equal.
9
Suppose \\P(x)\\ is some predicate for which the statement \\\forall x P(x)\\ is true. Is it also the case that \\\exists x P(x)\\ is true? In other words, is the statement \\\forall x P(x) \imp \exists x P(x)\\ always true? Is the converse always true? Explain.
10
For each of the statements below, give a domain of discourse for which the statement is true, and a domain for which the statement is false.
1. \\\forall x \exists y (y^2 = x)\text{.}\\
2. \\\forall x \forall y \exists z (x \lt z \lt y)\text{.}\\
3. \\\exists x \forall y \forall z (y \lt z \imp y \le x \le z)\\ Hint: domains need not be infinite.
Answer
1. This says that everything has a square root (every element is the square of something). This is true of the positive real numbers, and also of the complex numbers. It is false of the natural numbers though, as for \\x = 2\\ there is no natural number \\y\\ such that \\y^2 = 2\text{.}\\
2. This asserts that between every pair of numbers there is some number strictly between them. This is true of the rationals (and reals) but false of the integers. If \\x = 1\\ and \\y = 2\text{,}\\ then there is nothing we can take for \\z\text{.}\\
3. Here we are saying that something is between every pair of numbers. For almost every domain, this is false. In fact, if the domain contains \\\\1,2,3, 4\\\text{,}\\ then no matter what we take \\x\\ to be, there will be a pair that \\x\\ is *not* between. However, the set \\\\1,2,3\\\\ as our domain makes the statement true. Let \\x = 2\text{.}\\ Then no matter what \\y\\ and \\z\\ we pick, if \\y \lt z\text{,}\\ then 2 is between them.
0.3: Sets
1
Let \\A = \\1,2,3,4,5\\\text{,}\\ \\B = \\3,4,5,6,7\\\text{,}\\ and \\C = \\2,3,5\\\text{.}\\
1. Find \\A \cap B\text{.}\\
2. Find \\A \cup B\text{.}\\
3. Find \\A \setminus B\text{.}\\
4. Find \\A \cap \overline{(B \cup C)}\text{.}\\
5. Find \\A \times C\text{.}\\
6. Is \\C \subseteq A\text{?}\\ Explain.
7. Is \\C \subseteq B\text{?}\\ Explain.
Answer
1. \\A \cap B = \\3,4,5\\\text{.}\\
2. \\A \cup B = \\1,2,3,4,5,6,7\\\text{.}\\
3. \\A \setminus B = \\1,2\\\text{.}\\
4. \\A \cap \bar{(B \cup C)} = \\1\\\text{.}\\
5. \\A \times C = \\ (1,2), (1,3), (1,5), (2,2), (2,3), (2,5), (3,2), (3,3), (3,5), (4,2)\text{,}\\ \$4,3), (4,5), (5,2), (5,3), (5,5)\\\\
6. Yes. All three elements of \\C\\ are also elements of \\A\text{.}\\
7. No. There is an element of \\C\text{,}\\ namely the element 2, which is not an element of \\B\text{.}\\
2
Let \\A = \\x \in \N \st 3 \le x \le 13\\\text{,}\\ \\B = \\x \in \N \st x \mbox{ is even} \\\text{,}\\ and \\C = \\x \in \N \st x \mbox{ is odd} \\\text{.}\\
1. Find \\A \cap B\text{.}\\
2. Find \\A \cup B\text{.}\\
3. Find \\B \cap C\text{.}\\
4. Find \\B \cup C\text{.}\\
3
Find an example of sets \\A\\ and \\B\\ such that \\A\cap B = \\3, 5\\\\ and \\A \cup B = \\2, 3, 5, 7, 8\\\text{.}\\
4
Find an example of sets \\A\\ and \\B\\ such that \\A \subseteq B\\ and \\A \in B\text{.}\\
Answer
For example, \\A = \\1,2,3\\\\ and \\B = \\1,2,3,4,5,\\1,2,3\\\\\\
5
Recall \\\Z = \\\ldots,-2,-1,0, 1,2,\ldots\\\\ (the integers). Let \\\Z^+ = \\1, 2, 3, \ldots\\\\ be the positive integers. Let \\2\Z\\ be the even integers, \\3\Z\\ be the multiples of 3, and so on.
1. Is \\\Z^+ \subseteq 2\Z\text{?}\\ Explain.
2. Is \\2\Z \subseteq \Z^+\text{?}\\ Explain.
3. Find \\2\Z \cap 3\Z\text{.}\\ Describe the set in words, and using set notation.
4. Express \\\\x \in \Z \st \exists y\in \Z (x = 2y \vee x = 3y)\\\\ as a union or intersection of two sets already described in this problem.
Answer
1. No.
2. No.
3. \\2\Z \cap 3\Z\\ is the set of all integers which are multiples of both 2 and 3 (so multiples of 6). Therefore \\2\Z \cap 3\Z = \\x \in \Z \st \exists y\in \Z(x = 6y)\\\text{.}\\
4. \\2\Z \cup 3\Z\text{.}\\
6
Let \\A_2\\ be the set of all multiples of 2 except for \\2\text{.}\\ Let \\A_3\\ be the set of all multiples of 3 except for 3. And so on, so that \\A_n\\ is the set of all multiple of \\n\\ except for \\n\text{,}\\ for any \\n \ge 2\text{.}\\ Describe (in words) the set \\\bar{A_2 \cup A_3 \cup A_4 \cup \cdots}\text{.}\\
7
Draw a Venn diagram to represent each of the following:
1. \\A \cup \bar B\\
2. \\\bar{(A \cup B)}\\
3. \\A \cap (B \cup C)\\
4. \$A \cap B) \cup C\\
5. \\\bar A \cap B \cap \bar C\\
6. \$A \cup B) \setminus C\\
Answer
1. \\A \cup \bar B\text{:}\\
2. \\\bar{(A \cup B)}\text{:}\\
3. \\A \cap (B \cup C)\text{:}\\
4. \$A \cap B) \cup C\text{:}\\
5. \\\bar A \cap B \cap \bar C\text{:}\\
6. \$A \cup B) \setminus C\text{:}\\\![$$(https://math.libretexts.org/images/A-or-not-B.svg)
8
Describe a set in terms of \\A\\ and \\B\\ (using set notation) which has the following Venn diagram:
\![$$(https://math.libretexts.org/images/not-A-and-B.svg)
9
Find the following cardinalities:
1. \\\|A\|\\ when \\A = \\4,5,6,\ldots,37\\\\
2. \\\|A\|\\ when \\A = \\x \in \Z \st -2 \le x \le 100\\\\
3. \\\|A \cap B\|\\ when \\A = \\x \in \N \st x \le 20\\\\ and \\B = \\x \in \N \st x \mbox{ is prime} \\\\
Answer
1. 34\.
2. 103\.
3. 8\.
10
Let \\A = \\a, b, c, d\\\text{.}\\ Find \\\pow(A)\text{.}\\
Hint
We are looking for a set containing 16 sets.
11
Let \\A = \\1,2,\ldots, 10\\\text{.}\\ How many subsets of \\A\\ contain exactly one element (i.e., how many singleton subsets are there)? How many doubleton subsets (containing exactly two elements) are there?
12
Let \\A = \\1,2,3,4,5,6\\\text{.}\\ Find all sets \\B \in \pow(A)\\ which have the property \\\\2,3,5\\ \subseteq B\text{.}\\
13
Find an example of sets \\A\\ and \\B\\ such that \\\|A\| = 4\text{,}\\ \\\|B\| = 5\text{,}\\ and \\\|A \cup B\| = 9\text{.}\\
Answer
For example, \\A = \\1,2,3,4\\\\ and \\B = \\5,6,7,8,9\\\\ gives \\A \cup B = \\1,2,3,4,5,6,7,8,9\\\text{.}\\
14
Find an example of sets \\A\\ and \\B\\ such that \\\|A\| = 3\text{,}\\ \\\|B\| = 4\text{,}\\ and \\\|A \cup B\| = 5\text{.}\\
15
Are there sets \\A\\ and \\B\\ such that \\\|A\| = \|B\|\text{,}\\ \\\|A\cup B\| = 10\text{,}\\ and \\\|A\cap B\| = 5\text{?}\\ Explain.
16
In a regular deck of playing cards there are 26 red cards and 12 face cards. Explain, using sets and what you have learned about cardinalities, why there are only 32 cards which are either red or a face card.
0.4: Functions
1
Write out all functions \\f: \\1,2,3\\ \to \\a,b\\\\ (using two-line notation). How many are there? How many are injective? How many are surjective? How many are both?
Answer
There are 8 different functions. In two-line notation these are:
\begin{equation\*} f = \begin{pmatrix} 1 & 2 & 3 \\ a & a& a \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & b & b \end{pmatrix} \end{equation\*} \begin{equation\*} f = \begin{pmatrix} 1 & 2 & 3 \\ a & a& b \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ a & b & a \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & a& a \end{pmatrix} \end{equation\*} \begin{equation\*} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & b & a \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ b & a& b \end{pmatrix} \quad f = \begin{pmatrix} 1 & 2 & 3 \\ a & b & b \end{pmatrix} \end{equation\*}
None of the functions are injective. Exactly 6 of the functions are surjective. No functions are both (since no functions here are injective).
2
Write out all functions \\f: \\1,2\\ \to \\a,b,c\\\\ (in two-line notation). How many are there? How many are injective? How many are surjective? How many are both?
Answer
There are 9 functions: you have a choice of three outputs for \\f(1)\text{,}\\ and for each, you have three choices for the output \\f(2)\text{.}\\ Of these functions, 6 are injective, 0 are surjective, and 0 are both:
\begin{equation\*} f = \twoline{1 & 2}{a& a} \quad f = \twoline{1 & 2}{b & b} \quad f = \twoline{1 & 2}{c & c} \end{equation\*} \begin{equation\*} f = \twoline{1 & 2}{a& b} \quad f = \twoline{1 & 2}{a & c} \quad f = \twoline{1 & 2}{b & c} \end{equation\*} \begin{equation\*} f = \twoline{1 & 2}{b & a} \quad f = \twoline{1 & 2}{c & a} \quad f = \twoline{1 & 2}{c & b} \end{equation\*}
3
Consider the function \\f:\\1,2,3,4,5\\ \to \\1,2,3,4\\\\ given by the table below:
| | | | | | |
|----------|-----|-----|-----|-----|-----|
| \\x\\ | 1 | 2 | 3 | 4 | 5 |
| \\f(x)\\ | 3 | 2 | 4 | 1 | 2 |
1. Is \\f\\ injective? Explain.
2. Is \\f\\ surjective? Explain.
3. Write the function using two-line notation.
4
Consider the function \\f:\\1,2,3,4\\ \to \\1,2,3,4\\\\ given by the graph below.
\![$$(https://math.libretexts.org/images/graph-function-ques.svg)
1. Is \\f\\ injective? Explain.
2. Is \\f\\ surjective? Explain.
3. Write the function using two-line notation.
5
For each function given below, determine whether or not the function is injective and whether or not the function is surjective.
1. \\f:\N \to \N\\ given by \\f(n) = n+4\text{.}\\
2. \\f:\Z \to \Z\\ given by \\f(n) = n+4\text{.}\\
3. \\f:\Z \to \Z\\ given by \\f(n) = 5n - 8\text{.}\\
4. \\f:\Z \to \Z\\ given by \\f(n) = \begin{cases}n/2 & \text{ if } n \text{ is even} \\ (n+1)/2 & \text{ if } n \text{ is odd} . \end{cases}\\
Answer
1. \\f\\ is injective, but not surjective (since 0, for example, is never an output).
2. \\f\\ is injective and surjective. Unlike in the previous question, every integers is an output (of the integer 4 less than it).
3. \\f\\ is injective, but not surjective (10 is not 8 less than a multiple of 5, for example).
4. \\f\\ is not injective, but is surjective. Every integer is an output (of twice itself, for example) but some integers are outputs of more than one input: \\f(5) = 3 = f(6)\text{.}\\
6
Let \\A = \\1,2,3,\ldots,10\\\text{.}\\ Consider the function \\f:\pow(A) \to \N\\ given by \\f(B) = \|B\|\text{.}\\ That is, \\f\\ takes a subset of \\A\\ as an input and outputs the cardinality of that set.
1. Is \\f\\ injective? Prove your answer.
2. Is \\f\\ surjective? Prove your answer.
3. Find \\f\inv(1)\text{.}\\
4. Find \\f\inv(0)\text{.}\\
5. Find \\f\inv(12)\text{.}\\
Answer
1. \\f\\ is not injective. To prove this, we must simply find two different elements of the domain which map to the same element of the codomain. Since \\f(\\1\$ = 1\\ and \\f(\\2\$ = 1\text{,}\\ we see that \\f\\ is not injective.
2. \\f\\ is not surjective. The largest subset of \\A\\ is \\A\\ itself, and \\\|A\| = 10\text{.}\\ So no natural number greater than 10 will ever be an output.
3. \\f\inv(1) = \\\\1\\, \\2\\, \\3\\, \ldots \\10\\\\\\ (the set of all the singleton subsets of \\A\$.
4. \\f\inv(0) = \\\emptyset\\\text{.}\\ Note, it would be wrong to write \\f\inv(0) = \emptyset\\ - that would claim that there is no input which has 0 as an output.
5. \\f\inv(12) = \emptyset\text{,}\\ since there are no subsets of \\A\\ with cardinality 12.
7
Let \\A = \\n \in \N \st 0 \le n \le 999\\\\ be the set of all numbers with three or fewer digits. Define the function \\f:A \to \N\\ by \\f(abc) = a+b+c\text{,}\\ where \\a\text{,}\\ \\b\text{,}\\ and \\c\\ are the digits of the number in \\A\text{.}\\ For example, \\f(253) = 2 + 5 + 3 = 10\text{.}\\
1. Find \\f\inv(3)\text{.}\\
2. Find \\f\inv(28)\text{.}\\
3. Is \\f\\ injective. Explain.
4. Is \\f\\ surjective. Explain.
Answer
1. \\f\inv(3) = \\003, 030, 300, 012, 021, 102, 201, 120, 210, 111\\\\
2. \\f\inv(28) = \emptyset\\ (since the largest sum of three digits is \\9+9+9 = 27\$
3. Part (a) proves that \\f\\ is not injective. The output 3 is assigned to 10 different inputs.
4. Part (b) proves that \\f\\ is not surjective. There is an element of the codomain (28) which is not assigned to any inputs.
8
Let \\f:X \to Y\\ be some function. Suppose \\3 \in Y\text{.}\\ What can you say about \\f\inv(3)\\ if you know,
1. \\f\\ is injective? Explain.
2. \\f\\ is surjective? Explain.
3. \\f\\ is bijective? Explain.
Answer
1. \\\|f\inv(3)\| \le 1\text{.}\\ In other words, either \\f\inv(3)\\ is the emptyset or is a set containing exactly one element. Injective functions cannot have two elements from the domain both map to 3.
2. \\\|f\inv(3)\| \ge 1\text{.}\\ In other words, \\f\inv(3)\\ is a set containing at least one elements, possibly more. Surjective functions must have something map to 3.
3. \\\|f\inv(3)\| = 1\text{.}\\ There is exactly one element from \\X\\ which gets mapped to 3, so \\f\inv(3)\\ is the set containing that one element.
9
Find a set \\X\\ and a function \\f:X \to \N\\ so that \\f\inv(0) \cup f\inv(1) = X\text{.}\\
Answer
\\X\\ can really be any set, as long as \\f(x) = 0\\ or \\f(x) = 1\\ for every \\x \in X\text{.}\\ For example, \\X = \N\\ and \\f(n) = 0\\ works.
10
What can you deduce about the sets \\X\\ and \\Y\\ if you know …
1. there is an injective function \\f:X \to Y\text{?}\\ Explain.
2. there is a surjective function \\f:X \to Y\text{?}\\ Explain.
3. there is a bijectitve function \\f:X \to Y\text{?}\\ Explain.
11
Suppose \\f:X \to Y\\ is a function. Which of the following are possible? Explain.
1. \\f\\ is injective but not surjective.
2. \\f\\ is surjective but not injective.
3. \\\|X\| = \|Y\|\\ and \\f\\ is injective but not surjective.
4. \\\|X\| = \|Y\|\\ and \\f\\ is surjective but not injective.
5. \\\|X\| = \|Y\|\text{,}\\ \\X\\ and \\Y\\ are finite, and \\f\\ is injective but not surjective.
6. \\\|X\| = \|Y\|\text{,}\\ \\X\\ and \\Y\\ are finite, and \\f\\ is surjective but not injective.
12
Let \\f:X \to Y\\ and \\g:Y \to Z\\ be functions. We can define the composition of \\f\\ and \\g\\ to be the function \\g\circ f:X \to Z\\ which the image of each \\x \in X\\ is \\g(f(x))\text{.}\\ That is, plug \\x\\ into \\f\text{,}\\ then plug the result into \\g\\ (just like composition in algebra and calculus).
1. If \\f\\ and \\g\\ are both injective, must \\g\circ f\\ be injective? Explain.
2. If \\f\\ and \\g\\ are both surjective, must \\g\circ f\\ be surjective? Explain.
3. Suppose \\g\circ f\\ is injective. What, if anything, can you say about \\f\\ and \\g\text{?}\\ Explain.
4. Suppose \\g\circ f\\ is surjective. What, if anything, can you say about \\f\\ and \\g\text{?}\\ Explain.
Hint
Work with some examples. What if \\f = \twoline{1& 2 & 3}{a & a & b}\\ and \\g = \twoline{a& b & c}{5 & 6 & 7}\\?
13
Consider the function \\f:\Z \to \Z\\ given by \\f(n) = \begin{cases}n+1 & \text{ if }n\text{ is even} \\ n-3 & \text{ if }n\text{ is odd} . \end{cases}\\
1. Is \\f\\ injective? Prove your answer.
2. Is \\f\\ surjective? Prove your answer.
Answer
a: \\f\\ is injective.
*Proof*
Let \\x\\ and \\y\\ be elements of the domain \\\Z\text{.}\\ Assume \\f(x) = f(y)\text{.}\\ If \\x\\ and \\y\\ are both even, then \\f(x) = x+1\\ and \\f(y) = y+1\text{.}\\ Since \\f(x) = f(y)\text{,}\\ we have \\x + 1 = y + 1\\ which implies that \\x = y\text{.}\\ Similarly, if \\x\\ and \\y\\ are both odd, then \\x - 3 = y-3\\ so again \\x = y\text{.}\\ The only other possibility is that \\x\\ is even an \\y\\ is odd (or visa-versa). But then \\x + 1\\ would be odd and \\y - 3\\ would be even, so it cannot be that \\f(x) = f(y)\text{.}\\ Therefore if \\f(x) = f(y)\\ we then have \\x = y\text{,}\\ which proves that \\f\\ is injective.
\\\square\\
b: \\f\\ is surjective.
*Proof*
Let \\y\\ be an element of the codomain \\\Z\text{.}\\ We will show there is an element \\n\\ of the domain (\\\Z\$ such that \\f(n) = y\text{.}\\ There are two cases: First, if \\y\\ is even, then let \\n = y+3\text{.}\\ Since \\y\\ is even, \\n\\ is odd, so \\f(n) = n-3 = y+3-3 = y\\ as desired. Second, if \\y\\ is odd, then let \\n = y-1\text{.}\\ Since \\y\\ is odd, \\n\\ is even, so \\f(n) = n+1 = y-1+1 = y\\ as needed. Therefore \\f\\ is surjective.
\\\square\\
14
At the end of the semester a teacher assigns letter grades to each of her students. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?
Answer
Yes, this is a function, if you choose the domain and codomain correctly. The domain will be the set of students, and the codomain will be the set of possible grades. The function is almost certainly not injective, because it is likely that two students will get the same grade. The function might be surjective – it will be if there is at least one student who gets each grade.
15
In the game of *Hearts*, four players are each dealt 13 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?
16
Suppose 7 players are playing 5-card stud. Each player initially receives 5 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?
Answer
This cannot be a function. If the domain were the set of cards, then it is not a function because not every card gets dealt to a player. If the domain were the set of players, it would not be a function because a single player would get mapped to multiple cards. Since this is not a function, it doesn't make sense to say whether it is injective/surjective/bijective.
---