This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

-1
votes
2answers
101 views

prove that $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$

I need help with proving this: $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$ $C\subseteq Y$ Thanks.
0
votes
4answers
68 views

Prove that $(A^c \cup B^c) - A = A^c $

Prove that for any two sets A,B, we have $(A^c \cup B^c) - A = A^c $ Attempt Let $x \in\ (A^c \cup B^c) - A$ Then, $x \in\ A^c$ or $x \in\ B^c$ and $x \notin\ A$ $x \in\ A^c$ or $x \in\ B^c$ and ...
0
votes
1answer
38 views

How big a set can we get from this construction?

Construct a set $X\subset (0,1)$ likewise: Consider some irrational $x$ in $(0,1)$ which we represent in base $2$ e.g. $x=0.\,m_1m_2\,...$ where $m_i\in\{0,1\}$ for all $i$. Add it to $X$. Consider ...
1
vote
4answers
32 views

$R \setminus (S \cup T)$ . Where is $x$?

I am sorry for the messy math symbols. If I have the set: $R \setminus(S \cup T)$ , is it correct to assume that: $$R \setminus(S \cup T) = \{x: x∈ \mathbb{R} \text{ and } ( x \notin S \text{ and ...
1
vote
1answer
37 views

Is this complete partial order?

Is $(\mathbb{N} , \#)$ complete partial order, where $m\#n$ iff $(\exists k \in \mathbb{N})m=kn$. I proved it's partial order. For completeness I take directed subset and I know there is upper bond ...
2
votes
2answers
108 views

For all infinite cardinals $\kappa, \ (\kappa \times \kappa, <_{cw}) \cong (\kappa, \in).$

I don't understand the proof to the a/m claim. How we know that $\eta < \kappa$ and $(\alpha,\beta)<_{cw} (0, \eta) $ and hence $h: \mu \to \eta \times \eta$ is injective? Appreciate if anyone ...
3
votes
1answer
113 views

Given a subcollection of a powerset, do these “separation” relations have names?

Let $X$ denote a set and $\mathcal{F}$ denote a subcollection of $\mathcal{P}(X).$ Do the following relations on $\mathcal{P}(X)$ have a name? For $A,B \subseteq X$, call $A$ partially separated from ...
1
vote
4answers
57 views

check if $f(f^{-1}(D))=D$

I have to check whether $f(f^{-1}(D))=D$. I think this is not true but I'm stuck in my proof. Can somebody help me? Thanks in advance.
1
vote
2answers
162 views

Prove intersection of all inductive sets is inductive

How to prove that the intersection of all inductive sets is inductive? Subset A of ordered field F is inductive, when: 1) $1 \in A$ 2) if $a \in A$ then $a+1 \in A$ Prove that $$\mathbb{I} = ...
0
votes
3answers
64 views

Why $\mathbb{N} \subset V_\omega$ and $Seq(\mathbb{N}) \subset V_\omega$?

Let $V_\omega$ denote the set of all hereditarily finite sets. Let $Seq(\mathbb{N})$ denote the set of all finite sequences from $\mathbb{N}$. That is, $Seq(\mathbb{N}) = ...
2
votes
0answers
57 views

proving $f^{-1}(C\cup D)=f^{-1}(C)\cup f^{-1}(D)$

I don't understand why I have to prove these: $f^{-1}(C\cup D)\subseteq f^{-1}(C)\cup f^{-1}(D)$ $f^{-1}(C)\cup f^{-1}(D)\subseteq f^{-1}(C\cup D) $ Why can't I do something like that: $x\in ...
0
votes
2answers
21 views

Equivalence of operations by a function of certain sets.

Show that if $f : A \to B$ and $G,H$ are subsets of $B$, then $f^{-1}(G \cup H) = f^{-1}(G) \cup f^{-1} (H)$ and also that $f^{-1}(G \cap H) = f^{-1}(G) \cap f^{-1}(H)$.
3
votes
2answers
61 views

Prove B is a subset of D

Let A,B,C and D be four sets. Prove that if $A\cup B \subseteq C\cup D$, $A\cap B = \varnothing$, and $C\subseteq A$ then $B\subseteq D$
0
votes
1answer
50 views

The “counting” problem

Let $X$ be a set containing $n$ elements . Two subset $A$ and $B$ of $X$ are chosen at random . Find the probability that $ A \bigcup B = X $ . Solution given in the book : for each $x_i \in ...
1
vote
3answers
81 views

Show that $2^\mathbb{N} $ is equinumerous with $2^\mathbb{N\times N} $.

I need to show that $2^\mathbb{N} $ is equinumerous with $2^\mathbb{N\times N} $. I already found a function from $2^\mathbb{N} $ to $2^\mathbb{N \times N} $, wich just returns a pair containing ...
3
votes
1answer
113 views

Cardinality of the set of all natural sequences is $2^{\aleph_0}$ [duplicate]

I was wondering how can you prove that $\mathbb{N}^\mathbb{N} \sim 2^\mathbb{N}$ (where $\mathbb{N}^\mathbb{N}$ is the set of all functon $f:\mathbb{N}\rightarrow \mathbb{N}$). I think I can show ...
0
votes
1answer
55 views

How to show that this function is onto

Let $f$ be a bijection from $\mathbb{N}$ to the set $A$ and let $g$ be a bijection from $\mathbb{N}$ to the set $B$ and $h$ a function from $\mathbb{N}$ to the union of $A$ and $B$ defined by ...
1
vote
1answer
62 views

The usual ordering of R is not order isomorphic to c??

I am trying to understand the term "cofinality". I am reading about it in here: http://en.wikipedia.org/wiki/Cofinality. It went rather well until I encountered this statement: "The usual ordering of ...
1
vote
3answers
105 views

prove $f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ [duplicate]

I need help with this proof: $f: X\rightarrow Y$ $C,D\subseteq Y$ $f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ Thanks.
1
vote
1answer
59 views

Proving that $\bigcup_{n=1}^{\infty }R^n$ is a transitive relation on A

Let $R$ be a relation on set $A$. How can i prove that $\bigcup_{n=1}^{\infty }R^n$ is a transitive relation on $A$? Maybe it has to do with $\bigcup_{n=1}^{\infty }R^n=tc(R)$ ?
1
vote
2answers
450 views

Proofs by contradiction and set theory

I'm having trouble understanding proofs by contradiction. I'm running things by memory and not by understanding what a contradiction is. I'd like to know what we're assuming and how to start. My ...
4
votes
2answers
153 views

Is it necessary to use the axiom of Regularity to prove the successor function being injective?

Basically the problem is that given an inductive set $X$ we can define the successor function on $X$ such that $S:X\longrightarrow X$ and for all $x\in X$, $S(x)=x\cup \{x\}$. So, one of Peano axioms ...
-1
votes
1answer
103 views

Prove that all of the following sets have the same cardinality

I have encountered the following problem: Prove that the following sets have the same cardinality using Cantor-Bernstein theorem, or by showing a bijection: $$P(\mathbb{N}), \mathbb{N}\times ...
1
vote
0answers
37 views

What do indexed mean in 'indexed family' in set theory? [duplicate]

What do indexed mean in 'indexed family' in set theory? Thanks! :)
1
vote
1answer
224 views

Is there a bijective map from the open interval $(0,1)$ to $\mathbb{R}^2$?

I couldn't find a bijective map from the open interval $(0,1)$ to $\mathbb{R}^2$. Is there any example?
3
votes
1answer
690 views

Proving the generalized intersection of the interval (0, 1/n) is the empty set?

Prove that the generalized intersection of the interval (0,1/n) is the empty set? Aka prove that $(0,1) \cap (0, 1/2) \cap (0, 1/3) \cap (0, 1/4) ... = \emptyset$. I know that I need to prove this ...
3
votes
1answer
33 views

Set theory: ${R^R}$ notation

What is the meaning of ${R^R}$? I've encountred with this notation in a presentation of Discrete Mathematics
1
vote
2answers
70 views

cardinality of a set of natural lattice points versus natural numbers

Given a set D = $\{(a,b)∣a,b ∈ \mathbb{N}\}$ where L is the set of all points in the first quadrant whose coordinates are natural numbers. Which has more elements, D or $\mathbb{N}$? I know it has ...
1
vote
1answer
149 views

Cardinality of a set of functions , $f:\mathbb N \to \mathcal{P}(\mathbb N)$

Calculate the cardinality of the following sets: $A=\{f:\mathbb N \to \mathcal{P}(\mathbb N) : n \in f(n) \space \forall \space n \}$ $B=\{f:\mathbb N \to \mathcal{P}(\mathbb N) : n \notin f(n) ...
2
votes
1answer
210 views

Prove that if $A$ and $B$ are finite, then $A \cup B$ is finite

Statement: if $A$ and $B$ are finite, then $A \cup B$ is finite Proof: If $A$ and $B$ are finite, then there exists $m, n \in \mathbb{N}$ such that $A \approx \mathbb{N}_{m}$ and $B \approx ...
1
vote
1answer
57 views

How to characterize the set of all real functions defined on $X$.

Let $X$ be an arbitrary set. I consider the set of all real functions defined on $X$. I know that this is usually denoted by $\mathbb{R}^X$. However, I am interested in characterizing each point of ...
1
vote
1answer
139 views

Giving injective formulas for a function f: $\mathbb{N} \rightarrow L$ given a set $L = \{(a,b)\mid a,b ∈ \mathbb N\}$

Let $L = \{(a,b)\mid a,b ∈ \mathbb N\}$ $L$ is the set of all lattice points in the first quadrant (all points in first quadrant whose coordinates are natural numbers make $L$) a. Give a formula ...
1
vote
2answers
43 views

Prove that $ f(A) \subseteq B \implies A \subseteq f^{-1}(B) $

Let $ A,B ⊆ \mathbb R \ $ and $f\colon\mathbb R \to \mathbb R$ be a function. Then $ f(A) \subseteq B \implies A \subseteq f^{-1}(B) $.
0
votes
1answer
67 views

A seeming absurdity [duplicate]

I'm having a hard time getting over the following question, which appears in Schimmerling's "A Course on Set Theory." (Problem) Given that $\kappa$ and $\lambda$ are infinite cardinals with ...
0
votes
2answers
48 views

Having trouble reading a set theoretic equation

I've just begun an introductory text on probability. In the first chapter there is a preview/review of set theory, which I am not familiar with. One of the examples has me a little confused. I do not ...
-2
votes
1answer
77 views

Cardinality of “x−y∈Q”-equivalence class of 1/2 √ [duplicate]

For x,y∈I:=[0,1] define the relation on I as x−y∈Q. How big (using cardinal number) is the cardinality of the equivalence class [1/√2]? I have tried to solve it by finding the equivalence class but ...
1
vote
2answers
63 views

Is it proper subset or not?

Consider following statment $\{\{\varnothing\}\} \subset \{\{\varnothing\},\{\varnothing\}\}$ I think above statement is false as $\{\{\varnothing\}\}$ is subset of ...
0
votes
1answer
176 views

Set builder notation for this set

I need set builder notation for a set. Set under consideration is: $$\{m,n,o,p\}$$ What I suggest is: $$\{x\colon x\in\{m,n,o,p\}\}$$ Any suggestions is it correct?
1
vote
2answers
1k views

What will be set builder notation for this set?

Following set is neither of even nor of odd so how can I express this by using set builder notation? {0,3,6,9,12}
2
votes
1answer
81 views

Does the center of a convex region lie within that region?

There's probably a simple result that says this is true, but I sure can't find it. It seems obvious, though. Let $D$ be a closed, compact region in $\Re^n$. Further, let $D \subseteq [0,l]^n$ and ...
5
votes
1answer
123 views

bijection from $\mathbb{Q} - \{a\}$ to $\mathbb{Q}$ using elementary functions only?

I was wondering, can you define a bijection from $\mathbb{Q} - \{a\}$ to $\mathbb{Q}$ using elementary functions only ($a \in \mathbb{Q}$)? Of course there are many set theoretic bijections like ...
2
votes
1answer
108 views

Set theory - elements not in both finite sets

I have an understanding of the below problem but have little experience proving things in set theory so I don't know how to start it. For any two finite sets $A$ and $B$, define $f(A,B)$ to be the ...
0
votes
1answer
23 views

How many ways the set D can be constructed?

The following relations hold for four non-empty sets $A,B,C,D$: $ A \cup B \cup C \cup D = A \cap B $ $ B \cup C \cup D = B \cap C $ $ C \cup D = C $ If $A = \{1,2,3,4\} $ then in how many ways ...
5
votes
1answer
94 views

Why is this binary-relation antisymmetric?

Definition of antisymmetric binary-relation is $$\forall a,b\in\mathrm{A},\left[ \left(aRb\wedge bRa\right)\rightarrow\left(a=b\right)\right].$$ Let $\mathrm{A}=\left\{a\mid ...
0
votes
1answer
365 views

Maximal and minimal elements of the partial order relation

Let $A=\{1,2,3,4\}$ and $H$ is the set of antisymmetric relations on $A$. I think that $H = \{(1,2),(2,3),(3,4),(1,3),(1,4),(2,4)\}$. How would I find the minimum/maximum and min/max elements?
3
votes
3answers
165 views

Is this function injective / surjective?

A question regarding set theory. Let $g\colon P(\mathbb R)\to P(\mathbb R)$, $g(X)=(X \cap \mathbb N^c)\cup(\mathbb N \cap X^c)$ that is, the symmetric difference between $X$ and the natural ...
1
vote
2answers
107 views

Is this set infinite?

If we say that $B = L_1 \cup L_2$, $L_1 \cap L_2 = \emptyset$,also $B, L_1,L_2$ are infinite and we are given that $A \subset L_1$ and $B \backslash A$ is infinite, does that say that $L_1 \backslash ...
1
vote
1answer
66 views

If $\alpha,\beta$ are at most countable, so are $\alpha+\beta,\alpha\cdot\beta,\alpha^\beta$

If $\alpha$ and $\beta$ are at most countable ordinals, prove the following are at most countable: $\alpha + \beta$ $\alpha \cdot \beta$ $\alpha^{\beta}$
2
votes
1answer
65 views

How to show that $\mathcal P(\Bbb N)\sim\mathcal P(\Bbb N)^\Bbb N$?

I am trying to proof now that $\mathcal P(\Bbb N)$ is of the same cardinality as $\mathcal P(\Bbb N)^\Bbb N$ - the set of all functions $f:\Bbb N\to\mathcal P(\Bbb N)$. Currently I've tried to use the ...
0
votes
1answer
44 views

Coincident boundaries of sets

At the end of my lecture, which introduced closed sets and boundaries of sets, my professor asked the following question: Let $S,T,V \subset \mathbb{R}^2$ such that $int(S) \not = \emptyset$, $int(T) ...