search
Log In

Recent questions tagged set-theory&algebra

0 votes
1 answer
1
Consider the following properties: Reflexive Antisymmetric Symmetric Let $A=\{a,b,c,d,e,f,g\}$ and $R=\{(a,a), (b,b), (c,d), (c,g), (d,g), (e,e), (f,f), (g,g)\}$ be a relation on $A$. Which of the following property (properties) is (are) satisfied by the relation $R$? Only $a$ Only $c$ Both $a$ and $b$ $b$ and not $a$
asked Nov 20, 2020 in Discrete Mathematics jothee 70 views
0 votes
1 answer
2
Show that if $S$ is a set, then there does not exist an onto function $f$ from $S$ to $P(S),$ the power set of $S$. Conclude that $\mid S\mid < \mid P(S)\mid .$ This result is known as Cantor’s theorem. [Hint: Suppose such a function $f$ existed. Let $T = \{s \in S \mid s \notin f (s)\}$ and show that no element $s$ can exist for which $f (s) = T.]$
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 107 views
0 votes
0 answers
3
0 votes
0 answers
4
Show that the set of functions from the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is uncountable. [Hint: First set up a one-to-one correspondence between the set of real numbers between $0$ and $1$ and a subset of these functions. Do this by associating to the real number $0.\:d_{1}d_{2} \dots d_{n}\dots $ the function $f$ with $f (n) = dn.]$
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 72 views
0 votes
0 answers
5
Show that the set of all computer programs in a particular programming language is countable. [Hint: A computer program written in a programming language can be thought of as a string of symbols from a finite alphabet.]
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 42 views
0 votes
0 answers
6
Show that there is a one-to-one correspondence from the set of subsets of the positive integers to the set real numbers between $0$ and $1$. Use this result and question $34$ and $35$ to conclude that $ℵ_{0} < \mid P(Z^{+})\mid =\mid R\mid.\:[$Hint: Look at the first part of the hint for Exercise $35.]$
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 36 views
0 votes
0 answers
7
Show that there is no one-to-one correspondence from the set of positive integers to the power set of the set of positive integers. [Hint: Assume that there is such a one-to-one correspondence. Represent a subset of the set of positive integers as an infinite bit string with ... complement of the $ith$ bit of the $ith$ string in the list. Show that this new bit string cannot appear in the list.]
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 30 views
0 votes
0 answers
10
Show that when you substitute $(3n + 1)^{2}$ for each occurrence of $n$ and $(3m + 1)^{2}$ for each occurrence of m in the right-hand side of the formula for the function $f (m, n)$ in question $31,$ you obtain a one-to-one polynomial function $Z \times Z \rightarrow Z.$ It is an open question whether there is a one-to-one polynomial function $Q \times Q \rightarrow Q.$
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 20 views
0 votes
0 answers
11
0 votes
0 answers
16
Use question $25$ to provide a proof different from that in the text that the set of rational numbers is countable. [Hint: Show that you can express a rational number as a string of digits with a slash and possibly a minus sign.]
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 24 views
0 votes
0 answers
17
Prove that if it is possible to label each element of an infinite set $S$ with a finite string of keyboard characters, from a finite list characters, where no two elements of $S$ have the same label, then $S$ is a countably infinite set.
asked Apr 21, 2020 in Set Theory & Algebra Lakshman Patel RJIT 37 views
0 votes
0 answers
21
0 votes
0 answers
23
...