Physics Lournal

Chapter 0: Intro And Preliminary

What is Discrete Mathematics?

Generally, Discrete Mathematics is the application of any mathematical technique, to any distinct, or collection of distinct items.

Specifically, by discrete we mean items that are entirely separate from each other, with a clean demarcation.

Investigate!

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?

The number of handshakes that take place is $10!$ : we can prove this by imagining $1$ person shakes everyone's hand, and then steps away from the group. (We can do this because no one else needs to shake his hand, when it's their turn, as they already have when it was histurn.) There are now $9$ people left.

Then we imagine another person ( $1$ ), repeats this process. There are now 8 people left.

And so on, and so forth, until we've gone from a group of 10, to a group of 1.

Ah, well at least our hunch was correct: factorial began to seem a bit off when we realized we couldn't come up with a logical reason to multiply the first handshake iteration sum by the second, and also would get a rather large and unwieldy number from that.

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?

So we have a few variables here:

$P$ , for people, $h$ , for hot-dogs, and $n$ for our place in line.

We're going to rely on Classical Mechanics: The number of hot-dogs eaten by a person at a given place in line, n, $P_{n}(h)$ , is equal to the number of hot-dogs eaten at time $n - 1$ , plus two so: $P_{n}(h) = P_{n - 1}(h + 2)$ .

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):

If this chest is empty, then the other chest's message is true.

This chest is filled with treasure or the other chest contains deadly scorpions

Assume $C1$ is empty: $C2's$ message must be true. However, that says that $C1$ isn't empty, which means in order for $C1$ to be true, it must be lying. Logically we want to focus on if the consequent (the other chest's message being true)- $C1$ can only be false if it is empty, and $C2's$ message is false.

Assume $C2$ is true: If it contains the treasure, the other one ( $C1$ ) might, or might not have scorpions: it can have scorpions or be empty. We know if we check $C2$ , the worst outcome is that it, is empty, and the best outcome is that we're rich. We know if we check $C1$ , the worst outcome is that we die, and the best outcome is that we don't.

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?

Note that this is about Graph Theory: We're dealing with nodes (the towns), and edges (the roads), and trying to show that the graph representing this arrangement of towns and roads, contains nodes with indegree, and outdegree (inbound and outbound edges), values that cannot exist without overlap.

No:

graph TD; A-->B; B-->C; C-->D; D-->E; D-->C; E-->A; E-->D; E-->C;

At most, one city can be connected to two other cities, and furthermore, once one city is connected to three cities, any other city with two connections will cause an overlap on the third.

Mathematical Statements

A statement is a declarative sentence that obeys the law of excluded middles. It's values are binary, boolean in nature.

A statement can be atomic, meaning that is logically indivisible into further components, otherwise it is molecular, and thus is necessarily made up of atomic statements via the use of logical connectives.

$3 + x = 12$ :

This sentence is not a statement, as the boolean value of it depends on $x$ , which is a placeholder for information not given in the statement:

In order to deal with this, we have option of substituting the value via a $where$ clause, or we can capture the free variable by quantifying over it.

Logical Connectives:

These are the words: $and,\; or,\; if/then,\; not$ .

And, or and if/then, are binary connectives, as they require two operands, whereas not is a unary connective, as it only requires one.

Molecular statements, have truth values, that are defined by the connectives within them, and the truth values of the atomic statements therein.

When analyzing these connectives, we rely on propositional-variables, $\small P,\;Q,\;R,\;S.$ , as well as symbols for the connectives: $\land, \lor\, \implies, \neg$ , because the content of these statements are trivial, we care more about the logicality.

$\small P \land Q\; = Conjunction.$

$\small P \lor Q\; = Disjunction.$

$\small P \implies Q = Implication.$

$\small P \leftrightarrow Q = Biconditional.$

One should think of this as saying the two atomic parts of a statement are equivalent in terms of their boolean value. Again, we do not assume any causal relationship between P, and Q: P is not the cause of Q, but if P is true, then Q should be as well.

$\small \neg P = Negation.$

Truth Conditions

$\small P \land Q = T \iff P,\; and\; Q = T$ .

$\small P \lor Q = T \iff P \lor Q = T.$

$\small P \implies Q \iff P \land Q = T \lor F.$

$\small P \leftrightarrow Q = T \iff P \land Q = T \lor F.$

Implications

We say that $P$ is the hypothesis or antecedent, and that $Q$ is the conclusion or consequent.

Implications are strewn throughout mathematics (see Formal Logic), even if not obviously: Given the Pythagorean Theorem, $a^{2} + b^{2} = c^{2}$ , we realize it can not be a statement, as it contains uncaptured/unquantified free variables, but if we quantify that $a$ and $b$ are the legs of a right triangle, with hypotenuse $c$ , we now have a statement.

Example:

If Bob gets a 90%, he passes.

$P \implies Q$ , can still hold, even if $\neg P$ , as " $P_{i}$ ", isn't the only $P$ where Q, so we can't falsify $Q$ solely because we can say $\neg P$ .

In short, $\neg P \newcommand{\notimplies}{\;\not!!!\implies} \notimplies \neg(P \implies Q)$ .

With implications, we focus more on the truth value of the consequent ( $\small Q$ ), since there is no causal relationship, $Q$ is only logically dependent upon $P$ , the implication asserts the consequent, not the antecedent, hence the antecedent can be false, while the consequent remains true.

For instance, the fact that there is no gravity in sections of space does not mean that gravity is false- if things fall, gravity exists- we have artificial zero-gravity, but that certainly does not disprove the existence of gravity.

iff

If and only if is equivalent to: $(P \implies Q) \land (Q \implies P)$

We also deal with two concepts: the converse, and the contrapositive:

The converse of $P \implies Q$ , is simply a reversal of the antecedent and consequent: $Q \implies P$ .

Converses are logically independent of their implications.

The contrapositive of $P \implies Q$ , is the statement $\neg Q \implies \neg P$ .

The contrapositive of any implication must necessarily have the same truth value as its implication.

Predicates and Quantifiers.

Implications are strewn throughout mathematics (see Formal Logic), even if not obviously: Given the Pythagorean Theorem, $a^{2} + b^{2} = c^{2}$ , we realize it can not be a statement, as it contains uncaptured/unquantified free variables, but if we quantify that $a$ and $b$ are the legs of a right triangle, with hypotenuse $c$ , we now have a statement.

Specifically, we have symbology for dealing with these situations. First, the term for sentences with variables is predicate.

In situations where we need to speak about ranges of values, we apply quantifiers: For All: $\forall, \forall x$ , and Exists: $\exists, \exists x$ .

Usually we quantify over the $N$ , as they're discrete.

Negations:

$\neg \forall x\; P(x) = \exists x\; \neg P(x)$ .

Not for all x, is x prime = There exists some x such that x is not prime.

$\neg \exists x P(x) = \forall x \neg P(x)$ .

There does not exist an x such that is prime = For all x, x is not prime.

Effectively, negating a quantifier makes it switch types.

Implicit Quantifiers

For situations, such as square rectangle relationships (every square is a rectangle, but every rectangle is not a square), we have implicit quantifiers: given $S(x)$ , meaning $x$ is a square, and $R(x)$ , meaning $x$ is a rectangle, we can make the following statement: $\forall x(S(x) \implies R(x))$ .

Sets

Sets

Sets are fundamental: in short they are collections of discrete and unique objects, and generally aren't ordered.

Notation

$A =$ { $1,2,3$ } : A is the set containing elements, 1, 2 and 3.

$a \in$ { $a, b, c$ }: a is a member of the set containing elements a, b and c.

$d \notin$ { $a, b, c$ }: d is not a. member of the set containing elements a, b and c.

$A =$ { $1, b, {x, y, z}, \empty$ }: There are some things to notice about the set $A$ , first that $x \notin A$ , as there's not a letter in the set that equals x. Consider set $B = {1, b}$ , which contains elements in $A$ , but the set $B$ itself is not a member of $A$ , but rather a subset.

$A = {x \in \N: \exists n \in \N (x = 2n)}$ : A is the set of all x in the Natural numbers such that there exists an n in the Naturals such that x is equivalent to 2n.

Relationships Between Sets

Two sets can be considered equal if they have the same elements, barring any repeated elements. Also, it does not matter the representation of values in sets: $\small {1, 2, 3} = {\text{I, II, III}}$ .

Given $A = {1, 2, 3}\; {and}\; B = {1, 2, 3, 4}$ , we see that $A$ has some of the elements of $B$ , but not all of them. Basically, $A$ is a $\small {subset}$ of $B$ , or symbolically $A \sub B$ . If they had exactly the same elements, we would say $A \subseteq B$ , because $A$ is a $\small {subset\; of\; and\; is\; equal\; to}\; B$ .

Another method for comparing sets is by comparing size, which we refer to as cardinality: $|\small A|$ .

Operations On Sets

In terms of "addition", we can use the unionoperator to combine sets: $\small C = A \cup B$ . $C$ is the union of $A$ and $B$ .

Another operation is intersection, which selects the elements expressly in both sets: $\small C = A \cap B$ .

One more consideration: we want to clarify what "everything" is, with regards to our (perhaps finite) set, for instance, if we were only concerned with Naturals, our universe would be $N$ , also written $U$ .

Sometimes we will of course want to speak about elements that are not in our set, or the complement of a given set: $B = \bar A$ . Imagine $\small A = {1, 2, 3}\; {and}\; B ={1, 2, 3, 4, 5, 9}$ , we see $\small \bar A = {4, 5, 9}$ .

We also can combine operations, such as $\small A \cap \bar B$ : the set of all elements which are both members of $A$ , and not members of $B$ . This is the set difference. Effectively : $\small A \cap B = A \setminus B$ .

$\small x \in A \cup B \iff x \in A \lor x \in B$ : For x to be a member of the union of $\small A$ or $\small B$ , x must be a member of $\small A$ , or a member of $\small B.$

$x \in A \cap B \iff x \in A \land x \in B$ : For x to be a member of the intersection of $A$ or $B$ , x must be a member of $A$ , and a member of $B$ .

$x \in \bar A \iff \neg(x \in A)$ : For x to be a member of the complement of $A$ or $B$ , x must not be a member of $A$ .

Cartesian Products

This is represented by $\small A \times B$ , and effectively:

$\small A \times B = {(a,b): a \in A \land b \in B}$ : We're simply putting an element from the first set, in an ordered pair, with an element from the second set.

We can also take the cartesian product of a set with itself:

$\small A \times A = {(a,b): a,b \in A}\; \text{also written as:}\; A^{2}$ .

$A \times B$ : {(1,3), (1,4) (1,5), (2,3), (2,4), (2, 5)}

$A \times A$ : (1,2), (1,1), ()

Not sure if (2, 1) is relevant here, it seems redundant though.

Turns out it's not redundant.

Oh well taking the product of a set with itself does imply two sets, so that explains part of it, as well as the fact that the nature of sets to ignore duplicates does not transfer down to the tuples made from cartesian products of them, hence (2,1) and (1,2) being listed out.

It seems like: $\small |A \times B| = |B| *|A|$

$B \times B$ : (3,4), (3,5), (4,5)

Exercises

Given $A = {1, 4, 9}, {and}\; B = {1, 3, 6, 10}$ , find:

$A \cup B$ : ${1,4,9,6,3,10}$

$A \cap B$ : ${1}$ (a singleton).

$A \setminus B$ : ${4,9}$

$B \setminus A$ : ${3, 6, 10}$

Referenced in

Discrete Mathematics: OpenBook

Chapter 0: Intro And Preliminary

Chapter 0: Intro And Preliminary

What is Discrete Mathematics?

Generally, Discrete Mathematics is the application of any mathematical technique, to any distinct, or collection of distinct items.

Specifically, by discrete we mean items that are entirely separate from each other, with a clean demarcation.

Investigate!

Then we imagine another person (111), repeats this process. There are now 8 people left.

And so on, and so forth, until we've gone from a group of 10, to a group of 1.

Ah, well at least our hunch was correct: factorial began to seem a bit off when we realized we couldn't come up with a logical reason to multiply the first handshake iteration sum by the second, and also would get a rather large and unwieldy number from that.

So we have a few variables here:

PPP, for people, hhh, for hot-dogs, and nnn for our place in line.

We're going to rely on Classical Mechanics: The number of hot-dogs eaten by a person at a given place in line, n, Pn(h)P_{n}(h)Pn​(h), is equal to the number of hot-dogs eaten at time n−1n - 1n−1, plus two so: Pn(h)=Pn−1(h+2)P_{n}(h) = P_{n - 1}(h + 2)Pn​(h)=Pn−1​(h+2).

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):

If this chest is empty, then the other chest's message is true.

This chest is filled with treasure or the other chest contains deadly scorpions

Note that this is about Graph Theory: We're dealing with nodes (the towns), and edges (the roads), and trying to show that the graph representing this arrangement of towns and roads, contains nodes with indegree, and outdegree (inbound and outbound edges), values that cannot exist without overlap.

No:

At most, one city can be connected to two other cities, and furthermore, once one city is connected to three cities, any other city with two connections will cause an overlap on the third.

Mathematical Statements

A statement is a declarative sentence that obeys the law of excluded middles. It's values are binary, boolean in nature.

A statement can be atomic, meaning that is logically indivisible into further components, otherwise it is molecular, and thus is necessarily made up of atomic statements via the use of logical connectives.

3+x=123 + x = 123+x=12:

This sentence is not a statement, as the boolean value of it depends on xxx, which is a placeholder for information not given in the statement:

In order to deal with this, we have option of substituting the value via a wherewherewhere clause, or we can capture the free variable by quantifying over it.

Logical Connectives:

These are the words: and, or, if/then, notand,\; or,\; if/then,\; notand,or,if/then,not.

And, or and if/then, are binary connectives, as they require two operands, whereas not is a unary connective, as it only requires one.

Molecular statements, have truth values, that are defined by the connectives within them, and the truth values of the atomic statements therein.

When analyzing these connectives, we rely on propositional-variables, P, Q, R, S.\small P,\;Q,\;R,\;S.P,Q,R,S., as well as symbols for the connectives: ∧,∨ ⟹ ,¬\land, \lor\, \implies, \neg∧,∨⟹,¬, because the content of these statements are trivial, we care more about the logicality.

P∧Q =Conjunction.\small P \land Q\; = Conjunction.P∧Q=Conjunction.

P∨Q =Disjunction.\small P \lor Q\; = Disjunction.P∨Q=Disjunction.

P ⟹ Q=Implication.\small P \implies Q = Implication.P⟹Q=Implication.

P↔Q=Biconditional.\small P \leftrightarrow Q = Biconditional.P↔Q=Biconditional.

One should think of this as saying the two atomic parts of a statement are equivalent in terms of their boolean value. Again, we do not assume any causal relationship between P, and Q: P is not the cause of Q, but if P is true, then Q should be as well.

¬P=Negation.\small \neg P = Negation.¬P=Negation.

Truth Conditions

P∧Q=T ⟺ P, and Q=T\small P \land Q = T \iff P,\; and\; Q = TP∧Q=T⟺P,andQ=T.

P∨Q=T ⟺ P∨Q=T.\small P \lor Q = T \iff P \lor Q = T.P∨Q=T⟺P∨Q=T.

P ⟹ Q ⟺ P∧Q=T∨F.\small P \implies Q \iff P \land Q = T \lor F.P⟹Q⟺P∧Q=T∨F.

P↔Q=T ⟺ P∧Q=T∨F.\small P \leftrightarrow Q = T \iff P \land Q = T \lor F.P↔Q=T⟺P∧Q=T∨F.

Implications

We say that PPP is the hypothesis or antecedent, and that QQQ is the conclusion or consequent.

Example:

If Bob gets a 90%, he passes.

P ⟹ QP \implies QP⟹Q, can still hold, even if ¬P\neg P¬P, as "PiP_{i}Pi​", isn't the only PPP where Q, so we can't falsify QQQ solely because we can say ¬P\neg P¬P.

In short, ¬P !̸!! ⟹ ¬(P ⟹ Q)\neg P \newcommand{\notimplies}{\;\not!!!\implies} \notimplies \neg(P \implies Q)¬P!!!⟹¬(P⟹Q).

With implications, we focus more on the truth value of the consequent (Q\small QQ), since there is no causal relationship, QQQ is only logically dependent upon PPP, the implication asserts the consequent, not the antecedent, hence the antecedent can be false, while the consequent remains true.

For instance, the fact that there is no gravity in sections of space does not mean that gravity is false- if things fall, gravity exists- we have artificial zero-gravity, but that certainly does not disprove the existence of gravity.

iff

If and only if is equivalent to: (P ⟹ Q)∧(Q ⟹ P)(P \implies Q) \land (Q \implies P)(P⟹Q)∧(Q⟹P)

We also deal with two concepts: the converse, and the contrapositive:

The converse of P ⟹ QP \implies QP⟹Q, is simply a reversal of the antecedent and consequent: Q ⟹ PQ \implies PQ⟹P.

Converses are logically independent of their implications.

The contrapositive of P ⟹ QP \implies QP⟹Q, is the statement ¬Q ⟹ ¬P\neg Q \implies \neg P¬Q⟹¬P.

The contrapositive of any implication must necessarily have the same truth value as its implication.

Predicates and Quantifiers.

Specifically, we have symbology for dealing with these situations. First, the term for sentences with variables is predicate.

In situations where we need to speak about ranges of values, we apply quantifiers: For All: ∀,∀x\forall, \forall x∀,∀x, and Exists: ∃,∃x\exists, \exists x∃,∃x.

Usually we quantify over the NNN, as they're discrete.

Negations:

¬∀x P(x)=∃x ¬P(x)\neg \forall x\; P(x) = \exists x\; \neg P(x)¬∀xP(x)=∃x¬P(x).

Not for all x, is x prime = There exists some x such that x is not prime.

¬∃xP(x)=∀x¬P(x)\neg \exists x P(x) = \forall x \neg P(x)¬∃xP(x)=∀x¬P(x).

There does not exist an x such that is prime = For all x, x is not prime.

Effectively, negating a quantifier makes it switch types.

Implicit Quantifiers

Sets

Sets are fundamental: in short they are collections of discrete and unique objects, and generally aren't ordered.

Notation

A=A =A= {1,2,31,2,31,2,3} : A is the set containing elements, 1, 2 and 3.

a∈a \ina∈ {a,b,ca, b, ca,b,c}: a is a member of the set containing elements a, b and c.

d∉d \notind∈/ {a,b,ca, b, ca,b,c}: d is not a. member of the set containing elements a, b and c.

A=x∈N:∃n∈N(x=2n)A = {x \in \N: \exists n \in \N (x = 2n)}A=x∈N:∃n∈N(x=2n): A is the set of all x in the Natural numbers such that there exists an n in the Naturals such that x is equivalent to 2n.

Relationships Between Sets

Two sets can be considered equal if they have the same elements, barring any repeated elements. Also, it does not matter the representation of values in sets: 1,2,3=I, II, III\small {1, 2, 3} = {\text{I, II, III}}1,2,3=I, II, III.

Another method for comparing sets is by comparing size, which we refer to as cardinality: ∣A∣|\small A|∣A∣.

Operations On Sets

In terms of "addition", we can use the unionoperator to combine sets: C=A∪B\small C = A \cup BC=A∪B. CCC is the union of AAA and BBB.

Another operation is intersection, which selects the elements expressly in both sets: C=A∩B\small C = A \cap BC=A∩B.

One more consideration: we want to clarify what "everything" is, with regards to our (perhaps finite) set, for instance, if we were only concerned with Naturals, our universe would be NNN, also written UUU.

Sometimes we will of course want to speak about elements that are not in our set, or the complement of a given set: B=AˉB = \bar AB=Aˉ. Imagine A=1,2,3 and B=1,2,3,4,5,9\small A = {1, 2, 3}\; {and}\; B ={1, 2, 3, 4, 5, 9}A=1,2,3andB=1,2,3,4,5,9, we see Aˉ=4,5,9\small \bar A = {4, 5, 9}Aˉ=4,5,9.

Then we imagine another person ( $1$ ), repeats this process. There are now 8 people left.

$P$ , for people, $h$ , for hot-dogs, and $n$ for our place in line.

We're going to rely on Classical Mechanics: The number of hot-dogs eaten by a person at a given place in line, n, $P_{n}(h)$ , is equal to the number of hot-dogs eaten at time $n - 1$ , plus two so: $P_{n}(h) = P_{n - 1}(h + 2)$ .

$3 + x = 12$ :

This sentence is not a statement, as the boolean value of it depends on $x$ , which is a placeholder for information not given in the statement:

In order to deal with this, we have option of substituting the value via a $where$ clause, or we can capture the free variable by quantifying over it.

These are the words: $and,\; or,\; if/then,\; not$ .

When analyzing these connectives, we rely on propositional-variables, $\small P,\;Q,\;R,\;S.$ , as well as symbols for the connectives: $\land, \lor\, \implies, \neg$ , because the content of these statements are trivial, we care more about the logicality.

$\small P \land Q\; = Conjunction.$

$\small P \lor Q\; = Disjunction.$

$\small P \implies Q = Implication.$

$\small P \leftrightarrow Q = Biconditional.$

$\small \neg P = Negation.$

$\small P \land Q = T \iff P,\; and\; Q = T$ .

$\small P \lor Q = T \iff P \lor Q = T.$

$\small P \implies Q \iff P \land Q = T \lor F.$

$\small P \leftrightarrow Q = T \iff P \land Q = T \lor F.$

We say that $P$ is the hypothesis or antecedent, and that $Q$ is the conclusion or consequent.

$P \implies Q$ , can still hold, even if $\neg P$ , as " $P_{i}$ ", isn't the only $P$ where Q, so we can't falsify $Q$ solely because we can say $\neg P$ .

In short, $\neg P \newcommand{\notimplies}{\;\not!!!\implies} \notimplies \neg(P \implies Q)$ .

With implications, we focus more on the truth value of the consequent ( $\small Q$ ), since there is no causal relationship, $Q$ is only logically dependent upon $P$ , the implication asserts the consequent, not the antecedent, hence the antecedent can be false, while the consequent remains true.

If and only if is equivalent to: $(P \implies Q) \land (Q \implies P)$

The converse of $P \implies Q$ , is simply a reversal of the antecedent and consequent: $Q \implies P$ .

The contrapositive of $P \implies Q$ , is the statement $\neg Q \implies \neg P$ .

In situations where we need to speak about ranges of values, we apply quantifiers: For All: $\forall, \forall x$ , and Exists: $\exists, \exists x$ .

Usually we quantify over the $N$ , as they're discrete.

$\neg \forall x\; P(x) = \exists x\; \neg P(x)$ .

$\neg \exists x P(x) = \forall x \neg P(x)$ .

$A =$ { $1,2,3$ } : A is the set containing elements, 1, 2 and 3.

$a \in$ { $a, b, c$ }: a is a member of the set containing elements a, b and c.

$d \notin$ { $a, b, c$ }: d is not a. member of the set containing elements a, b and c.

$A = {x \in \N: \exists n \in \N (x = 2n)}$ : A is the set of all x in the Natural numbers such that there exists an n in the Naturals such that x is equivalent to 2n.

Two sets can be considered equal if they have the same elements, barring any repeated elements. Also, it does not matter the representation of values in sets: $\small {1, 2, 3} = {\text{I, II, III}}$ .

Another method for comparing sets is by comparing size, which we refer to as cardinality: $|\small A|$ .

In terms of "addition", we can use the unionoperator to combine sets: $\small C = A \cup B$ . $C$ is the union of $A$ and $B$ .

Another operation is intersection, which selects the elements expressly in both sets: $\small C = A \cap B$ .

One more consideration: we want to clarify what "everything" is, with regards to our (perhaps finite) set, for instance, if we were only concerned with Naturals, our universe would be $N$ , also written $U$ .

Sometimes we will of course want to speak about elements that are not in our set, or the complement of a given set: $B = \bar A$ . Imagine $\small A = {1, 2, 3}\; {and}\; B ={1, 2, 3, 4, 5, 9}$ , we see $\small \bar A = {4, 5, 9}$ .

We also can combine operations, such as $\small A \cap \bar B$ : the set of all elements which are both members of $A$ , and not members of $B$ . This is the set difference. Effectively : $\small A \cap B = A \setminus B$ .

$\small x \in A \cup B \iff x \in A \lor x \in B$ : For x to be a member of the union of $\small A$ or $\small B$ , x must be a member of $\small A$ , or a member of $\small B.$

$x \in A \cap B \iff x \in A \land x \in B$ : For x to be a member of the intersection of $A$ or $B$ , x must be a member of $A$ , and a member of $B$ .

$x \in \bar A \iff \neg(x \in A)$ : For x to be a member of the complement of $A$ or $B$ , x must not be a member of $A$ .

This is represented by $\small A \times B$ , and effectively:

$\small A \times B = {(a,b): a \in A \land b \in B}$ : We're simply putting an element from the first set, in an ordered pair, with an element from the second set.

$\small A \times A = {(a,b): a,b \in A}\; \text{also written as:}\; A^{2}$ .

$A \times B$ : {(1,3), (1,4) (1,5), (2,3), (2,4), (2, 5)}

$A \times A$ : (1,2), (1,1), ()

It seems like: $\small |A \times B| = |B| *|A|$

$B \times B$ : (3,4), (3,5), (4,5)

Given $A = {1, 4, 9}, {and}\; B = {1, 3, 6, 10}$ , find:

$A \cup B$ : ${1,4,9,6,3,10}$

$A \cap B$ : ${1}$ (a singleton).

$A \setminus B$ : ${4,9}$

$B \setminus A$ : ${3, 6, 10}$