Hot answers tagged elementary-set-theory
9
You have only counted the numbers whose decimal expansion is finite. This covers absolutely no irrational number, and in fact not even all the rational numbers as well.
Furthermore there is absolutely no reason to expect that this sort of process is continuous. That is to say, the set of finite strings of integers is countable, but the set of infinite ...
6
$ \mathbb{Z} $ is defined as the set of integers, and in general for any set A, we can define $ A^2=A\times A=\left\{(a,b): a,b\in A\right\}$. According to this definition, $ \mathbb{Z}^2=\mathbb{Z}\times\mathbb{Z}=\left\{(a,b): a,b\in \mathbb{Z}\right\}$, so it's basically the set of vectors with 2 coordinates, when every coordinate is an integer.
4
A couple of ‘entry level’ treatments that can be confidently recommended.
Herbert B. Enderton, The Elements of Set Theory (Academic Press, 1997) is particularly clear in marking off the informal development of the theory of sets, cardinals, ordinals etc. (guided by the conception of sets as constructed in a cumulative hierarchy) and the formal ...
4
Let $S$ be a non-empty set such that every non-empty subset of it has an $\in$-maximum.
Then for $x,y \in S$ with $x \ne y$, we have either $x \in y$ or $y \in x$ because by hypothesis, $\{x,y\}$ has an $\in$-maximum. Therefore, $(S, \in)$ is a linear order. In the degenerate case that $S$ has only one element, clearly $(S, \in)$ is also a linear order.
...
4
You’re confusing yourself by using more notation than is necessary. Suppose that $y\in f\left[\bigcup\mathscr{A}\right]$; then by definition there is an $x\in\bigcup\mathscr{A}$ such that $y=f(x)$. By the definition of union we know that $x\in A_x$ for some $A_x\in\mathscr{A}$, so $y=f(x)\in f[A_x]\subseteq\bigcup\left\{f[A]:A\in\mathscr{A}\right\}$. Since ...
4
Using the second part of the definition recursively, we see $S$ must contain
$\varnothing=0$
$0\cup\{0\}=1$
$1\cup\{1\}=2$
$2\cup\{2\}=3$
$\cdots$
which are all distinct. Note that when we look at the set-theoretic construction of the naturals, we have $0=\varnothing$ and $n=\{k:k<n\}=\{k<n-1\}\cup\{n-1\}=n-1\cup\{n-1\}$.
4
You may be very interested in the following paper:
Victoria Gitman, Joel David Hamkins, Thomas A. Johnstone, What is the theory ZFC without power set? (arXiv, 2011)
Note that you cannot prove the existence of $\omega_1$ either, this is because $H(\omega_1)$, the set of the hereditarily countable sets contain all the countable ordinals, and it is a ...
3
You are not correct, of course, there are ordinals of unbounded cardinalities.
Note that it is sufficient to prove that there is a set of countable ordinals. If there is a set of countable ordinals, then Peter's hint completes the problem. To do that, note that you can find in $\mathcal P(\omega\times\omega)$ copies of every countable ordinal (as ...
3
Assuming that you’re using the notation $2^S$ for the power set of $S$, then yes, you’ve correctly described the set of functions from $A$ to $B$. If $A\ne\varnothing$ and $B=\varnothing$, $A\times B=\varnothing$, so the only $f\in 2^{A\times B}$ is $\varnothing$, and it fails to satisfy the first clause of the definition and is therefore not actually in ...
3
1) and 2) are explained in page 8, ${\scr P} x$ indicates that $x$ satisfies some predicate or some property (for example consider $x$ satisfies $\scr P$ if and only if $x$ is a positive integer then $2,23$ does not satisfy $\scr P$ and therefore is not an element of $\{x:{\scr P} x\}$), and $a _x$ is a function of $x$, so you can just substitute that by ...
3
Let's begin by understanding the letters and their meanings, then we'll give context to everything.
$\exists$ is a quantifier. It means that the following symbol is a variable (a set, in the case of set theory) and we assert there is an object which the properties which we require that symbol to have.
$S$ is that symbol. It is a placeholder that will be ...
3
The following are equivalent: $$y\in f\left(\bigcup\mathcal{A}\right)\\\exists x\in\bigcup\mathcal{A}:y=f(x)\\\exists A\in\mathcal A:\exists x\in A:y=f(x)\\\exists A\in\mathcal{A}:y\in f(A)\\y\in\bigcup\{f(A):A\in\mathcal{A}\}$$ You should be able to justify each step by definition of union or image.
3
Quote from Wikipedia: "To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction. See OISC) and the ability to change arbitrary memory ...
3
The best rigorous treatment that I’ve seen at the senior undergraduate/first-year graduate level is Karel Hrbacek & Thomas Jech, Introduction to Set Theory. The first edition was already very good, and the third has been expanded to include some important topics that were not originally covered. I agree with the very favorable Amazon review by Michael ...
2
I'm not an expert in Set Theory, but I'd say that if you're working in $ZF$, i.e, in particular, if you assume the Axiom of Foundation, then you can't find an example of what you're looking for. Indeed, if a set $x$ is transitive and each of its non empty subsets has $\in -$ maximum element, then trivially $x$ is totally (linearly) ordered by the membership ...
2
You have to be a bit careful with asking "is $f(n)$" recursive, where $f(n) = U(n,n)$ and $U$ is a universal GOTO program (or recursive function or turing machine or whatever).
$f$ isn't total, so if you distinguish between recursive and partially recursive functions, it's obviously not recursive. It's partially recursive though, since every GOTO program ...
2
Assuming $B = \{a_1,a_2,a_3,...,a_n\} \subset \mathbb R$, with $|B| = n$,
$B^n$ is the set of all ordered n-tuples of elements of $B$:
The exponent refers to the operation of the Cartesian Product of $B$ with itself, n times:
$$B^n = \underbrace{B \times B \times \cdots \times B}_{\Large\text{n times}} =\{(b_1, b_2,\cdots, b_n) \mid b_i \in B\}.$$
Can ...
2
See Theorem 2.14 of Rudin's PMA, the idea for which Rudin credits Cantor, who provided the canonical argument for the uncountability of the reals: See Cantor's Diagonalization Process.
How is your proof distinct from that proof?
Indeed, if you thought of this on your own, KUDOS!
See also Rudin's Theorem 2.43 (p. 41).
2
It is fairly simple to list them. Sets have no duplicate elements by default. Sets do not include elements of different types or pairs. So you can't have pairs and elements. Pairs are generated through Cartesian products.
{a, b, c, d, e}
{a, b, c, d}
{a, b, c, e}
{a, b, c}
So the answer is 4.
2
According to one convention for writing the composition of two relations, $\langle a,b\rangle\in(R_1\cup R_2)\circ R_3$ if and only if
$$\exists x\in A\Big(\langle a,x\rangle\in R_3\land\langle x,b\rangle\in R_1\cup R_2\Big)\;.$$
But this is true if and only if
$$\exists x\in A\left(\langle a,x\rangle\in R_3\land\Big(\langle x,b\rangle\in R_1\lor\langle ...
2
You are still quite far from proving the theorem. The issue seems to be that you misunderstood what the theorem is saying. I will try to explain it with a minimum of logical symbols, as you said you prefer that.
We are given a set $A$. First, let us investigate the premise:
$$\forall \mathcal F: \cup \mathcal F = A \to A \in \mathcal F$$
One could say ...
2
The ordinal $\omega_1$ has cardinality $\aleph_1$ which is greater than $\aleph_0$. Similarly, $\omega_2$, $\omega_3$,.... has cardinalities which are all greater than $\aleph_0$.
You can say that every countable ordinal has cardinality which is not greater than $\aleph_0$, in fact the cardinality is equal to $\aleph_0$.
Note that the ordinals ...
2
The condition that
$$\tag1 A\not\subseteq\bigcup(\mathcal A\setminus\{A\})\qquad\text{for all }A\in \mathcal A$$
is necessary to distinguish $\mathcal A$ from $\mathcal A\setminus\{A\}$ and sufficient as it implies that $A\in \mathcal B\subseteq \mathcal A$ iff $A\subseteq \bigcup\mathcal B$.
For each $A\in \mathcal A$, $(1)$ allows us to select an element ...
2
With the issue of possibly empty sets $A, B$, you might want to read up a bit on the existence of the Empty function.
In mathematics, an empty function is a function whose domain is the empty set. For each set A, there is exactly one such empty function
$$f_A: \varnothing \rightarrow A.$$
The graph of an empty function is a subset of the Cartesian ...
2
(In ZFC) by Cantor's theorem, $2^{\aleph_{0}}=\vert \mathcal{P}(\omega)\vert> \vert \omega\vert=\aleph_{0}$, so that $\vert P(\omega)\vert (\approx \mathbb{R})$ is an uncountable cardinal and therefore an uncountable (limit) ordinal (here $2^{\aleph_{0}}$ is cardinal exponentiation). The claim that $2^{\aleph_{0}}=\aleph_{1}$, i.e that the least cardinal ...
2
Use $x=x$ for $\varphi(x,y)$. Then your version of the axiom gives us a universal set $Y$: every $y$ is in $Y$. So it leads to an inconsistent theory.
The part that says that $\varphi(x,y,p) \land \varphi(x,z,p)$ implies $y=z$ says that the relation $\varphi$ is "function-like." It is a very strong set construction principle, but does not (one hopes) lead ...
2
Cantor's theorem is indeed very close to the diagonal argument.
The idea is a generalization of the following concept. We write a table: $$\begin{array}{|c|c|c|c|c}
\hline
\quad & f(x_1) & f(x_2) & f(x_3) & \ldots\\\hline
x_1 & 0 & 1 & 0 & \ldots\\\hline
x_2 & 1 & 1 & 0 & \ldots\\\hline
x_3 & 0 & 0 ...
2
First a minor technical objection: the index set $A$ need not be countable, so you can’t assume that you can list it as $a_1,a_2,\dots\,$.
Your major error comes when you go from $x\in f[F_a]$ to $f(x)\in F_a$: $x\in f[F_a]$ means that there is some $y\in F_a$ such that $x=f(y)$. However, since you’re assuming that $f$ is one-to-one, this $y$ is unique and ...
2
To extend a little Peter's comment, you are assuming that you have the decimal expansion of all real numbers. Even if you find a way to extend your method to reals with infinite decimal places (such as $\pi$), there are still a countable number of them. You are missing actually a number of reals that are uncountable and cannot be written with any algorithm: ...
2
Let's denote the $n^\text{th}$ number in your list by $f(n)$.
To use your method to prove that $[0,1)$ is countable, you need to show that $f$ is a surjection, that is, for every real number $x \in [0,1)$ there is a natural number $n$ such that $f(n) = x$. In particular, you have to show that there is a natural number $n$ such that $f(n) = 1/3$.
Note that ...
Only top voted, non community-wiki answers of a minimum length are eligible
