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

0
votes
1answer
7 views

Set builder form for representing strings

Is there a way to represent strings or palindromes using set notation? For representing palindrome using set notation, I arrived at this notation $$S=\{ab^{n}c:N\; |\; n \geq 1 \land n \leq 3\}$$ I ...
0
votes
1answer
21 views

Stuck on basics: How to prove that {subst($\alpha$,s)} is well defined?

So I feel like this is a really basic point that I'm missing and I can't really manage to prove that: So I have a substitution function $s: Var \rightarrow WFF$ and a subst function: $WFF \times ...
0
votes
2answers
30 views

The cardinal of the set of all measures on $\mathbb{R}$

It is a very simple question that I don't know how to do: Let $M = \{\mu \colon \mathcal{B}(\mathbb{R})\to \mathbb{R} \colon \mu \text{ is a measure}\}$ $$|M| = \ ?$$ Any help will be appreciated.
1
vote
1answer
50 views

Proving this equivalence relation

If $X,Y$ are reflexive, symmetric, and transitive, then $X \times Y$ is an equivalence relation where ${(a,b):a\in X, b\in Y}$. I am trying to self learn these topics. I do know what an ...
0
votes
0answers
52 views

Prove $X\times Y$ is an equivalence relation

(Relation between two sets) If $X$ and $Y$ are sets, a relation between $X$ and $Y$ is a subset $R \subset X \times Y.$ For a relation $R \subset X\times Y$ and $a \in X$ and $b \in Y$ if $(x,y) \in ...
5
votes
2answers
381 views

Inverse of a set, possible?

Just like ordinary algebraic operations have inverses, could we imagine the inverse of a set? Like $x\in\{x\}$ then maybe the inverse denoted $[|x|]$ would mean $$\{\ [|x|]\ \}=x$$ Would this idea ...
0
votes
2answers
44 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
1answer
32 views

The empty set as an Indexing set. [duplicate]

For each $\alpha\in I$, let $A_\alpha$ be a subset of some nonempty set $S$. So if $I=\emptyset$, then $$ \bigcup_{\alpha\in I} A_\alpha=\emptyset $$ and $$ \bigcap_{\alpha\in I} A_\alpha=S. $$ Why ...
-1
votes
2answers
39 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
32 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}$ ...
1
vote
4answers
58 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 ...
2
votes
1answer
34 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 ...
3
votes
2answers
30 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
3answers
98 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
32 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]. ...
1
vote
5answers
82 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 ...
2
votes
7answers
219 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 ...
-4
votes
1answer
66 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 ...
2
votes
1answer
1k views

into function vs injective function

In many mathematical books that I have read and from lectures from professors, the words 'into' and 'injective' were used interchangeably, but in Patrick Suppes book Axiomatic Set Theory he gives a ...
1
vote
4answers
64 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, ...
0
votes
1answer
27 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
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 ...
-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
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 ...
1
vote
1answer
52 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, ...
1
vote
3answers
64 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 ...
2
votes
2answers
19 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 ...
9
votes
5answers
869 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 ...
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 ...
3
votes
2answers
491 views

Any reference that explains generated equivalence relation

Im looking for a reference that characterizes when an equivalence relation can be generated from a relation and gives a clear explanation of it.
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
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 ...
3
votes
1answer
43 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
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 ...
2
votes
1answer
54 views

Composite function intersection

I m stacked in one prove which dealt with sets and functions. I m concerned to prove that: $$f \circ g ( X \cap Y) \subseteq (f \circ g)( X) \cap (f \circ g) (Y)$$ Assume that $g$ is function from $A$ ...
0
votes
1answer
33 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
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 ...
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 ...
1
vote
2answers
229 views

The “Empty Tuple” or “0-Tuple”: Its Definition and Properties

(I would like to link to a previous discussion on the subject: What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation)) In axiomatic (ZFC) set theory, we define ...
0
votes
1answer
28 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?
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$?
2
votes
2answers
59 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 ...
2
votes
2answers
55 views

How are some infinities larger than other infinities

I heard an expressions, some infinities are larger than others recently, and they stated that it was proved to be so. I haven't been able to find this proof, and ...
2
votes
2answers
33 views

Proof of Set Theory Algebra using Logic

Let A, B and C be sets. I am trying to prove that $$A\cup(B \setminus C)=(A\cup B)\setminus(C\setminus A)$$ And I am supposed to use logic to work through this problem, so first I let A={x|P}, ...