Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Adamson U
Discreet Math
Practice Quiz

Question:
1
...

2
...

3
...

4
...

5
...

6
...

7
...

8
...

9
...

10
...


Answer:
1
...
Suppose we have two countable sets, A and B
...
This creates a oneto-one correspondence between the details of the union of A and B and the natural numbers,
so the union of A and B is countable
...
This means that each group component can be paired with a unique natural
number, and every natural number corresponds to a component of the set
...
This is because the elements of A are already
countable and have one-to-one correspondence with the natural numbers
...


By doing this, we have created a one-to-one correspondence between the elements of the
union of A and B and the natural numbers, which means that the association of A and B is also
countable
...
To prove that the intersection of two countable sets is countable, we can use the fact that a
group is countable if a one-to-one correspondence exists between its elements and the natural
numbers
...
In that case, we can create a one-toone correspondence between the features of the intersection of A and B and the natural
numbers by listing the details of A that are also in B in any order
...

A set is countable if there is a one-to-one correspondence between its elements and the
natural numbers
...


Given two countable sets, A and B, we can create a one-to-one correspondence between the
elements of the intersection of A and B and the natural numbers by listing the details of A that
are also in B in any order
...
By listing these
elements in any order, we can pair each piece with a unique natural number, which is the
definition of countable
...


3
...
Since the set of real numbers is uncountable, and the
addition of a countable set is a subset of the group of real numbers, it follows that the
complement of a countable set is also uncountable
...
The complement of a group is defined as the
set of all features that are not in that set
...


Since the set of real numbers is uncountable, and the complement of a countable set is a subset
of the group of real numbers, it follows that the addition of a countable set is also uncountable
...
And since the complement of a
countable set is a subset of the uncountable set of real numbers, it must also be uncountable
...
To prove that the Cartesian product of two countable sets is countable, we can use the fact
that a group is countable if a one-to-one correspondence exists between its elements and the
natural numbers
...
In that case, we can create a
one-to-one correspondence between the details of their Cartesian product A x B and the
natural numbers by listing all the ordered pairs (a, b) where a is an element of A and b is an
element of B in lexicographic order (i
...
, (a1, b1), (a1, b2),
...
, (an,
bn) )
...

The Cartesian product of two sets, A and B, denoted by A x B, is the set of all ordered pairs (a,b)
where a is an element of A and b is an element of B
...
This means that each group component can be paired with a unique natural
number, and every natural number corresponds to a component of the set
...

Lexicographic order is a way of arranging words or other strings in a dictionary or a phonebook,
where each piece is ordered first by its first letter, then by its second letter, and so on
...


So, given that we have two countable sets, A and B, by listing all the ordered pairs (a, b) of the
Cartesian product A x B in lexicographic order, we can pair each element of A x B with a unique
natural number, which is the definition of countable
...
To prove that the set of all real numbers is uncountable, one way is to use the diagonal
argument
...
We can do this
by creating a table of all real numbers in the form of decimal expansions
...
This number is different from every number in the list and thus cannot be on the list, which
shows our assumption is incorrect
...

The proof that the set of all real numbers is uncountable is based on the idea of contradiction
...


To prove this assumption is false, a method is used to construct an actual number that cannot
be found on the list
...
Then, a new actual number is considered whose first digit is different from the first
digit of the first number in the list; the second digit is other than the double-digit of the second
number in the list, and so on
...


This means our initial assumption that the set of real numbers is countable needs to be
corrected; therefore, the location of all real numbers is uncountable
...


6
...
One way to do this is to create a one-to-one correspondence between the details of
the set of natural numbers and the natural numbers themselves
...
, and correspond each natural number n to the nth
element of this list
...

One way to demonstrate this for the set of natural numbers is to create a one-to-one
correspondence between the elements of the natural numbers and the natural numbers
themselves
...
and
corresponding each natural number n to the nth element of this list
...

Since the set of natural numbers corresponds one-to-one with the collection of natural
numbers, it's countable
...
The injective function is a function that assigns a unique element of the set to each
part of the image set, and the surjective function is a function that gives every detail of the
image set to at least one aspect of the group
...


7
...
One way to do this is to create a one-to-one correspondence between the details of
the set of rational numbers and the natural numbers by listing the rational numbers in the form
of a list of fractions in lowest terms, in lexicographic order (i
...
, (0,1), (1,1), (-1,1), (1,2), (-1,2),
(2,1), (-2,1)
...

One way to demonstrate this for the set of rational numbers is to create a one-to-one
correspondence between the elements of the rational numbers and the natural numbers
themselves
...
e
...
By
listing the fractions this way, every rational number will be listed exactly once, and the list of
bits corresponds to the set of natural numbers
...
The injective function is a function that assigns a unique element of the set to each
part of the image set, and the surjective function is a function that gives every detail of the
image set to at least one aspect of the group
...


It's important to note that this proof is not the only one, and there are other ways to
demonstrate that the set of rational numbers is countable, but this one is one of the more
commonly used
...
To prove that the set of all irrational numbers is uncountable, one way is to use the diagonal
argument
...

We can do this by creating a table of all irrational numbers in the form of decimal expansions
...
This number is different from every number in the list and thus cannot be on the list,
which shows our assumption is incorrect
...

The proof that the set of all irrational numbers is uncountable is based on the idea of
contradiction and the diagonal argument, which is similar to the evidence that the location of
real numbers is uncountable
...


To prove this assumption is false, a method is used to construct an irrational number that
cannot be found on the list
...
Then, a new irrational number is considered, whose first digit is
different from the first digit in the list, whose second digit is other than the double digit of the
second number in the list, and so on
...


This means our initial assumption that the set of irrational numbers is countable needs to be
corrected; therefore, the location of all irrational numbers is uncountable
...


9
...
One way to do this is to create a one-to-one correspondence between the details of
the set of algebraic numbers and the natural numbers by listing all algebraic numbers by their
defining polynomials in lexicographic order
...

One way to create a one-to-one correspondence between the set of algebraic numbers and the
natural numbers is by listing all algebraic numbers by their defining polynomials in lexicographic
order
...


For example, the polynomial 3x^2 + 2x + 1 would come before the polynomial 3x^2 + 3x + 1 in
lexicographic order
...
Therefore, the set of all algebraic numbers is countable because
a one-to-one correspondence exists between its elements and the natural numbers
...
To prove that the set of all transcendental numbers is uncountable, one way is to use the
fact that the setting of all real numbers is uncountable and that the set of all transcendental
numbers is a subset of the location of all real numbers
...

The statement says that one way to prove that all transcendental numbers are uncountable is
by using the set of all real numbers as uncountable and that all transcendental numbers are a
subset of all real numbers
...


A set is uncountable if there is no one-to-one correspondence between its elements and the
natural numbers, and the location of real numbers is known to be uncountable
...


Since the set of all transcendental numbers is a subset of the location of all real numbers,
meaning that all transcendental numbers are real numbers, if we can show that the set of all
real numbers is uncountable, it follows that the setting of all transcendental numbers is also
uncountable
...




---