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

-4
votes
1answer
35 views

Counterexamples in set theory [duplicate]

I have a question which states that: Prove or find a counterexample of sets $A, B, C$ such that $A\cap B = B\cap C = A\cap C =\emptyset$ but $A\cap B\cap C \neq\emptyset$ I know ...
1
vote
0answers
13 views

If $X$ is a finite set of cardinality $n$, where $n$ exists in $P$, show that the following conditions on a function $f: X \to X$ are equivalent: [duplicate]

(a) $f$ is an injection (b) $f$ is a surjection (c) $f$ is a bijection I know that (c) implies (a) and (b) and (a) and (b) imply (c). I also have the following definition that I've been playing ...
0
votes
1answer
20 views

Images of Functions and their Preimages

Suppose that $f: A \to B$ and suppose $C ⊆ A$ and $D ⊆ B$ Prove or give a counterexample: a) $f(C) ⊆ D \iff C ⊆ f^{-1}(D)$. This is true correct? b) If $f$ is injective then $f^{-1}(f(C)) = C$ ...
3
votes
1answer
21 views

Cardinality of of set surjection [on hold]

Let $A$ and $B$ be finite sets. Prove there exists a surjection $f:A \to B$ iff $\#B ≤ \#A$ For this question, does the pigeonhole principle just prove it, or is there more needed? Edit: Also Can i ...
3
votes
1answer
19 views

Need help proving indexed family of sets questions

Need to prove the equality: $$ (\bigcup_{i\in I} A_i)-(\bigcup_{j\in J} B_j)=\bigcup_{i\in I}(\bigcap_{j\in J}[A_i-B_j]) $$ Any ideas on how to start? Thank you
1
vote
1answer
23 views

Show that if the projection of a set is negligible, then the set is negligible as well

I'd like a hint in the right direction, im drawing a complete blank. let $E \subset \mathbb R^2$. We'll define the projection of $E$ unto the $x$ axis as: $P_x(E)=\{x| \exists y \in \mathbb R s.t ...
1
vote
0answers
20 views

Set geometry and inclusion

Let's define first the operator for any matrix $C\in\cal M_{m,n}$,$|C|=\big(C^TC\big)^{1/2}$ where $(\cdot)^{1/2}$ is the principle square root operator. I would like to prove that the set of the ...
-1
votes
0answers
16 views

prove the statements of well ordered sets… [on hold]

Show that: a. If $(X,<)$ is a chain and finite set, then is it a Well Ordered Set? b. If $(X,<)$ is Well Ordered then any Y $\subseteq$ X is Well Ordered. c. If $(X,<)$ is Well Ordered and ...
0
votes
0answers
14 views

$\ K = \{ (1,1) , (2,1) , (3,1) \} f(R) = RK$

$\ M$ is the set of all relations on $\ A = \{1,2,3\}$ $\ K$ is the the following relation on A $\ K=\{(1,1),(2,1),(3,1)\}$ let there be $\ f :M\rightarrow M$ $\ f(R) = RK$ is f injective? ...
-1
votes
1answer
25 views

Symmetric Difference Quesions [on hold]

Let $A$ and $B$ be sets. The symmetric difference of $A$ and $B$ is denoted by $AΔB$. Prove that: (a) $AΔB ⊆ A$ iff $B ⊆ A$ (b) $AΔB ⊆ B$ iff $ A ⊆ B $ (c) If $A$ and $B$ are finite sets, ...
0
votes
1answer
86 views

Show that a particular set is a poset

I would like to know if my understanding of the concept of a poset is correct. From what I've learnt from the class: A poset must be transitive, reflexive, and antisymmetric. Am I right? Therefore, ...
0
votes
0answers
8 views

Going down from filters to sets for specific relations

Let $\mathfrak{A}$ be a bounded lattice. I call a $2$-staroid a relation $f\in\mathscr{P}(\mathfrak{A}\times\mathfrak{A})$ such that $i\sqcup j \mathrel{f} b\Leftrightarrow i\mathrel{f} b\vee ...
1
vote
1answer
20 views

Prove that if the relation (R) is symmetric and antisymmetric on the set X, there exists a Y subset of X such that R is the = relation on Y.

Prove that for any relation R on a set X that is both symmetric and antisymmetric, there is subset Y \subseteq X for which R is the relation = on Y. I will tell you what I know. I know that ...
0
votes
2answers
27 views

Cardinality of two sets cross-multiplied

Let $A$ and $B$ be sets. Prove that $ \#(A \times B) = \#(B \times A)$. What I have done: There exist an element $m$ in $A$ such that the element also exists in $B$. If $\#A = \#B$, then $\#B = ...
1
vote
1answer
16 views

Set composed of operations on a Subset

Let there be a set P, and a set K such that $P\subset K$. Let there be 2 binary operations closed on K written $+$ and $\times$. Is there any way to define K as having only elements composed of ...
0
votes
0answers
11 views

Certain constructs on filters and on principal filters

Let $\mathfrak{X}$ be a lattice. I will call a set $S\in\mathscr{P}\mathfrak{X}$ a free star when the least element of $\mathfrak{X}$ is not in $S$ and $X\sqcup Y\in S\Leftrightarrow X\in S\vee Y\in ...
3
votes
3answers
36 views

union of cartesian products problem!

$$\bigcup_{i \in I}A _{i}\times \bigcup_{j \in J}B _{j} = \bigcup_{(i\times j) \in I\times J}A_{i} \times B_{j}$$ $$\bigcup_{k\in N} \mathbb{N}\times\{k\} = \mathbb{N}\times\mathbb{N}$$ i'm not yet ...
-1
votes
0answers
105 views

Construction of the field of real numbers within $ZF$ [duplicate]

I am interested in a problem whether the field of real numbers can be constructed within $ZF$. I will state the problem more precisely as follows. Definition 1 An ordered field $K$ is called ...
2
votes
0answers
21 views

Intuition - Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5] [duplicate]

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 ...
1
vote
0answers
34 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
53 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
20 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
32 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
38 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
62 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
40 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
16 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
92 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
32 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
42 views

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

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

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

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
23 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
2answers
66 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
33 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
71 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|$, ...