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
votes
2answers
37 views

Set theory: Why are these two sets different?

I'm currently working through a set theory book and one of the exercises is to explain why $\{z|z\subseteq \{\emptyset\}\}$ and $\{x|x\in \mathbb{Z}, 0<x<1\}$ are different. I'm just completely ...
2
votes
0answers
19 views

Clarification on the definition of $X^{\omega}$

I have never seen this notation before (graduated with a math degree a few months ago; not in school currently). Here's what I gather from Munkres' Topology: Given a set $X$, an $\mathbf{\omega}$ ...
0
votes
4answers
51 views

Is there numbers that don't fit in our sets of numbers?

It is said that the first numbers we used were natural numbers like $0$, $1$ ,$2$... in $\mathbb{N}$. Then we discovered negative numbers $-1$,$-2$... , and classified them all in $\mathbb{Z}$. Then ...
3
votes
2answers
27 views

Cardinal Arithmetic proof issues.

Let $X$ be a finite set and let $x$ be an object which is not an element of $X$. Then $X \cup \{x\}$ is finite and $|X \cup \{x\}| = |X| + 1$. Proof. Let X be a finite set with cardinality n, ...
1
vote
1answer
27 views

Existence of finite sets of infinite set without using AC

Is it possible to prove that every infinite set $B$ has a subset of cardinality $n$, for every natural $n$, without using AC? I know how to prove this claim by induction. In the induction step I chose ...
1
vote
3answers
95 views

Is natural numbers set $\mathbb N$ infinite set?

A set with uncountable number of elements is called an infinite set. Is that the set of all natural numbers, $\Bbb N=\text{{$1,2,3,\ldots$}}$ infinite set? As far i know $\Bbb N$ is "countably" ...
3
votes
1answer
30 views

Question concerning the universe of sets.

I am reading Charles Pinter's Introduction to Set Theory Every proper class is in one-to-one correspondence with the universal class $\mathscr{U}$, that is, the class of all sets [emph. added]. ...
0
votes
1answer
24 views

Alternate element disjoint exhaustive Subsets with same cardinality

Suppose $U$ is an ordered set, I want to construct subsets $A$ and $B$ such that: (1) (Disjoint) $A \cap B = \phi $ (2) (Exhaustive) $A \cup B = U$ (3) (Alternate elements) $\forall x,y \in A, ...
1
vote
5answers
75 views

Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable

Prove that if sets $A$ and $B$ are countable, then their union $A\cup B$ is countable. I'm really confused because I'm not sure if $A$ and $B$ are finite or infinite. If I have to consider every ...
2
votes
2answers
58 views

Set theory intersections and unions

I'm in an intro to discrete mathematics course, and this is a question on my first homework. I showed what I have so far, I think the answer to the first part of the question may be right, but I'm ...
-4
votes
1answer
64 views

How to describe the Cartesian product $\mathbb{R} × \mathbb{R}$?

I am taking a discrete mathematics course in the spring and in an attempt to fully understand the material I am reading ahead. I came across this statement Let $\mathbb{R}$ denote the set of all real ...
1
vote
1answer
56 views

Basic Set Theory regarding the set $\{0\}$

For each nonnegative integer $n$, let $U_n = \left \{n,−n\right \}$. Find $U_1,\:U_2,\:\text{and}\:U_0$. $U_1 = \left \{1,−1\right \}, U_2=\left \{2,−2\right \}, U_0 = \left \{0,−0\right \} = \left ...
1
vote
4answers
63 views

Show the inverse of a bijective function is bijective

We have a function $\varphi:G\rightarrow H$ is an isomorphism, show its inverse $\varphi^{-1}:H\rightarrow G$ is also an isomorphism I am fine with showing it to be a homomorphism and surjective, ...
-3
votes
1answer
34 views

Injective function from rational numbers to rational numbers [on hold]

Suppose we have $f\colon\mathbb{Q}\to\mathbb{Q}$, $f\circ g=f$ and $g\circ f=f$. Question: is $g$ the identity function $g\colon\mathbb{Q}\to\mathbb{Q}$? Is $g$ and injective function? (meaning ...
1
vote
1answer
48 views

Show an equivalence via induction

Let $f$ be a set function $f: 2^{V} \rightarrow \mathbb{N}_{0}$; let $S,T\subset V$ be such that $S \subset T$ and let $j$ be any element such that $j \in (V \setminus T)$ (so $j$ doesn't belong to ...
1
vote
3answers
63 views

Rigorous proof that countable union of countable sets is countable

I am unsuccessfully trying to understand the proof of the fact that countable union of countable sets is countable.The argument presented till now is: Let $\displaystyle \bigcup S_n$ be a countable ...
0
votes
1answer
26 views

Properties of Image and Inverse Image

Let $f:X\rightarrow Y,A\subset X$ and $B\subset Y$. If $f^{-1}(B) \subset A$, then $B \subset f(A)$ I cannot understand that why this statement is false. Any counterexample?
1
vote
1answer
50 views

How to denote the set of all students who take the same class as some given student $s'$?

I have a set of Students: $S = \{s_1, \ldots, s_2 \}$. Now each student takes some class (doesn't matter what class). Now I need to have a set $X$ that contains all students that take the same class, ...
2
votes
2answers
18 views

How to prove this statement about this relation:

Let $p$ be a prime. On $\mathbb{Z}_{>0}$ we define the relation $\sim$ as $a\sim b\iff [\forall n\in \mathbb{Z}_{>0}: p^n|a \iff p^n|b]$. Prove that $[\forall x,y \in \mathbb{Z}_{>0}: x\sim ...
1
vote
1answer
26 views

What is the cardinality of the following equivalence classes?

We have the relation $\sim$ on $\mathbb{R}$ defined by $a\sim b \iff [\exists q\in \mathbb{Q}: a-b=q\pi]$. What are the possible cardinalities of the equivalence classes?
0
votes
0answers
51 views

Undergraduate Set theory

I'm reviewing some set theory notes and I know its a basic question, but I just want confirmation. Let the universe of discourse be $\mathbb{Z}$. What is $\{x \mid x\geq 0 \wedge x>0\}$ equal ...
3
votes
1answer
43 views

Show that $≺$ is a total ordering

Let $ℕ$ be the set of positive integers. Let $D(n)$ denotes the number of divisors of $n$. We define this binary relation: $n≺m⇔n≤m$ and $D(n)≤D(m)$ where $≤$ is the usual ordering in $ℕ$. Show ...
0
votes
2answers
59 views

Is this proof of uncountability of Cantor set true?

To construct Cantor set $C$, start with $I_1=[0,1]$ and define $$E_1=\{0,1\}=\{x:x\text{ is an end point of the set }I_1\}.$$ $\operatorname{card}(E)=\#(E)=2$. After deleting the middle open interval ...
9
votes
5answers
858 views

Contradictory definition in set theory book?

I'm using a book that defines $A\setminus B$ (apparently this is also written as $A-B$) as $\{x\mid x\in A,x\not\in B\}$, but then there was an exercise that asked to find $A\setminus A$. Wouldn't it ...
1
vote
2answers
34 views

Proof of the description of a set

We are supposed to describe the set $\bigcup_{n=1}^\infty A_n$ with a proof. $A_n = \{(x, y) \in \mathbb{R}^2 | y-x^{2n} \geq 0 \}$. This is what I have so far: "This is just the set of all points ...
1
vote
1answer
27 views

What can we say about the set X?

We have a certain set $X$ for which is valid: $\forall U\subset X:[ U\neq X ]\rightarrow U\nsim X$. What can we say about $X$? I think we've got to use the axiom of choice here. My first guess would ...
0
votes
1answer
32 views

Cantor's theorem.

If $A$ is a infinite set then the power set of $A$, $\mathcal{P}(A)$, is an uncountable set. To proof first I take $A$ countable, and I suppose $\mathcal{P}(A)$ is countable, i.e., ...
1
vote
2answers
37 views

Is there an uncountable set S, a subset of P(N), such that for any A,B an element of S; the intersection of A and B is finite? [duplicate]

I have a feeling no such uncountable set exists but have no idea how I could formulate a proof to show this. If such an uncountable set did exist I could try and use a form of the diagonalization ...
1
vote
1answer
37 views

Proving that $x \not\in B \cap C \iff x \not\in B \lor x \not\in C$.

I've got a set theory question. I'm required to show that $x \not\in B \cap C$ if and only if $x \not\in B$ or $x \not\in C$. I decided to call the universal set $S$ (which contains both and $B$ and ...
0
votes
1answer
27 views

Set notation check

Are the three statements: $(a,b,c)\in\mathbb{Q}^3$ $\{a,b,c\}\subset\mathbb{Q}$ $a,b,c \in\mathbb{Q}$ equivalent ways of saying that a, b and c are rational numbers?
1
vote
1answer
30 views

Cantor Pairing Function [on hold]

I know that: $J(m,n)=\frac{(m+n)^{2}+m+n}{2}$. Is the Cantor pairing function that gives me a bijection between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$. But how can I show the Cantor ...
2
votes
2answers
56 views

Opposite of a function being bijective?

A function is bijective if it is both surjective and injective. Is there a term for when a function is both not surjective and not injective?
0
votes
2answers
23 views

Can a surjective function have an element in the domain not mapped to the codomain?

I have seen a lot of definitions for surjectivity stating that every element in the codomain must be mapped to something in the domain. But does the opposite also have to hold true for a function to ...
4
votes
0answers
23 views

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal?

Is the limit of a recursive sequence of recursive ordinals itself a recursive ordinal? If so, is there a nice proof of this?
0
votes
2answers
59 views

Suppose A and B are finite sets and $f : A \rightarrow B$ is surjective. Is it possible that |A| < |B|?

I am trying to understand better what surjective functions is from a set $A$ to a set $B$, and from what I understood, it basically means this: A function is subjective (onto) from set $A$ to set ...
1
vote
1answer
29 views

Is $A∩B^c∩C^c = A-[A∩(B∪C)] $ ? (Set Theory)

I'm studying set operations. The example problem is: Find a simpler expression of $[(A∪B)∩(A∪C)∩(B^c∩C^c)]$ assuming all three sets intersect. The answer I came up with is $A∩B^c∩C^c$, while the ...
0
votes
2answers
44 views

can the empty set be an element of a group?

is the following group legal: $x = \{1,2,\emptyset\}$? If so, is $P(x) = \{ \emptyset, \{1\}, \{2\}, \{1,2\}, \{\emptyset\}, \{1, \emptyset\}, \{2,\emptyset\}, \{1,2,\emptyset\} \}$ ? When I write ...
3
votes
2answers
103 views

Confusion about the definition of function

Yesterday I was talking to one of my friends about the definition of function. The formal definition of function is given by Cartesian Products but my friend's question was whether it is possible to ...
2
votes
2answers
39 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
1
vote
1answer
35 views

What is the cardinality of the class of $0$ in $\mathbb{R}$?

What is the cardinality of the class of $0$ in $\mathbb{R}$? In other words: what is the cardinality of the class of all rational Cauchy sequences that converge to $0$?
4
votes
6answers
410 views

Question on induction technique

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?
0
votes
2answers
33 views

Set theory and logic proof

Problem: Prove that if the sets $A,B,C \in U$, where $U$ is a universal set, then $A \cap B = A \cup B$ if and only if $A = B$ My attempt:We can show that $A \cap B = A \cup B$ if $A = B$ with the ...
3
votes
2answers
60 views

How do I prove that there doesn't exist a set whose power set is countable? [duplicate]

I don't even know where to begin on this one. Let $A$ be a countable set. In other words, $|A| = |\mathbb{N}|$. I'm trying to prove that there doesn't exist an $x$ such that $\mathcal{P}x = A$. ...
1
vote
2answers
52 views

How do I prove that for any set $A$, $|A| < |\mathbb{N}|$ implies that $A$ is finite?

Here's what I've tried so far. Let $A$ be a set and suppose $|A| < |\mathbb{N}|$. By the definition of less than for cardinalities (I'm reading out of Hrbacek's Introduction to Set Theory), this ...
3
votes
2answers
24 views

Given a set $A$, how do I prove that there exists a set of all sets $x$ such that $\bigcup x=A$?

I am working with Zermelo-Fraenkel axioms. Specifically, I am allowed to assume the Axiom of Pair, Axiom Schema of Comprehension, Axiom of Union, and Axiom of Power Set, etc. (not yet allowed to use ...
1
vote
1answer
30 views

Proof on $\bigcup A=\varnothing\Rightarrow\forall a\in A, a=\varnothing$

Is this proof valid? $\textbf{Claim: }\bigcup A=\varnothing\Rightarrow\forall a\in A, a=\varnothing$ Proof. Let us suppose that there was an $x\in A$ where $x\neq\varnothing$. Since $x\in \bigcup A ...
0
votes
3answers
53 views

How to come up with bijections?

Is there a good technique for finding bijections in general? Like between the integers and the natural numbers or between [0,1) and (0,1).
4
votes
2answers
44 views

example of uncountable set

I am looking for simple proofs of uncountable sets: I know a set is said to be uncountable if there is no injective function from the set to the natural numbers. I know the set of real numbers is ...
1
vote
1answer
39 views

Definiton of function

Are these two statements true about the definition of a function $f$ from $A$ into $B$ For every element $a \in A$, there exists at least one element $b \in B$ such that $f(a)=b$ For every element ...
2
votes
7answers
213 views

How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...