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
57 views

Given $S = \{ … -15, -10, -5, 0 \}$, how do I prove that $S \sim \mathbb{Z}$? [closed]

In those kind of questions do I need to just find a function that maps every member of set $S$ to set $\mathbb{Z}$?
1
vote
1answer
11 views

Cardinality of equivalence relations on N [duplicate]

I asked a similar question yesterday about well ordered sets, now I am having troubles with equivalence relations. Could someone suggest an injection from a well known set of cardinality ...
1
vote
1answer
16 views

Solution check. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the following properties.

I'm revising some old psets while preparing an exam and going through some things that I left unverified. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the ...
22
votes
8answers
3k views

There is a subset of positive integers which no computer program can print

It's said that a computer program "prints" a set A ($A \subset \mathbb N$, positive integers.) if it prints every element in A in ascending order (Even if A is infinite.). For example, the program can ...
0
votes
2answers
16 views

Proving the cardinality of $|A| =|\mathbb Z|$

Let $A=\{ (2n,-3n)~|~ n\in \mathbb Z\}$. Prove that $|A| =|\mathbb Z|$. What would an example of a function, $f:\mathbb{Z}\to A$? Would it be something like $f(x)=(2x,-3x)$? Thanks for the help.
3
votes
1answer
46 views

Finding an injection from $2^{\mathbb{N}} $ to the set of well orderings of $\mathbb{N}$

The question is to show that the cardinality of all well orderings of the natural numbers equals to $2^{\aleph_{0}}$ . So we need two injections for it. One way is easy using the identity map but how ...
1
vote
2answers
95 views

Prove formally that |N| = | N union a finite set |.

I'd like to show that the cardinality of $\mathbb{N}$ is the same as the cardinality of $\mathbb{N}$ union some other finite set (disjoint from $\mathbb{N}$). For example show that: $|\mathbb{N}|= ...
4
votes
3answers
39 views

$\bigcup X$ finite implies $\mathcal P(X)$ is finite.

Can anyone help with this past paper question from a Set Theory exam. Prove that, for all sets $X$, $\bigcup X$ finite implies $\mathcal P(X)$ finite. I am using the Kuratowski definition of ...
0
votes
0answers
33 views

Prove that $|A| =|\mathbb Z|$.

Let $A=\{ (2n,-3n)~|~ n\in \mathbb Z\}$. Prove that $|A| =|\mathbb Z|$. So to clarify this, I have to find a function that is bijective between $A$ and $\mathbb Z$ to prove that the cardinality of ...
0
votes
2answers
2k views

Must an infinite intersection of infinite sets be infinite?

If $A_2$ is a subset of $A_1$, $A_3$ is a subset of $A_2$, and this goes on infinitely and all contain an infinite number of elements, then is the intersection from $n=1$ to infinity, infinite as ...
1
vote
2answers
24 views

Is $f$ injective and surjective?

Let $f:\mathbb{N}\to \mathbb{Z}$ given by $\displaystyle f(a)=\frac{(-1)^a(2a-1)+1}{4}$. Is $f$ injective and surjective? I am having trouble bringing down the $a$ from the exponent. For injective, ...
3
votes
1answer
46 views

Defining bijections between sets

I am having troubles understanding how to properly define bijections between the sets say $X,Y,Z$ to show that 1) $(Z^X)^Y \cong Z^{(X\times Y)}$ In my notes it says that I can map, $F:X\times Y ...
2
votes
1answer
29 views

Express the statement that $x$ has at least one element in the language of set theory

For a past paper for a module that I am revising for, we are asked to express the Axiom Schema of Separation for the property that "$x$ has at least one element". I understand that the Axiom Schema ...
1
vote
0answers
31 views

$\epsilon_0$ is closed under addition, multiplication, exponentiation of ordinals

Question: Let $f: \Bbb{N}\rightarrow \text{Ord}$ (where "Ord" is the set of ordinals) be defined inductively by: $$f(0)=\omega\\ f(n^+)=\omega^{f(n)}$$ Let $\epsilon_0=\{\sup f(i) : i \in \Bbb{N}\}.$ ...
-4
votes
0answers
42 views

$\cup _{n=0}^{\infty }[0,n]=\cup _{n=5}^{\infty }$ $[0,n]$ [on hold]

My question is why $$\bigcup_{n=0}^{+\infty}[0,n]=\bigcup_{n= 5}^{+\infty}[0,n]$$? Can you explain?
2
votes
1answer
36 views

Cardinality of Power set of naturals equal to $\Bbb{N}^\Bbb{N}$

The question: Decide with proof which has greater Cardinality $\Bbb{N}^\Bbb{N}$ or $2^\Bbb{N}$. My intuition: They will be the same. By Cantors argument and the continuum hypothesis, both will have ...
0
votes
2answers
131 views

Deciding whether $f^{-1} (f(A)) = A$ or $f(f^{-1}(B)) = B$

$X$ and $Y$ are two sets and $f:X\to Y$. If $f(C)=\{f(x):x\in C\}$ for $C\subseteq X$ and $f^{-1}(D)=\{x:f(x)\in D\}$ for $D\subseteq Y$, then the true statement is (A) $f(f^{-1}(B))=B$ (B) ...
5
votes
2answers
4k views

Surjectivity implies injectivity

Let S be a finite set.Let F be a surjective function from S to S. How do I prove that it is injective?
0
votes
1answer
23 views

This seems simple but, how do i prove A isn't in C?

$A\in B$ and $B\in C$, Is it posible to prove $A$ isn't in $C$? Sorry for simplistic exercise, but been wondering this for days now... The question in the book says: Can you deduce that $A\in C$ ? ...
0
votes
0answers
33 views

If {x,{x,y}}={z,{z,t}} then x=z and y=t must be? [duplicate]

Question If {x,{x,y}}={z,{z,t}} then x=z and y=t must be? My answer: Yes. Assume $x\neq y$. Then, {$x$,{$y$,$z$}} has two elements: $x$ and {$x$,$y$}. Thus, $x\neq z$ since {$z$,{$z,t$}} should have ...
2
votes
0answers
40 views

Every subset of a finite set is finite.. confused why this proof is wrong..

Prop. Every subset of a finite set is finite Proof. Let A,B sets and suppose B is a finite set. Also let $A \subseteq B$ If B = $\varnothing$, A is also $\varnothing$ and is finite. If B $\neq ...
-1
votes
3answers
57 views

If $\{x\}=\{z\}$, does that necessarily mean that $x=z$?

Proposition. If $\{\{x\},\{x,y\}\}=\{\{z\},\{z,t\}\}$ then $x=z$ and $y=t$. My question is that if $\{x\}=\{z\}$ then, must $x=z$ be?
0
votes
1answer
28 views

Is there an example where $ A \subseteq\mathcal {P}\bigcup A\ $ is no longer true?

I came up with the following: Let A = {x} Then $ \bigcup A = x $ $ \mathcal {P} \bigcup A =$ ? This is where I get stuck. The definition of power set is the set of all subsets of $A$ ...
0
votes
0answers
25 views

Is $D$ a field?

Problem. Let $D$ be an integral domain and let $\mathcal{F}(D)$ be a field of quotients of $D$. If $D\subset \mathcal{F}(D)$ then prove or disprove that, $D$ is a field. ...
-5
votes
0answers
20 views

Set Theory. Basic Theorems. [on hold]

Any infinity set M contains part N, which is equivalent to all M. What does equivalent mean? N will be M, won't it?
1
vote
5answers
63 views

Help with set proof: $A \cap B = A $ if and only if $A \subseteq B $.

$A \cap B = A $ if and only if $A \subseteq B $ It's been a while since I've done this sort of proof. I can't think of how I would prove this statement. I'm too used to numerical proofs. What ...
0
votes
2answers
40 views

Prove the existence of a bijection

Let $A$ and $B$ be sets, and suppose $A$ is infinite. Let $B$ be a countably infinite subset of $A$. Show that if $f: \mathbb{N} \to B$ and $g: B \to \mathbb{N}$ are bijections, then $$ h: A \to A- ...
0
votes
0answers
13 views

Set theory-commutative,idempotent property

Is $A \backslash B'$ commutative and idempotent? I think that this is commutative, but how can I prove it? With Venn diagram? And what about the idempotent property? I think this is idempotent too.
7
votes
8answers
2k views

What is an example of function $f: \Bbb{N} \to \Bbb{Z}$ that is a bijection?

Could you give me an example of function $ f \colon \mathbb N \to \mathbb Z$ that is both one-to-one and onto? Does this work: $f(n) := n \times (-1)^n$? N starts with zero.
0
votes
0answers
11 views

Let $A$ be a nonempty set. Prove that if $S$ and $R$ are equivalence relations on $A$, then $S \cup R$ is both reflexive and symmetric.

Let $A$ be a nonempty set. Prove that if $S$ and $R$ are equivalence relations on $A$, then $S \cup R$ is both reflexive and symmetric. My method: Let $x \in A$ be given. Then $x \in S$ or $x \in ...
0
votes
4answers
74 views

Equivalence relation for “almost equal to” [on hold]

Let $A$ and $B$ be subsets of the set of natural numbers. We say that $A$ is almost equal to $B$, and write $A \approx B$, if there exists a finite subset $X \subset$ (natural numbers) such that $A ...
0
votes
1answer
28 views

Injective, Surjective, and Cardinality

Let $f:(0,\infty)\to (0,1)$ given by $f(x) = \frac{x}{x+1}$. Decide whether $f$ is injective and whether it is surjective? What does this say about the cardinality of $R$ and $(0,1)$? I am not how to ...
0
votes
1answer
26 views

Verify the following statement, $ \{\{x\}, \{x,y\}\} \in\ A \implies \{x,y\} \in\bigcup A $?

My attempt at solving it: Let $ A = \{a,b,c,d\} $ where: $ a = \{x\} , b = \{x,y\} , c = \{x,y,z\} $ and $ d = \{\{x\}, \{x,y\}\} $ Then, $ \bigcup A =a \cup\ b \cup\ c \cup\ d = ...
0
votes
1answer
33 views

Is $f$ surjective and injective?

Let $f$ be a function from $f:\mathbb{N}\to \mathbb{Z}$ given by $f(a) = (-1)^aa$. Decide whether $f$ is injective and whether it is surjective. Which function do I start with in determining this? ...
0
votes
1answer
24 views

Open Interval in subsets

Suppose that $X$ is a subset of $\Bbb R$. If there exists an open interval contained in $X$, then $\# X = \# \Bbb R$.
1
vote
1answer
15 views

Prove that if $f : A \rightarrow B$ is a function, $D \subseteq A$, and $E \subseteq A$ then $f(D) - f(E) \subseteq f(D - E)$.

Prove that if $f : A \rightarrow B$ is a function, $D \subseteq A$, and $E \subseteq A$ then $f(D) - f(E) \subseteq f(D - E)$. My method: Let $y \in f(D) - f(E)$. Hence $y \in f(D)$ and $y \notin ...
1
vote
1answer
18 views

Complement of the universal set (U) is the empty set (∅)

The question ask me to state True or False and give reasons. However I prefer True. Reason: The Universal set denoted by (U) is simply a set of all given sets and complement is simply saying that ...
-3
votes
1answer
64 views

$\mathbb N\times\mathbb N$ is countable

$$\mathbb N\times\mathbb N \text{ is countable}.$$ Is there any way to prove it using induction? without fundamental theorem of arithmetic
1
vote
2answers
443 views

Characteristic function of union of two sets formula and intuition

From http://topologicalmusings.wordpress.com/2008/03/20/inclusion-exclusion-principle-counting-all-the-objects-outside-the-oval-regions-2/ Is there an easier proof or way to calculate $1[A \cup ...
2
votes
0answers
40 views

$\mathrm{R}^n$ for non-integer values of $n$?

If I have a set of all possible $x$ for $x \in \mathrm{R}^n$ for non-natural number $n$, what meaning would this have and how would it be used? For instance, if I had $\mathrm{R}^{2.5}$, would this ...
-6
votes
1answer
45 views

How many sets can we create?

If a set is defined based on the following three points: 1)It has exactly three elements; 2)All elements are in Arithmetic Progression; 3)All elements are primes. Eg: $\{3,5,7\}$. How many such ...
-1
votes
1answer
24 views

ordinal cardinal task? [on hold]

a) Show that if $\alpha$ is an infinite ordinal then $\alpha+1$ is NOT a cardinal. b) Show that the following statement is false: Every limit ordinal is a cardinal. Help a brother out (please)
0
votes
1answer
70 views

Partition on a Closed Set $A= [2,3]$

Is it possible to define a partition of a closed set, such that the union of the partitions will give $[2,3]$ and their intersection to be empty?
-5
votes
1answer
27 views

Set theory task regarding cardinal arithmatic [on hold]

HELP a student !! Show, by using cardinal arithmatic and the fact $|\mathbb{R}|=2^{\omega}$, that $|(\mathbb{N}\rightarrow\mathbb{R})|=2^{\omega}$ and ...
1
vote
1answer
22 views

is it true that $A \cap (E_1^c \backslash E_2^c) \subset E_2$

For $A,E_1,E_2 \in \mathcal{F}$ where $\mathcal{F}$ is a $\sigma-$algebra is it true that: $$A \cap (E_1^c \backslash E_2^c) \subset E_2?$$
-3
votes
0answers
32 views

Strict cardinality, continuum hypothesis, upper bound and more [on hold]

We assume that there is no cardinal strictly between $\omega$ and $2^{\omega}$, in other words we assume the continuum hypothesis. You may use the fact that if $A=_cA^{'}$ and $B=_cB^{'}$, then ...
1
vote
1answer
23 views

Zorn's Lemma and well orderings [on hold]

State two conditions, wich are equivalent to the axiom of choice; one of them is usually called "Zorn's lemma" and the other speaks about well orderings. Help, please !
-3
votes
0answers
24 views

Set-theory task [on hold]

Define the binary operations $`+`$ and $`\cdot`$ on well ordered sets. Then show that there are ordinals $\alpha$ and $\beta$ such that $\alpha + \beta \neq \beta + \alpha$. Define the binary ...
-2
votes
0answers
27 views

ZFC and cardinality [on hold]

TASK: Show that assuming the axioms ZFC every set has a unique cardinality. You may use the cantor-shröder-bernstein theorem or the result that every well ordering is isomorphic to a unique ordinal. ...
-4
votes
1answer
74 views

Prove that set {1, 0} exists.

I have an exercise: Prove that set {1, 0} exists. Set theory is quite confusing for me to grasp at the moment but I know few axioms that should prove that this is set but how do I actually show ...