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, ...

learn more… | top users | synonyms

1
vote
0answers
47 views

Power Set, Bijection Function, Equivalence Relation

Let $S$ be a set and $P(S)$ the power set of $S$. For sets $A,B⊆P(S)$, we say that $A \sim B$ if there exists a bijective function $f: A \rightarrow B$. Show that $\sim $ is an equivalence relation.
1
vote
2answers
63 views

Cardinality, Finite Sets Proof

Let $S$ and $T$ be finite sets. Prove that if $|T-S| = |S-T|$, then $|S| = |T|$.
0
votes
1answer
23 views

question about the axiom of choice [duplicate]

We know axiom of choice states that: Given any collection $\{ S_i : i \in I \} $ of nonempty sets, there exists a choice function $f: I \to \bigcup_{i \in I} S_i $ such that $f(i) \in S_i $ for all ...
1
vote
4answers
35 views

mapping from $2^A$ to $P(A)$

Let $2^A$ denote the set of all functions from set $A$ into two-element set 2. How to show that there exists one-to-one and onto mapping from $2^A$ to $P(A)$ (power set)?
0
votes
1answer
34 views

Cardinality of the Set of $\mathbb{C}$ valued sequences

Working a functional analysis question that I believe requires this and I'm struggling to determine this set's cardinality".
0
votes
1answer
21 views

For any function $f$, $f(s) \in f(S) \not\implies \Leftarrow s \in S$

This already contains many counterexamples, so I'm not seeking any more of them; I'm interested in learning about my errors with the notation and definitions. Richard Hammack P213 Defintion 12.9: ...
-1
votes
0answers
39 views

Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5] [on hold]

Define $I_n = \{1, 2, ..., n \} $. Let $A$ be a nonempty set. TFAE : (i) $A$ is finite (ie: a bijection $h:A\rightarrow I_{N}$ exists) or A is countably infinite (ie: a bijection $h:A\rightarrow ...
2
votes
0answers
67 views

Prove $f_\infty: A_\infty \rightarrow B_\infty$ is a bijection

I am using the Cantor-Schroder-Beenstein Theorem to prove $f_\infty: A_\infty \rightarrow B_\infty$ is a bijection. The cases of $f_+: A_+ \rightarrow B_+$ and $f_-: A_- \rightarrow B_-$ being ...
0
votes
1answer
32 views

Set theory notation, commas

$$A = \{\{b^2+2k: k\in\mathbb Z\}: b\in\mathbb N, b < 3\}\cap M$$ Is that correct? I'm trying to say that the set $A$ is equal to the intersection of set $M$ and the set of all numbers which are of ...
0
votes
1answer
42 views

Basic topology questions with cantor's set

I have 3 questions in toplogy, one of which I managed to solve (but would appreciate input regardless) and 2 which are more difficult. I'd like a push in the right direction. Define $K$ as ternary ...
1
vote
1answer
17 views

What is wrong with the following proof saying Zorn's lemma implies Hausdorff maximum principle?

I am reading 'Topology' by J.R. Munkres's first chapter on set theory. In the exercises 5-7 on page 72 he asks the reader to show that Zorn's lemma implies Hausdorff maximum principle via the ...
2
votes
3answers
39 views

Enumeration of rational numbers

If $\Bbb Q=\{q_n:n\in \Bbb N\}$ be an enumeration of $\Bbb Q$, is it true that $|q_n|<1/n$ for infinitely many $n$? I just come up with this question, it seemed simple but I can't solve it. Is ...
1
vote
1answer
61 views

What's wrong with my proof?

Let $f:A\to B$ be a function. Let $T_1$ and $T_2$ be subsets of $B$. Show that if $f$ is onto, then $$f^{-1}(T_1)\subset f^{-1}(T_2) \implies T_1\subset T_2$$ I proved it as follows. Let $x\in ...
1
vote
2answers
38 views

Proof strategy - If $g \circ f = id_A$, then f onto $\iff$ g 1-1. [Chartrand 3Ed P239 9.72]

For nonempty sets A and B and functions f : A → B and g : B → A, suppose that $g \circ f =$ the identity function on A. $(♦)$ (d) $(=>)$ Assume that $f$ is onto. This means there exist ...
1
vote
0answers
23 views

The product of two rational Dedekind cuts

If $a,b\in \mathbb{Q}$ and $C_a$ and $C_b$ are both positive rational Dedekind cuts then $C_a\cdot C_b=C_{a\cdot b}$. First of all this is my definition of product: Let $r,s$ Dedekind cuts such ...
2
votes
1answer
22 views

Number of subsets of a nonempty finite set with a given property.

Let $S$ be a set with $|S|=n$, where $n$ is a positive integer. How many subsets $B$ of $S\times S$ are there with the property that $(a,a) \in B$ for all $a \in S$ and $(a,b) \in B \implies (b,a) \in ...
4
votes
2answers
40 views

Proving that $\mathrm{card}(2^{\mathbb{N}})=\mathrm{card}(\mathbb{N}^\mathbb{N})$

I'd like to prove that $\mathrm{card}(2^{\mathbb{N}})=\mathrm{card}(\mathbb{N}^\mathbb{N})$, I have the following 'sketch' but I'm not sure if this works. ...
1
vote
3answers
94 views

Question regarding axiom of unions

By axiom of union for any set A there is a set B such that x belongs to B if and only if x belongs to some z which belongs to A. According to this everything is a set.My question is what would union ...
2
votes
0answers
28 views

Did I prove in correct process?

The question is "prove that if g of f is 1-1, then f is 1-1." Did I prove it correctly? If not, what is wrong?
1
vote
4answers
78 views

$f[A]\cap f[B]\supsetneq f[A\cap B]$ - Where does the string of equivalences fail ? [Chartrand 3E 9.12(b), 9.29]

I only realised that equality may fail in $f[A]\cap f[B]\supseteq f[A\cap B]$ (i.e., that we can have $A,B,f$ for which $f[A]\cap f[B]\neq f[A\cap B]$) after checking the answer. I don't see any ...
1
vote
2answers
33 views

How show $\mathbb N \cong \mathbb Q$ using Cantor pairing?

According to this: http://en.wikipedia.org/wiki/Cantor_pairing_function#Cantor_pairing_function, we can show that $\mathbb N\times\mathbb N\cong\mathbb N$. But as for $\mathbb Q$, this is not the ...
1
vote
1answer
18 views

Class term with Kuratowski pair

As usual $(x, y)$ is an abbreviation for $\left\{\{x\}, \{x,y\}\right\}$. Given the class term: $\left\{(x,y) \ |\ x\in A \wedge y\in A \right\}$ for every $x$ is in $A$ and every $y$ in $A$ the ...
0
votes
2answers
46 views

How find this $\max{|A|}$ if $A=\{S_{i}|S_{i}\equiv 1\pmod 2\}$

let $(a_{1},a_{2},\cdots,a_{2014})$ be a permutation of $(1,2,3,\cdots,2014)$,and define $$S_{k}=a_{1}+a_{2}+\cdots+a_{k},k=1,2,3,\cdots,2014$$ Find the $\max{|A|}$, where ...
1
vote
3answers
45 views

Define the $\mathcal P \left(\cup\{\{\emptyset\}\}\right)$ set.

What is the $\mathcal P \left(\cup\{\{\emptyset\}\}\right)$ set?
0
votes
0answers
20 views

For a filtered set how can we show there exists a maximal element [closed]

According to my teacher's definition for a filtered set, for every two subset elements of the set there exists an element that these two are subsets of. Then if I choose the maximal element, won't it ...
0
votes
1answer
22 views

An alternative succinct proof needed for trivial cardinality fact

Let $|X|$ denote the cardinality of a set, i.e. the least ordinal $\alpha$ such that there is a bijection between X and $\alpha$. For any sets $X$ and $Y$ we write $X\preccurlyeq Y$ if the exists an ...
0
votes
2answers
24 views

understanding example of a family of sets

This example is from the Wikipedia page on "family of sets": I don't understand what elements of $S$ have to do with $A_1,A_2,...$etc, and how are they matched? $S$ has five elements yet $F$ has ...
1
vote
1answer
69 views

Need help with a fundamental theorem of finite arithmetic

An amateur mathematician, I am working with a finite set $N$, elements $0, m\in N$ and partial function $S$ on $N$ such that the following Peano-like relations hold. ($0$ is the first element of $N$. ...
1
vote
2answers
34 views

Trying to do an easy proof about countable sets.

I'd like to prove that every time $\mathbb{Z}$ appears can be changed by $\mathbb{N}$. Seems intuitive enough for me, but I can't find a formal way to prove it. Using $\mathbb{N}\sim\mathbb{Z}$ I ...
3
votes
3answers
72 views

How elements are defined in axiomatic set theory

I'm trying to understand the axioms of axiomatic set theory. I'm studying this book and I didn't understand how can we define the elements of a set and the set $\{x\}$. If I define the singleton, I ...
0
votes
2answers
48 views

How to prove that if $A\subseteq B$and $|A|=|B|$, then $A=B$

Apart from the question in the title, the other question that related to the first question: Define: $f(X)=${$f(x)|x\in X$}. if $X$ is finite, $f(X)\subset X$ and $f$ is one to one, then $|f(X)|=|X|$, ...
2
votes
1answer
37 views

Uncountable, algebraically independent subset of $\mathbb{C}$?

Does such a subset exist? I am interested in algebraic independence over $\mathbb{Q}$. Could this be proven in an abstract way or would it be more appropriate to construct an explicit example?
2
votes
1answer
80 views

What are interesting examples of existential proofs based on cardinality arguments?

Probably the most famous example of a proof, where consideration of cardinalities is used to show existence of some object, it the Cantor's proof that there exist transcendental numbers. What are ...
0
votes
1answer
36 views

Formal statement of the well-ordering theorem

Out of interest, how would you write the well-ordering theorem in pure set-theoretic language?
2
votes
0answers
43 views

For an infinite set $A$, does $|A| = |A \times A|$? [duplicate]

I know that $|\mathbb{N}| = |\mathbb{N}^2|$, and that $|\mathbb{R}| = |\mathbb{R}^2|$. It seems like this might be true for all sets, but I don't know how to go about proving this. It's easy to ...
-2
votes
0answers
24 views

Progression of Cardinality of powers of two

I am researching how to represent a progression of sets and their cardinalities. I can use some guidance on what I am looking for. There exists a progression of elements and sets such that the ...
0
votes
1answer
8 views

An indexed family of filters and their elements

Let $X$ is an indexed (by some set $n$) family of filters (on some poset $\mathfrak{A}$). Is there any standard notation/terminology for the set $\{ y\in \mathfrak{A}^n \,|\, \forall i\in n:y_i\in ...
1
vote
1answer
22 views

Does an order relation on a set induce an order relation on the power set?

Suppose $A$ is a simply ordered set. Is there a natural induced simple order on the power set $\mathcal{P}(A)$ ? If A happens to be well ordered the following seems to define a simple order on ...
0
votes
3answers
39 views

Proof that $X^C \cap Y^C= \;(X \cup Y)^c$

Proof that if $X \subset S,\; Y\subset S,\;$ then $\;X^C \cap Y^C= \;(X \cup Y)^c:$ It must be shown that the two sets have the same elements, that each element of the set on the left is an element ...
0
votes
2answers
45 views

Suppose $A, B$, and C are sets. Prove that $C\subset A\Delta B \Leftrightarrow C \subset A \cup B$ and $A \cap B \cap C = \emptyset $

The problem statement is in the title. I'm proving a problem in class and I need to show the above containment. I've drawn some Venn diagrams to make sure the containment makes sense, and it does to ...
0
votes
1answer
21 views

countable set that contains 1 and pi and has polynomial with coefficients in set s.t. all real roots are in set

Deduce that there is a countable set X that contains the real numbers 1 and pi and has the further property that if P is any non-zero polynomial with coefficients in X, then all real roots of P belong ...
1
vote
5answers
109 views

How can one find a set of given cardinality and disjoint from a given set?

In Algebra by Serge Lang, the author asserts, to prove the existence of a field extension where an irreducible polynom has a root, that if you take one set $A$ and a cardinal $\mathcal{C}$, that you ...
1
vote
1answer
42 views

$\cup_{i=1}^n [\frac 1n , 1] = ]0,1] $??

I was just confused, wheater $\cup_{i=1}^n [\frac 1n, 1] = ]0,1]$ is. I also thought that it might be [0,1] but I think that is not true. Cheers
1
vote
4answers
100 views

ZFC: Why is the set $\{ x \mid x = x\} $ not defined?

Why is the set $\{ x \mid x = x\} $ not defined? Since, $x=x$ is always true, the set is actually "the set of everything". But why is it illegal to be defined as a set?
0
votes
1answer
37 views

Bijection and image

Let f: A -> B be a bijection, so f^-1: B -> A is a function. Let X be a subset of A. How do I prove that Im(f)(X) = Preim(f^-1)(X)? Thank you.
2
votes
3answers
52 views

Determining injectivity and surjectivity

Are these functions injective or surjective? Also, how should I go about proving this? The function maps $ℕ×ℕ$ to $ℤ$. $f(a,b) = 4a+5b$ $f(m,n) = m^2-n$ $f(p,q) = 5^p·3^q$ Thanks!
2
votes
1answer
43 views

I currently know Calculus I — What steps would I take to understand Zermelo–Fraenkel set theory?

While this question can be discussed, it should have a clear answer by stating the following: How can one go from a high school / low-level college understanding of mathematics (completed Calculus ...
0
votes
0answers
17 views

When can I use an “indexed set”? [closed]

For example, if I'm given a filtered set, can I use indexed set notation? When am I not allowed to use it?
-2
votes
0answers
31 views

Please prove these [closed]

Let $$O = \{n\in\mathbb Z: n \text{ is an odd integer}\} = \{n \in \mathbb Z : \exists k\in\mathbb Z, n = 2k + 1\}$$ and let $$T = \{n \in\mathbb Z:n^2\text{ is an odd integer}\}$$ Prove or disprove ...
1
vote
1answer
16 views

Solving a poset for less than equal?

I don't completely understand posets yet, so I'm confused on how to do this particular problem. Here is the question: Let S be the set of all real numbers. Prove that the less than or equal to ...