This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...
2
votes
3answers
41 views
What is the definition of a labeled function?
I always see that people label their functions by giving an index. Specifically I have this example:
$Theorem$: There is a unique binary operation $+:\mathbb{N}\times\mathbb{N}$ that satisfies the ...
3
votes
0answers
15 views
Prove that $\dim(X,\succsim)\leq|X^2|$ - A starting point for a journey into order theory
During the last week I kept on thinking about what looked an easy problem at a first glance.
Let $(X,\succsim)$ be a preordered set, and define $\mathcal{L}(\succsim)$ as the set of all complete ...
0
votes
1answer
48 views
prove $A \sim B\implies 2^A \sim 2^B$.
I want to prove that if $A \sim B$ then $2^A \sim 2^B$.
$A\sim B$: There is a bijection from $A$ to $B$
thanks.
3
votes
3answers
47 views
Cardinal arithmetic questions
I have problem to solve:
Let $a,b$ and $c$ be cardinal numbers. Prove that $a+b=b$, $b \le c$ implies $a+c=c$.
And trying to prove this I got couple questions:
For infinite cardinal $c$, is ...
2
votes
3answers
62 views
Cardinality of set containing all infinite subsets of $\mathbb{Q}$
I need to find the cardinality of the set $S$ of all infinite subsets of $\mathbb{Q}$.
It's easy to prove $\operatorname{card} S=\mathfrak c$ if you first prove that the cardinality of the set of ...
7
votes
1answer
36 views
Does deleting a subset of an infinite set that has strictly smaller cardinality leave the cardinality of the infinite set unchanged?
Is it a theorem of ZFC that if
$X \subseteq Y$,
$|X| < |Y|$,
$Y$ is infinite,
then
$|Y \setminus X|=|Y|$?
7
votes
4answers
126 views
How to justify the existence of a function, in general?
Maybe I'm too naive in asking this question, but I think it's important and I'd like to know your answer. So, for example I always see that people just write something like "let $f:R\times ...
7
votes
3answers
207 views
Is there any way to save this “proof” that $\aleph_0=\aleph$?
I came up with this idea of proving that $\aleph_0=\aleph$. I know this is not true at all, but maybe there is more to it than I can see.
we start with the inequality $\aleph_0 \leq ...
-2
votes
1answer
46 views
Discrete Math Satisfying functions with sets [closed]
Let $A = \{1, 2, 3,\ldots, 10\},$ and $ B = \{1, 2, 3, \ldots , 7\}.$
How many functions $f : A\to B$ satisfy $|f(A)| = 4?$ How many have $|f (A)| \le 4$?
0
votes
1answer
30 views
Problem with a set theory proof (Cartesian product)
I have a problem doing the following proof:
Let $A,B,C$ be sets so that $A\cap B=A\cap C=B\cap C=\emptyset$.
Prove that $(A\times B)\cup (B\times C)=((A\cup B)\times (B\cup ...
0
votes
1answer
30 views
Finite Disjoint Subsets [closed]
Consider that we have a set $S$ with cardinality $2^{\kappa}$ where $\kappa$ is an infinite cardinal. Now, let's consider $A$, the collection of all finite and mutually disjoint finite subsets of $S$. ...
2
votes
1answer
43 views
Equivalent forms of the recursion theorem
I have found the next two definitions on the theorem of recursion:
Definition 1:
For any set $A$, any $a\in A$ and any function $g:A\times \mathbb{N} \longrightarrow A$, there exists a unique ...
2
votes
1answer
56 views
How do we know we need the axiom of choice for some theorem?
I have been working through Munkres Topology book and in an exercise he says that there was a theorem he proved in a previous section that relied on the axiom of choice and the task is to find it. I ...
1
vote
3answers
59 views
Proving $(A\le B)\vee (B\le A)$ for sets $A$ and $B$
For any pair of sets $A$ and $B$, we can define $A\le B$ iff there exists injection $f\colon A\rightarrow B$. I am trying prove that
$$(A\le B)\vee (B\le A).$$
I have tried assuming $\neg (A\le ...
1
vote
1answer
51 views
The comprehension axioms follows from the replacement schema.
I hope to show that the comprehension axioms follows from the replacement schema.
This is a solution that professor wrote.
$P(u,u)$: every set $u$, exists an unique $u$ such that $\psi(u)$.
Then ...
0
votes
1answer
29 views
Cardinality of Distinct Hilbert Systems with Detachment
Let us consider all formulas T of classical propositional logic which are tautologies up to simple substitution of variables where a variable can get simply substituted for another variable if and ...
0
votes
2answers
52 views
What is the complement of $A = \{1,3,5\}$ in $S = \{1,2,3,4,5,6\}$?
Roll a 6 sided die once. Let $S=\{1,2,3,4,5,6\}$ be the sample space of all possible things that could happen. Let the event $A=\{1,3,5\}$ and the event $B=\{1,4\}$.
What is the complement of $A$?
6
votes
1answer
68 views
Lebesgue measure zero set of cardinality $\mathfrak c$
Suppose $A\subset\mathbb R$ is a Lebesgue measure zero set. Must $\mathbb R\setminus A$ has cardinality $\mathfrak c$?
If so, does there exist another Lebesgue measure zero set $B$ of cardinality ...
0
votes
2answers
54 views
Ordering a set of infinite numbers to make it countable, with the constraint that we have no formula for generating those numbers.
Say we have a set $\{1,a_{1},a_{2}\dots 2\}$. Here, $a_{1},a_{2}\dots$ are an infinite number of terms between $1$ and $2$.
We'll assume that the set $a_{1},a_{2}\dots$ is countable. Clearly the ...
19
votes
4answers
310 views
“$f$ is a function from $A$ to $B$” vs. “$f $is a function from $A$ into $B$”?
When we say that
$f$ is a function from $A$ to $B$
is this different from saying
$f$ is a function from $A$ into $B$
I know what injective ("1-1"), surjective ("onto"), and bijective ...
1
vote
1answer
36 views
Which of the following statements are true?
I need to verify a few of my answers and get help on a few others.
Let $ (X,\preceq) $ be a partially ordered set and $A \subseteq X. $
Min$A$ exists and $ (A,\preceq) $ is totally ordered ...
2
votes
3answers
38 views
Is a totally ordered set well-ordered, provided that its countable subsets are?
Let $(X,⪯$) be totally ordered set, prove that if every non empty countable subset of $X$ is well ordered then X is well ordered.
It does seem obvious that any subset should have a minimum but I ...
0
votes
0answers
24 views
A problem on well ordered sets [duplicate]
Let $(X,\preceq) $ be totally ordered set, prove that if every non empty subset of $X$ is well ordered then $ X $ is well ordered.
It does seem obvious that any subset should have a minimum but I am ...
2
votes
2answers
81 views
Can the following set exist?
Say $a$ and $b$ are two numbers. Can the set $\{a,x_{1},x_{2},\dots b\}$ exist, where there are infinite $x_{i}$s?
Please note that one can't say $[0,1]$ is an example. This is because all the ...
1
vote
1answer
38 views
Number of days it took to climb the mountain (BdMO 2012 National Primary/Junior question)
From the Bangladesh Mathematical Olympiad 2012 National Primary (Question 7, or ৭).
When Tanvir climbed the Tajingdong mountain, on his way to the top he saw it was raining $11$ times. At ...
1
vote
1answer
43 views
Is there a preference between proving a total order (strict vs partial)?
I know that proving a relation $\mathcal{R}$ to be a strict total order (asymmetric, transitive,and total ) implies that the relation $S$ defined as $X\mathcal{S} Y \longleftrightarrow ...
1
vote
1answer
24 views
Cardinality and surjective functions
Let $A$ denote a set and $P(A)$ be the power set. By definition for cardinalities $|A|\le|B|$ iff there exists an injection $A \hookrightarrow B$. Note that there is an obvious surjection $P(A) \to ...
3
votes
2answers
61 views
To prove $f$ to be a monotone function
A open set is a set that can be written as a union of open intervals. If $f$
is a real valued continuous function on $\mathbb{R}$ that maps every open set to an
open set, then prove that $f$ is a ...
0
votes
2answers
32 views
Cartesian product and union
How can we prove that
$(A\cup C)\times (B \cup D) \subset (A \times B) \cup (C \times D) \Rightarrow (C \subset A ~\land ~ D \subset B) ~~ \lor ~~ (A \subset C ~ \land ~ B \subset D) $?
I've tried to ...
3
votes
1answer
42 views
Equivalence relation - Proof question
Prove that the relation, two finite sets are equivalent if there is a one-to-one correspondence between them, is an equivalence relation on the collection $S$ of all finite sets.
I'm sure I know the ...
3
votes
2answers
40 views
Concerning the proof of the Cantor–Bernstein theorem
I've seen two proofs for the Cantor–Bernstein theorem which says that for two sets $X$ and $Y$ if $\#X \le \#Y$ and $\#Y \le \#X$ then $\#X=\#Y$, equivalently if we can find an injection from $X$ to ...
4
votes
3answers
137 views
Yablo's paradox? a paradox without self-reference [closed]
Yablo's paradox arises from considering the following infinite set of sentences:
$$(S_1): \mbox{for all }k > 1, S_k\mbox{ is false} \\
(S_2): \mbox{for all }k > 2, S_k\mbox{ is false} \\
...
2
votes
1answer
60 views
Is the upper limit of sets empty?
Let $E_k^n$ be measurable subset of $[0,1]$ for any natural numbers $k$ and $n$.
For a fixed $n$ we have
$$E_1^n\supseteq E_2^n\supseteq
E_3^n\supseteq\ldots
E_{k}^n\supseteq ...
1
vote
2answers
30 views
How do I prove such a function exists? (Question involves quotient modules.)
I seem to encounter this issue whenever a question involves quotient objects. In this case, I have modules $M_1$ and $M_2$ and subsets $N_1$ and $N_2$ thereof respectively. It is given that $N_1$ and ...
2
votes
2answers
45 views
standard definitions when talking about ordered sets
What is the standardization if any when it comes to ordered sets?.
Specifically I'm always confused in the following cases:
1) When someone say "a partial ordered set": to me it can mean a strict ...
3
votes
1answer
72 views
Class of all finite sets
In a higher algebra book that I'm working through, the natural numbers are constructed in the following manner:-
Consider the class $S$ of all finite sets. Now, $S$ is partitioned into equivalence ...
2
votes
3answers
45 views
Need help with Cantor-Bernstein-Schroeder Proof at ProofWiki
This concerns Proof 6 of the CBST theorem at ProofWiki.
I am stuck on the line beginning "Similarly, let $g' = $"
The 2nd equality on this line is not immediately obvious to me. How do you prove ...
2
votes
1answer
32 views
A picky question on set theory
I just came to this math statement:
Let A,B,C be sets. Then: (AxB)xC = Ax(BxC)
My question is, why is it so?
I mean,
(AxB)xC = { ((a1,b1),c1), ((a1,b2),c3), ... }
and
Ax(BxC) = { (a1,(b1,c1)), ...
0
votes
2answers
25 views
Minimum Equivalence Relation
Let $X= \{1,2,3,4\}$, and $R = \{(1,2),(3,4)\}$.
Show the minimum equivalence relation on $X$ that extends $R$.
How many elements does the quotient set $X/R$ have ?
Can somebody give hints to solve it ...
0
votes
1answer
25 views
Order preserving maps
Suppose $f:X \to Y$ is order preserving. Let $A$ be a subset of $X$.
Does is follow that if $A$ is well ordered then $f(A)$ is well ordered?
1
vote
4answers
47 views
Totally ordered sets
Let T be a totally ordered set that is finite. Does it follow that minimum and maximum of T exist?
Since T is finite, I believe there exists a minimal of T. From that it maybe able to be shown that ...
10
votes
6answers
212 views
what is a function? please.
Axiom schema of replacement: Let the domain of the function $F$ be the set $A$. Then the range of $F$ (the values of $F(x)$ for all members $x$ of $A$) is also a set. — Tarski–Grothendieck ...
-1
votes
1answer
41 views
Is a finite subset of a partially ordered set bounded?
Suppose $X$ is a partially ordered set. Let $A$ be a finite subset of $X$. Is $A$ bounded? (That is, do there exist upper and lower bounds for $A$?)
It seems false but unable to find a counter ...
0
votes
1answer
35 views
Does a lower bounded set always have an infimum?
Let $A$ be a partially ordered subset of $X$. If $A$ is bounded below, does $\inf(A)$ exist?
2
votes
3answers
39 views
Composition $R \circ R$ of a partial ordering $R$ with itself is again a partial ordering
If $R$ is a partial ordering then $R\circ R$ is a partial ordering.
I cannot seem to prove this can anyone help ?
9
votes
1answer
627 views
Are real numbers “a joke”? [closed]
Recently I stumbled upon the website of Prof. N. J. Wildberger, who has an written a thought-provoking article about set theory and the real numbers. In his opinion, real numbers are actually "a ...
1
vote
3answers
47 views
Discrete Mathematics-set theory
In the theorem "the complement of empty set is the universal set" , I know how it happens. But how can I prove it in contradiction method?
Thank you.
2
votes
1answer
37 views
Proper map on from compact manifolds
I'm stuck on this statement. Could anyone please help me out?
Let $X$ be a compact manifold, every map $f: X \longrightarrow Y$ is proper.
The definition of proper: a smooth map between manifolds is ...
3
votes
2answers
61 views
X is infinite if and only if X is equivalent to a proper subset of itself.
Prove that a set $X$ is infinite if and only if $X$ is equivalent to a proper subset of itself.
If $X$ is finite, then suppose $|X|=n$. Any proper subset $Y$ of $X$ has size $m<n$, and so ...
2
votes
1answer
63 views
Getting rid of the set builder notation in the expression $\{ f(x) \mid P(x) \} = \{ g(x)\mid Q(x) \}$
The set-builer notation is used to have
$$\{ x \mid P(x) \} = \{ x \mid Q(x) \}$$
denote
$$\forall x\ \big(P(x) \Leftrightarrow Q(x) \big).$$
And some people write
$$\{ x \in U \mid P(x) ...
